Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks!

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

2 Answers

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|improve this answer
add comment

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|improve this answer
1  
Actually I have a basic knowledge in group theory, but thanks for the enrichment! –  SuperStamp Feb 1 at 14:52
add comment

Your Answer

 
discard

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.