All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Composite? Yes. (Posted on 2010-08-24) Difficulty: 3 of 5
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.)
Solution 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:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information