Opravovatelia

Alic [email protected]

Matúš [email protected]

Prvým pozorovaním je, že ak máme v koterci psa s číslom $x$, tak opakovaným sčítaním $x + x + \dots + x$ vieme vytvoriť všetky kladné násobky $kx$ (pre $k \in \mathbb{N}$). Teda vieme zostaviť ľubovoľné väčšie násobky daného čísla.

Taktiež, keď ľubovoľne sčítavame čísla $a$ a $b$, výsledok $a+b$ je deliteľný najväčším spoločným deliteľom $\text{NSD}(a,b)$.

Dôležitá podmienka je, že v koterci je aspoň jedno kladné a aspoň jedno záporné číslo. Opakovaným sčítavaním rôznych kombinácií týchto čísel sa tak môžeme posúvať dopredu aj dozadu na číselnej osi.

Použitím opakovaného sčítania a kombinovaním kladných a záporných čísel sa preto dá približovať k nule, teda dostať číslo s čo najmenšou absolútnou hodnotou. Už vieme, že aj toto číslo je deliteľné $\text{NSD}(a,b)$. Keďže jeho absolútna hodnota je zároveň najmenšia, akú vieme dostať, toto číslo priamo je $\text{NSD}(a,b)$. O tom, že $\text{NSD}(a,b)$ vieme vytvoriť ako súčet (či už kladných alebo záporných) násobkov čísel $a,b$, hovorí aj Bezoutova veta.

Keď vieme vytvoriť $\text{NSD}(a,b)$, opakovaným sčítaním vieme vytvoriť aj všetky jeho násobky. Preto máme v koterci všetky celé čísla deliteľné $\text{NSD}(a,b)$. Inými slovami, každé číslo, ktoré je deliteľné $\text{NSD}(a,b)$, sa v koterci nachádza. Rozdiel $a-b$ je vždy deliteľný $\text{NSD}(a,b)$. Podľa predchádzajúcej vety je preto určite v koterci aj tento rozdiel. Týmto sme úlohu dokázali.

Poznámka: Mnohí z Vás riešili nesúdeliteľnosť čísel $a,b$ ako samostatný prípad. Všimnime si, že takýto postup nie je nutný, nakoľko vyššie uvedené riešenie je aplikovateľné aj tu – len v tom prípade $\text{NSD}(a,b) = 1$.