Powers of Two

**Defunkt** · October 3rd 2010, 05:52 AM

Challenge Question

Prove that for $m \ne n \in \mathbb{N}$ , $gcd \left( 2^{2^n}}+1, 2^{2^m}}+1 \right) = 1$

Note: There is a very simple solution (in terms of not requiring the use of theorems, not neccesarily in terms of length )

Moderator approved. CB

**undefined** · October 3rd 2010, 06:22 AM

Originally Posted by Defunkt

Challenge Question

Prove that for $m \ne n \in \mathbb{N}$ , $gcd \left( 2^{2^n}}+1, 2^{2^m}}+1 \right) = 1$

Note: There is a very simple solution (in terms of not requiring the use of theorems, not neccesarily in terms of length )

It has been discussed on the forum before.

http://www.mathhelpforum.com/math-he...ms-144720.html

Note: LaTeX colour tags don't work now, but they used to, hence the words "red" and "black" in my LaTeX.

Note #2: Since that thread is kind of long, you can find the main part of the proof here

http://en.wikipedia.org/wiki/Fermat_...sic_properties

**Defunkt** · October 3rd 2010, 07:32 AM

Oh..

Well, here's my proof, which is a little bit different:

Spoiler:

**melese** · October 3rd 2010, 04:59 PM

Denote by $F_n=2^{2^n}+1$ the $n$ -th Fermat Number. Observe that (1) $2^{2^n}-1=(2^{2^{n-1}}+1)(2^{2^{n-1}}-1)=(2^{2^{n-1}}+1)(2^{2^{n-2}}+1)(2^{2^{n-2}}-1)=$
$...=(2^{2^{n-1}}+1)(2^{2^{n-2}}+1)(2^{2^{n-3}}+1)\cdots(2^{2^1}+1)(2^{2^0}+1)(2^{2^0}-1)$ .

What happens? At each stage we take the rightmost term $2^{2^k}-1$ and factor it into: $(2^{2^{k-1}}+1)(2^{2^{k-1}}-1)$ ; continuing this way gives the above factorization of $2^{2^n}-1$ .

Now we can write (1) in the following form: (2) $F_n-2=F_{n-1}\cdot F_{n-2}\cdot F_{n-3}\cdots F_1\cdot F_0$ .

Suppose that $m<n$ . Then by (2), $F_n-2=t\cdot F_m$ , where $t$ is a positive integer. It follows that any common divisor of $F_n$ and $F_m$ must divide $2$ , and therefore is equal to $1$ or $2$ . Fermat Numbers are odd, so the only common divisor they have is $1$ .

Incidentally, the result of this problem is one of the proofs that there are infinitely many prime numbers....

**PaulRS** · January 4th 2011, 03:29 AM

Let's assume $\text{gcd}\left(2^{2^m}+1,2^{2^n}+1\right) > 1<br />$ , then there's a prime $p$ that divides both $2^{2^m}+1$ and $2^{2^n}+1$ .

Thus $2^{2^n}\equiv -1 (\bmod.p)$ and $2^{2^m}\equiv -1 (\bmod.p)$ but without loss of generality -by symmetry- we may assume that $m > n$ and then $2^{2^m} = \left(2^{2^n}\right)^{2^{m-n}}\equiv_p (-1)^{2^{m-n}} = 1$ which implies $-1 \equiv 1 (\bmod.p)$ thus $p=2$ which is abusrd since both numbers are odd.

Remark: In fact one may observe that $2^{2^n}\equiv -1 (\bmod.p)$ implies that the order of 2 module p is $2^{n+1}$ so applying this to both m and n yields $m = n$

Thread: Powers of Two

LinkBack

Thread Tools

Display

Fermat Numbers

Similar Math Help Forum Discussions

Powers of 2

Powers of 0 and 1

Powers - please help!

Search Tags