 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Composite? Yes. (Posted on 2010-08-24) Prove that (258+1)/5 is a composite number.

 No Solution Yet Submitted by Ady TZIDON No Rating Comments: ( Back to comment list | You must be logged in to post comments.) Complete solution Comment 3 of 3 | 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 258 = 22 � (24)14 = 4 � 114 = 4 (modulo 5).
Hence 258 + 1 =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 <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
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:

<blockquote>

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.

Edited on October 28, 2012, 4:01 am
 Posted by Danish Ahmed Khan on 2012-10-28 03:57:15 Please log in:

 Search: Search body:
Forums (7)