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

1. ## 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.

2. 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 $\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.