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: $\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.

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

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
$\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?

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, $\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$

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: $\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

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

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