Bizonyítás
A \varphi(p^k) a 20.18. Következmény alapján a 0, 1, 2, ..., p^k-1 közül a p^k-hoz relatív prímek számát adja meg. Nincs más dolgunk tehát, mint ezeket megszámlálni. A 21.4. Lemma szerint egy tetszőleges a egész szám akkor és csak akkor relatív prím p^k-hoz, ha nem osztható p-vel.
Ahhoz tehát, hogy megkapjuk \varphi(p^k) értékét, meg kell számolnunk, hogy összesen hány p-vel osztható egész szám van az első p^k darab pozitív egész szám között. A 21.4. Lemma alapján ugyanis épp az ezeken kívüli számok lesznek relatív prímek p^k-hoz. A p-vel osztható számok ebben a tartományban az alábbiak lesznek:
Ezek száma tehát összesen p^{k-1}. Ezt levonva p^k-ból valóban \varphi(p^k) értékét kapjuk, ahogyan a tétel állítja:
Végül a speciális eset: A \varphi(p) a 20.18. Következmény alapján a 0, 1, 2, ..., p-1 számok közül a p-hez relatív prímek számát adja meg. Ezt ugyanúgy a 21.4. Lemma alapján tudjuk megszámlálni: megszámláljuk, hogy hány p-vel osztható van ezek között, majd ezt levonjuk a darabszámukból, ami ugye p.
A 0 biztosan osztható p-vel a 16.2. Tétel 3. pontja miatt. A felsorolt további számok közül viszont egyik sem osztható p-vel. Tegyük fel ugyanis indirekt, hogy nem ez a helyzet, vagyis létezik olyan r közöttük, hogy p|r. Ebből a 17.2. Lemma alapján p\leq r következne, ami ellentmondás.
Mivel tehát a 0, 1, 2, ..., p-1 számok közül csak a 0 volt osztható p-vel, így a 21.4. Lemma alapján valóban a maradék p-1 darab szám lesz relatív prím p-hez, azaz:
∎