Skip to main content.

Solution to puzzle 147: Prime or composite 2

Skip restatement of puzzle.Is the number (2^58 + 1)/5 prime or composite?


We first note that the number (2^58 + 1)/5 is in fact an integer.
This may be seen by writing 258 = 22 · (24)14 congruent to 4 · 114 congruent to 4 (modulo 5).
Hence 258 + 1 congruent to 0 (mod 5).
(Alternatively, consider that 5 = 4 + 1 is a factor of 429 + 1 = 258 + 1, since (x + 1) is a factor of (xn + 1) when n is odd.)

Now we factorize 258 + 1.
Note that (229 + 1)2 = (258 + 1) + 230, and so 258 + 1 can be written as a difference of two squares:
258 + 1 = (229 + 1)2 − (215)2 = (229 + 215 + 1)(229 − 215 + 1).
Clearly, both factors are greater than 5, and so 258 + 1 = 5ab, where a and b are integers greater than 1.

Therefore, the number (2^58 + 1)/5 is composite.


Remarks

The above result may be regarded as an example of the factorization
4x4 + 1 = (2x2 + 2x + 1)(2x2 − 2x + 1),
with x = 214.

In fact, 229 + 215 + 1 = 536903681 is prime, and 229 − 215 + 1 = 536838145 = 5 · 107367629, both of which are prime, so that the prime factorization of 258 + 1 is 5 · 107367629 · 536903681.

In 1869, F. Landry announced the factorization of 258 + 1:

No one of the numerous factorisations of the numbers 2n ± 1 gave as much trouble and labour as that of 258 + 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 258 + 1.

However, only a few years later, Aurifeuille noticed that 536903681 − 5 · 107367629 = 216, and thereby obtained the above factorization.

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

Back to top