Fermat vs Euler

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\cdots (p-1)\equiv a\cdot 2a \cdots (p-1)a \;(\mathrm{mod}\;p).\)
  4. Cancellation: \(1\equiv a^{p-1}\;(\mathrm{mod}\;p).\)

However, when we are talking about a 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...