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,  
 A: 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.
A: 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.)
A: 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.  
