youproof.orgDeep Math. Human Access.

Bizonyítás

Nincs más dolgunk, mint mechanikusan leellenőrizni a 14.12. Definíció szerinti gyűrűaxiómák teljesülését.

A műveletek kommutativitása

Ez egyszerűen adódik a 18.3. Definícióból, valamint a hagyományos összeadás és szorzás kommutativitásából:

\begin{aligned}a\oplus b&=\bmod_m(a+b)=\bmod_m(b+a)=b\oplus a \\ a\odot b&=\bmod_m(a\cdot b)=\bmod_m(b\cdot a)=b\odot a\end{aligned}
Neutrális elem létezése

Az |m|=1 esetben a 18.3. Definíció utáni megjegyzés 4. pontja alapján Z_m épp a nullgyűrű. Ebben az egyetlen elem a 0, amely nyilván mindkét műveletre nézve neutrális elem. Feltehetjük tehát, hogy |m|\neq 1. Mivel Z_m elemei épp a modulo m maradékok, ezért rájuk alkalmazható a 18.3. Definíció utáni megjegyzés 5. pontja. Ez alapján könnyen adódik, hogy mindkét művelethez létezik neutrális elem, méghozzá a 0 és az 1:

\begin{aligned} a\oplus 0&=\bmod_m(a+0)=\bmod_m(a)=a \\ a\odot 1&=\bmod_m(a\cdot 1)=\bmod_m(a)=a \end{aligned}
Ellentett elem létezése

Ehhez azt kell megmutatni, hogy tetszőleges a maradékhoz létezik olyan b maradék, amelyre a\oplus b=0 teljesül. Ha a=0, akkor a b=0 választás nyilván megfelelő, hiszen az előző pont alapján 0\oplus 0=0. Az a\neq 0 esetekben a b=|m|-a választás lesz a megfelelő, hiszen ekkor egyrészt nyilván teljesül a 0\leq b\lt |m| egyenlőtlenség – azaz b is egy modulo m maradék –, másrészt pedig az a\oplus b moduláris összeadást kifejtve az alábbit kapjuk:

a\oplus b=\bmod_m(a+b)=\bmod_m(a+\underbrace{|m|-a}_{=b})=\bmod_m(|m|)

Ha m pozitív, akkor \bmod_m(|m|)=\bmod_m(m), ha pedig negatív, akkor \bmod_m(|m|)=\bmod_m(-m). A 16.2. Tétel 8. pontja alapján viszont az ellentettképzés nem befolyásolja az oszthatóságot, így mindkét esetben 0 lesz a maradék, azaz b valóban a ellentettje.

A moduláris összeadás asszociativitása

Azt kell megmutatni, hogy

(a\oplus b)\oplus c=a\oplus (b\oplus c)

Fejtsük ki mindkét oldalt a 18.3. Definíció alapján. A végrehajtás során képződő részeredményeket jelöljük r_1-gyel és q_1-gyel, a végeredményeket pedig r_2-vel és q_2-vel:

\begin{aligned} (a\oplus b)\oplus c&=\overbrace{\bmod_m(a+b)}^{=r_1}\oplus c=\bmod_m(r_1+c)=r_2 \\ a\oplus (b\oplus c)&=a\oplus \underbrace{\bmod_m(b+c)}_{=q_1}=\bmod_m(a+q_1)=q_2 \end{aligned}

Azt kell megmutatnunk, hogy r_2=q_2, azaz mindegy, hogy milyen sorrendben végezzük el a két moduláris ö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_1 és q_1 valamint az r_2 és q_2 maradékokra valamilyen k_1 és n_1, valamint k_2 és n_2 hányadosokkal:

\begin{aligned} a+b&=k_1m+r_1 \\ b+c&=n_1m+q_1 \\ r_1+c&=k_2m+r_2 \\ a+q_1&=n_2m+q_2 \end{aligned}

Az első két egyenletet átrendezve megkapjuk r_1-et és q_1-et:

\begin{aligned} r_1&=a+b-k_1m \\ q_1&=b+c-n_1m \end{aligned}

Ezeket behelyettesítve a másik két egyenletbe az alábbiakat kapjuk:

\begin{aligned} \overbrace{a+b-k_1m}^{=r_1}+c&=k_2m+r_2 \\ a+\underbrace{b+c-n_1m}_{=q_1}&=n_2m+q_2 \end{aligned}

Ezeket megint átrendezve kifejezhetjük az r_2 és a q_2 maradékokat:

\begin{aligned} r_2&=a+b-k_1m+c-k_2m \\ q_2&=a+b+c-n_1m-n_2m \end{aligned}

Azt kell megmutatnunk, hogy ezek valójában megegyeznek. Írjuk hát fel a kettejük különbségét:

\begin{aligned} r_2-q_2&=\overbrace{\bcancel{a}+\bcancel{b}-k_1m+\bcancel{c}-k_2m}^{r_2}\overbrace{-\bcancel{a}-\bcancel{b}-\bcancel{c}+n_1m+n_2m}^{-q_2}=\\ &=(n_1+n_2-k_1-k_2)\cdot m \end{aligned}

Azt kaptuk tehát, hogy teljesül az m|r_2-q_2 oszthatóság. Mivel r_2 és q_2 nemnegatív maradékok, így alkalmazható rájuk a 18.1. Lemma, amiből r_2=q_2 következik. Az \oplus művelet tehát valóban asszociatív.

A moduláris szorzás asszociativitása

