A tételt a c kitevőre vonatkozó teljes indukcióval fogjuk igazolni.

Nézzük először a c=1 esetet! A 24.18. Tétel 3. pontja alapján ekkor G_p épp megegyezik a (\Z/p\Z)^{\times} multiplikatív csoporttal. Ennek rendje a modulo p redukált maradékosztályok számával, azaz \varphi(p)-vel egyezik meg, ami a 21.5. Tétel alapján valóban p-1.

Az indukció megindításához tegyük fel, hogy valamilyen c kitevő – mint például a most megmutatott c=1 – esetén a tétel igaz, azaz G_{p^c} elemszáma p-1. Azt kell igazolnunk, hogy ekkor G_{p^{c+1}} elemszáma is p-1. Rögzítsük G_{p^c} egy reprezentánsrendszerét, azaz válasszunk ki mindegyik G_{p^c}-beli nem Miller-Rabin-tanúból pontosan egy reprezentánselemet. Ekkor a G_{p^c} halmaz – amelynek tehát indukciós feltételezésünknek megfelelően p-1 eleme van – a következőképpen írható fel a most rögzített a_1, a_2, …, a_{p-1} reprezentánselemek segítségével:

G_{p^c}=\{[a_1]_{p^c}; [a_2]_{p^c}; [a_3]_{p^c};\ldots ;[a_{p-1}]_{p^c}\}

E reprezentánsrendszer felhasználásával most definiálunk egy f:G_{p^c}\to G_{p^{c+1}} függvényt, amely tehát a G_{p^c} halmaz minden eleméhez hozzárendel egy-egy elemet a G_{p^{c+1}} halmazból. Tekintsük a fenti reprezentánsrendszer szerinti bármelyik tetszőleges elemet, legyen ez például az [a_i]_{p^c}\in G_{p^c} nem Miller-Rabin-tanú. Ekkor a 24.18. Tétel 1. pontja alapján az a_i reprezentánselemre teljesül az alábbi kongruencia:

a_i^{p-1}\equiv 1\pmod{p^c}

Ebben az esetben a 26.19. Lemma alapján pontosan egy olyan modulo p^{c+1} maradékosztály létezik, amelynek elemeire (és csak azokra) fennáll az alábbi mindkét kongruencia:

\begin{aligned}x&\equiv a_i\pmod{p^c} \\ x^{p-1}&\equiv 1\pmod{p^{c+1}}\end{aligned}

Jelöljük ezt a modulo p^{c+1} maradékosztályt B_i-vel. Mivel tehát B_i elemeire teljesül a fenti kongruenciarendszer, és így az abban lévő második kongruencia is, ezért a 24.18. Tétel 1. pontja alapján a B_i maradékosztály nem Miller-Rabin-tanúja p^{c+1}-nek, azaz B_i\in G_{p^{c+1}}.

Ez tehát azt jelenti, hogy ha a keresett f függvényt az alábbi képlettel definiáljuk, akkor az valóban minden G_{p^c}-beli nem Miller-Rabin-tanúhoz egyértelműen hozzárendel egy-egy G_{p^{c+1}}-beli nem Miller-Rabin-tanút:

f([a_i]_{p^c})=B_i

Előszöris azt mutatjuk meg, hogy az így definiált f függvény injektív, azaz különböző G_{p^c}-beli elemekhez különböző G_{p^{c+1}}-beli elemeket rendel hozzá. Indirekt tegyük fel, hogy nem ez a helyzet, azaz létezik olyan egymástól különböző a_i és a_j a fent rögzített reprezentánsrendszerben, amelyekre teljesül az alábbi:

f([a_i]_{p^c})=f([a_j]_{p^c})

Az f függvény tehát indirekt feltételezésünk szerint az [a_i]_{p^c} és az [a_j]_{p^c} maradékosztályokhoz ugyanazt az alábbi ábrán B-vel jelölt modulo p^{c+1} maradékosztályt rendeli hozzá:

Tekintsük B-nek egy tetszőleges b reprezentánselemét. Ekkor b-re teljesülni fog a fenti kongruenciarendszer, és így az abban lévő első kongruencia a_i és a_j esetén is, azaz:

\begin{aligned}b&\equiv a_i\pmod{p^c} \\ b&\equiv a_j\pmod{p^c}\end{aligned}

