A (\Z/p\Z)^{\times} csoport a \Z/p\Z maradékosztálygyűrű redukált maradékosztályaiból áll, ezért a 20.7. Definíció alapján ennek a csoportnak a rendje \varphi(p), azaz a 21.5. Tétel miatt p-1. Mivel a 24.14. Következmény miatt bármely elem rendje osztója a csoport rendjének, ezért ha d\nmid p-1, akkor (\Z/p\Z)^{\times}-ben nincs d rendű elem.

Az általánosság megsértése nélkül feltehetjük tehát, hogy d|p-1. A d rendű redukált maradékosztályok a 24.12. Tétel 4. pontja szerint mind megoldásai a \Z/p\Z maradékosztálygyűrű elemein értelmezett alábbi egyenletnek:

x^d=[1]_p

Mindkét oldalból kivonva az [1]_p maradékosztályt az alábbi egyenletet kapjuk:

x^d-[1]_p=[0]_p

Vegyük észre, hogy ennek az egyenletnek a megoldásai a 26.7. Definíció alapján épp egy \Z/p\Z feletti d-edfokú polinom gyökei. Mivel \Z/p\Z izomorf \Z_p-vel, ami pedig a 18.5. Tétel alapján nullosztómentes, így \Z/p\Z is nullosztómentes. Emiatt viszont a 26.11. Tétel alapján ennek a bizonyos polinomnak legfeljebb d darab gyöke, azaz a fenti egyenletnek legfeljebb d darab megoldása van. Azt ugyan nem tudjuk még, hogy a (\Z/p\Z)^{\times} csoportban létezik-e egyáltalán d rendű redukált maradékosztály – hiszen épp ezt szeretnénk igazolni –, de ha igen, akkor ő mindenképpen megoldás. Tegyük fel tehát, hogy például az [a]_p redukált maradékosztály egy d rendű megoldás, azaz:

[a]_p^d=[1]_p

Mivel [a]_p rendje d, így a 24.12. Tétel 3. pontja szerint az ő [a]_p^0, [a]_p^1, [a]_p^2, …, [a]_p^{d-1} hatványai mind különböznek egymástól, azaz különböző redukált maradékosztályok. Ezek a hatványok viszont szintén megoldásai a fenti egyenletnek, hiszen a hatványozás azonosságairól szóló 24.10. Tétel 2. pontja alapján tetszőleges k kitevő esetén teljesül az alábbi:

([a]_p^k)^d=[a]_p^{kd}=[a]_p^{dk}=(\underbrace{[a]_p^d}_{=[1]_p})^k=[1]_p

Mivel a megoldásszámról láttuk, hogy nem lehet d-nél nagyobb, így az [a]_p^0, [a]_p^1, …, [a]_p^{d-1} hatványokon kívül nincs más megoldás. Kérdés, hogy ezek közül melyek azok, amelyek [a]_p-hez hasonlóan szintén d rendűek. A csoportelem hatványának rendjéről szóló 26.12. Tétel alapján tetszőleges i kitevő esetén [a]_p^i rendje akkor és csak akkor egyezik meg [a]_p rendjével (azaz d-vel), ha az i kitevő relatív prím d-hez. Így tehát a d rendű elemek száma megegyezik a 0, 1, …, d-1 kitevők közül azoknak a számával, amelyek relatív prímek d-hez. Ez a 20.17. Következmény alapján épp \varphi(d).

Most foglaljuk össze az eddigieket: Az egyszerűség kedvéért jelöljük h(d)-vel a d rendű elemek számát. Eddig azt igazoltuk, hogy amennyiben d nem osztója p-1-nek, akkor h(d)=0, ha pedig d osztója p-1-nek, akkor az alábbi két eset lehetséges: h(d)=\varphi(d) vagy h(d)=0. A tétel bizonyításához azt kell belátnunk, hogy az utóbbi kizárt.

Tekintsük ezért p-1 összes pozitív osztóját: d_1, d_2, …, d_k. Mivel a 24.14. Következmény alapján bármely elem rendje csak ezen számok közül kerülhet ki, továbbá ugye összesen p-1 darab elem van, ezért egyrészt igaz az alábbi:

h(d_1)+h(d_2)+\ldots+h(d_k)=p-1

Másrészt a 26.13. Tétel alapján igaz az alábbi is:

\varphi(d_1)+\varphi(d_2)+\ldots+\varphi(d_k)=p-1

Érvényes tehát az alábbi összefüggés:

h(d_1)+\ldots+h(d_k)=\varphi(d_1)+\ldots+\varphi(d_k)

Az eddigiek alapján a baloldalon minden h(d_i) tag vagy 0-val vagy pedig \varphi(d_i)-vel egyezik meg. Ez az egyenlőség viszont csak ez utóbbi esetben teljesülhet, azaz p-1 minden d osztója esetén a d rendű elemek száma valóban \varphi(d).

A modulo p primitív gyökök épp azok az elemek, amelyeknek rendje p-1. A fentiek szerint ezekből \varphi(p-1) darab van, ami biztosan nagyobb 0-nál, azaz létezik primitív gyök modulo p.