1
$\begingroup$

Suppose that $n \in \mathbb{N}$ and that $2 \leq a \leq n-2.$ I want to show that if $a^3 \equiv a$ (mod $n$), then $n$ is composite.

Well, $n$ being composite means that there are other factors (apart from $1$ and itself) that, when multiplied together, yield $n$. I'm trying to wrap my head around this problem, but cannot seem to get anywhere. Since we are showing $n$ is composite, perhaps Fermat's Little Theorem will not be useful here, but, instead, maybe there needs to be a direct application of Euler's Theorem. Comments and suggestions are welcome.

$\endgroup$
5
$\begingroup$

You know that $n\mid a(a-1)(a+1)$. If $n$ is prime, then $n\mid a-1$ or $n\mid a$ or $n\mid a+1$. That's not possible, since $a\leqslant n-2$.

$\endgroup$
  • $\begingroup$ Never occurred to me one can do it that way. Short and simple. +1 $\endgroup$ – John Smith Apr 16 '18 at 21:39

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.