Results 1 to 5 of 5

Math Help - Powers of Two

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

    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
    Last edited by Defunkt; October 3rd 2010 at 07: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 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
    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 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
    Follow Math Help Forum on Facebook and Google+

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

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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
    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: November 3rd 2009, 11:06 AM
  2. Powers of 0 and 1
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: July 19th 2008, 07:00 AM
  3. Powers - please help!
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 9th 2008, 08:23 PM

Search Tags


/mathhelpforum @mathhelpforum