Results 1 to 5 of 5

Thread: Powers of Two

  1. #1
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976

    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
    Last edited by Defunkt; Oct 3rd 2010 at 06:19 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Defunkt View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Oh..

    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$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    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....
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Powers of 2
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 3rd 2009, 10:06 AM
  2. Powers of 0 and 1
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Jul 19th 2008, 06:00 AM
  3. Powers - please help!
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jul 9th 2008, 07:23 PM

Search Tags


/mathhelpforum @mathhelpforum