Zápis Euklidovho algoritmu do tabuľky

[Martin Sleziak]

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ť

Nájdite, ak existuje, aspoň jedno celočíselné riešenie rovnice
$$193x+18y=2.$$

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$.
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.)