TITLE: $a^{n-1}=1\pmod n$ but $a^d\neq 1 \pmod n$ for every proper divisor $d$ of $n-1$. Prove that $n$ is a prime.
QUESTION [0 upvotes]: Let $a$ and $n>1$ be any integers such that $a^{n-1}=1\pmod n$ but $a^d\neq 1 \pmod n$ for every proper divisor $d$ of $n-1$. Prove that $n$ is a prime.

REPLY [2 votes]: Suppose $n$ is composite. Then $\def\Z{\Bbb Z}\Z/n\Z$ has zero divisors, so its group of invertible elements has less than $n-1$ elements. In particular, it cannot contain an element of order$~n-1$, like $a$. Contradiction.
{"set_name": "stack_exchange", "score": 0, "question_id": 1911321}