Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We've learn in class that if $a^{p-1} \not\equiv 1 \pmod p$ then $p$ must be a composite number.
What is the explanation for that?


share|cite|improve this question
Do you already know some group theory? – DonAntonio Feb 1 '14 at 14:39
$a^{p-1} \equiv 1 \pmod p$ if $p$ is a prime:'s_little_theorem .But there are none primes such that the equation holds, like $341=11 \cdot 31$. – miracle173 Feb 1 '14 at 14:41
@miracle173, but, if $a^{p-1}\not\equiv 1 \pmod p,p$ can not be prime – lab bhattacharjee Feb 1 '14 at 14:43
@DonAntonio, I do know group theory. – SuperStamp Feb 1 '14 at 14:44
up vote 3 down vote accepted

At first $a$ and $p$ must be coprime, otherwise the statement is false. For example: Let $p$ be prime number and let $a=p$, then obviously we have:

$$p^{p-1} \equiv 0 \not \equiv 1 \pmod p$$

But we said that $p$ is prime number, so the statement is false:

If $(a,p) = 1$, then for every prime number we have:

$$a^{p-1} \equiv 1 \pmod p$$

This is true due to Fermat's Little Theorem. If you are interested in proof for this Theorem, I'm sure there are few on the Internet, because this is famous theorem.

So if $p$ is prime then $a^{p-1} \equiv 1 \pmod p$ holds, but if it doesn't hold it then $p$ can't be a prime number. So $p$ must be compisite.

Note that the converse doesn't hold, i.e. if $p$ is composite, then $a^{p-1} \equiv 1 \pmod p$ isn't always true. For more you can check Fermat pseudoprimes

share|cite|improve this answer

Since you know group theory, you can see that if $\;\Bbb F_p:=$ the ring with $\;p\;$ elements, then $\;\Bbb F_p^*=\;$ the multiplicative group of invertible elements, and thus $\;\forall\;a\in\Bbb F_p^*\;,\;\;a^r=1\;,\;\;r=\left|\Bbb F_p^*\right|\;$

Now you can easily show that

$$r=\left|\Bbb F_p^*\right|=p-1\iff p\;\;\text{is a prime number}\ldots$$

share|cite|improve this answer
Actually I have a basic knowledge in group theory, but thanks for the enrichment! – SuperStamp Feb 1 '14 at 14:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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