Results 1 to 2 of 2

Math Help - 2^n is incongruent to 1 (mod n)

  1. #1
    Member
    Joined
    Nov 2006
    Posts
    123

    Post 2^n is incongruent to 1 (mod n)

    Question
    Show that 2^n is incongruent to 1 (mod n) for all n>1.

    Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Jenny20 View Post
    Question
    Show that 2^n is incongruent to 1 (mod n) for all n>1.

    Thank you very much.
    First you can prime decompose n for it is larger than 1.
    Then by relative primeness the congruences simplifies.
    In that case, the problem simplifies to showing,
    2^n\not \equiv 1 (\mbox{ mod } n)
    Where, n=p^m.

    Now, if n is even there is nothing to prove because if it were the case that,
    2^n\equiv 1 we have,
    \gcd (2^n,1)>1 while \gcd(1,n)=1, a contradiction.

    Thus, n=p^m for an odd prime and \gcd(2,n)=1.

    There are 2 cases either 2 is a primitive root or it is not.

    1)2 is a primitive root. Then \phi(n) divides n. But that cannot be because \phi(n) is even for n>1 and n is odd. A contradiction.

    2)If 2 is not a primitive root then by Gauss' theorem since n=p^m it has a primitive root. Call it r. Thus, 2\equiv r^j for 1<j\leq \phi(n).

    Let the order of 2 be k. Thus,
    (r^j)^k=r^{jk}\equiv 1.
    Since r is a primitive root, \phi(n) | jk. If k is even then there is nothing to prove because that would imply that the order divides n which is a contradiction for it is odd. Now if k is odd by Euclid's lemma we have \phi(n) | j . Thus, j is even that means (r^k)^j\equiv 1 implies r^k is a quadradic residue of n=p^m and therefor a quadradic residue of p, in that case k must be even because primitive roots are quadradic residues if and only if for even indexes. Thus, the order of 2 is even contrary to our assumption that the order was odd. Hence in all cases 2^n can never be congruence to 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. incongruent solutions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2010, 06:27 PM
  2. incongruent integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 8th 2009, 05:43 PM
  3. incongruent primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2008, 10:14 AM
  4. incongruent integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2008, 10:00 AM
  5. incongruent solutions to (mod n)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 4th 2008, 03:28 PM

Search Tags


/mathhelpforum @mathhelpforum