Results 1 to 2 of 2

Thread: 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
    10
    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 $\displaystyle n$ for it is larger than 1.
    Then by relative primeness the congruences simplifies.
    In that case, the problem simplifies to showing,
    $\displaystyle 2^n\not \equiv 1 (\mbox{ mod } n)$
    Where, $\displaystyle n=p^m$.

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

    Thus, $\displaystyle n=p^m$ for an odd prime and $\displaystyle \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 $\displaystyle \phi(n)$ divides $\displaystyle n$. But that cannot be because $\displaystyle \phi(n)$ is even for $\displaystyle n>1$ and $\displaystyle n$ is odd. A contradiction.

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

    Let the order of 2 be $\displaystyle k$. Thus,
    $\displaystyle (r^j)^k=r^{jk}\equiv 1$.
    Since $\displaystyle r$ is a primitive root, $\displaystyle \phi(n) | jk$. If $\displaystyle k$ is even then there is nothing to prove because that would imply that the order divides $\displaystyle n$ which is a contradiction for it is odd. Now if $\displaystyle k$ is odd by Euclid's lemma we have $\displaystyle \phi(n) | j $. Thus, $\displaystyle j$ is even that means $\displaystyle (r^k)^j\equiv 1$ implies $\displaystyle r^k$ is a quadradic residue of $\displaystyle n=p^m$ and therefor a quadradic residue of $\displaystyle p$, in that case $\displaystyle 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 $\displaystyle 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: Oct 16th 2010, 06:27 PM
  2. incongruent integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 8th 2009, 05:43 PM
  3. incongruent primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 9th 2008, 10:14 AM
  4. incongruent integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 9th 2008, 10:00 AM
  5. incongruent solutions to (mod n)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jun 4th 2008, 03:28 PM

Search Tags


/mathhelpforum @mathhelpforum