Ám ekkor a 20.2. Tétel 2. és 3. pontjai miatt teljesül az alábbi kongruencia is:

a_i\equiv a_j\pmod{p^c}

Ám ez ellentmondás, hiszen indirekt feltételezésünkben azt mondtuk, hogy a_i és a_j egymástól különbözőek, és így – mivel ők a G_{p^c} halmaz egy reprezentánsrendszerének elemei – nem lehetnének azonos modulo p^c maradékosztályban. Az f függvény tehát valóban injektív, azaz különböző G_{p^c}-beli elemekhez szükségképpen különböző G_{p^{c+1}}-beli elemeket rendel hozzá.

Végül azt igazoljuk, hogy f az injektivitáson kívül szürjektív is, azaz nem létezik olyan G_{p^{c+1}}-beli elem, amely ne lenne hozzárendelve valamelyik G_{p^c}-beli elemhez. Indirekt tegyük fel, hogy nem ez a helyzet, vagyis létezik az alábbi ábrán látható B\in G_{p^{c+1}} maradékosztály, amely nincs hozzárendelve semelyik G_{p^c}-beli maradékosztályhoz f által:

Tekintsük B egy tetszőleges b reprezentánselemét, azaz legyen B=[b]_{p^{c+1}}. Mivel [b]_{p^{c+1}}\in G_{p^{c+1}}, ezért a 24.18. Tétel 1. pontja alapján b-re teljesül az alábbi kongruencia:

b^{p-1}\equiv 1\pmod{p^{c+1}}

Ám mivel a p^c|p^{c+1} oszthatóság nyilvánvalóan teljesül, ezért a 20.2. Tétel 9. pontja alapján teljesül az alábbi kongruencia is:

b^{p-1}\equiv 1\pmod{p^c}

Ám ekkor a 24.18. Tétel 1. pontja szerint a b által reprezentált modulo p^c maradékosztály nem Miller-Rabin-tanúja p^c-nek, azaz [b]_{p^c}\in G_{p^c}. Mivel azonban a korábban rögzített a_1, a_2, a_3, …, a_{p-1} egész számok a G_{p^c} halmaz egy reprezentánsrendszerét alkotják, ezért b szükségképpen azonos modulo p^c maradékosztályban van pontosan az egyikükkel. Azaz létezik olyan a_i ebben a reprezentánsrendszerben, amely esetén b-re teljesül az alábbi kongruencia is:

b\equiv a_i\pmod{p^c}

Összegezve tehát b az egyike azon egész számoknak, amelyek kielégítik az alábbi kongruenciarendszert:

\begin{aligned}x&\equiv a_i\pmod{p^c} \\ x^{p-1}&\equiv 1\pmod{p^{c+1}}\end{aligned}

Azt is láttuk, hogy b-re teljesül az alábbi kongruencia is:

b^{p-1}\equiv 1\pmod{p^c}

Ekkor azonban a 26.19. Lemma alapján a fenti kongruenciarendszert kielégítő egész számok épp egy modulo p^{c+1} maradékosztályt alkotnak, amelyben ezek szerint b is benne van, így ez épp a B=[b]_{p^{c+1}} maradékosztály. Az f függvény viszont épp ezt a maradékosztályt rendeli hozzá [a_i]_{p^c}-hez, ami ellentmond indirekt feltételezésünknek, miszerint B egy olyan G_{p^{c+1}}-beli maradékosztály, amely nincs hozzárendelve semelyik G_{p^c}-beli maradékosztályhoz sem f által. Az f függvény tehát valóban szürjektív.

Mivel f-ről megmutattuk, hogy egyszerre injektív és szürjektív, ezért ő tulajdonképpen egy kölcsönösen egyértelmű megfeleltetést létesít G_{p^c} és G_{p^{c+1}} elemei között, így e két halmaznak pontosan ugyanannyi eleme van tetszőleges pozitív c kitevő esetén. A bizonyítás elején a c=1 kitevő esetén láttuk, hogy a G_p halmaznak p-1 eleme van. A most bizonyított indukció miatt ekkor p-1 eleme lesz G_{p^2}-nek is, majd emiatt G_{p^3}-nak is, stb. Tehát tetszőleges pozitív c kitevő esetén G_{p^c}-nek is valóban p-1 eleme lesz, ahogyan a tétel állítja.