elementary number theory - If $a notequiv 1 pmod{n}$, then does $a^n notequiv 1 pmod{n}$?

We have that:
If $a \equiv 1 \pmod{n}$, then does $a^n \equiv 1 \pmod{n}$?

But I don't know if this is true:
If $a \not\equiv 1 \pmod{n}$, then does $a^n \not\equiv 1 \pmod{n}$?

I tried to find a counter example, but it always turned out to be true. Any idea?

Thanks,

Answer

Think about equalities: it is certainly true that if $x=1$, then $x^n=1$; but it is not true that if $x\neq 1$ then $x^n\neq 1$ (e.g., $x=-1$, $n$ even).

The same is true with congruences: congruences modulo $n$ may be added and multiplied, just like equalities: if $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$, then $a+c\equiv b+d\pmod{n}$ (adding the two congruences) and $ac\equiv bd\pmod{n}$ (multiplying the two congruences). Same as with equalities. This immediately gives you that if $a\equiv 1 \pmod{n}$, then multiplying the congruence by itself $m$ times you will get $a^m \equiv 1^m=1\pmod{n}$, and in particular $a^n\equiv 1\pmod{n}$.

However, we cannot just add and multiple non-equalities: that is, if $a\neq b$ and $c\neq d$, then it does not follow that $a+c\neq b+d$ or that $ac\neq bd$ (I'll leave it to you to find easy counterexamples). Note well: these are not inequalities of the form $a\lt b$, but merely of the form "not equal to". Likewise with congruences. Just because $a\not\equiv 1 \pmod{n}$, it does not follow that $a^2\not\equiv 1^2\pmod{n}$, or $a^n\not\equiv 1\pmod{n}$ in general.

It does follow for $n$ prime, but that's not because of the properties of congruences, but rather because of Fermat's Little Theorem: because Fermat's Little Theorem tells you that $a^p\equiv a\pmod{p}$ when $p$ is a prime, so you can conclude that if $a\not\equiv 1\pmod{p}$, then $a^p \equiv a\not\equiv 1\pmod{p}$. But this is a particular property of primes, not of congruences.

Added. Going from the comments, some situations where it is true and some where it is false:

• If $\gcd(a,n)\gt 1$, then of course $a\not\equiv 1\pmod{n}$, and likewise $a^n\not\equiv 1\pmod{n}$; this is the "trivial case", one might say.




• If $\gcd(a,n)=1$, then of course we have $a^{\varphi(n)}\equiv 1 \pmod{n}$ by Euler's Theorem; thus, $a^n\equiv a^{\varphi(n)}a^{n-\varphi(n)}\equiv a^{n-\varphi(n)}\pmod{n}$. If $\gcd(\varphi(n),n-\varphi(n))=\gcd(\varphi(n),n)=1$, then from $a^{n-\varphi(n)}\equiv 1\pmod{n}$ you can conclude that $a\equiv 1\pmod{n}$, since no element, other than $1$, of the multiplicative group modulo $n$ has order dividing $n-\varphi(n)$ (since they all have order dividing $\varphi(n)$).




• However, if $\gcd(\varphi(n),)\gt 1$, then we can always pick a prime $p$ that divides $\gcd(\varphi(n),n)$, and find an element $a$ of the multiplicative group modulo $n$ that has order exactly $p$. That will mean that $a\not\equiv 1\pmod{n}$, but $a^p\equiv 1\pmod{n}$. Then we will have $a^{n} = a^{\varphi(n)}a^{n-\varphi(n)} = (a^{p})^k\equiv 1\pmod{n}$, where $kp = n-\varphi(n)$, so in this case there will always be a counterexample.

In short, the implication
$$a\not\equiv 1\pmod{n}\Longrightarrow a^n\not\equiv 1\pmod{n}$$

holds if and only if $\gcd(n,a)\gt 1$ or $\gcd(a,n)=\gcd(\varphi(n),n)=1$, where $\varphi(n)$ is Euler's phi function.