# If $a^{n-1} \equiv 1 \pmod{n}$, can we say that $(a,n) = 1$?

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?

Thanks,

-

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.

-
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 math.stackexchange.com/questions/26145/…? 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.)

-
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.

-