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?

  • $\begingroup$ 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 $\endgroup$ – Tobias Kildetoft Nov 1 '16 at 11:23
  • $\begingroup$ Fermat proved his result for prime moduli, Euler generalized it to composite moduli. For composite moduli, $\varphi(m)\neq m-1$. $\endgroup$ – lulu Nov 1 '16 at 11:24
  • $\begingroup$ I do believe it works for $a,p$ relatively primes. $\endgroup$ – Simply Beautiful Art Nov 1 '16 at 11:28
  • $\begingroup$ @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. $\endgroup$ – yashirq Nov 1 '16 at 11:30
  • $\begingroup$ 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. $\endgroup$ – 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.


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.