# Powers of Two

• October 3rd 2010, 05:52 AM
Defunkt
Fermat Numbers
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
• October 3rd 2010, 06:22 AM
undefined
Quote:

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
• October 3rd 2010, 07:32 AM
Defunkt

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

Spoiler:
Write $A_m = 2^{2^m} + 1$ and $A_n = 2^{2^n}+1$ and assume WLOG that m>n.
Let $k = m - n$ so that $m = n + k$. Now we have:

$A_m = \left( 2^{2^m}-1 \right) +2 = \left( 2^{2^n \cdot 2^k} - 1 \right) + 2 = \left( 2^{2 \cdot 2^n} \right)^{2^{k-1}} - 1 + 2$

Let $b = 2^{2^n}, \ a = 2^{2 \cdot 2^n}$ so that $a = b^2$. Rewrite $A_m$:

$A_m = \left( a^{2^{k-1}} -1 \right) + 2 = (a-1) \left( 1 + a + a^2 + \ldots + a^{2^{k-1} -1} \right) + 2$

So if we write for simplicity's sake $d = \left( 1 + a + a^2 + \ldots + a^{2^{k-1} -1} \right)$ we get

$A_m = (a-1)d + 2 = (b^2 - 1)d + 2 = (b+1)(b-1)d + 2 = \left( 2^{2^n} + 1 \right) \left( b-1 \right) d + 2$
Therefore $A_m = A_n(b-1)d + 2$

And so $gcd(A_m, A_n) \ | \ 2$, but since they are both odd, so is their greatest common divisor, and thus $gcd(A_m , A_n) =1$
• October 3rd 2010, 04:59 PM
melese
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. 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....
• January 4th 2011, 03:29 AM
PaulRS
Let's assume $\text{gcd}\left(2^{2^m}+1,2^{2^n}+1\right) > 1
$
, 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$