Elsőként azt mutatjuk meg, hogy ha n Carmichael-szám, akkor teljesíti a fenti két kritériumot. Először igazoljuk, hogy n négyzetmentes, ami a 26.16. Lemma alapján azt jelenti, hogy nem létezik olyan pozitív prímosztója, amelynek a négyzetével is osztható. Tegyük fel indirekt, hogy nem ez a helyzet, azaz p egy olyan galád pozitív prímosztó, amelynek a négyzete szintén n osztója. Ezt a 24.15. Definíció alapján úgy is mondhatjuk, hogy az n egész szám p-adikus rendje legalább 2. Azaz:

\begin{aligned}v_p(n)&=k \\ k&\geq 2\end{aligned}

Ez azt jelenti, hogy n felírható az alábbi alakban, ahol m tovább már nem osztható p-vel:

n=p^km

Mivel p prím, ezért az, hogy m nem osztható p-vel egyben azt is jelenti, hogy p^k és m relatív prímek, azaz (p^k,m)=1. Ekkor érvényes a kínai maradéktétel (22.2. Tétel), amelynek következményeként a 22.8. Tétel alapján fennáll az alábbi gyűrűizomorfizmus:

\Z/n\Z \simeq \Z/p^k\Z \times \Z/m\Z

Következésképp egyértelműen létezik olyan X maradékosztály a baloldali maradékosztálygyűrűben, amelyhez a 22.8. Tételben szereplő g gyűrűizomorfizmus az ([1+p]_{p^k};[1]_m) maradékosztálypárt rendeli hozzá a jobboldali szorzatgyűrűből. Legyen a ennek az X maradékosztálynak egy reprezentánseleme. Ekkor tehát az említett g gyűrűizomorfizmus az alábbi hozzárendelést valósítja meg:

[a]_n \xmapsto{g} (\underbrace{[1+p]_{p^k}}_{=[a]_{p^k}};\underbrace{[1]_m}_{=[a]_m})

Azaz fennállnak a jobboldalon szereplő maradékosztályok közötti alábbi egyenlőségek:

\begin{aligned}[a]_{p^k}&=[1+p]_{p^k} \\ [a]_m&=[1]_m\end{aligned}

A második egyenlőségből a 20.14. Tétel alapján következik, hogy a relatív prím m-hez. Az [a]_m=[1]_m maradékosztály ugyanis nyilván invertálható a \Z/m\Z gyűrűben, hiszen ő ennek a gyűrűnek az egységeleme, amelynek inverze önmaga. Az első egyenlőségből szintén a 20.14. Tétel alapján következik, hogy a pontosan akkor relatív prím p^k-hoz, ha 1+p is az, hiszen ők ugyanannak a modulo p^k maradékosztálynak a reprezentánselemei. Ez viszont nyilván teljesül, hiszen 1+p biztosan nem osztható p-vel, így annak semmilyen hatványával sem. Azt kaptuk tehát, hogy a-nak nincs közös prímtényezője sem m-mel, sem pedig p^k-val is, következésképp az ő szorzatukkal, azaz n-nel sem. Az a egész szám tehát relatív prím n-hez, azaz a 20.14. Tétel alapján [a]_n egy redukált maradékosztály.

Ugye n-ről most tudjuk, hogy Carmichael-szám, ami a 23.7. Definíció alapján azt jelenti, hogy egyetlen redukált maradékosztály sem lehet Fermat-tanú, ezért nyilván a most megkonstruált [a]_n sem az. Azaz a Fermat-tanúkra vonatkozó 23.3. Definíció alapján teljesül az alábbi kongruencia:

a^{n-1}\equiv 1\pmod n

Mivel azonban n=p^km, ezért nyilván teljesül a p^k|n oszthatóság, és így a 20.2. Tétel 9. pontja alapján az alábbi kongruencia is:

a^{n-1}\equiv 1\pmod{p^k}

Az a egész számot viszont úgy választottuk ki, hogy kongruens legyen 1+p-vel modulo p^k, ezért a 20.2. Tétel 8. pontja alapján teljesül az alábbi kongruencia is:

