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:

a⊕b= mod m(a+b)= mod m(b+a)=b⊕aa⊙b= mod m(a⋅b)= mod m(b⋅a)=b⊙a\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|m|=1 esetben a 18.3. Definíció utáni megjegyzés 4. pontja alapján ZmZ_m épp a nullgyűrű. Ebben az egyetlen elem a 00, amely nyilván mindkét műveletre nézve neutrális elem. Feltehetjük tehát, hogy ∣m∣≠1|m|\neq 1. Mivel ZmZ_m elemei épp a modulo mm 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 00 és az 11:

a⊕0= mod m(a+0)= mod m(a)=aa⊙1= mod m(a⋅1)= mod m(a)=a\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 aa maradékhoz létezik olyan bb maradék, amelyre a⊕b=0a\oplus b=0 teljesül. Ha a=0a=0, akkor a b=0b=0 választás nyilván megfelelő, hiszen az előző pont alapján 0⊕0=00\oplus 0=0. Az a≠0a\neq 0 esetekben a b=∣m∣−ab=|m|-a választás lesz a megfelelő, hiszen ekkor egyrészt nyilván teljesül a 0≤b<∣m∣0\leq b\lt |m| egyenlőtlenség – azaz bb is egy modulo mm maradék –, másrészt pedig az a⊕ba\oplus b moduláris összeadást kifejtve az alábbit kapjuk:

a⊕b= mod m(a+b)= mod m(a+∣m∣−a⏟=b)= mod m(∣m∣)a\oplus b=\bmod_m(a+b)=\bmod_m(a+\underbrace{|m|-a}_{=b})=\bmod_m(|m|)

Ha mm pozitív, akkor  mod m(∣m∣)= mod m(m)\bmod_m(|m|)=\bmod_m(m), ha pedig negatív, akkor  mod m(∣m∣)= mod m(−m)\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 00 lesz a maradék, azaz bb valóban aa ellentettje.

A moduláris összeadás asszociativitása

Azt kell megmutatni, hogy

(a⊕b)⊕c=a⊕(b⊕c)(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 r1r_1-gyel és q1q_1-gyel, a végeredményeket pedig r2r_2-vel és q2q_2-vel:

(a⊕b)⊕c= mod m(a+b)⏞=r1⊕c= mod m(r1+c)=r2a⊕(b⊕c)=a⊕ mod m(b+c)⏟=q1= mod m(a+q1)=q2\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 r2=q2r_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  mod m\bmod_m függvény szerinti maradékos osztásokat elvégezve négy egyenletet írhatunk fel az r1r_1 és q1q_1 valamint az r2r_2 és q2q_2 maradékokra valamilyen k1k_1 és n1n_1, valamint k2k_2 és n2n_2 hányadosokkal:

a+b=k1m+r1b+c=n1m+q1r1+c=k2m+r2a+q1=n2m+q2\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 r1r_1-et és q1q_1-et:

r1=a+b−k1mq1=b+c−n1m\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:

a+b−k1m⏞=r1+c=k2m+r2a+b+c−n1m⏟=q1=n2m+q2\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 r2r_2 és a q2q_2 maradékokat:

r2=a+b−k1m+c−k2mq2=a+b+c−n1m−n2m\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:

r2−q2=a+b−k1m+c−k2m⏞r2−a−b−c+n1m+n2m⏞−q2==(n1+n2−k1−k2)⋅m\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∣r2−q2m|r_2-q_2 oszthatóság. Mivel r2r_2 és q2q_2 nemnegatív maradékok, így alkalmazható rájuk a 18.1. Lemma, amiből r2=q2r_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⊙b)⊙c=a⊙(b⊙c)(a\odot b)\odot c=a\odot (b\odot c)

Ismét fejtsük ki mindkét oldalt a részeredményeket r1r_1-gyel és q1q_1-gyel, a végeredményeket pedig r2r_2-vel és q2q_2-vel jelölve:

(a⊙b)⊙c= mod m(ab)⏞=r1⊙c= mod m(r1c)=r2a⊙(b⊙c)=a⊙ mod m(bc)⏟=q1= mod m(aq1)=q2\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  mod m\bmod_m függvény szerinti maradékos osztásokat elvégezve négy egyenletet írhatunk fel az r1r_1 és q1q_1 valamint az r2r_2 és q2q_2 maradékokra valamilyen k1k_1 és n1n_1 valamint k2k_2 és n2n_2 hányadosokkal:

ab=k1m+r1bc=n1m+q1r1c=k2m+r2aq1=n2m+q2\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 r1r_1-et és q1q_1-et:

r1=ab−k1mq1=bc−n1m\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:

(ab−k1m⏞=r1)⋅c=k2m+r2a⋅(bc−n1m⏟=q1)=n2m+q2\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:

abc−k1mc=k2m+r2abc−an1m=n2m+q2\begin{aligned} abc - k_1mc &= k_2m+r_2 \\ abc - an_1m &= n_2m+q_2 \end{aligned}

Ezeket megint átrendezve kifejezhetjük az r2r_2 és a q2q_2 maradékokat:

r2=abc−k1mc−k2mq2=abc−an1m−n2m\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:

r2−q2=abc−k1mc−k2m⏞r2−abc+an1m+n2m⏞−q2==(an1+n2−k1c−k2)⋅m\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∣r2−q2m|r_2-q_2 oszthatóság. Ebből viszont ugyancsak a 18.1. Lemma miatt r2=q2r_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⊙(b⊕c)=(a⊙b)⊕(a⊙c)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 mm modulussal, azaz végsősoron megegyeznek. A két oldal kifejtése:

a⊙(b⊕c)=a⊙ mod m(b+c)⏞=r1= mod m(ar1)=r2(a⊙b)⊕(a⊙c)= mod m(ab)⏟=q1⊕ mod m(ac)⏟=q2= mod m(q1+q2)=q3\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 k1k_1, k2k_2, n1n_1, n2n_2 és n3n_3 hányadosokkal:

b+c=k1m+r1ar1=k2m+r2ab=n1m+q1ac=n2m+q2q1+q2=n3m+q3\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 r2r_2 és q3q_3 maradékokat:

r2=ab+ac−ak1m−k2mq3=ab−n1m+ac−n2m−n3m\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:

r2−q3=ab+ac−ak1m−k2m⏞r2−ab+n1m−ac+n2m+n3m⏞−q3==(n1+n2+n3−ak1−k2)⋅m\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∣r2−q3m|r_2-q_3 oszthatóság, és így ismét a 18.1. Lemma alkalmazásával r2=q3r_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 ZmZ_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 ZmZ_m egységelemes, hacsak nem a nullgyűrűről – az ∣m∣=1|m|=1 esetről – van szó, amit a 14.12. Definíció szerint nem tekintünk annak.

∎