youproof.orgDeep Math. Human Access.

Bizonyítás

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

\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 r-rel, q_1-gyel, q_2-vel és q_3-mal:

\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=q_3, azaz mindegy, hogy melyik gyűrűben végezzük el az összeadást, a végeredmény ugyanaz lesz. A \bmod_m függvény szerinti maradékos osztásokat elvégezve négy egyenletet írhatunk fel az r, q_1, q_2 és q_3 maradékokra valamilyen k, n_1, n_2 és n_3 hányadosokkal:

\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 r-et, amely a \bmod_m(a+b) maradékképzés eredménye:

r=a+b-km

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

\begin{aligned} q_1&=a-n_1m \\ q_2&=b-n_2m \end{aligned}

Ezeket behelyettesítve a negyedik egyenletbe ezt kapjuk:

\underbrace{a-n_1m}_{=q_1}+\underbrace{b-n_2m}_{=q_2}=n_3m+q_3

Ezt átrendezve megkapjuk q_3-at:

q_3=a-n_1m+b-n_2m-n_3m

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

\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-q_3 oszthatóság. Mivel r és q_3 nemnegatív maradékok, így alkalmazható rájuk a 18.1. Lemma, amiből r=q_3 következik. A \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 gyűrű esetén a \cdot, míg a Z_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:

\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 r-rel, q_1-gyel, q_2-vel és q_3-mal:

\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=q_3, azaz mindegy, hogy melyik gyűrűben végezzük el a szorzást, a végeredmény ugyanaz lesz. A \bmod_m függvény szerinti maradékos osztásokat elvégezve ismét négy egyenletet írhatunk fel az r, q_1, q_2 és q_3 maradékokra valamilyen k, n_1, n_2 és n_3 hányadosokkal:

\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 r-et, amely a \bmod_m(ab) maradékképzés eredménye:

r=ab-km

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

\begin{aligned} q_1&=a-n_1m \\ q_2&=b-n_2m \end{aligned}

Ezeket behelyettesítve a negyedik egyenletbe ezt kapjuk:

(\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-an_2m-n_1mb+n_1mn_2m=n_3m+q_3

Ezt átrendezve megkapjuk q_3-at:

q_3=ab-an_2m-n_1mb+n_1mn_2m-n_3m

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

\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-q_3 oszthatóság. Mivel r és q_3 nemnegatív maradékok, így ismét alkalmazható rájuk a 18.1. Lemma, amiből r=q_3 következik. A \bmod_m függvény tehát a szorzást is tartja, és így valóban egy gyűrűhomomorfizmus \Z és Z_m között.

Azt kell még igazolni, hogy szürjektív, ami itt azt jelenti, hogy minden Z_m-beli elemhez létezik legalább egy olyan egész szám, amelynek épp ő a modulo m 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 0, 1, 2, ..., |m|-1 egész számokat a \bmod_m maradékképző függvény önmagukra képezi le, amelyek viszont pontosan a Z_m elemei.

∎