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

• Jun 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: $\displaystyle 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.
• Jun 2nd 2012, 03:18 AM
BobP
Re: 2^46 + 5^40 Not Prime - How to Prove?
$\displaystyle (2^{23}+5^{20})^{2}=2^{46}+5^{40}+2*2^{23}*5^{20}= 2^{46}+5^{40}+2^{24}*5^{20}$

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

Therefore,

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

and the RHS factors as the difference of two squares.
• Jun 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.
• Jun 7th 2012, 10:34 PM
Sarasij
Re: 2^46 + 5^40 Not Prime - How to Prove?
Quote:

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

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

Therefore,

$\displaystyle 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?
• Jun 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, $\displaystyle 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:

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

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

$\displaystyle 2^{36} + 5^{37} \equiv 1 + 2 \equiv 0 \pmod 3$
• Jun 8th 2012, 08:55 PM
Sarasij
Re: 2^46 + 5^40 Not Prime - How to Prove?
Got it...thanks...
• Jun 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: $\displaystyle 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 $\displaystyle 2^{46} + 5^{40} \equiv 0 \pmod{7}$
Spoiler:
ba
• Jun 30th 2012, 07:50 AM
skeptopotamus
Re: 2^46 + 5^40 Not Prime - How to Prove?
Quote:

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

No, sorry. The smallest prime divisor of $\displaystyle 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