2
$\begingroup$

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,

3 Answers 3

7

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.

  • 0
    @Myself: I think I neither put in everything I say, nor say everything I put in. (-: (I wasn't trying to brow-beat you, just that the even case may have felt like cheating$a$bit, so an example with odd $n$ would be interesting; note that if $n-\varphi(n)$ is relatively prime to $\varphi(n)$, then the conclusion *will* follow).2011-03-09
2

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

1

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