Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
7  
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

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
1  
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$...

share|improve this answer
    
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\:.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.