Fermat Number Proof: Relatively Prime

• cragar
In summary: So this proof is incomplete. The correct proof would be to use the fact that ##2^n-1|2^{mn}-1## for all odd numbers m, but I didn't want to get into that here.In summary, the conversation discusses how to show that all Fermat numbers are relatively prime. One possible approach is to use the fact that if they share common factors, then it should divide their difference. However, this proof is incomplete as it does not consider the possibility of one of the factors being non-integer. A more complete proof would use the property that 2^n-1 divides 2^{mn}-1 for all odd numbers m.
cragar

Homework Statement

Show that all fermat numbers are relatively prime.

The Attempt at a Solution

If they share common factors then it should divide their difference so I look at
n>x
$(2^{2^n}+1)-(2^{2^x}+1)=2^{2^x}(2^{2^n-2^x}-1)$
Now since fermat numbers are odd their factors will have to be contained in
$(2^{2^n-2^x}-1)$ Now if they share common factors then it should divide
$(2^{2^n-2^x}-1)+(2^{2^n}+1)= (2^{2^n-2^x}+2^{2^n})=2^{2^n}(2^{-2^x}+1)$
Since fermat numbers are odd their factors must divide into
$(2^{-2^x}+1)$ but this is not an integer so this contradicts our assumption that it will divide our sum, so fermat numbers are relatively prime.

Looks good. The usual way to prove this is to use one of the properties of Fermat numbers, like ##F_0F_1...F_{n-1} + 2 = F_n##, which gives a much quicker and neater proof. But proving that proposition is more work to begin with. So your way is better from first principles.

This webdocument is quite useful: http://modular.math.washington.edu/edu/2010/414/projects/tsang.pdf

EDIT: Please see Joffan's and Dick's posts. You cannot use this if one (or more) of your factors is not an integer.

Last edited by a moderator:
Sorry, no - you can't present that final step as a valid factorization with one of the parts non-integer.

Joffan said:
Sorry, no - you can't present that final step as a valid factorization with one of the parts non-integer.

Obviously, let's prove ##2^n-1## is prime. ##2^n-1=2^n(1-2^{-n})##, ##2^n-1## is odd therefore any factor must divide ##1-2^{-n}## which not an integer. QED. That's baloney. ##2^4-1=15## is not prime.

Dick said:
Obviously, let's prove ##2^n-1## is prime. ##2^n-1=2^n(1-2^{-n})##, ##2^n-1## is odd therefore any factor must divide ##1-2^{-n}## which not an integer. QED. That's baloney. ##2^4-1=15## is not prime.

A very good point. When making the argument, both factors must be integers.

1. What is a Fermat number?

A Fermat number is a number of the form 2^(2^n) + 1, where n is a non-negative integer. These numbers were first studied by Pierre de Fermat in the 17th century.

2. Why are Fermat numbers important in number theory?

Fermat numbers have many interesting properties, including being prime or having only a few prime factors. They also play a role in the study of perfect numbers and Mersenne primes.

3. What is the proof that all Fermat numbers are relatively prime?

The proof involves using modular arithmetic and induction to show that for any two distinct Fermat numbers, their greatest common divisor (GCD) is 1. This means that they are relatively prime.

4. How does the proof of Fermat numbers being relatively prime relate to Fermat's Last Theorem?

Fermat's Last Theorem states that there are no positive integer solutions to the equation a^n + b^n = c^n for n > 2. The proof of Fermat numbers being relatively prime is a key step in Andrew Wiles' proof of Fermat's Last Theorem.

5. Are there any exceptions to the rule that all Fermat numbers are relatively prime?

Yes, there are two known exceptions to this rule: F_0 = 3 and F_1 = 5. These two numbers are not relatively prime, as their GCD is 1. This is because they are the only two Fermat numbers that are also prime numbers.

Replies
9
Views
2K
Replies
6
Views
2K
Replies
9
Views
2K
Replies
3
Views
957
Replies
2
Views
2K
Replies
2
Views
3K
Replies
13
Views
3K
Replies
7
Views
2K
Replies
5
Views
1K
Replies
5
Views
1K