(1+p)^{n-1}\equiv 1\pmod{p^k}

Viszont indirekt feltételezésünk szerint a k kitevő legalább 2, és így teljesül a p^2|p^k oszthatóság, és így a 20.2. Tétel 9. pontja miatt az alábbi kongruencia is:

(1+p)^{n-1}\equiv 1\pmod{p^2}

A kongruencia baloldalán tehát egy olyan n-1 tényezős szorzat szerepel, amelynek minden tényezője 1+p:

(1+p)^{n-1}=\underbrace{(1+p)\cdot (1+p)\cdot \ldots \cdot (1+p)}_{\text{(n-1) darab}}

A 24.16. Lemma bizonyításának gondolatmenetéhez hasonlóan a 14.12. Definícióban szereplő disztributivitási szabályok alapján ezt az n-1 darab zárójelet úgy kell felbontani, hogy minden zárójelből az összes lehetséges kombinációban kiválasztunk pontosan egy tagot, ezeket összeszorozzuk egymással, és az így kapott szorzatokat összeadjuk. Így az alábbi tagok keletkeznek valamilyen A_0, A_1, A_2, …, A_{n-1} szorzó tényezőkkel attól függően, hogy melyik kombinációt hányféleképpen lehet előállítani az n-1 darab zárójelből:

\begin{aligned}(1+p)^{n-1} &= A_0\cdot 1^{n-1}\cdot p^0 \\ &+ A_1\cdot 1^{n-2}\cdot p^1 \\ &+ A_2\cdot 1^{n-3}\cdot p^2 \\ &+ A_3\cdot 1^{n-4}\cdot p^3 \\ &\vdots \\ &+ A_{n-1}\cdot 1^0\cdot p^{n-1}\end{aligned}

Itt az A_0 együttható nyilván 1 lesz, hiszen egyféleképpen lehet kiválasztani mind az n-1 darab zárójelből az 1 tagot. Ehhez hasonló okok miatt az A_1 együttható n-1 lesz, hiszen n-1-féleképpen lehet kiválasztani az n-1 darab zárójelből azt az egyet, amiből a p tagot vesszük az adott szorzathoz. A zárójelek felbontása után kapott kifejezés tehát így néz ki:

(1+p)^{n-1} = \underbrace{1}_{=A_0}p^0 + \underbrace{(n-1)}_{=A_1}p^1 + A_2p^2 + A_3p^3 + \ldots + A_{n-1}p^{n-1}

Mivel minket ennek a kifejezésnek az értéke modulo p^2 érdekel minket, ezért nincs szükségünk az A_2, A_3, …, A_{n-1} együtthatók pontos értékére – amelyeket egyébként a binomiális tétel alapján lehetne kiszámítani. Vegyük ugyanis észre, hogy a 3. tagtól kezdve minden tag osztható p^2-tel, vagy másként fogalmazva 0-val kongruens modulo p^2. Így az alábbi kongruenciát kapjuk:

(1+p)^{n-1}\equiv 1+(n-1)p\pmod{p^2}

A baloldalon szereplő (1+p)^{n-1} már megmutattuk, hogy 1-gyel kongruens modulo p^2, emiatt a jobboldal is, azaz:

1\equiv 1+(n-1)p\pmod{p^2}

Mivel n osztható p-vel (hiszen egy prímtényezőjéről van szó), így felírható n=t\cdot p alakban valamilyen alkalmasan választott t egész számmal:

1\equiv 1+(\underbrace{tp}_{=n}-1)p\pmod{p^2}

A jobboldalon szereplő zárójelet felbontva az alábbi adódik:

1\equiv 1+\underbrace{tp^2}_{\equiv 0}-p\pmod{p^2}

A középső tp^2 tag osztható p^2-tel, azaz 0-val kongruens modulo p^2, így az elhagyható a jobboldalról:

1\equiv 1-p\pmod{p^2}

Ez viszont a 20.1. Tétel 3. pontja alapján azt jelentené, hogy teljesül az alábbi oszthatóság:

