1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$ ?? $\endgroup$ – Mr.Fry Jun 9 '15 at 2:19
  • $\begingroup$ You probably mean $a^{m-1}\equiv1$. $\endgroup$ – lhf Jun 9 '15 at 2:24
  • $\begingroup$ ah yes, sorry! that is what i meant $\endgroup$ – futuremathteacher Jun 9 '15 at 2:29
  • $\begingroup$ Such $m$ are by definition Carmichael numbers. See math.stackexchange.com/questions/1764812/… $\endgroup$ – lhf Jun 1 '18 at 17:47
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How do you know that $(g,m)=1$? You can't just pick any primitive root. $\endgroup$ – Thomas Andrews Jun 9 '15 at 2:48
  • $\begingroup$ 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$) $\endgroup$ – futuremathteacher Jun 9 '15 at 2:52
  • 1
    $\begingroup$ maths.ed.ac.uk/~chris/NTh/wkp3_12sol.pdf I didn't read it completely, but it seems shorter! $\endgroup$ – mich95 Jun 9 '15 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.