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

1. ## 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.

2. ## 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.

3. ## 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.

4. ## Re: 2^46 + 5^40 Not Prime - How to Prove?

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?

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

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$

6. ## Re: 2^46 + 5^40 Not Prime - How to Prove?

Got it...thanks...

7. ## Re: 2^46 + 5^40 Not Prime - How to Prove?

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

8. ## Re: 2^46 + 5^40 Not Prime - How to Prove?

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