youproof.orgDeep Math. Human Access.

Bizonyítás

Mivel teljesül az ed≡1(modφ(m))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:

φ(m)∣ed−1\varphi(m)|ed-1

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

kφ(m)=ed−1k\varphi(m)=ed-1

Mindkét oldalhoz 11-et adva:

kφ(m)+1=edk\varphi(m) + 1=ed

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

xkφ(m)+1⏞=ed≡x(modm)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 xx relatív prím mm-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φ(m))k⋅x≡x(modm)(x^{\varphi(m)})^k\cdot x\equiv x\pmod m

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

1k⋅x⏟=x≡x(modm)\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 xx nem relatív prím az m=pqm=pq modulushoz, azaz xx-nek és mm-nek van egységtől különböző közös osztója. Ekkor a p∣xp|x és a q∣xq|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 xx relatív prím lenne pp-hez is és qq-hoz is, és a 20.12. Következmény miatt az m=pqm=pq modulushoz is, ami ellentmondás. A p∣xp|x és q∣xq|x oszthatóságok tekintetében tehát az alábbi három eset lehetséges:

1. eset: p∣xp|x és q∣xq|x

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

x≡0(modp)x≡0(modq)\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φ(m)+1k\varphi(m)+1-edik hatványra emelve teljesülnek az alábbi kongruenciák is:

xkφ(m)+1≡0(modp)xkφ(m)+1≡0(modq)\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:

xkφ(m)+1≡x(modp)xkφ(m)+1≡x(modq)\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∣xp|x és q∤xq\nmid x

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

xkφ(m)+1≡x(modp)x^{k\varphi(m) +1}\equiv x\pmod p

Továbbá mivel φ(m)=(p−1)(q−1)\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:

xkφ(m)+1=xk(p−1)(q−1)⏞=φ(m)+1=(xq−1)k(p−1)⋅xx^{k\varphi(m)+1}=x^{k\overbrace{(p-1)(q-1)}^{=\varphi(m)} + 1}=(x^{q-1})^{k(p-1)}\cdot x

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

xq−1≡1(modq)x^{q-1}\equiv 1\pmod q

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

(xq−1)k(p−1)⋅x≡x(modq)(x^{q-1})^{k(p-1)}\cdot x\equiv x\pmod q

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

xkφ(m)+1≡x(modq)x^{k\varphi(m)+1}\equiv x\pmod q
3. eset: p∤xp\nmid x és q∣xq|x

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

xkφ(m)+1≡x(modp)xkφ(m)+1≡x(modq)\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φ(m)+1ed=k\varphi(m)+1, ezért mindhárom esetben végülis azt kaptuk, hogy teljesül az alábbi két kongruencia:

xed≡x(modp)xed≡x(modq)\begin{aligned} x^{ed}&\equiv x\pmod p \\ x^{ed}&\equiv x\pmod q \end{aligned}

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

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

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

([xed]p;[xed]q)=([x]p;[x]q)([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/pZ×Z/qZ\Z/p\Z \times \Z/q\Z direkt szorzat elemei kölcsönösen egyértelműen megfeleltethetők a Z/pqZ\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 pqpq maradékosztályokat rendeli hozzá:

([xed]p;[xed]q)→[xed]pq([x]p;[x]q)→[x]pq\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:

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

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

xed≡x(modpq⏟=m)x^{ed}\equiv x\pmod{\underbrace{pq}_{=m}}

∎