Fermat NumbersDate: 01/25/2003 at 14:13:49 From: Ghori Subject: Fermat Number How can we prove that any two Fermat Numbers are coprime? Date: 01/25/2003 at 23:19:33 From: Doctor Paul Subject: Re: Fermat Number First establish by induction the following identity: [F_0 * F_1 * F_2 * ... * F_(n-1)] + 2 = F_n. Then we have: F_0 * F_1 * F_2 * ... * F_(n-1) = F_n - 2 Now suppose that there exists some integer d > 1 that divides both F_n and F_m for some m < n. Since d divides F_m for some m < n, it is clear that d also divides F_0 * F_1 * F_2 * ... * F_(n-1) But since F_0 * F_1 * F_2 * ... * F_(n-1) = F_n - 2, we can say that d must divide F_n - 2. We assumed above that d divides F_n. This, coupled with the fact that d divides F_n - 2 implies that d divides two. So either d = 2 or d = 1. But every Fermat number is odd. Thus it cannot be the case that d = 2. Hence d = 1. This contradicts the assumption that d > 1. Since this contradiction was derived directly from the assumption, it must be the case that our assumption is false. Thus no such d > 1 exists and it in fact is the case that the Fermat numbers are pairwise relatively prime. I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 01/26/2003 at 07:18:19 From: Ghori Subject: Fermat Number Dear Paul, Thanks for this lovely proof. But how can we establish the following identity. [F_0 * F_1 * F_2 * ... * F_(n-1)] + 2 = F_n. Best Regards Ghori Date: 01/26/2003 at 10:37:29 From: Doctor Paul Subject: Re: Fermat Number Proceed by induction on n. If n = 1, the equation yields 3 + 2 = 5 which is clearly true. Now assume that [F_0 * F_1 * F_2 * ... * F_(n-1)] + 2 = F_n. We want to prove: [F_0 * F_1 * F_2 * F_(n-1) * F_n] + 2 = F_(n+1). To do this, proceed as follows: Let x = [F_0 * F_1 * F_2 * ... * F_(n-1)] and let y = [F_0 * F_1 * F_2 * ... * F_(n-1) * F_n] Then we want to prove that y + 2 = F_(n+1) Notice that y = x * (x+2). This follows directly from the inductive hypothesis. So we want to show that [x * (x+2)] + 2 = F_(n+1) Now, [x * (x+2)] + 2 Notice that by the inductive hypothesis, we have: x = F_n - 2 Thus [x * (x+2)] + 2 = [(F_n - 2) * ((F_n - 2) + 2)] + 2 = [(F_n - 2) * F_n] + 2 = (F_n)^2 - 2*F_n + 2 = (2^(2^n) + 1) * (2^(2^n) + 1) - 2 * (2^(2^n) + 1) + 2 = 2^(2^n) * 2^(2^n) + 2 * 2^(2^n) + 1 - 2 * 2^(2^n) - 2 + 2 = 2^(2^n) * 2^(2^n) + 1 = 2^(2^n + 2^n) + 1 = 2^(2*(2^n)) + 1 = 2^(2^(n+1)) + 1 = F_(n+1) I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 01/27/2003 at 04:14:31 From: Ghori Subject: Fermat Numbers Are there infinitely many Fermat Numbers? How do we know that each Fermat Number will have a prime divisor? Date: 01/27/2003 at 18:34:27 From: Doctor Paul Subject: Re: Fermat Numbers The Fermat numbers are defined by: F_n = 2^(2^n)) + 1 Inasmuch as there are infinitely many positive integers that we can choose as the value for n, there are infinitely many Fermat numbers. By the Fundamental Theorem of Arithmetic, we know that each positive integer can be uniquely decomposed into a product of primes. The fact that F_n can be thus decomposed is all we need to guarantee the existence of a prime divisor of F_n for all positive integers n. You asked previously: If P_n is the n-th prime, how can we show that P_n <= F_n ? One of the other math doctors noticed: P_n has to be less than F_n because a prime dividing F_n is P_m, where m is at least n, since there are certainly primes that divide no Fermat prime (e.g. 2). I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 01/28/2003 at 16:53:20 From: Ghori Subject: Fermat Number Again thanks for your sincere response. I have never seen any volunteer academic service better than "Ask Dr Math." It is really a very great service. It would be unfair if I did not appreciate the people who provide this service. Of course, this service has promoted the awareness and importance of Mathematics. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/