Az itt következő bizonyítás Erdős Pál - Surányi János: Válogatott fejezetek a számelméletből, Tankönyvkiadó Vállalat, Budapest 1960 könyvből való.A tétel alapvető jelentőségű a nyilvános kulcsú titkosítások számára.
A hivatkozott VI. és VII. tételeket, amelyeket a bizonyítás felhasznál itt nem bizonyítjuk, csak a kimondjuk. A tételek bizonyítása megtalálható a hivatkozott könyvben. (Kérdés, hogy a könyv hol található meg.)
Bizonyítás:
A bizonyítás abból fog állni, hogy megvizsgáljuk sorra
az a, 2a, ..., (p-1)a számok maradékát
p-vel való osztásnál: legyen
Egyik rk sem lehet nulla, mert k nem osztható p-vel, s így relatív prím hozzá, a-ra feltétel szerint ugyanaz áll, s így a VII. tétel szerint ka is relatív prím p-hez.
Az összes maradékok különböznek egymástól. Legyen ugyanis k1>k2 és vonjuk ki a k1-edik egyenletből a k2-ediket:
Itt a (k1-k2) szám p-nél kisebb pozitív egész, és így a bal oldal az előbbiekhez hasonló okoskodás szerint nem osztható p-vel, tehát rk1-rk2 sem lehet 0.
Az r1,r2,...,rp-1 számok tehát az 1,2,...,p-1 számok közül kerülnek ki, és nincs köztük két egyenlő. Ebből viszont az következik, hogy valamilyen sorrendben az 1,2,...,p-1 számok mindegyike előfordul közöttük. Szorozzuk össze most az egyenlőségeinket és vizsgáljuk meg a jobb oldalt. Itt, ha tagonként beszorzunk, az r1 r2 ... rp-1 tagon kívül csupa p-vel osztható tag keletkezik, e tag pedig utolsó megállapításunk szerint (p-1)!-sal egyenlő. Ilyen alakú egyenlőséget kapunk tehát:
ahol Q valamilyen egész szám. Ezt úgy is mondhatjuk, hogy
osztható p-vel. (p-1)! azonban relatív prím p-hez a VII. tétel értelmében, mert mindegyik tényezője relatív prím hozzá. Így a VI. tétel szerint ap-1-1 osztható p-vel, és ezt akartuk bizonyítani.