Azt kell megmutatni, hogy

(a\odot b)\odot c=a\odot (b\odot c)

Ismét fejtsük ki mindkét oldalt a részeredményeket r_1-gyel és q_1-gyel, a végeredményeket pedig r_2-vel és q_2-vel jelölve:

\begin{aligned} (a\odot b)\odot c&=\overbrace{\bmod_m(ab)}^{=r_1}\odot c=\bmod_m(r_1c)=r_2 \\ a\odot (b\odot c)&=a\odot \underbrace{\bmod_m(bc)}_{=q_1}=\bmod_m(aq_1)=q_2 \end{aligned}

A \bmod_m függvény szerinti maradékos osztásokat elvégezve négy egyenletet írhatunk fel az r_1 és q_1 valamint az r_2 és q_2 maradékokra valamilyen k_1 és n_1 valamint k_2 és n_2 hányadosokkal:

\begin{aligned} ab&=k_1m+r_1 \\ bc&=n_1m+q_1 \\ r_1c&=k_2m+r_2 \\ aq_1&=n_2m+q_2 \end{aligned}

Az első két egyenletet átrendezve megkapjuk r_1-et és q_1-et:

\begin{aligned} r_1&=ab-k_1m \\ q_1&=bc-n_1m \end{aligned}

Ezeket behelyettesítve a másik két egyenletbe az alábbiakat kapjuk:

\begin{aligned} (\overbrace{ab-k_1m}^{=r_1})\cdot c&=k_2m+r_2 \\ a\cdot(\underbrace{bc-n_1m}_{=q_1})&=n_2m+q_2 \end{aligned}

A zárójeleket felbonthatjuk:

\begin{aligned} abc - k_1mc &= k_2m+r_2 \\ abc - an_1m &= n_2m+q_2 \end{aligned}

Ezeket megint átrendezve kifejezhetjük az r_2 és a q_2 maradékokat:

\begin{aligned} r_2&=abc-k_1mc-k_2m \\ q_2&=abc-an_1m-n_2m \end{aligned}

Azt kell megmutatnunk, hogy ezek valójában megegyeznek. Írjuk hát fel a kettejük különbségét:

\begin{aligned} r_2-q_2&=\overbrace{\bcancel{abc}-k_1mc-k_2m}^{r_2}\overbrace{-\bcancel{abc}+an_1m+n_2m}^{-q_2}=\\ &=(an_1+n_2-k_1c-k_2)\cdot m \end{aligned}

Ismét azt kaptuk, hogy teljesül az m|r_2-q_2 oszthatóság. Ebből viszont ugyancsak a 18.1. Lemma miatt r_2=q_2 következik, azaz a \odot művelet is asszociatív.

A disztributivitási szabályok

Mivel a \odot művelet kommutativitását már igazoltuk, ezért elegendő az egyik oldali disztributivitást igazolni, azaz hogy

a\odot (b\oplus c)=(a\odot b)\oplus (a\odot c)

A recept a megszokott: ismét a definíció szerint kifejtjük mindkét oldalt, majd megmutatjuk, hogy a különbségük osztható az m modulussal, azaz végsősoron megegyeznek. A két oldal kifejtése:

\begin{aligned} a\odot (b\oplus c)&=a\odot \overbrace{\bmod_m(b+c)}^{=r_1}=\bmod_m(ar_1)=r_2 \\ (a\odot b)\oplus (a\odot c)&=\underbrace{\bmod_m(ab)}_{=q_1} \oplus \underbrace{\bmod_m(ac)}_{=q_2}=\bmod_m(q_1+q_2)=q_3 \end{aligned}

Ez tehát az alábbi maradékos osztásokat jelenti valamilyen k_1, k_2, n_1, n_2 és n_3 hányadosokkal:

\begin{aligned} b+c&=k_1m+r_1 \\ ar_1&=k_2m+r_2 \\ ab&=n_1m+q_1 \\ ac&=n_2m+q_2 \\ q_1+q_2&=n_3m+q_3 \end{aligned}

Ebből az egyenletrendszerből a már megszokott módon kifejezzük az r_2 és q_3 maradékokat:

\begin{aligned} r_2&=ab+ac-ak_1m-k_2m \\ q_3&=ab-n_1m+ac-n_2m-n_3m \end{aligned}

Azt kell megmutatnunk, hogy ezek valójában megegyeznek. Írjuk hát fel a kettejük különbségét:

\begin{aligned} r_2-q_3&=\overbrace{\bcancel{ab}+\bcancel{ac}-ak_1m-k_2m}^{r_2}\overbrace{-\bcancel{ab}+n_1m-\bcancel{ac}+n_2m+n_3m}^{-q_3}=\\ &=(n_1+n_2+n_3-ak_1-k_2)\cdot m \end{aligned}

Teljesül tehát az m|r_2-q_3 oszthatóság, és így ismét a 18.1. Lemma alkalmazásával r_2=q_3 adódik, azaz a \odot művelet disztributív a \oplus műveletre nézve.

Minthogy minden gyűrűaxióma teljesül, továbbá a moduláris szorzás is kommutatív, ezért Z_m valóban egy kommutatív gyűrű. Láttuk továbbá, hogy a moduláris szorzásra nézve is létezik neutrális elem, ezért Z_m egységelemes, hacsak nem a nullgyűrűről – az |m|=1 esetről – van szó, amit a 14.12. Definíció szerint nem tekintünk annak.

∎