Amennyiben a relatív prím a p modulushoz, akkor alkalmazható az Euler-Fermat tétel (20.19. Tétel). Eszerint teljesül az alábbi kongruencia:
a^{\varphi(p)}\equiv 1\pmod pA 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:
a^{p-1}\equiv 1\pmod pÁm ebben az esetben a 20.2. Tétel 7. pontja miatt a kongruencia mindkét oldalát megszorozhatjuk a-val. Így teljesül az alábbi kongruencia is, amely a tétel második állítása:
a^p\equiv a\pmod pMá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:
a\equiv 0\pmod pÁm ekkor a 20.2. Tétel 8. pontja alapján a kongruencia mindkét oldalát p-edik hatványra emelhetjük. Így teljesül az alábbi kongruencia is:
a^p\equiv 0\pmod pMivel 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:
a^p\equiv a\pmod p