1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof about 2 numbers being relatively prime.

  1. May 28, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove that their are an infinite amount of primes by observing that in the series
    [itex] 2^2+1, 2^{2^2}+1,2^{2^3}+1,2^{2^4}+1,........ [/itex]
    every 2 numbers are relatively prime.
    3. The attempt at a solution
    I was going to take 2 of the numbers in the series and look at their difference because if they have common factors then it should divide their difference, but then im not sure how this will work.
    or maybe I should look at these numbers mod2 or something, well I guess mod2 these all equal 1.
     
  2. jcsd
  3. May 28, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Seems a good start. Suppose p divides each, so it divide the difference. Can you then discard a factor of the difference and deduce that p divides the remaining factor?
     
  4. May 29, 2013 #3
    If I look at [itex] 2^4+1-(2^2+1)=2^4-2^2=2^2(2^2-1) [/itex] we know that
    [itex] 2^2+1 [/itex] and [itex]2^2-1 [/itex] are relatively prime because they are an odd number separated by a power of 2. But then I was trying to generalize this proof. where we have
    [itex] 2^x+1,2^y+1 [/itex] x<y then [itex] 2^y+1-2^x-1=2^x(2^{y-x}-1 [/itex] I guess I could make a similar argument that [itex] 2^{y-x}-1 [/itex] and [itex] 2^x+1 [/itex] are relatively prime.
     
  5. May 29, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I don't think that argument will work.
    As I said, suppose p divides 22x+1 and 22y+1, so it follows that p divides 22y-2x-1. Can you now construct more numbers it must divide?
     
  6. May 29, 2013 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    These numbers are called Fermat numbers. Define F(n)=2^(2^n)+1. Then if you can show the recursion relation F(n)=F(n-1)F(n-2)...F(1)F(0)+2, you are pretty much home free. Try concentrating on proving that. That's the usual route. Start by writing down the most obvious relation between F(n) and F(n-1) that you can think of.
     
    Last edited: May 29, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof about 2 numbers being relatively prime.
  1. Prime number proof (Replies: 2)

  2. Prime Number Proof (Replies: 6)

Loading...