# 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?

×