Fermat vs Euler

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

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

However, when we are talking about a composite number nn, we have aϕ(n)1 (mod  n)a^{\phi(n)} \equiv 1\ (\mathrm{mod}\;n) for coprime integers aa and nn 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...