# 2^46 + 5^40 Not Prime - How to Prove?

• June 1st 2012, 10:22 PM
skeptopotamus
2^46 + 5^40 Not Prime - How to Prove?
The title really says it all. My research adviser showed me the problem: $2^{46} + 5^{40}$ is not prime, apparently. He said that the proof is very short, elegant and elementary, but that he couldn't have seen it unless someone showed him. I also don't see it.
• June 2nd 2012, 03:18 AM
BobP
Re: 2^46 + 5^40 Not Prime - How to Prove?
$(2^{23}+5^{20})^{2}=2^{46}+5^{40}+2*2^{23}*5^{20}= 2^{46}+5^{40}+2^{24}*5^{20}$

$=2^{46}+5^{40}+(2^{12}*5^{10})^{2}.$

Therefore,

$2^{46}+5^{40}=(2^{23}+5^{20})^{2}-(2^{12}*5^{10})^{2},$

and the RHS factors as the difference of two squares.
• June 2nd 2012, 04:58 AM
skeptopotamus
Re: 2^46 + 5^40 Not Prime - How to Prove?
Awesome, thanks! I'm usually quite good at these types of problems, but I just didn't see this one. I went at it cohomologically after a direct check on primes up to 37 didn't work, which went nowhere.
• June 7th 2012, 10:34 PM
Sarasij
Re: 2^46 + 5^40 Not Prime - How to Prove?
Quote:

Originally Posted by BobP
$(2^{23}+5^{20})^{2}=2^{46}+5^{40}+2*2^{23}*5^{20}= 2^{46}+5^{40}+2^{24}*5^{20}$

$=2^{46}+5^{40}+(2^{12}*5^{10})^{2}.$

Therefore,

$2^{46}+5^{40}=(2^{23}+5^{20})^{2}-(2^{12}*5^{10})^{2},$

and the RHS factors as the difference of two squares.

If this problem is to judge whether 236 + 537 is a prime or not,how can we approach?
• June 8th 2012, 10:06 AM
skeptopotamus
Re: 2^46 + 5^40 Not Prime - How to Prove?
Quote:

Originally Posted by Sarasij
If this problem is to judge whether 236 + 537 is a prime or not,how can we approach?

There is not a general way to do these types of problems, unfortunately. However, $2^{36} + 5^{37}$ specifically can be solved using the most elementary technique of just manually checking for primes less than, say, 31 or so. That is how I start any of these problems, given that of course the vast majority of odd numbers are divisible by one of these primes.

For example:

$2^2 \equiv 1 \pmod 3$
$2^{2k} \equiv 1 \pmod 3$
$2^{36} \equiv 1 \pmod 3$

$5^2 \equiv 1 \pmod 3$
$5^{2\ell} \equiv 1 \pmod 3$
$5^{36} \equiv 1 \pmod 3$
$5^{37} = 5 \cdot 5^{36} \equiv 5 \cdot 1 \equiv 5 \equiv 2 \pmod 3$

$2^{36} + 5^{37} \equiv 1 + 2 \equiv 0 \pmod 3$
• June 8th 2012, 08:55 PM
Sarasij
Re: 2^46 + 5^40 Not Prime - How to Prove?
Got it...thanks...
• June 29th 2012, 10:47 PM
harrypham
Re: 2^46 + 5^40 Not Prime - How to Prove?
Quote:

Originally Posted by skeptopotamus
The title really says it all. My research adviser showed me the problem: $2^{46} + 5^{40}$ is not prime, apparently. He said that the proof is very short, elegant and elementary, but that he couldn't have seen it unless someone showed him. I also don't see it.

I think $2^{46} + 5^{40} \equiv 0 \pmod{7}$
Spoiler:
ba
• June 30th 2012, 07:50 AM
skeptopotamus
Re: 2^46 + 5^40 Not Prime - How to Prove?
Quote:

Originally Posted by harrypham
I think $2^{46} + 5^{40} \equiv 0 \pmod{7}$
Spoiler:
ba

No, sorry. The smallest prime divisor of $2^{46} + 5^{40}$ is 13,469.

http://www.wolframalpha.com/input/?i=factor+calculator&f1=2^46+%2B+5^40&x=8&y=9&f=Fa ctor.factfunction_2^46+%2B+5^40