youproof.orgDeep Math. Human Access.

Bizonyítás

Mivel teljesül az ed\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)|ed-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\varphi(m)=ed-1

Mindkét oldalhoz 1-et adva:

k\varphi(m) + 1=ed

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

x^{\overbrace{k\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. Ehhez alakítsuk át a kongruencia baloldalán álló kifejezést a 18.8. Tétel 2. és 3. pontjainak 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 6. és 5. pontjai 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 az m=pq modulushoz, azaz x-nek és m-nek van egységtől különböző közös osztója. Ekkor a p|x és a q|x oszthatóságok közül legalább az egyik teljesül. Ha ugyanis egyik sem teljesülne, akkor a 21.4. Lemma alapján x relatív prím lenne p-hez is és q-hoz is, és a 20.12. Következmény miatt az m=pq modulushoz is, ami ellentmondás. A p|x és q|x oszthatóságok tekintetében tehát az alábbi három eset lehetséges:

1. eset: p|x és q|x

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

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

Ekkor a 20.2. Tétel 6. pontja alapján e kongruenciák mindkét oldalát a k\varphi(m)+1-edik hatványra emelve teljesülnek az alábbi kongruenciák is:

\begin{aligned} x^{k\varphi(m)+1}&\equiv 0\pmod p \\ x^{k\varphi(m)+1}&\equiv 0\pmod q \end{aligned}

A két-két kongruenciát összevetve a 20.2. Tétel 2. és 3. pontja alapján az alábbi kongruenciákat kapjuk:

\begin{aligned} x^{k\varphi(m)+1}&\equiv x\pmod p \\ x^{k\varphi(m)+1}&\equiv x\pmod q \end{aligned}
2. eset: p|x és q\nmid x

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

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

Továbbá mivel \varphi(m)=(p-1)(q-1), ezért teljesül az alábbi – itt a második lépésben felhasználtuk a hatványozás azonosságairól szóló a 18.8. Tételt:

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

Mivel q\nmid x, ezért a 21.4. Lemma alapján x relatív prím q-hoz, és így alkalmazható a kis Fermat-tétel, amely szerint tehát teljesül az alábbi kongruencia:

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

A 20.2. Tétel 6. pontja alapján mindkét oldalt a k(p-1)-edik hatványra emelve, valamint a 20.2. Tétel 5. pontja alapján mindkét oldalt x-szel megszorozva továbbra is érvényes kongruenciát kapunk:

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

De mivel x^{k\varphi(m)+1} = (x^{q-1})^{k(p-1)}\cdot x, ezért teljesül az alábbi kongruencia:

x^{k\varphi(m)+1}\equiv x\pmod q
3. eset: p\nmid x és q|x

Ebben az esetben az x egész szám q helyett p-hez lesz relatív prím, tehát az előző gondolatmenetet szinte szóról szóra meg lehet ismételni, csak p és q szerepét fel kell cserélni. Ekkor is azt fogjuk kapni, hogy teljesülnek az alábbi kongruenciák:

\begin{aligned} x^{k\varphi(m)+1}&\equiv x\pmod p \\ x^{k\varphi(m)+1}&\equiv x\pmod q \end{aligned}

Mivel ugye ed=k\varphi(m)+1, ezért mindhárom esetben végülis 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.3. és a 22.4. Tétel alapján azonban tudjuk, hogy a \Z/p\Z \times \Z/q\Z direkt szorzat elemei kölcsönösen egyértelműen megfeleltethetők a \Z/pq\Z maradékosztálygyűrű elemeivel. Ez a leképezés az iménti egyenlet bal és jobboldalához a 22.4. Tételben szereplő képlet alapján az alábbi modulo pq maradékosztályokat 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}}

∎