We first note that the number <img src="http://www.qbyte.org/puzzles/p147.gif" alt="(2^58 + 1)/5" class="w" height="36" width="43"> is in fact an integer.
This may be seen by writing 2⁵⁸ = 2² · (2⁴)¹⁴ = 4 · 1¹⁴ = 4 (modulo 5).
Hence 2⁵⁸ + 1 =0 (mod 5).
(Alternatively, consider that 5 = 4 + 1 is a factor of 4²⁹ + 1 = 2⁵⁸ + 1, since (x + 1) is a factor of (xⁿ + 1) when n is odd.)

Now we factorize 2⁵⁸ + 1.
Note that (2²⁹ + 1)² = (2⁵⁸ + 1) + 2³⁰, and so 2⁵⁸ + 1 can be written as a difference of two squares:
2⁵⁸ + 1 = (2²⁹ + 1)² − (2¹⁵)² = (2²⁹ + 2¹⁵ + 1)(2²⁹ − 2¹⁵ + 1).
Clearly, both factors are greater than 5, and so 2⁵⁸ + 1 = 5ab, where a and b are integers greater than 1.

Therefore, the number <img src="http://www.qbyte.org/puzzles/p147.gif" alt="(2^58 + 1)/5" class="w" height="36" width="43"> is composite.

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

In fact, 2²⁹ + 2¹⁵ + 1 = 536903681 is prime, and 2²⁹ − 2¹⁵ + 1 = 536838145 = 5 · 107367629, both of which are prime, so that the prime factorization of 2⁵⁸ + 1 is 5 · 107367629 · 536903681.

In 1869, F. Landry announced the factorization of 2⁵⁸ + 1:

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

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

Edited on October 28, 2012, 4:01 am

Posted by Danish Ahmed Khan on 2012-10-28 03:57:15