Výpočet n.s.d. (rozšírený Euklidov algoritmus)
Posted: Tue Nov 06, 2018 3:43 pm
Na prednáške ste videli takýto výsledok, ktorému sa niekedy hovorí aj Bézoutova identita:
V skutočnosti to bolo sformulované trochu inak, bolo to súčasťou dlhšieho tvrdenia (Lema 1.7.7 v LAG1, Lema 2.1 v Korbaš-Gyurki). Ale z formulácie ktorú máte z prednášky (resp. v knihe) vidno aj platnosť toho čo som napísal vyššie.
Toto tvrdenie ste využili pri dôkaze existencie multiplikatívnych inverzov v poli $\mathbb Z_p$ (kde $p$ je prvočíslo).
Dôkaz, ktorý ste videli (a ktorý je aj v týchto knihách), je taký že z neho nevidno postup akým by sa dalo pre zadané $p$, $q$ vypočítať $x$, $y$. (T.j. je to existenčný dôkaz, nie konštruktívny.)
Chceme sa trochu pozrieť na to, ako sa dá takéto niečo rátať. T.j. ukážeme si postup, ktorým pre zadané $p$, $q$ vieme vypočítať $r=\gcd(p,q)$ a súčasne aj nájsť $x$, $y$ také aby platilo $r=px+qy$. (Pre istotu spomeniem aj to, že $x$ a $y$ touto pomienkou nie sú jednoznačne určené - nám bude stačiť nájsť jednu takú dvojicu.)
Postup, ktorý si ukážeme, sa volá rozšírený Euklidov algoritmus. Viac sa o ňom dá dozvedieť na veľa miestach - aj tu na fóre máte nejaké posty, kde sú nejaké odkazy a aj konkrétna ukážka vypočítaného príkladu: viewtopic.php?t=1035 a viewtopic.php?t=298
Napriek tomu sem skúsim pridať ešte nejaký príklad - a ideálne taký, na ktorom sa bude dať ukázať ako to súvisí s inverznými prvkami.
(A súčasne tento topic môžete použiť na to, aby ste sa opýtali ak sú nejaké nejasnosti. Takisto ak ste sa niektorí z vás učili túto istú vec na strednej škole trochu inak a viete k tomu napísať niečo rozumné, čo môže pomôcť vašim kolegom; alebo aspoň ukázať inú možnosť pre zápis toho istého algoritmu, tak takéto niečo je samozrejme vítané.)
Úloha: Vypočítajte $r=\gcd(101,31)$ a nájdite $x,y\in\mathbb Z$ také, aby platilo $101x+31y=r$.
Riešenie. Základná idea celého postupu je, že ak sa pozerám na delitele čísel $a$ a $b$, tak tie sú presne rovnaké ako delitele čísel $a-kb$ a $b$ pre ľubovoľné celé číslo $k$. (Skúste si rozmyslieť prečo.) Potom platí aj $\gcd(a,b)=\gcd(a-kb,b)$.
Špeciálne v našom prípade ak od $101$ odčítam nejaký násobok čísla $31$, tak nezmením n.s.d. Platí teda $\gcd(101,31)=\gcd(101-31k,31)$.
Asi môže byť ľahšie rátať s čo najmenšími číslami, takže by som chcel číslo $101-31k$ mať pomerne malé. Napríklad ak číslo $101$ vydelím so zvyškom číslom $31$, tak dostanem číslo tvaru $101-31k$, ktoré je určite menšie ako $31$. (Delenie so zvyškom znamená, že $101=31k+z$, pričom $0\le z<31$.)
V našom prípade máme $101=3\cdot31+8$, a teda
$$\gcd(101,31)=\gcd(31,8).$$
Teraz by sme mohli presne ten istý postup opakovať, ale máme výhodu že už pracujeme s menšími číslami. Čiže opäť delením so zvyškom by sme vedeli dostať $\gcd(31,8)=\gcd(8,7)$. (Číslo $7$ je zvyšok čísla $31$ po delení číslom $8$.)
Môžete skúsiť dokončiť tento postup samostatne kým budete čítať ďalej. A rozmyslieť si, či z tohoto nejako viete vyčítať n.s.d.
Zatiaľ sme iba vypočítali n.s.d. zadaných čísel. Skúsime sa pozrieť na to ako ešte nájsť čísla $x$, $y$.
Aby to bolo prehľadnejšie, skúsim celý postup zapísať do tabuľky. V tejto tabuľke si budem v druhom a treťom stĺpci udržiavať celé čísla $x$ a $y$ tak, aby som v prvom stĺpci mali $101x+31y$. Je jasné, že takáto podmienka sa nepokazí ak nejaký riadok vynásobím celočíselnou konštantou a ani keď nejaké takéto riadky sčitujem resp. odčitujem.
Pridal som ešte štvrtý stĺpec na vysvetleni aké úpravy som robil.
Na začiatku si môžeme nainicializovať tabuľku takto:
$$\begin{array}{|c|c|c||c|}
\hline
101 & 1 & 0 & \\\hline
31 & 0 & 1 & \\\hline
\end{array}$$
A potom postupujeme tak, že sa snažíme kombinovať riadky:
$$\begin{array}{|c|c|c||c|}
\hline
101 & 1 & 0 & \\\hline
31 & 0 & 1 & \\\hline
8 & 1 &-3 & r_1-3\cdot r_2\\\hline
7 &-3 &10 & r_2-3\cdot r_3\\\hline
1 & 4 &-13& r_3-r_4 \\\hline
\end{array}$$
Zápisom $r_1-3\cdot r_2$ myslím to, že som od prvého riadku $r_1$ odčítal trojnásobok druhého $3\cdot r_2$.
Tiež si môžete uvedomiť, že som postupoval presne podľa algoritmu, ktorý som vysvetlil vyššie - v každom kroku som od predošlého čísla odčítal taký násobok nasledujúceho, aby my vyšiel zvyšok po delení. Čiže v každom kroku som vlastne delil so zvyškom.
Jednak sme týmto výpočtom zistili, že $\gcd(101,31)=\gcd(31,8)=\gcd(8,7)=\gcd(7,1)=1$.
Čiže poznáme hodnotu n.s.d. $$\gcd(101,31)=1.$$
Súčasne ak sa pozrieme na posledný riadok, tak vidíme, že
$$4\cdot101-13\cdot31=1.$$
(Či nám to vyšlo správne môžete samozrejme skontrolovať priamo výpočtom.)
Teda sme zistili, že uvedená rovnosť platí napríklad pre $x=4$ a $y=-13$.
Môžeme si tiež všimnúť, že výpočet sme mohli o máličko urýchliť ak by sme si všimli že máme násobok osmičky blízko čísla $32$ a tak by sme mohli n.s.d dostať už v štvrtom kroku.
$$\begin{array}{|c|c|c||c|}
\hline
101 & 1 & 0 & \\\hline
31 & 0 & 1 & \\\hline
8 & 1 &-3 & r_1-3\cdot r_2\\\hline
1 & 4 &-13& 4\cdot r_3-r_2 \\\hline
\end{array}$$
Dostávame presne ten istý výsledok.
Ak skontrolujeme, že $101$ je prvočíslo (čo nie je príliš ťažké), tak vlastne bez akéhokoľvek počítania vieme že medzi prirodzenými číslami má toto číslo delitele iba $1$ a $101$, a je okamžite jasné že $\gcd(101,31)=1$.
Pri výpočte, ktorý sme si ukázali, sme však nepotrebovali nikde informáciu, že to je prvočíslo. A vyrátali sme aj niečo navyše - nie iba hodnotu n.s.d. ale zistili sme aj to, ako n.s.d. vieme vyjadriť v tvare celočíselnej kombinácie daných čísel.
Pretože $101$ je prvočíslo, $(\mathbb Z_{101},\oplus,\odot)$ je pole. (Sčitujeme a násobíme modulo $101$. Pretože v tomto poste sa vyskytujú dve rozličné sčitovania násobenia, tak aby som ich odlíšil, označil som ich radšej iným symbolom.)
Úloha: Čomu sa rovná $31^{-1}$ v poli $\mathbb Z_{101}$?
Chceme si vlastne ukázať, že výpočet ktorý sme si ukázali sa dá použiť na výpočet inverzného prvku v poli $\mathbb Z_p$. (A malo by vám to výrazne pripomínať argument, ktorý ste použili v dôkaze, že $\mathbb Z_p$ je pole.)
Riešenie. Už sme zistili, že ako počítame v celých číslach, tak máme
$$4\cdot101-13\cdot31=1.$$
Toto je len inak zapísaný fakt, že $-13\cdot31$ dáva po delení číslom $101$ zvyšok $1$, t.j. pri počítaní v $\mathbb Z_{101}$ máme
$$-13\odot101=1.$$
Ešte si môžeme uvedomiť, že v $\mathbb Z_{101}$ platí $-13=88$. (Inak povedané, zvyšok čísla $-13$ po delení číslom $101$ je $88$.)
Zistili sme, že $$88\odot101=1$$ a $$31^{-1}=88.$$
Budem v tomto poste najväčší spoločný deliteľ čísel $p$ a $q$ označovať ako $\gcd(p,q)$.Tvrdenie. Ak $r$ je najväčší spoločný deliteľ čísel $p$, $q$, tak existujú také celé čísla $x$, $y$ že platí
$$r=px+qy.$$
V skutočnosti to bolo sformulované trochu inak, bolo to súčasťou dlhšieho tvrdenia (Lema 1.7.7 v LAG1, Lema 2.1 v Korbaš-Gyurki). Ale z formulácie ktorú máte z prednášky (resp. v knihe) vidno aj platnosť toho čo som napísal vyššie.
Toto tvrdenie ste využili pri dôkaze existencie multiplikatívnych inverzov v poli $\mathbb Z_p$ (kde $p$ je prvočíslo).
Dôkaz, ktorý ste videli (a ktorý je aj v týchto knihách), je taký že z neho nevidno postup akým by sa dalo pre zadané $p$, $q$ vypočítať $x$, $y$. (T.j. je to existenčný dôkaz, nie konštruktívny.)
Chceme sa trochu pozrieť na to, ako sa dá takéto niečo rátať. T.j. ukážeme si postup, ktorým pre zadané $p$, $q$ vieme vypočítať $r=\gcd(p,q)$ a súčasne aj nájsť $x$, $y$ také aby platilo $r=px+qy$. (Pre istotu spomeniem aj to, že $x$ a $y$ touto pomienkou nie sú jednoznačne určené - nám bude stačiť nájsť jednu takú dvojicu.)
Postup, ktorý si ukážeme, sa volá rozšírený Euklidov algoritmus. Viac sa o ňom dá dozvedieť na veľa miestach - aj tu na fóre máte nejaké posty, kde sú nejaké odkazy a aj konkrétna ukážka vypočítaného príkladu: viewtopic.php?t=1035 a viewtopic.php?t=298
Napriek tomu sem skúsim pridať ešte nejaký príklad - a ideálne taký, na ktorom sa bude dať ukázať ako to súvisí s inverznými prvkami.
(A súčasne tento topic môžete použiť na to, aby ste sa opýtali ak sú nejaké nejasnosti. Takisto ak ste sa niektorí z vás učili túto istú vec na strednej škole trochu inak a viete k tomu napísať niečo rozumné, čo môže pomôcť vašim kolegom; alebo aspoň ukázať inú možnosť pre zápis toho istého algoritmu, tak takéto niečo je samozrejme vítané.)
Úloha: Vypočítajte $r=\gcd(101,31)$ a nájdite $x,y\in\mathbb Z$ také, aby platilo $101x+31y=r$.
Riešenie. Základná idea celého postupu je, že ak sa pozerám na delitele čísel $a$ a $b$, tak tie sú presne rovnaké ako delitele čísel $a-kb$ a $b$ pre ľubovoľné celé číslo $k$. (Skúste si rozmyslieť prečo.) Potom platí aj $\gcd(a,b)=\gcd(a-kb,b)$.
Špeciálne v našom prípade ak od $101$ odčítam nejaký násobok čísla $31$, tak nezmením n.s.d. Platí teda $\gcd(101,31)=\gcd(101-31k,31)$.
Asi môže byť ľahšie rátať s čo najmenšími číslami, takže by som chcel číslo $101-31k$ mať pomerne malé. Napríklad ak číslo $101$ vydelím so zvyškom číslom $31$, tak dostanem číslo tvaru $101-31k$, ktoré je určite menšie ako $31$. (Delenie so zvyškom znamená, že $101=31k+z$, pričom $0\le z<31$.)
V našom prípade máme $101=3\cdot31+8$, a teda
$$\gcd(101,31)=\gcd(31,8).$$
Teraz by sme mohli presne ten istý postup opakovať, ale máme výhodu že už pracujeme s menšími číslami. Čiže opäť delením so zvyškom by sme vedeli dostať $\gcd(31,8)=\gcd(8,7)$. (Číslo $7$ je zvyšok čísla $31$ po delení číslom $8$.)
Môžete skúsiť dokončiť tento postup samostatne kým budete čítať ďalej. A rozmyslieť si, či z tohoto nejako viete vyčítať n.s.d.
Spoiler:
Aby to bolo prehľadnejšie, skúsim celý postup zapísať do tabuľky. V tejto tabuľke si budem v druhom a treťom stĺpci udržiavať celé čísla $x$ a $y$ tak, aby som v prvom stĺpci mali $101x+31y$. Je jasné, že takáto podmienka sa nepokazí ak nejaký riadok vynásobím celočíselnou konštantou a ani keď nejaké takéto riadky sčitujem resp. odčitujem.
Pridal som ešte štvrtý stĺpec na vysvetleni aké úpravy som robil.
Na začiatku si môžeme nainicializovať tabuľku takto:
$$\begin{array}{|c|c|c||c|}
\hline
101 & 1 & 0 & \\\hline
31 & 0 & 1 & \\\hline
\end{array}$$
A potom postupujeme tak, že sa snažíme kombinovať riadky:
$$\begin{array}{|c|c|c||c|}
\hline
101 & 1 & 0 & \\\hline
31 & 0 & 1 & \\\hline
8 & 1 &-3 & r_1-3\cdot r_2\\\hline
7 &-3 &10 & r_2-3\cdot r_3\\\hline
1 & 4 &-13& r_3-r_4 \\\hline
\end{array}$$
Zápisom $r_1-3\cdot r_2$ myslím to, že som od prvého riadku $r_1$ odčítal trojnásobok druhého $3\cdot r_2$.
Tiež si môžete uvedomiť, že som postupoval presne podľa algoritmu, ktorý som vysvetlil vyššie - v každom kroku som od predošlého čísla odčítal taký násobok nasledujúceho, aby my vyšiel zvyšok po delení. Čiže v každom kroku som vlastne delil so zvyškom.
Jednak sme týmto výpočtom zistili, že $\gcd(101,31)=\gcd(31,8)=\gcd(8,7)=\gcd(7,1)=1$.
Čiže poznáme hodnotu n.s.d. $$\gcd(101,31)=1.$$
Súčasne ak sa pozrieme na posledný riadok, tak vidíme, že
$$4\cdot101-13\cdot31=1.$$
(Či nám to vyšlo správne môžete samozrejme skontrolovať priamo výpočtom.)
Teda sme zistili, že uvedená rovnosť platí napríklad pre $x=4$ a $y=-13$.
Môžeme si tiež všimnúť, že výpočet sme mohli o máličko urýchliť ak by sme si všimli že máme násobok osmičky blízko čísla $32$ a tak by sme mohli n.s.d dostať už v štvrtom kroku.
$$\begin{array}{|c|c|c||c|}
\hline
101 & 1 & 0 & \\\hline
31 & 0 & 1 & \\\hline
8 & 1 &-3 & r_1-3\cdot r_2\\\hline
1 & 4 &-13& 4\cdot r_3-r_2 \\\hline
\end{array}$$
Dostávame presne ten istý výsledok.
Ak skontrolujeme, že $101$ je prvočíslo (čo nie je príliš ťažké), tak vlastne bez akéhokoľvek počítania vieme že medzi prirodzenými číslami má toto číslo delitele iba $1$ a $101$, a je okamžite jasné že $\gcd(101,31)=1$.
Pri výpočte, ktorý sme si ukázali, sme však nepotrebovali nikde informáciu, že to je prvočíslo. A vyrátali sme aj niečo navyše - nie iba hodnotu n.s.d. ale zistili sme aj to, ako n.s.d. vieme vyjadriť v tvare celočíselnej kombinácie daných čísel.
Pretože $101$ je prvočíslo, $(\mathbb Z_{101},\oplus,\odot)$ je pole. (Sčitujeme a násobíme modulo $101$. Pretože v tomto poste sa vyskytujú dve rozličné sčitovania násobenia, tak aby som ich odlíšil, označil som ich radšej iným symbolom.)
Úloha: Čomu sa rovná $31^{-1}$ v poli $\mathbb Z_{101}$?
Chceme si vlastne ukázať, že výpočet ktorý sme si ukázali sa dá použiť na výpočet inverzného prvku v poli $\mathbb Z_p$. (A malo by vám to výrazne pripomínať argument, ktorý ste použili v dôkaze, že $\mathbb Z_p$ je pole.)
Riešenie. Už sme zistili, že ako počítame v celých číslach, tak máme
$$4\cdot101-13\cdot31=1.$$
Toto je len inak zapísaný fakt, že $-13\cdot31$ dáva po delení číslom $101$ zvyšok $1$, t.j. pri počítaní v $\mathbb Z_{101}$ máme
$$-13\odot101=1.$$
Ešte si môžeme uvedomiť, že v $\mathbb Z_{101}$ platí $-13=88$. (Inak povedané, zvyšok čísla $-13$ po delení číslom $101$ je $88$.)
Zistili sme, že $$88\odot101=1$$ a $$31^{-1}=88.$$