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

**skeptopotamus** · June 1st 2012, 10:22 PM

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.

**BobP** · June 2nd 2012, 03:18 AM

$(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.

**skeptopotamus** · June 2nd 2012, 04:58 AM

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.

**Sarasij** · June 7th 2012, 10:34 PM

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 2³⁶ + 5³⁷ is a prime or not,how can we approach?

**skeptopotamus** · June 8th 2012, 10:06 AM

Originally Posted by Sarasij

If this problem is to judge whether 2³⁶ + 5³⁷ 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$

**Sarasij** · June 8th 2012, 08:55 PM

Got it...thanks...

**harrypham** · June 29th 2012, 10:47 PM

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:

**skeptopotamus** · June 30th 2012, 07:50 AM

Originally Posted by harrypham

I think $2^{46} + 5^{40} \equiv 0 \pmod{7}$

Spoiler:

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

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

LinkBack

Thread Tools

Display

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

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

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

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

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

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

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

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

Similar Math Help Forum Discussions

Using the fact that a pair of numbers is relatively prime to prove that one is prime

Prove that if n>=2 and not prime, then n has a prime divisor p<=(sq.root)n

Prove that for every prime p, there exists another prime q such that p and q-1 are...

Prove that if p is an odd prime, 1^2 * 3^2 ...(p-2)^2 = (-1)^(p+1)/2 (mod p)

if ((2^n) -1 ) is prime, prove n is prime ?! >.<

Search Tags