Results 1 to 8 of 8

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

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    24

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2009
    Posts
    652
    Thanks
    128

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    24

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

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

    Quote Originally Posted by BobP View Post
    (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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2011
    Posts
    24

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

    Quote Originally Posted by Sarasij View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

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

    Got it...thanks...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie harrypham's Avatar
    Joined
    Nov 2011
    From
    Vietnam
    Posts
    14

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

    Quote Originally Posted by skeptopotamus View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Nov 2011
    Posts
    24

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

    Quote Originally Posted by harrypham View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Replies: 6
    Last Post: August 27th 2010, 11:44 PM
  4. Replies: 3
    Last Post: October 3rd 2009, 05:18 AM
  5. if ((2^n) -1 ) is prime, prove n is prime ?! >.<
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 18th 2009, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum