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:

- Consider \(1,2,\cdots,p-1\) and \(a,2a,\cdots,(p-1)a.\)
- They are permutations of each other under \(\mathrm{mod}\;p.\)
- \(1\cdot 2\cdots (p-1)\equiv a\cdot 2a \cdots (p-1)a \;(\mathrm{mod}\;p).\)
- 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...