Question

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

Thank you very much.

Printable View

- Jan 12th 2007, 01:37 PMJenny202^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, 02:11 PMThePerfectHacker
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.