Először a Carmichael-számok paritására vonatkozó állítást igazoljuk.

Legyen n tetszőleges Carmichael-szám. Az n és az n-1 egész számok egymáshoz relatív prímek. Ugyanis bármilyen közös osztó a 16.2. Tétel 6. pontja alapján osztója e két szám különbségének, azaz 1-nek, és így a 16.5. Tétel miatt ez a közös osztó csak egység lehet. Így tehát az [n-1]_n egy redukált maradékosztály, és mivel n Carmichael-szám, ezért ez a maradékosztály a 23.7. Definíció alapján biztosan nem Fermat-tanú. Azaz a 23.3. Definíció értelmében teljesül az alábbi kongruencia:

(n-1)^{n-1}\equiv 1\pmod n

Az n-1\equiv -1\pmod n kongruencia nyilván teljesül, ezért a fenti kongruenciát a 20.2. Tétel 8. pontja alapján a következőképpen írhatjuk át:

(-1)^{n-1}\equiv 1\pmod n

Azt viszont tudjuk, hogy a -1 bármilyen hatványa +1 vagy -1 attól függően, hogy a kitevő páros vagy páratlan. Tegyük fel indirekt, hogy jelen esetben n-1 páratlan. Ekkor a fenti kongruencia így néz ki:

-1\equiv 1\pmod n

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

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

Ez viszont lehetetlen, hiszen n Carmichael-szám, emiatt pozitív és összetett, következésképp biztosan nagyobb 2-nél, vagyis nem lehet osztója neki. Indirekt feltevésünk, miszerint n-1 páratlan hibás volt, azaz n-1 páros, és így n valóban páratlan.

Most igazoljuk a Carmichael-számok prímtényezőire vonatkozó állítást.

Legyen n továbbra is tetszőleges Carmichael-szám, de tegyük fel indirekt, hogy neki csak két prímtényezője van, azaz felírható n=pq alakban valamilyen alkalmasan választott p és q prímszámokkal. A Korselt-kritérium (26.17. Tétel) alapján n négyzetmentes, így e két prímtényező biztosan különbözik egymástól, azaz p\neq q. Ezenkívül az általánosság megsértése nélkül feltehetjük, hogy p\gt q, hiszen ha nem így lenne, akkor szerepük felcserélésével az alábbi gondolatmenet ugyanígy végigjátszható. Továbbá azt is feltehetjük, hogy mindkét prímtényező pozitív. Ha ugyanis nem így lenne, akkor az ő ellentettjükre ez már teljesül – hiszen n Carmichael-szám, és így pozitív –, és az alábbi gondolatmenetet rájuk alkalmazhatjuk.

Szintén a Korselt-kritérium (26.17. Tétel) alapján tudjuk, hogy teljesül az alábbi oszthatóság:

p-1|n-1

Azaz létezik olyan k egész szám, amelyre teljesül az alábbi egyenlet:

(p-1)\cdot k=n-1

Mivel azt feltételeztük, hogy n=pq, ezért ez így is írható:

(p-1)\cdot k=\underbrace{pq}_{=n}-1

A jobboldal értéke nem változik, ha hozzá is adunk q-t és le is vonunk belőle q-t:

(p-1)\cdot k=pq-q+q-1

A 14.12. Definícióban szereplő disztributivitási szabályok alapján ez így is írható:

(p-1)\cdot k=(p-1)\cdot q+q-1

Mindkét oldalból levonhatunk (p-1)q-t:

(p-1)\cdot k - (p-1)\cdot q=q-1

Most a baloldalra alkalmazhatjuk a disztributivitási szabályt:

(p-1)\cdot (k-q)=q-1

Azt kaptuk tehát, hogy létezik olyan egész szám – nevezetesen a k-q – amellyel p-1-et megszorozva q-1-et kapunk. Teljesül tehát az alábbi oszthatóság:

p-1|q-1

Mivel q egy pozitív prím, így q-1 is pozitív, ezért a 17.2. Lemma alapján ő legalább akkora, mint bármely osztója, azaz:

p-1\leq q-1

A 15.11. Definícióban szereplő 1. rendezési axióma alapján mindkét oldalhoz 1-et adva ezt kapjuk:

p\leq q

Ez viszont ellentmondás, hiszen azt feltételeztük, hogy p\gt q. Ugyanilyen gondolatmenet alapján p\lt q-ból p\geq q következne, ami szintén ellentmondás. Indirekt feltételezésünk tehát hibás volt, és így n biztosan nem írható fel pq alakban, azaz szükségképpen valóban legalább 3 prímtényezője kell legyen.