# Powers of Two

• Oct 3rd 2010, 05:52 AM
Defunkt
Fermat Numbers
Challenge Question

Prove that for $\displaystyle m \ne n \in \mathbb{N}$, $\displaystyle 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
• Oct 3rd 2010, 06:22 AM
undefined
Quote:

Originally Posted by Defunkt
Challenge Question

Prove that for $\displaystyle m \ne n \in \mathbb{N}$, $\displaystyle 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
• Oct 3rd 2010, 07:32 AM
Defunkt

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

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

$\displaystyle 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 $\displaystyle b = 2^{2^n}, \ a = 2^{2 \cdot 2^n}$ so that $\displaystyle a = b^2$. Rewrite $\displaystyle A_m$:

$\displaystyle 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 $\displaystyle d = \left( 1 + a + a^2 + \ldots + a^{2^{k-1} -1} \right)$ we get

$\displaystyle 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 $\displaystyle A_m = A_n(b-1)d + 2$

And so $\displaystyle gcd(A_m, A_n) \ | \ 2$, but since they are both odd, so is their greatest common divisor, and thus $\displaystyle gcd(A_m , A_n) =1$
• Oct 3rd 2010, 04:59 PM
melese
Denote by $\displaystyle F_n=2^{2^n}+1$ the $\displaystyle n$-th Fermat Number. Observe that (1) $\displaystyle 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)=$
$\displaystyle ...=(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 $\displaystyle 2^{2^k}-1$ and factor it into: $\displaystyle (2^{2^{k-1}}+1)(2^{2^{k-1}}-1)$; continuing this way gives the above factorization of $\displaystyle 2^{2^n}-1$.

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

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

Incidentally, the result of this problem is one of the proofs that there are infinitely many prime numbers....
• Jan 4th 2011, 03:29 AM
PaulRS
Let's assume $\displaystyle \text{gcd}\left(2^{2^m}+1,2^{2^n}+1\right) > 1$ , then there's a prime $\displaystyle p$ that divides both $\displaystyle 2^{2^m}+1$ and $\displaystyle 2^{2^n}+1$.

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

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