p^2|\underbrace{1-(1-p)}_{=p}

Ez egyértelmű ellentmondás, ami az indirekt feltételezésünkből következne, ha igaz volna. Nem igaz tehát, hogy n osztható p^2-tel, vagy ugyanezen gondolatmenet alapján bármely más prímosztó négyzetével. Következésképp n valóban négyzetmentes.

Most a p-1|n-1 oszthatóságot igazoljuk. Legyen p továbbra is n tetszőleges pozitív prímtényezője. Az előzőekben tehát beláttuk, hogy az n egész szám p-adikus rendje 1, azaz n felírható az alábbi alakban, ahol m tovább már nem osztható p-vel:

n=pm

Mivel p prím, ezért az, hogy m nem osztható p-vel egyben azt is jelenti, hogy p és m relatív prímek, azaz (p,m)=1. Ismét érvényes tehát a kínai maradéktétel (22.2. Tétel), így a 22.8. Tétel alapján fennáll az alábbi gyűrűizomorfizmus:

\Z/n\Z \simeq \Z/p\Z \times \Z/m\Z

Tekintsük most a jobboldalon szereplő \Z/p\Z gyűrű multiplikatív csoportját, azaz a (\Z/p\Z)^{\times} csoportot. Ez a \Z/p\Z gyűrű invertálható elemeiből áll, amelyek épp a modulo p redukált maradékosztályok. Ezek számát a 20.7. Definíció alapján az Euler-féle \varphi-függvény adja meg. Mivel p prím, ezért ez a 21.5. Tétel alapján jelen esetben épp p-1, ami tehát a (\Z/p\Z)^{\times} multiplikatív csoport rendje.

A 26.14. Tétel alapján a (\Z/p\Z)^{\times} csoportban létezik primitív gyök, hiszen p prím. Azaz a 26.1. Definíció utáni megjegyzés szerint létezik olyan b egész szám, hogy az általa reprezentált [b]_p redukált maradékosztály rendje épp megegyezik a csoport rendjével, azaz:

o([b]_p)=p-1

A fennálló gyűrűizomorfizmus miatt létezik olyan X maradékosztály a \Z/n\Z gyűrűben, amelyhez a 22.8. Tételben szereplő g gyűrűizomorfizmus a ([b]_p;[1]_m) maradékosztálypárt rendeli hozzá a \Z/p\Z \times \Z/m\Z szorzatgyűrűből. Legyen a ennek az X maradékosztálynak egy reprezentánseleme. Ekkor a g gyűrűizomorfizmus az alábbi hozzárendelést valósítja meg:

[a]_n \xmapsto{g} (\underbrace{[b]_p}_{=[a]_p};\underbrace{[1]_m}_{=[a]_m})

Azaz fennállnak a jobboldalon szereplő maradékosztályok közötti alábbi egyenlőségek:

\begin{aligned}[a]_p&=[b]_p \\ [a]_m&=[1]_m\end{aligned}

Az a egész szám tehát egyrészt relatív prím m-hez, mivel az általa reprezentált maradékosztály nyilván redukált, hiszen a \Z/m\Z maradékosztálygyűrű egységeleméről van szó. Másrészt relatív prím p-hez is, ugyanis a vele azonos modulo p maradékosztályban lévő b is az, hiszen ez a maradékosztály a (\Z/p\Z)^{\times} multiplikatív csoport egy eleme (konkrétan az egyik primitív gyök), azaz redukált maradékosztály. Következésképp a az n=pm szorzathoz is relatív prím, azaz (a,n)=1, és így [a]_n szintén redukált maradékosztály a \Z/n\Z gyűrűben.

Mivel azonban n ugye Carmichael-szám, ezért a 23.7. Definíció alapján [a]_n biztosan nem Fermat-tanú, azaz teljesül az alábbi kongruencia:

a^{n-1}\equiv 1\pmod n

