A d titkos kitevőt tehát alábbi lineáris kongruencia megoldásaként kapjuk:

e\cdot x\equiv 1\pmod{(p-1)\cdot (q-1)}

Ennek a kongruenciának a 20.12. Tétel alapján természetesen létezik megoldása, amely a 20.13. Tétel 1. pontja szerint egyértelmű.

A továbbiakban azt szeretnénk igazolni, hogy tetszőleges x egész szám esetén teljesül az alábbi kongruencia:

x^{e\cdot d}\equiv x\pmod m

A 22.6. Tétel bizonyításának gondolatmenetét követve az e\cdot d\equiv 1\pmod{(p-1)\cdot (q-1)} kongruenciából következik, hogy létezik olyan k egész szám, amelyre teljesül az alábbi:

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

A fenti bizonyítandó kongruencia tehát így is írható:

x^{\overbrace{k\cdot (p-1)\cdot (q-1)+1}^{=ed}}\equiv x\pmod m

Legyen most r az m modulus egy tetszőleges pozitív prímosztója. Mivel p és q relatív prímek és m=pq, ezért r biztosan osztója p és q közül pontosan az egyiknek. Az általánosság megsértése nélkül feltehetjük, hogy p-nek osztója, máskülönben az alábbi gondolatmenet ugyanígy működik p és q szerepének felcserélésével. Ekkor az alábbi két eset lehetséges:

• Ha p prím, akkor r=p, és így r-1=p-1, azaz r-1|p-1.
• Ha p Carmichael-szám, akkor r|p, és így a Korselt-kritérium miatt r-1|p-1.

Mindkét esetben azt kaptuk tehát, hogy teljesül az r-1|p-1 oszthatóság, azaz létezik olyan egész szám, amivel r-1-et megszorozva p-1-et kapunk. Jelöljük ezt az egész számot \frac{p-1}{r-1}-gyel.

A kis Fermat-tételből (22.1. Tétel) tudjuk, hogy bármilyen r-hez relatív prím x egész szám esetén teljesül az alábbi kogruencia:

x^{r-1}\equiv 1\pmod r

Ekkor tetszőleges n pozitív egész esetén a 20.2. Tétel 8. pontja alapján teljesül az alábbi kongruencia is:

x^{n\cdot (r-1)}\equiv 1\pmod r

Szorozzuk meg mindkét oldalt x-szel:

x^{n\cdot (r-1) + 1}\equiv x\pmod r

Vegyük észre, hogy ez a kongruencia már abban az esetben is teljesül, ha x nem relatív prím r-hez. Ilyenkor ugyanis x szükségképpen többszöröse r-nek – hiszen r ugye prím –, vagyis a kongruencia mindkét oldalán 0 áll ebben az esetben. Ha tehát ez a kongruencia minden x-re és minden pozitív egész n-re teljesül, akkor nyilván teljesül az alábbi speciális eseben is:

n=k\cdot \frac{p-1}{r-1}\cdot (q-1)

Ez egy egész szám, méghozzá a korábban már igazolt r-1|p-1 oszthatóság miatt. Ezt behelyettesítve a fenti kongruencia kitevőjébe az alábbit kapjuk:

x^{\overbrace{k\cdot \frac{p-1}{r-1}\cdot (q-1)}^{=n}\cdot (r-1) + 1}\equiv x\pmod r

Elvégezve a kitevőben lévő r-1-gyel való szorzást az alábbi kongruenciát kapjuk:

x^{k\cdot (p-1)\cdot (q-1) + 1}\equiv x\pmod r

Ez tehát az m modulus minden pozitív r prímosztójára teljesül, ami viszont azt jelenti, hogy a 20.1. Tétel 3. pontja alapján teljesül az alábbi oszthatóság:

r|x^{k\cdot (p-1)\cdot (q-1)+1}-x

Felhívnánk a figyelmet arra, hogy az m=pq modulus négyzetmentes. Ennek egyrészt az az oka, hogy p és q nem tartalmaznak közös prímtényezőket, hiszen azt mondtuk, hogy egymáshoz relatív prímek. Másrészt pedig mindkettőre igaz, hogy vagy prím, vagy pedig Carmichael-szám, márpedig egy prím nyilvánvalóan, egy Carmichael-szám pedig a Korselt-kritérium (26.17. Tétel) miatt négyzetmentes, így a relatív prímség miatt ezek szorzata is az, vagyis a 26.16. Lemma alapján m minden prímtényezője első hatványon szerepel.

Mármost ha m minden prímtényezőjére teljesül a fenti oszthatóság, akkor ezek szorzatára is teljesül. Mivel mindegyikük első hatványon szerepel m prímtényezős felbontásában, ezért ez a szorzat m-mel egyezik meg. Vagyis teljesül az alábbi oszthatóság is:

m|x^{k\cdot (p-1)\cdot (q-1)+1}-x

Ez viszont ismét a 20.1. Tétel 3. pontja alapján azt jelenti, hogy a bizonyítandó kongruencia is teljesül:

x^{k\cdot (p-1)\cdot (q-1)+1}\equiv x\pmod m