If $a \not\equiv 1 \pmod{n}$, then does $a^n \not\equiv 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,

-
Did you try n = 4? –  Jason DeVito Mar 9 '11 at 17:38
@Jason DeVito: not yet. Thank you, I found my counter example ;). –  Chan Mar 9 '11 at 17:39

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.

-
Perhaps we should call them "unequalities" :-) –  Aryabhata Mar 9 '11 at 17:55
By Chinese Remainder theorem, it's true for square-free numbers as well, if I'm not mistaken. –  Myself Mar 9 '11 at 17:55
@Arturo Magidin: ofcourse thanks! I was reasoning that if $a^{10} \equiv 1\mod 10$ then $a^{10}\equiv 1\mod p$ for $p=2,5$. But then ofcours it's not true that $a^p \equiv 1\mod p$. –  Myself Mar 9 '11 at 17:59
@Myself: Doesn't work, at least not for even squarefree numbers greater than $2$: if $n$ is squarefree and even, greater than $2$, then $(-1)^n\equiv 1\pmod{n}$ even though $-1\not\equiv 1\pmod{n}$. –  Arturo Magidin Mar 9 '11 at 18:04
@Myself: for an odd example, take $n=55$; note that $\varphi(n)=40$, and $5$ divides both $\varphi(n)$ and $n-\varphi(n)$. There is an integer $a$, relatively prime to $n$, such that the (multiplicative) order of $a$ modulo $n$ is exactly $5$. Then $a\not\equiv 1\pmod{55}$, but $a^{55} = a^{40}a^{15}=a^{40}(a^5)^3 \equiv 1\pmod{55}$. –  Arturo Magidin Mar 9 '11 at 18:17

Counterexample: $a = 9$, $n = 10$...

-
Many thanks. –  Chan Mar 9 '11 at 17:44

This can be completely analyzed by basic group thory. Mod $\rm\:n\:$, the elements coprime to $\rm\:n\:$ comprise the unit group of order $\rm\:\phi = \phi(n)\:.\$ Thus $\rm\ x^n = x^{\phi} = 1\ \Rightarrow\ x^{(n,\ \phi)} = 1\:.\:$ So if they are coprime, i.e. $\rm\:(n,\phi)=1\:,\:$ then we deduce that $\rm\:x=1\:$ and the result is true. Otherwise it fails since then we may choose a prime $\rm\:p\ |\ (n,\phi)\$ properly, and a counterxample arises by choosing an element of order $\rm\:p\:.$

-