Motto
Za väčšinu toho čo viem, vďačím svojim žiakom.
Skôr než sa pustíme do hľadania dier na racionálnej číselnej osi, budeme sa zaoberať špeciálnymi rovnicami typu $$\bf{a \cdot m + b \cdot n = c},$$ kde neznáme $\bf{m, n}$, aj parametre $\bf{a, b, c}$ nadobúdajú len celočíselné hodnoty. Takýmto rovniciam s dvoma celočíselnými premennými, alebo sústavám $\bf{k – 1}$ takýchto rovníc s $\bf{k}$ celočíselnými premennými hovoríme Diofantické rovnice [5] , alebo sústavy diofantických rovníc.
Zamyslime sa nad rovnicou $\bf{a \cdot m + b \cdot n = c}$. Keby čísla $\bf{a, b, c}$ mali spoločného deliteľa, mohli by sme ním rovnicu predeliť, preto sa budeme zaoberať iba prípadom, keď najväčší spoločný deliteľ týchto troch čísel je $1$. Nezaujímavý je prípad, keď čísla $\bf{a, b}$ majú netriviálneho spoločného deliteľa $\bf{d}$, ale tento nie je deliteľom čísla $\bf{c}$: $$\bf{pd \cdot m + qd \cdot n = c}$$ vtedy totiž rovnica v obore celých čísel zrejme nemá riešenie.
Miesto dlhého teoretizovania vyriešme radšej
V koncertnej sále boli klavíry a stoličky. Spolu mali $104$ nôh. Koľko tam bolo klavírov a koľko stoličiek, ak vieme, že stoličiek bolo viac? (Predpokladáme, že každá stolička má $4$ a každý klavír $3$ nohy.)
Máme teda vyriešiť rovnicu: $$\bf{3p + 4q = 104}$$ pričom z kontextu úlohy vyplýva, že oborom premenných sú nezáporné celé čísla.
Rovnicu upravíme:
$\bf{3p + 3q - 102 = 2 - q}$ z čoho je zrejmé, že riešenie bude existovať len ak existuje také celé číslo $\bf{r}$, že
$\bf{2 - q = 3r}$ odkiaľ dostávame $\bf{\bbox[lime, 5px]{q = 2 - 3r}}$
Tento výsledok dosadíme do prvej rovnice a máme:
$\bf{3p + 4(2-3r) = 104}$ čo po úpravách dáva $\bf{p - 4r = 32}$, odkiaľ $\bf{\bbox[lime, 5px]{p = 32 + 4r}}$
Všetky riešenia dostaneme z tabuľky: $$ \begin{array}{|c|c|c|c|c|} \hline r & \cellcolor{magenta} \bf{-9} & \cellcolor{lime} \bf{-8} & \cellcolor{lime} \bf{-7} & \cellcolor{lime} \bf{-6} & \cellcolor{lime} \bf{-5} & \cellcolor{red} \bf{-4} & \cellcolor{red} \bf{-3} & \cellcolor{red} \bf{-2} & \cellcolor{red} \bf{-1} & \cellcolor{red} \bf{0} & \cellcolor{magenta} \bf{1} \\ \hline p & \cellcolor{magenta} \bf{-4} & \cellcolor{lime} \bf{0} & \cellcolor{lime} \bf{4} & \cellcolor{lime} \bf{8} & \cellcolor{lime} \bf{12} & \cellcolor{red} \bf{16} & \cellcolor{red} \bf{20} & \cellcolor{red} \bf{24} & \cellcolor{red} \bf{28} & \cellcolor{red} \bf{36} & \cellcolor{magenta} \bf{40} \\ \hline q & \cellcolor{magenta} \bf{29} & \cellcolor{lime} \bf{26} & \cellcolor{lime} \bf{23} & \cellcolor{lime} \bf{20} & \cellcolor{lime} \bf{17} & \cellcolor{red} \bf{14} & \cellcolor{red} \bf{11} & \cellcolor{red} \bf{8} & \cellcolor{red} \bf{5} & \cellcolor{red} \bf{2} & \cellcolor{magenta} \bf{-1} \\ \hline \end{array} $$
Fialové možnosti dávajú záporné výsledky, v červených prípadoch je viac klavírov ako stoličiek, preto zostávajú len zelené možnosti ako správne riešenia.
Pán Milan A. je numizmatik. Ak si svoje kremnické dukáty rozdelí do siedmich radov, zvýšia mu $4$, ak ich rozloží do jedenástich radov, zvýši mu $5$ dukátov. Koľko má dukátov, ak vieme že ich nemá viac ako $1000$?
Máme vlastne vyriešiť rovnicu $\bf{7a + 4 = 11b + 5 \qquad (1)}$
Pričom oborom premenných sú nezáporné celé čísla a $\bf{7a + 4 \lt 1000}$
Podobne ako v minulom príklade rovnicu upravíme na tvar
Pre túto rovnicu zopakujme náš postup, t. j. upravme ju na tvar:
Pre túto rovnicu opäť zopakujeme náš postup, t. j. upravíme ju na tvar:
Z tejto rovnice dostávame: $\bf{d = 3e - 1}$
Teraz budeme spätne dosadzovať do predchádzajúcich rovníc. Postupne budeme dostávať:
Uvedomme si, že náš postup musel mať úspech. Sledujme koeficienty pri neznámych v jednotlivých rovniciach: $$\begin{aligned} &\bf{(1) \qquad 7 \; a \; 11} \\ &\bf{(2) \qquad 4 \; a \; 7} \\ &\bf{(3) \qquad 3 \; a \; 4} \\ &\bf{(4) \qquad 1 \; a \; 3} \\ \end{aligned}$$
Nepripomína vám to hľadanie najväčšieho spoločného deliteľ čísiel $\bf{7}$ a $\bf{11}$ Euklidovým algoritmom? Oprávnene áno, čiže naše koeficienty sa neustále zmenšujú a vzhľadom na podmienku, že ich NSD je $1$, po konečnom počte krokov dostaneme rovnicu, v ktorej je pri jednej z premenných koeficient $1$.
Nájdite najmenšie prirodzené číslo $\bf{n}$ také, že zlomok $\bf{\frac{5n + 2}{3n + 1}}$ sa dá krátiť.
Krátky experiment (pozri hárok zlomok zošitu Diofantos) nič nerieši. Máme podozrenie, že zlomok je v základnom tvare pre každé $\bf{n}$, to sa ale experimentom dokázať nedá. Uvažujme takto:
Diofantos
Ak $\bf{a / b}$ (pozri poznámku[6] ) a $\bf{a / c}$ tak zrejme aj $\bf{a / b + c}$ a pre ľubovoľné $\bf{k}$ celé $\bf{a / k \cdot b}$.
Ak teda $\bf{d / 5n + 2}$ a súčasne $\bf{d / 3n + 1}$, tak $\bf{d / 3 \cdot (5n + 2) - 5 \cdot (3n + 1) = 1}$.
Teda každý spoločný deliteľ čitateľa aj menovateľa nášho zlomku je deliteľom jednotky, presnejšie najväčší spoločný deliteľ čitateľa a menovateľa je jednotka, zlomok sa nikdy krátiť nedá.
Tento trik (vyjadrenie faktu, že spoločný deliteľ dvoch čísel je aj deliteľom súčtu ich ľubovoľných násobkov[7] ) použijeme aj pri nasledujúcom príklade:
Stojíte pred prameňom prírodnej minerálnej vody a máte k dispozícii jeden päťlitrový a jeden trojlitrový demižón. Dá sa len pomocou nich načapovať pri prameni presne jeden liter minerálky ?
Využijeme, že $\bf{2 \cdot 5 – 3 \cdot 3 = 1}$. To znamená, že budeme musieť dvakrát načapovať do plna päťlitrový demižón a trikrát vyliať plný trojlitrový demižón. To sa dá uskutočniť takouto postupnosťou krokov ( modrá znamená načapovanie, červená vyliatie): $$(0; 0) \bbox[cyan, 5px]{\spadesuit} (5; 0) \spadesuit (2; 3) \bbox[red, 5px]{\spadesuit} (2; 0) \spadesuit (0;2) \bbox[cyan, 5px]{\spadesuit} (5; 2) \spadesuit (4; 3) \bbox[red, 5px]{\spadesuit} (4; 0) \spadesuit (1; 3) \bbox[red, 5px]{\spadesuit} (1; 0)$$
Nájdite všetky trojciferné čísla, ktoré pri delení s číslom $\bf{33}$ dávajú zvyšok $\bf{10}$ a pri delení s číslom $\bf{28}$ zvyšok $\bf{6}$. (Pomôžte si 1. hárkom zošitu Diofantos. Pomocou neho skontrolujte aj výsledok posledného príkladu.)
Diofantos
Nájdite najmenšie prirodzené číslo $\bf{a}$, pre ktoré má rovnica $$\bf{30x + 42y = 100 + a}$$ riešenie v množine prirodzených čísel.