Bizonyítás

Amennyiben $a$ relatív prím a $p$ modulushoz, akkor alkalmazható az Euler-Fermat tétel, amely szerint ugye teljesül az alábbi kongruencia:

A 21.5. Tétel alapján az Euler-féle $\varphi$-függvény értéke ebben az esetben $p-1$. Ebből a tétel első állítása adódik:

Ám ebben az esetben a 20.2. Tétel 5. pontja szerint a kongruencia mindkét oldalát megszorozhatjuk $a$-val. Így teljesül az alábbi kongruencia is, amely tehát a tétel második állítása azokra az esetekre, amikoris $a$ relatív prím $p$-hez:

Már csak annyit kell megmutatni, hogy ez a második állítás abban az esetben is teljesül, ha $a$ és $p$ nem relatív prímek. A 21.4. Lemma alapján ebben az esetben teljesül a $p|a$ oszthatóság. Ez viszont a 20.1. Tétel 3. pontja alapján épp az alábbi kongruenciát jelenti:

Ám ekkor a 20.2. Tétel 6. pontja alapján a kongruencia mindkét oldalát $p$-edik hatványra emelhetjük. Így teljesül az alábbi kongruencia is:

Mivel tehát $a$ is és $a^p$ is $0$-val kongruens modulo $p$, ezért a 20.2. Tétel 3. pontja alapján ők egymással is kongruensek modulo $p$, épp ahogyan a tétel állítja: