# Why $p$ has to be a prime in Fermat's theorem?

Fermat's theorem states:

Let $p$ denote a prime. If $p\nmid a$, then $a^{p-1} \equiv 1$(mod $p$).

Euler's generalization of Fermat's theorem states:

If $(a, m) = 1$, then $a^{\phi(m)} \equiv 1$(mod $m$).

We know $\phi(m)$ may not be a prime. For example $\phi(5)$ = 4 is not a prime.

Then why $p$ has to be a prime in Fermat's theorem?

• I don't see how your question relates to Euler's generalization. $\varphi(p) = p-1$ for all primes $p$, and this is precisely the exponent in Fermat – Tobias Kildetoft Nov 1 '16 at 11:23
• Fermat proved his result for prime moduli, Euler generalized it to composite moduli. For composite moduli, $\varphi(m)\neq m-1$. – lulu Nov 1 '16 at 11:24
• I do believe it works for $a,p$ relatively primes. – Simply Beautiful Art Nov 1 '16 at 11:28
• @lulu I don't mean $φ(m)=m−1$. When m = 4, the numbers coprime to 4 is 1 and 3, so $\phi 4$ will be 2. – yashirq Nov 1 '16 at 11:30
• Yes, Euler's Theorem is true. But I don't see the problem...people generalize theorems all the time, doesn't make the special case uninteresting. – lulu Nov 1 '16 at 11:31

Euler's totient function $\varphi(n)$ is defined to be the number of integers between 1 and n coprime to n. So if $\varphi(n)=n-1$ then all of $1,2,3\dotsb n-2,n-1$ are relatively prime to n. Which means n is prime.