youproof.orgDeep Math. Human Access.

Bizonyítás

Azt kell megmutatni, hogy a  mod m\bmod_m függvény tartja az eredeti Z\Z gyűrű mindkét műveletét. Nézzük először az összeadást, amelyet a Z\Z gyűrű esetén a ++, míg a ZmZ_m gyűrű esetén a ⊕\oplus szimbólummal fogjuk jelölni. Az alábbi összefüggést kell tehát igazolni:

 mod m(a+b)= mod m(a)⊕ mod m(b)\bmod_m(a+b)=\bmod_m(a)\oplus \bmod_m(b)

Fejtsük ki mindkét oldalt a 18.3. Definíció alapján. A bal- és jobboldalon képződő maradékokat jelöljük rr-rel, q1q_1-gyel, q2q_2-vel és q3q_3-mal:

 mod m(a+b)=r mod m(a)⏟=q1⊕ mod m(b)⏟=q2= mod m(q1+q2)=q3\begin{aligned} \bmod_m(a+b)&=r \\ \underbrace{\bmod_m(a)}_{=q_1}\oplus \underbrace{\bmod_m(b)}_{=q_2}&=\bmod_m(q_1+q_2)=q_3 \end{aligned}

Azt kell megmutatnunk, hogy r=q3r=q_3, azaz mindegy, hogy melyik gyűrűben végezzük el az összeadást, a végeredmény ugyanaz lesz. A  mod m\bmod_m függvény szerinti maradékos osztásokat elvégezve négy egyenletet írhatunk fel az rr, q1q_1, q2q_2 és q3q_3 maradékokra valamilyen kk, n1n_1, n2n_2 és n3n_3 hányadosokkal:

a+b=km+ra=n1m+q1b=n2m+q2q1+q2=n3m+q3\begin{aligned} a+b&=km+r \\ a&=n_1m+q_1 \\ b&=n_2m+q_2 \\ q_1+q_2&=n_3m+q_3 \end{aligned}

Az első egyenletből kifejezhetjük rr-et, amely a  mod m(a+b)\bmod_m(a+b) maradékképzés eredménye:

r=a+b−kmr=a+b-km

A második és harmadik egyenletből kifejezhetjük q1q_1-et és q2q_2-t, amely a  mod m(a)⊕ mod m(b)\bmod_m(a)\oplus \bmod_m(b) moduláris összeadás két tagját fogja adni:

q1=a−n1mq2=b−n2m\begin{aligned} q_1&=a-n_1m \\ q_2&=b-n_2m \end{aligned}

Ezeket behelyettesítve a negyedik egyenletbe ezt kapjuk:

a−n1m⏟=q1+b−n2m⏟=q2=n3m+q3\underbrace{a-n_1m}_{=q_1}+\underbrace{b-n_2m}_{=q_2}=n_3m+q_3

Ezt átrendezve megkapjuk q3q_3-at:

q3=a−n1m+b−n2m−n3mq_3=a-n_1m+b-n_2m-n_3m

Azt kell tehát igazolnunk, hogy rr és q3q_3 valójában megegyeznek. Ehhez írjuk fel kettejük különbségét:

r−q3=a+b−km⏞r−a+n1m−b+n2m+n3m⏞−q3==(n1+n2+n3−k)⋅m\begin{aligned} r-q_3&=\overbrace{\bcancel{a}+\bcancel{b}-km}^{r}\overbrace{-\bcancel{a}+n_1m-\bcancel{b}+n_2m+n_3m}^{-q_3}= \\ &=(n_1+n_2+n_3-k)\cdot m \end{aligned}

Azt kaptuk tehát, hogy teljesül az m∣r−q3m|r-q_3 oszthatóság. Mivel rr és q3q_3 nemnegatív maradékok, így alkalmazható rájuk a 18.1. Lemma, amiből r=q3r=q_3 következik. A  mod m\bmod_m függvény tehát valóban tartja az összeadást.

Most a szorzást ellenőrizzük nagyjából ugyanezzel a módszerrel. A Z\Z gyűrű esetén a ⋅\cdot, míg a ZmZ_m gyűrű esetén a ⊙\odot szimbólummal fogjuk jelölni ezt a műveletet. Az alábbi összefüggést kell tehát igazolni:

 mod m(a⋅b)= mod m(a)⊙ mod m(b)\bmod_m(a\cdot b)=\bmod_m(a)\odot \bmod_m(b)

