Fermat Number ProofDate: 01/30/2001 at 00:26:36 From: Robyn Subject: Fermat numbers Dr. Math, Two questions: 1) Prove that if n > 0, then the Fermat number 2^2^n + 1 is of the form 9k-1 or 9k-4. 2) Prove that n and 2^2^n + 1 are relatively prime for every n > 0. Answers would be appreciated! Robyn Date: 01/30/2001 at 12:41:52 From: Doctor Rob Subject: Re: Fermat numbers Thanks for writing to Ask Dr. Math, Robyn. The first proof starts with Euler's Theorem: If (a,n) = 1, then a^phi(n) = 1 (mod n), where phi is the Euler phi function. Apply this with a = 2 and n = 9. Then phi(9) = 6, so 2^6 = 1 (mod 9). Thus for any nonnegative integer s, 2^(6*s) = 2^0 = 1 (mod 9). That means that the exponent of 2 can be reduced modulo 6. You cannot apply Euler's Theorem with a = 2 and n = 6, because (a,n) = 2 > 1. Now it is obvious that 2^n = 0 (mod 2) and Euler's theorem says that 2^2 = 1 (mod 3). This implies that for any nonnegative integer r, 2^(2*r) = 1 (mod 3) and 2^(2*r+1) = 2 (mod 3). Using the Chinese Remainder Theorem, that means that for any nonnegative integer r, 2^(2*r) = 4 (mod 6), 2^(2*r+1) = 2 (mod 6). Now you can finish be evaluating 2^(2^n) + 1 modulo 9 when n = 2*r and when n = 2*r + 1. To prove that 2^(2^n) + 1 and n are relatively prime, it suffices to show that every prime divisor p of 2^(2^n) + 1 has the form p = k*2^(n+1) + 1 for some k > 0. (This was proven by Leonhard Euler in 1770.) Obviously any prime divisor p of 2^(2^n) + 1 must be odd. Now let e be the order of 2 modulo p, that is, the least exponent such that 2^e = 1 (mod p). Obviously e > 1. Since 2^(2^(n+1)) = 1 (mod p), it must be that e | 2^(n+1). Write r*e = 2^(n+1). Then obviously r and e are both powers of 2. Since e > 1, e/2 is an integer, and then 2^(e/2) = -1 (mod p). Thus -1 = 2^(2^n) = 2^(e*r/2) = [2^(e/2)]^r = (-1)^r = -1 (mod p), so that r must be odd. Since r is a power of 2, obviously r = 1, so that e = 2^(n+1). That proves that 2^(n+1) | p - 1. Let k = (p-1)/2^(n+1) >= 1, and then solve for p to get p = k*2^(n+1) + 1. Q.E.D. Now use that to show that if p is a prime divisor of 2^(2^n) + 1, that p cannot divide n, and you'll be done. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/