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

• Jan 12th 2007, 02:37 PM
Jenny20
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.
• Jan 13th 2007, 03:11 PM
ThePerfectHacker
Quote:

Originally Posted by Jenny20
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.

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.