2
$\begingroup$

The integers $a$ and $n > 1$ satisfy $a^{n-1} \equiv 1\ (mod\ n)$ but $a^{m} \not\equiv 1\ (mod\ n)$ for every divisor $m$ of $n - 1$, other than itself. Prove that $n$ is prime.

The way I went about proving it was,


We know for every integer $k \geq 1$, $a^k \equiv 1 (mod\ n) \iff d\ \vert\ k$, where $d$ is the order of $a$.

Note $a^{n-1} \equiv 1\ (mod\ n)$ and all divisors $d\ \vert\ n - 1$ have $a^{d} \not\equiv 1\ (mod\ n)$. $\implies$ $n - 1$ is the order of $a$.

So we know $\{1, a, a^2, ..., a^{n-1}\} \subseteq residue\ class\ mod\ n$
So at least $n - 1$ elements coprime to $n \implies$ $n$ is prime


So assuming this proof is correct, I was wondering if anyone had a more formal justification / better explanation for the last two lines. My thought process was because we know the order of $a$ is $n-1$, all powers of $a$ are incongruent to each other and the set of incongruent $n -1$ elements forms a set of residues mod n.

And since there are $n -1$ elements less than and coprime to $n$, we get that $n$ must be prime.

Is this correct? If not, does anyone know of a better proof (using only elementary number theory techniques)?

$\endgroup$
  • 1
    $\begingroup$ "we know the order of a is n−1, all powers of a are incongruent to each other and the set of incongruent n−1 elements forms a set of residues mod n. And since there are n−1 elements less than and coprime to n, we get that n must be prime." This last bit is correct and more formal perhaps than your "last two lines". Your argument is probably the most elementary (another one being given in an answer below) $\endgroup$ – Max Mar 18 '18 at 20:41
  • $\begingroup$ Gotcha, thanks! $\endgroup$ – SS' Mar 18 '18 at 20:42
2
$\begingroup$

Well, if $n-1$ is the order of $a$, then $n-1\mid \varphi(n)$. Since $\varphi(n)\leq n-1$, we know $\varphi(n)=n-1$. This means $n$ is prime.

Not necessarily a better proof, but shorter, and I'd say simpler too.

$\endgroup$

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.