Zápis Euklidovho algoritmu do tabuľky
Posted: Wed Mar 01, 2017 11:53 am
Na dnešnom cviku sme si ukázali trochu iný zápis výpočtu vyjadrenie n.s.d. ako celočíselnej kombinácie. (Princíp je ten istý, je to trochu inak zapísané - tak som chcel ukázať aj takýto "tabuľkový" zápis, možno sa niekomu bude zdať prehľadnejší.
Niečo viac o takom postupe sa dá nájsť tu: viewtopic.php?t=298
Tu ho skúsim ešte raz zopakovať
Prvé dva riadky vyplním ľahko, zvolím si $x=1$, $y=0$ a obrátene.
A potom si už stačí uvedomiť, že táto vlastnosť sa nepokazí, keď pridám nový riadok ktorý vznikne už z existujúcich riadkov súčtom, rozdielom celočíselným násobkom a podobne. Takýmto spôsobom sa snažím dostať k čo najmenším číslam.
Posledný stĺpec má iba pomocný charakter - poznačil som v ňom aké úpravy som robil s predošlými riadkami. (Jednak to pomôže ak bude niekto iný čítať moje riešenie. A pomôže to aj mne, ak si chcem ešte raz prekontrolovať jednotlivé kroky.)
$$\begin{array}{|c|c|c||c|}
\hline
193 & 1 & 0 & \\\hline
18 & 0 & 1 & \\\hline
5 &-1 &11 & \texttt{11*2r-1r} \\\hline
2 &-4 &43 & \texttt{4*3r-2r} \\\hline
\end{array}$$
Posledný riadok mi hovorí, že
$$(-4)\cdot193+43\cdot18=2.$$
Môžem to aj prekontrolovať tak, že to naozaj vypočítam.
Tým sme túto úlohu vyriešili - našli sme aspoň jedno riešenie zadanej rovnice.
Ak by sme chceli urobiť aj to, že dostaneme najväčší spoločný deliteľ čísel $193$ a $18$ a vyjadriť ho ako ich celočíselnú kombináciu, tak by sme potrebovali urobiť ešte jeden krok tak, aby sme v prvom stĺpci dostali jednotku. (Môžete si vyskúšať, čo vám vyjde.)
Niečo viac o takom postupe sa dá nájsť tu: viewtopic.php?t=298
Tu ho skúsim ešte raz zopakovať
V podstate to, čo robím nižšie je, že v tabuľke sa snažím mať vždy také čísla, že ak v druhom a treťom stĺpci mám čísla $x$, $y$, tak číslo v prvom stĺpci je $193x+18y$.Nájdite, ak existuje, aspoň jedno celočíselné riešenie rovnice
$$193x+18y=2.$$
Prvé dva riadky vyplním ľahko, zvolím si $x=1$, $y=0$ a obrátene.
A potom si už stačí uvedomiť, že táto vlastnosť sa nepokazí, keď pridám nový riadok ktorý vznikne už z existujúcich riadkov súčtom, rozdielom celočíselným násobkom a podobne. Takýmto spôsobom sa snažím dostať k čo najmenším číslam.
Posledný stĺpec má iba pomocný charakter - poznačil som v ňom aké úpravy som robil s predošlými riadkami. (Jednak to pomôže ak bude niekto iný čítať moje riešenie. A pomôže to aj mne, ak si chcem ešte raz prekontrolovať jednotlivé kroky.)
$$\begin{array}{|c|c|c||c|}
\hline
193 & 1 & 0 & \\\hline
18 & 0 & 1 & \\\hline
5 &-1 &11 & \texttt{11*2r-1r} \\\hline
2 &-4 &43 & \texttt{4*3r-2r} \\\hline
\end{array}$$
Posledný riadok mi hovorí, že
$$(-4)\cdot193+43\cdot18=2.$$
Môžem to aj prekontrolovať tak, že to naozaj vypočítam.
Tým sme túto úlohu vyriešili - našli sme aspoň jedno riešenie zadanej rovnice.
Ak by sme chceli urobiť aj to, že dostaneme najväčší spoločný deliteľ čísel $193$ a $18$ a vyjadriť ho ako ich celočíselnú kombináciu, tak by sme potrebovali urobiť ešte jeden krok tak, aby sme v prvom stĺpci dostali jednotku. (Môžete si vyskúšať, čo vám vyjde.)