# Show that every $m$ which has the property that $a^{m-1}\equiv1 \pmod m$ for all $a$ with $(a,m)=1$ is square-free

$a^{m-1}\equiv1 \pmod{m}$ for all $a$ with $(a,m)=1$.

I was able to prove the first part of the problem: show that for every $a$ such that $(a, 561)=1$, the congruence $a^{560} \equiv 1\pmod{561}$ holds by using Fermat's Little Theorem, but don't see how to generalize this.

• Edit your question. I don't understand what you are trying to say. If $m$ is square free and $(a,m)=1$ then $a^m - 1 \equiv 1\ \textrm{mod m}$ ?? – Mr.Fry Jun 9 '15 at 2:19
• You probably mean $a^{m-1}\equiv1$. – lhf Jun 9 '15 at 2:24
• ah yes, sorry! that is what i meant – futuremathteacher Jun 9 '15 at 2:29
• Such $m$ are by definition Carmichael numbers. See math.stackexchange.com/questions/1764812/… – lhf Jun 1 '18 at 17:47

Assume $m>2$, and that the property $a^{m-1} \equiv 1$ mod $m$ holds for all $a$ relatively prime to $m$.
We must have $(-1)^{m-1} \equiv 1$ mod $m$, so $m-1$ is even and $m$ is odd. Now we prove such $m$ must be square free.
Let $p$ be an odd prime dividing $m$ exactly $k$ times. Let $g$ be a primitive root mod $p^{k}$.
$g^{m-1} \equiv 1$ mod $p^{k}$. so the order of $g$ divides $m-1$ so $p^{k-1}(p-1)$ divides $m-1$. so $p^{k-1}$ divides $m-1$. But also $p^{k-1}$ divides $p^{k}$ which divides $m$, hence $p^{k-1}$ divides $m$ and $m-1$ and hence $p^{k-1}=1$ so $k=1$. $m$ is squarefree.
• How do you know that $(g,m)=1$? You can't just pick any primitive root. – Thomas Andrews Jun 9 '15 at 2:48
• Is there a way to prove this without using primitive roots? We haven't learned them yet. We can use ideas like order though (i.e. k is the minimal integer such that $a^k \equiv 1$) – futuremathteacher Jun 9 '15 at 2:52