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.

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,

share|improve this question
add comment

3 Answers

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|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 math.stackexchange.com/questions/26145/…? Thanks in advance. –  Chan Mar 11 '11 at 3:36
add comment

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|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
add comment

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|improve this answer
add comment

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.