A 20.5. Tétel alapján a maradékosztályok közötti szorzást – és így a hatványozást is – a reprezentánselemeken kell végrehajtani. Ezért a fenti kongruencia baloldalán épp az [a]_n maradékosztály n-1-edik hatványának reprezentánseleme áll, amely hatvány tehát nem más, mint az [1]_n maradékosztály. Ám ekkor művelettartó tulajdonsága alapján a fenti g gyűrűizomorfizmus az alábbi hozzárendelést valósítja meg:

\underbrace{[a]^{n-1}_n}_{=[1]_n} \xmapsto{g} ([b]_p;[1]_m)^{n-1}

A 22.7. Tétel alapján a jobboldali szorzatgyűrűben a hatványozást komponensenként kell végrehajtani, így valójában az alábbi hozzárendelésről van szó:

[1]_n \xmapsto{g} (\underbrace{[b]^{n-1}_p}_{=[1]_p};[1]_m)

A jobboldal alapján tehát a \Z/p\Z maradékosztálygyűrűben fennáll az alábbi, maradékosztályok közötti egyenlőség:

[b]^{n-1}_p= [1]_p

Minthogy [b]_p a (\Z/p\Z)^{\times} multiplikatív csoport egy eleme, amely csoportnak [1]_p épp a neutrális eleme, ezért a 24.12. Tétel 2. pontja alapján teljesül az alábbi oszthatóság:

o([b]_p)|n-1

Azt azonban már korábban láttuk, hogy [b]_p rendje épp p-1, azaz valóban teljesül a p-1|n-1 oszthatóság n bármely pozitív p prímtényezőjére.

Végezetül megmutatjuk, hogy ha egy összetett számra teljesülnek a tételben szereplő kritériumok, akkor ő szükségképpen Carmichael-szám. Legyen ezért n tetszőleges összetett szám, amely négyzetmentes, és tegyük fel, hogy bármely pozitív p prímtényezőjére teljesül a p-1|n-1 oszthatóság. Válasszunk egy tetszőleges a egész számot, amely relatív prím n-hez. Mivel p az n egy prímtényezője, ezért a relatív prím p-hez is. Ekkor a kis Fermat-tétel alapján (22.1. Tétel) teljesül az alábbi kongruencia:

a^{p-1}\equiv 1\pmod p

A feltételünk szerint azonban most fennáll a p-1|n-1 oszthatóság, azaz létezik olyan t egész szám, amelyre teljesül az alábbi:

(p-1)t=n-1

A fenti kongruencia mindkét oldalát a t-edik hatványra emelve ezt kapjuk:

(a^{p-1})^t\equiv 1^t\pmod p

A hatványozás azonosságairól szóló 18.8. Tétel 2. pontja alapján tehát:

a^{\overbrace{n-1}^{=(p-1)t}}\equiv 1\pmod p

Ez a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesül az alábbi oszthatóság:

p|a^{n-1}-1

Azt kaptuk tehát, hogy az n egész szám tetszőleges pozitív prímtényezőjére igaz, hogy ő az a^{n-1}-1 egész számnak is prímtényezője. Tekintsük most n egy olyan prímtényezős felbontását, amelyben minden tényező pozitív (ilyen nyilván létezik, hiszen maga n is pozitív):

n=p_1\cdot p_2\cdot p_3\cdot \ldots \cdot p_r

A fenti gondolatmenet alapján eszerint a p_1, p_2, …, p_r prímek mind az a^{n-1}-1 egész szám pozitív prímtényezői. Minthogy n-ről azt mondtuk, hogy négyzetmentes, ezért ezek a prímtényezők páronként különbözőek. Emiatt végülis az ő szorzatuk – azaz maga n – szintén osztója az a^{n-1}-1 egész számnak:

\underbrace{p_1\cdot p_2\cdot p_3\cdot \ldots \cdot p_r}_{=n}|a^{n-1}-1

Ez a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesül az alábbi kongruencia:

a^{n-1}\equiv 1\pmod n

Így tehát semmilyen tetszőlegesen választott [a]_n redukált maradékosztály nem lehet Fermat-tanú, azaz a 23.7. Definíció alapján az n összetett szám valóban Carmichael-szám.