Ismét fejtsük ki mindkét oldalt a 18.3. Definíció alapján. A kapott maradékokat jelöljük rr-rel, q1q_1-gyel, q2q_2-vel és q3q_3-mal:

 mod m(a⋅b)=r mod m(a)⏟=q1⊙ mod m(b)⏟=q2= mod m(q1⋅q2)=q3\begin{aligned} \bmod_m(a\cdot b)&=r \\ \underbrace{\bmod_m(a)}_{=q_1}\odot \underbrace{\bmod_m(b)}_{=q_2}&=\bmod_m(q_1\cdot q_2)=q_3 \end{aligned}

Azt kell megmutatnunk, hogy r=q3r=q_3, azaz mindegy, hogy melyik gyűrűben végezzük el a szorzást, a végeredmény ugyanaz lesz. A  mod m\bmod_m függvény szerinti maradékos osztásokat elvégezve ismét négy egyenletet írhatunk fel az rr, q1q_1, q2q_2 és q3q_3 maradékokra valamilyen kk, n1n_1, n2n_2 és n3n_3 hányadosokkal:

ab=km+ra=n1m+q1b=n2m+q2q1q2=n3m+q3\begin{aligned} ab&=km+r \\ a&=n_1m+q_1 \\ b&=n_2m+q_2 \\ q_1q_2&=n_3m+q_3 \end{aligned}

Az első egyenletből kifejezhetjük rr-et, amely a  mod m(ab)\bmod_m(ab) maradékképzés eredménye:

r=ab−kmr=ab-km

A második és harmadik egyenletből kifejezhetjük q1q_1-et és q2q_2-t, amely a  mod m(a)⊙ mod m(b)\bmod_m(a)\odot \bmod_m(b) moduláris szorzás két tényezőjét fogja adni:

q1=a−n1mq2=b−n2m\begin{aligned} q_1&=a-n_1m \\ q_2&=b-n_2m \end{aligned}

Ezeket behelyettesítve a negyedik egyenletbe ezt kapjuk:

(a−n1m⏟=q1)⋅(b−n2m⏟=q2)=n3m+q3(\underbrace{a-n_1m}_{=q_1})\cdot (\underbrace{b-n_2m}_{=q_2})=n_3m+q_3

Bontsuk fel a baloldali zárójelet, alkalmazva a 14.12. Definíció 5. pontja szerinti disztributivitási szabályokat:

ab−an2m−n1mb+n1mn2m=n3m+q3ab-an_2m-n_1mb+n_1mn_2m=n_3m+q_3

Ezt átrendezve megkapjuk q3q_3-at:

q3=ab−an2m−n1mb+n1mn2m−n3mq_3=ab-an_2m-n_1mb+n_1mn_2m-n_3m

Azt kell tehát igazolnunk, hogy rr és q3q_3 valójában megegyeznek. Ehhez írjuk fel kettejük különbségét:

r−q3=ab−km⏞r−ab+an2m+n1mb−n1mn2m+n3m⏞−q3==(an2+n1b+n3−k−n1mn2)⋅m\begin{aligned} r-q_3&=\overbrace{\bcancel{ab}-km}^{r}\overbrace{-\bcancel{ab}+an_2m+n_1mb-n_1mn_2m+n_3m}^{-q_3}= \\ &=(an_2+n_1b+n_3-k-n_1mn_2)\cdot m \end{aligned}

Azt kaptuk tehát, hogy teljesül az m∣r−q3m|r-q_3 oszthatóság. Mivel rr és q3q_3 nemnegatív maradékok, így ismét alkalmazható rájuk a 18.1. Lemma, amiből r=q3r=q_3 következik. A  mod m\bmod_m függvény tehát a szorzást is tartja, és így valóban egy gyűrűhomomorfizmus Z\Z és ZmZ_m között.

Azt kell még igazolni, hogy szürjektív, ami itt azt jelenti, hogy minden ZmZ_m-beli elemhez létezik legalább egy olyan egész szám, amelynek épp ő a modulo mm maradéka. Ez viszont nyilvánvalóan következik a 18.3. Definíció utáni megjegyzés 5. pontjából. Eszerint ugyanis a 00, 11, 22, ..., ∣m∣−1|m|-1 egész számokat a  mod m\bmod_m maradékképző függvény önmagukra képezi le, amelyek viszont pontosan a ZmZ_m elemei.

∎