Mivel teljesül az e\cdot d\equiv 1\pmod{\varphi(m)} kongruencia, ezért a 20.1. Tétel 3. pontja alapján teljesül az alábbi oszthatóság:

\varphi(m)|e\cdot d-1

Az oszthatóság 16.1. Definíciója alapján ekkor létezik olyan k egész szám, amelyre teljesül az alábbi egyenlet:

k\cdot \varphi(m)=e\cdot d-1

Mindkét oldalhoz 1-et adva:

k\cdot \varphi(m) + 1=e\cdot d

Azt kell tehát bizonyítani, hogy tetszőleges x esetén teljesül az alábbi kongruencia:

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

Itt két eset lehetséges. Az első (és legvalószínűbb) esetben x relatív prím m-hez. Ekkor közvetlenül alkalmazható az Euler-Fermat tétel (20.19. Tétel). Ehhez alakítsuk át a kongruencia baloldalán álló kifejezést a 18.8. Tétel 2. és 3. pontjának megfelelően:

(x^{\varphi(m)})^k\cdot x\equiv x\pmod m

Az Euler-Fermat tétel miatt az x^{\varphi(m)} kifejezés 1-gyel kongruens modulo m. Így a 20.2. Tétel 5. és 8. pontja alapján a fenti kongruencia egyszerűsíthető:

\underbrace{1^k\cdot x}_{=x}\equiv x\pmod m

Ez a kongruencia viszont nyilvánvalóan teljesül a 20.2. Tétel 1. pontja alapján.

Most nézzük meg, hogy mi a helyzet abban a nem túl gyakori esetben, ha x NEM relatív prím m-hez, azaz x-nek és m-nek van egységtől különböző közös osztója. Mivel az m=pq modulusnak csak két prímtényezője van (p és q), ezért ez csak az alábbi három esetben fordulhat elő:

1. eset: Az x többszöröse p-nek is és q-nak is, azaz magának az m=pq modulusnak. Ilyenkor tehát teljesül az alábbi kongruencia:

x\equiv 0\pmod m

Ekkor a 20.2. Tétel 8. pontja alapján mindkét oldalt a k\cdot \varphi(m)+1-edik hatványra emelve teljesül az alábbi kongruencia is:

x^{k\cdot \varphi(m)+1}\equiv 0\pmod m

A két kongruenciát összevetve a 20.2. Tétel 2. és 3. pontjai alapján valóban teljesül a tétel állítása, azaz:

x^{k\cdot \varphi(m)+1}\equiv x\pmod m

2. eset: Az x többszöröse p-nek, de nem többszöröse q-nak. Azaz teljesül a p|x oszthatóság, de nem teljesül a q|x oszthatóság. Ebben az esetben a 21.4. Lemma alapján x relatív prím q-hoz. Mivel \varphi(m)=(p-1)\cdot (q-1), ezért teljesül az alábbi:

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

Felhasználva a hatványozás azonosságairól szóló 18.8. Tétel 2. és 3. pontját, ez a hatványkifejezés az alábbi alakba írható:

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

Mivel x relatív prím q-hoz, ezért a kis Fermat-tétel (22.1. Tétel) miatt teljesül az alábbi kongruencia:

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

A 20.2. Tétel 8. pontja alapján mindkét oldalt a k\cdot (p-1)-edik hatványra emelve továbbra is érvényes kongruenciát kapunk:

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

Így tehát a x^{k\cdot \varphi(m) +1} = (x^{q-1})^{k\cdot (p-1)}\cdot x kifejezésre teljesül az alábbi kongruencia:

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

Továbbá nyilván teljesül az alábbi kongruencia is, mivel x többszöröse p-nek, és így mindkét oldal 0-val kongruens modulo p:

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

3. eset: Az x többszöröse q-nak, de nem többszöröse p-nek. Azaz teljesül a q|x oszthatóság, de nem teljesül a p|x oszthatóság. Ebben az esetben az x egész szám q helyett p-hez lesz relatív prím. Ekkor az előző gondolatmenet szinte szóról szóra megismételhető, pusztán a p és q szerepét kell felcserélni.

Mivel ed=k\cdot \varphi(m)+1, ezért a 2. és 3. esetben is tulajdonképpen azt kaptuk, hogy teljesül az alábbi két kongruencia:

\begin{aligned}x^{ed}&\equiv x\pmod p \\ x^{ed}&\equiv x\pmod q\end{aligned}

Ez a \Z/p\Z és a \Z/q\Z maradékosztálygyűrűkben az alábbiakat jelenti:

\begin{aligned}[x^{ed}]_p &= [x]_p \\ [x^{ed}]_q &= [x]_q\end{aligned}

Ennek megfelelően ezt így írhatjuk fel a \Z/p\Z \times \Z/q\Z direkt szorzat egy elemeként:

([x^{ed}]_p; [x^{ed}]_q) = ([x]_p; [x]_q)

A 22.4. Tétel és a 22.5. Tétel alapján azonban tudjuk, hogy a \Z/p\Z \times \Z/q\Z elemei kölcsönösen egyértelműen megfeleltethetők a \Z/pq\Z maradékosztálygyűrű elemeivel. Ez a leképezés a fenti egyenlet bal és jobboldalához a 22.5. Tételben szereplő képlet alapján az alábbiakat rendeli hozzá:

\begin{aligned}([x^{ed}]_p; [x^{ed}]_q) &\to [x^{ed}]_{pq} \\ ([x]_p; [x]_q) &\to [x]_{pq}\end{aligned}

Mármost ha itt a nyilak baloldalán álló objektumok megegyeznek, akkor a leképezés kölcsönösen egyértelműsége miatt a nyilak jobboldalán álló objektumok is meg kell egyezzenek, azaz:

[x^{ed}]_{pq}=[x]_{pq}

Ugyanezt kongruenciával megfogalmazva megkapjuk a tétel állítását:

x^{ed}\equiv x\pmod{\underbrace{pq}_{=m}}