Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $a^{n-1} \equiv 1 \pmod{n}$, can we say that $(a,n) = 1$? If not, what conditions do we need to make this argument true? Any idea?


share|cite|improve this question
up vote 5 down vote accepted

We have the following two elementary facts that you may be overlooking:

  • If $a\equiv b\pmod{n}$, then $\gcd(n,a) = \gcd(n,b)$ (since $\gcd(n,a) = \gcd(n,a+kn)$ for any $k$, and $a\equiv b\pmod{n}$ implies that $b=a+kn$ for some $k$).

  • If $a|b$, then $\gcd(n,a)|\gcd(n,b)$. Simply note that any common divisor of $n$ and $a$ must be a common divisor of $n$ and $b$, since $a|b$ holds.

So, if $m\geq 1$ and $a^m\equiv 1\pmod{n}$, then since $a|a^m$ we have $$\gcd(n,a) \;|\; \gcd(n,a^m) = \gcd(n,1) = 1,$$ hence $\gcd(n,a)=1$.

In particular, for $a^{n-1}\equiv 1 \pmod{n}$: if $n\gt 1$, then apply the observation above with $m=n-1$. If $n=1$ then you cannot apply the observation, since then you have $n-1 = 0$, but if $n=1$, then $\gcd(n,a) = \gcd(1,a) = 1$ as well.

share|cite|improve this answer
Thank you. If $n \neq 1$, can you give me a short elementary proof how it actually works. I just can't see it from your arguments above. – Chan Mar 11 '11 at 3:26
@Chan: What are you unclear about? Why $\gcd(n,a^m)=1$? – Arturo Magidin Mar 11 '11 at 3:27
Yes, can you explain that? – Chan Mar 11 '11 at 3:29
@Chan: Done. Does that do? – Arturo Magidin Mar 11 '11 at 3:33
Thanks, reading it ^_^! By the way, if you have some times, would you mind taking a look at this thread…? Thanks in advance. – Chan Mar 11 '11 at 3:36

Yes. Suppose $n>1$. Since $a^{n-1}$ is relatively prime to $n$, $a$ and $n$ can share no common prime factors.

In fact, you may note that the invertible elements in the ring of integers mod $n$ are precisely the integers (or residue classes thereof) prime to $n$. So since $a$ has an inverse in this ring (namely, $a^{n-2}$), $a$ must be relatively prime to $n$.

(If $n =1$, the statement is true automatically.)

share|cite|improve this answer
Thank you. – Chan Mar 11 '11 at 3:28
I fear I may have misdirected you (since I also had "yes if $n\gt 1$", until I realized $n$ was both in the exponent and the modulus). If $n=1$, then $\gcd(n,a)=1$ holds (though of course, $a^{m-1}\equiv 1\pmod{n}$ does not imply $\gcd(a,n)=1$ if $m=1$). – Arturo Magidin Mar 11 '11 at 3:41
@Arturo: Dear Arturo, sure, thanks for pointing that out. – Akhil Mathew Mar 11 '11 at 4:22

Or as noted, that holds for any $m\geq 1.$ Since, if $\gcd(a,n)=d$ then $d|n|a^m-1$ and $d|a.$ Hence, $d|1$ and we're done.

share|cite|improve this answer

Your Answer


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.