Is the number prime or composite?

We first note that the number is in fact an integer.

This may be seen by writing 2^{58} = 2^{2} · (2^{4})^{14} 4 · 1^{14} 4 (modulo 5).

Hence 2^{58} + 1 0 (mod 5).

(Alternatively, consider that 5 = 4 + 1 is a factor of 4^{29} + 1 = 2^{58} + 1, since (x + 1) is a factor of (x^{n} + 1) when n is odd.)

Now we factorize 2^{58} + 1.

Note that (2^{29} + 1)^{2} = (2^{58} + 1) + 2^{30}, and so 2^{58} + 1 can be written as a difference of two squares:

2^{58} + 1 = (2^{29} + 1)^{2} − (2^{15})^{2} = (2^{29} + 2^{15} + 1)(2^{29} − 2^{15} + 1).

Clearly, both factors are greater than 5, and so 2^{58} + 1 = 5ab, where a and b are integers greater than 1.

Therefore, the number is *composite*.

The above result may be regarded as an example of the factorization

4x^{4} + 1 = (2x^{2} + 2x + 1)(2x^{2} − 2x + 1),

with x = 2^{14}.

In fact, 2^{29} + 2^{15} + 1 = 536903681 is prime, and 2^{29} − 2^{15} + 1 = 536838145 = 5 · 107367629, both of which are prime, so that the prime factorization of 2^{58} + 1 is 5 · 107367629 · 536903681.

In 1869, F. Landry announced the factorization of 2^{58} + 1:

No one of the numerous factorisations of the numbers 2

^{n}± 1 gave as much trouble and labour as that of 2^{58}+ 1. This number is divisible by 5; if we remove this factor, we obtain a number of 17 digits whose factors have 9 digits each. If we lose this result, we shall miss the patience and courage to repeat all calculations that we have made and it is possible that many years will pass before someone else will discover the factorisation of 2^{58}+ 1.

However, only a few years later, Aurifeuille noticed that 536903681 − 5 · 107367629 = 2^{16}, and thereby obtained the above factorization.

Source: You Are a Mathematician, by David Wells. See Chapter 4.