Fermat vs Euler

Number Theory Level 5

Fermat's little theorem states that for prime \(p\), we have \(a^{p-1} \equiv 1 (\mathrm{mod}\;p)\) (\(p\not\mid a\)). Here is a proof:

  1. Consider \(1,2,\cdots,p-1\) and \(a,2a,\cdots,(p-1)a\)
  2. They are permutations of each other under \(\mathrm{mod}\;p\)
  3. \(1\cdot 2\cdot \cdots \cdot (p-1)\equiv a\cdot 2a \cdot \cdots (p-1)a \;(\mathrm{mod}\;p)\)
  4. Cancellation: \(1\equiv a^{p-1}\;(\mathrm{mod}\;p)\)

However, when we are talking about composite number \(n\), we have \(a^{\phi(n)} \equiv 1 (\mathrm{mod}\;n)\) for coprime integers \(a\) and \(n\) instead, from Euler's theorem.

If I use the above proof flow for the Euler's theorem, in which step do I first make a mistake?


Problem Loading...

Note Loading...

Set Loading...