2. Príbeh o Dášenke a minci vzorové riešenie

Pripomeňme si, že ráno dostala Dášenka dve rovnaké čísla \(p\) a \(d\), ktoré sú väčšie ako nula. Následne niekoľkokrát hodila mincou a podľa toho, čo jej padlo spravila jednu z nasledovných operácií.

• Z (znak): pripočítame \(d\) ku \(p\), takže vznikne dvojica čísel \(p+d\) a \(d\)
• H (hlava): pripočítame \(p\) ku \(d\), takže vznikne dvojica čísel \(p\) a \(d+p\)

Na konci dňa mala Dáša dvojicu čísel \(P\) a \(D\). Našou úlohou bolo z týchto čísel zistiť, s akou hodnotou \(p\) začínala a tiež prísť na to, čo jej padalo na minci.

Na začiatok urobme niekoľko užitočných pozorovaní:

• Dáša nikdy nemohla mať záporné číslo alebo nulu.

  Obe čísla \(p, d\) sú ráno väčšie ako nula a operácie \(Z\) a \(H\) k nim hodnoty pričítavajú. No a súčet dvoch kladných čísel môže byť iba kladný.

• Okrem rána (pred prvým hodom) sa Dášine čísla nemôžu rovnať.

  Predstavme si, že v nejakom momente má Dášenka čísla \(P'\) a \(D'\). Po ďalšom hode bude mať čísla \(P'+D'\) a \(D'\) (resp. \(P'\) a \(D'+P'\)). Ak by sa ale tieto dve čísla rovnali, tak platí \(P'+D' = D'\) (resp. \(P' = D'+P'\)), čo znamená, že \(P' = 0\) (resp. \(D' = 0\)). Podľa predchádzajúceho pozorovania sa však niečo také nemôže stať.

Podúloha a)

Dášenka doniesla Bobovi čísla \(P=15\) a \(D=35\).

Ako zistíme začiatočné čísla a postupnosť hodov? Najlepšie by bolo odsimulovať Dášenkino hádzanie, nevieme však, kde začať. Mohli by sme teda vyskúsať všetky možné začiatočné hodnoty \(p\). Tých je iba 15. Uvedomme si totiž, že platí \(p \leq P = 15\) a \(p \leq D = 35\). Nepoznáme však ani postupnosť hodov, museli by sme vyskúšať všetky možnosti toho, čo mohla Dáša hodiť.

Skúšať všetky možnosti hodov je naozaj náročné a počet možností stúpa veľmi rýchlo s rastúcim počtom hodov. V prvom kroku mohla hodiť buď \(H\) alebo \(Z\). To sú dve možnosti. V druhom kroku síce platí to isté, ale už musíme rátať s tým, čo padlo v prvom kroku, takže máme štyri možnosti: \(ZZ, ZH, HZ, HH\). Pri troch hodoch je tých možností opäť dvakrát viac, lebo pre každú z postupností pre dva hody máme dve možnosti čo mohlo padnúť ďalšie: \(ZZ\pmb{Z}, ZZ\pmb{H}, ZH\pmb{Z}, ZH\pmb{H}, HZ\pmb{Z}, HZ\pmb{H}, HH\pmb{Z}, HH\pmb{H}\). Každým hodom sa počet možností, ktoré musíme vyskúšať, zdvojnásobí. Už pre 10 hodov musíme vyskúšať viac ako \(1\,000\) možností, preto to nevyzerá ako správny postup.

Skúsme sa teda na to pozrieť zozadu. Pri tomto postupe aspoň poznáme výsledné hodnoty \(P\) a \(D\). Čísla, ktoré mala Dášenka pred posledným hodom si označme \(P'\) a \(D'\), ich hodnotu zatiaľ nepoznáme. Následne padla minca, čísla sa zmenili a dostali sme čísla \(P\) a \(D\). Posledný hod mohol byť \(Z\) aj \(H\), skúsme preto vyskúšať obe možnosti.

Posledný hod: znak

Ak čísla pred posledným hodom boli \(P'\) a \(D'\) a hodili sme \(Z\), tak nové čísla musia byť \(P'+D'\) a \(D'\). Zároveň vieme, že nové čísla sú \(P = 15\) a \(D = 35\) (keďže to bol posledný hod), takže musí platiť:

\[P'+D' = P = 15\] \[D' = D = 35\]

Z týchto rovníc vyplýva, že \(D' = 35\) a \(P' + 35 = 15\), teda \(P' = -20\).

To sa ale vylučuje s naším pozorovaním – nemôžeme mať záporné číslo. Posledný hod teda nemohol byť znak.

Posledný hod: hlava

Budeme postupovať úplne rovnako ako predtým.

Čísla pred posledným hodom boli \(P'\) a \(D'\) a hodili sme \(H\), takže nové čísla musia byť \(P'\) a \(D'+P'\). Zároveň vieme, že nové čísla sú \(P = 15\) a \(D = 35\) (keďže to bol posledný hod), takže musí platiť:

\[P' = P = 15\] \[D'+P' = D = 35\]

Z toho jasne vyplýva, že \(P' = 15\) a \(D' + 15 = 35\), teda \(D' = 20\).

Obe čísla su kladné, takže posledný hod mohol byť \(H\). Keďže sme však hod znak vylúčili, posledný hod musela byť hlava.

Zvyšné hody

Teraz však máme úplne rovnakú úlohu, ale s číslami \(15\) a \(20\). Rovnakou úvahou ako predtým by sme zistili, že posledný hod nemohol byť znak (čísla pred hodom by museli byť \(-5\) a \(20\)), ale musel byť hlava. Takže dostaneme čísla \(15\) a \(5\). A takto postupujeme, až kým nemáme dve rovnaké čísla:

Začiatočné čísla \(p\) a \(d\) boli rovné číslu 5, a skrátená postupnosť hodov je 2Z, 2H.

Tento príklad bol pekný. Keď sme išli odzadu, tak v každom kroku nám vyšla iba jedna možnosť hodu, druhá nebola možná, lebo viedla k záporným číslam. Musí to tak však byť vždy? Vieme si z tohto príkladu odvodiť aj nejaké všeobecnejšie pozorovania?

• Ak máme výsledné čísla \(P\) a \(D\), tak predchádzajúce čísla \(P'\) a \(D'\) vieme zistiť pomocou jedného odčítania (ak vám nasledujúce rovnice nie sú jasné, skúste sa vrátiť vyššie, kde sme odvádzali hodnoty \(P'\) a \(D'\)):

  • Hod \(Z\):

    \[P' = P - D\] \[D' = D\]

  • Hod \(H\):

    \[P' = P\] \[D' = D - P\]
• Ak sú čísla \(P\) a \(D\) rôzne, tak práve jedno z \(P-D\) alebo \(D-P\) je kladné.
• Aby sme nedostali záporné čísla, tak vždy odčítavame menšie číslo od väčšieho. To zároveň určuje, posledný hod mince. Ak je menšie prvé číslo, posledný hod bol \(H\), ak je menšie druhé číslo, posledný hod bol \(Z\).
• Keďže čísla sú vždy rôzne, tak nikdy nemáme na výber medzi hlavou a znakom. Rovnaké čísla môžeme mať iba na začiatku nášho zisťovania, keď sme prišli k hľadaným číslam z rána.
• Postupnosť hodov zisťujeme odzadu.

Podúloha b)

Dášenka doniesla Bobovi čísla \(P=111\) a \(D=9\).

Rovnako ako v podúlohe a) to vieme spraviť postupným odčítavaním odzadu, čím dostaneme takýto výsledok:

Určite vás ale nebavilo odčítavať 9 stále a stále dookola – až dvanásťkrát. Nedalo by sa to spraviť rýchlejšie?

Vieme že 9 potrebujeme odčítať od čísla 111 toľkokrát, aby toto prvé číslo bolo menšie ako 9. Takže ak je rozdiel medzi 111 a 9 rovný 102, tak potrebujeme odčítať toľko 9, aby ich súčet bol aspoň 102. Zároveň to ale nemôžeme prehnať a dostať sa k záporným číslam. Hľadáme teda najmenší počet 9, ktorých súčet je aspoň 102.

Naša otázka teda je: “Koľkokrát musíme vynásobiť číslo 9, aby sme dostali číslo 102?”, na čo si vieme odpovedať pomocou delenia \(102 / 9 \doteq 11,3\). Vidíme, že 11 deviatiek nebude stačiť a potrebujeme ich 12 (lebo \(12 \cdot 9 = 108\) a to je naozaj väčšie ako 102). Mohli by sme teda povedať, že potrebný počet deviatiek je číslo \(\frac{102}{9}\) zaokrúhlené nahor, teda 12.

Iný pohľad na to je, že potrebujeme od 111 odčítavať 9 kým nebudeme dostávať záporné čísla. Čo je vlastne inak povedané, “Koľkokrát sa deviatka zmestí do čísla 111?”. To sa dá vyjadriť podielom \(111 / 9 \doteq 12,3\), ktorý zaokrúhlime nadol, dostaneme teda číslo \(12\).

Vidíme, že oba postupy nám dávajú rovnaký výsledok – 12 odčítaní, ktorý sedí s naším predošlým riešením. Namiesto dvanástich odčítaní teda spravíme jedno delenie, do skrátenej postupnosti hodov si zapíšeme \(12Z\) a nové hodnoty \(P\) a \(D\) budú \(111 - 12\cdot 9\), teda 3 a 9.

Tento postup vieme samozrejme zovšeobecniť. Majme čísla \(P\) a \(D\), o ktorých predpokladajme, že \(P > D\) (ak to bude naopak, tak postup bude takmer rovnaký). Chceme preto zistiť, koľko znakov v rade padlo na minci. Pýtame sa teda, koľkokrát sa hodnota \(D\) zmestí do \(P\), čo vieme zistiť pomocou celočíselného delenia \(P / D\) (celočíselné delenie zaokrúhľuje nadol), túto hodnotu si označme \(k\). Následne si do postupnosti hodov zapíšeme \(kZ\), hodnota \(D\) ostane nezmenená a novú hodnotu \(P\) vypočítame ako \(P - k\cdot D\).

Môžete si všimnúť ešte jednu zaujímavú vlastnosť. Od čísla \(P\) odpočítavame hodnotu \(D\) najviac krát ako vieme. To čo nám ostane je preto zvyšok po delení čísla \(P\) číslom \(D\). Tomu naozaj zodpovedá aj hodnota \(P - k\cdot D\). A keďže väčšina programovacích jazykov vie zvyšok po delení počítať priamo, najrýchlejší spôsob ako zistiť novú hodnotu \(P\) je použiť príkaz P = P%D (% označuje zvyšok po delení).

Čo ak je nová hodnota nula? Túto možnosť, že \(P - k\cdot D = 0\) sme doteraz ignorovali. Všimnime si však, že v takomto prípade je číslo \(P\) násobkom čísla \(D\). Ak teda od \(P\) odčítam \(D\) iba \(k-1\) krát, dostanem dve rovnaké čísla, obe rovné \(D\). Takáto situácia preto nastane iba raz, a to na konci nášho výpočtu. Do skrátenej postupnosti vtedy zapíšeme \((k-1)Z\) a za hodnoty čísel \(p\) a \(d\) dosadíme aktuálne \(D\).

Podúloha c)

Vedeli by ste riešiť takýto problém pre ľubovoľnú dvojicu čísel \(P\) a \(D\)?

V predošlých častiach sme si ukázali všetky potrebné postupy, ostáva spojiť ich dokopy.

• Ak je \(P > D\) tak zisťujeme dĺžku sekvencie znakov

  \(k = \frac{P}{D}\) zaokrúhlené nadol

  hodnota \(D\) sa nemení

  • Ak \(P\) nie je deliteľné \(D\)

    zmeníme hodnotu \(P\) na \(P - k\cdot D\)

    zapíšeme \(kZ\) do skrátenej postupnosti

  • Ak je \(P\) deliteľné \(D\)

    zmeníme hodnotu \(P\) na \(P - (k-1)\cdot D\) (čo je vlastne \(D\))

    zapíšeme \((k-1)Z\) do skrátenej postupnosti

• Ak je \(D > P\) tak zisťujeme dĺžku sekvencie hláv

  \(k = \frac{D}{P}\) zaokrúhlené nadol

  hodnota \(P\) sa nemení

  • Ak \(D\) nie je deliteľné \(P\)

    zmeníme hodnotu \(D\) na \(D - k\cdot P\)

    zapíšeme \(kH\) do skrátenej postupnosti

  • Ak \(P\) delí \(D\)

    zmeníme hodnotu \(D\) na \(D - (k-1)\cdot P\) (čo je vlastne \(P\))

    zapíšeme \((k-1)H\) do skrátenej postupnosti

Tento postup spraví jeden krok nášho postupu. Budeme ho preto opakovať až kým sa čísla \(P\) a \(D\) nebudú rovnať. Všimnite si naviac, že v každom kroku sa zmení to, ktoré číslo je väčšie, takže naša skrátená postupnosť bude striedať hlavy a znaky.

Tento postup vieme samozrejme zapísať aj v ľubovoľnom programovacom jazyku. Skúste si pozrieť nižšie uvedenú implementáciu v Pythone. Zistíte, že sa veľmi podobá tomu, ako sme si to zapísali pred chvíľou.

print("Napis prve cislo:")
P = int(input())                                    # napr. číslo 111
print("Napis druhe cislo:")
D = int(input())                                    # napr. číslo 9

zoznam = []                                         # tu zapisujeme skrátenú postupnosť
while P != D:                                       # kým sa čísla P a D nerovnajú opakuj
    print(P,D)
    if P > D:
        k = P // D # celočíselné delenie
        if P % D != 0:  # číslo P nedáva po delení D zvyšok 0, nie je ním teda deliteľné
            P = P - k*D
            zoznam.append((k, 'Z'))
        elif P % D != 0:  # zvyšok je 0, P je deliteľné D
            P = P - (k-1)*D
            zoznam.append((k-1, 'Z'))
    elif D > P:
        k = D // P # celočíselné delenie
        if D % P != 0: # číslo D nie je deliteľné P 
            D = D - k*P
            zoznam.append((k, 'H'))
        elif D % P == 0:  # číslo D je deliteľné P
            D = D - (k-1)*P
            zoznam.append((k-1, 'H'))

# keďže zisťujeme ťahy odzadu, tak musíme zoznam obrátiť
zoznam.reverse()
print("Skrateny zoznam hodov:", zoznam)             # [(2, 'H'), (12, 'Z')]

# vypiseme aj zaciatocne cislo
print("Rano dostala Dasa cisla rovne hodnote:", P)  # 3

Je to dostatočne rýchle?

Pokúsme sa zamyslieť nad tým, koľkokrát musíme zopakovať vyššie uvedený postup. V jednom kroku sa rozhodneme, ktoré z čísel \(P\) a \(D\) je väčšie a toto väčie číslo upravíme, pričom bude menšie ako druhé číslo. Takže to, ktoré číslo je väčšie, sa bude v každom kroku striedať. Ak je najskôr \(P > D\), tak hneď potom bude \(P < D\), následne opäť \(P > D\), a tak ďalej až kým \(P = D\).

Pri každom tomto kroku vložíme do skrátenej postupnosti jeden záznam, teda jedno číslo a hod \(Z\) alebo \(H\). Trvanie nášho programu bude teda priamo úmerné dĺžke skrátenej postupnosti. Stále však nevieme, aká dlhá bude táto postupnosť a či to náš algoritmus zvládne aj pre čísla veľkosti milión.

Pozrime sa bližšie na to, ako sa mení číslo \(P\). V každom druhom kroku sa veľkosť tohto čísla zmenší, keďže hodnoty \(P\) a \(D\) sa zmenšujú nastriedačku. Ako rýchlo sa toto číslo zmenšuje? Ak by sa v každých dvoch krokoch zmenšilo iba o 1, tak je to zlé. Pretože naša skrátená postupnosť by potom mala dĺžku \(2\cdot P\), čo je veľa. Môže sa však číslo \(P\) zmenšiť o tak málo? Skúste nájsť takú dvojicu \(P\) a \(D\), že po úprave čísla \(P\) sa toto číslo zmenší iba o 1.

V skutočnosti totiž platí, že hodnota čísla \(P\) sa musí pri jednej úprave zmenšiť aspoň na polovicu. Ukážme si, prečo je to tak. Všimnite si, že číslo \(P\) sa mení v závislosti od čísla \(D\). Dokonca sme si ukázali, že výsledná hodnota \(P\) musí byť po úprave menšia ako hodnota \(D\). Ak je teda číslo \(D\) malé, bude malá aj nová hodnota \(P\). Nová hodnota \(P\) preto bude aspoň polovičná ak platí, že \(D \leq \frac{P}{2}\) – číslo \(D\) je menšie ako polovica \(P\) a preto aj \(P\) bude po úprave menšie ako jeho polovica.

Čo však v prípade, keď \(D > \frac{P}{2}\)? Pozrime sa na to, čo spraví náš algoritmus. Najskôr zistí, koľkokrát sa do čísla \(P\) zmestí číslo \(D\). Odpoveďou je raz, pretože \(D\) je väčšie ako polovica \(P\), takže dvakrát sa tam nezmestí. V ďalšom kroku sa od \(P\) jedenkrát odpočíta číslo \(D\). No a výsledok musí byť menší ako polovica \(P\). Ak totiž máte číslo \(P\) a zoberiete z neho viac ako jeho polovicu (číslo \(D\)), ostane vám menej ako polovica (nová hodnota \(P\)).

Tým pádom sa po každých dvoch krokoch hodnota čísla \(P\) zmenšila aspoň na polovicu. Čo sa stane, ak bude číslo \(P\) milión? V najhoršom prípade sa toto číslo zakaždým zmenší presne na polovicu až kým z neho neostane číslo 1, čo je najmenšie číslo, s ktorým Dášenka mohla začínať.

\[1000000 / 2 = 500000 / 2 = 250000 / 2 = 125000 / 2 = 62500 / 2 = 31250 / 2 = 15625 / 2 \doteq 7812 / 2 = 3906\] \[3906 / 2 = 1953 / 2 \doteq 976 / 2 = 488 / 2 = 244 / 2 = 122 /2 = 61 / 2 \doteq 30 / 2 = 15 / 2 \doteq 7 / 2 \doteq 3 / 2 \doteq 1\]

Predošlý zápis znázorňuje, ako by sa hodnota \(P\) zmenšovala¹. Vidíme, že na to, aby sme z nej dostali 1 potrebujem iba 19 krokov. Samozrejme, nezabudnime, že hodnota \(P\) sa zmení iba v každom druhom kroku, niekedy sa totiž musí zmenšovať aj \(D\). Stále z toho však vychádza, že nám stačí 38 krokov. A aj to iba v najhoršom možnom prípade.

Pre zaujímavosť, číslo 19 – koľkrát môžme vydeliť číslo \(1\,000\,000\) číslom 2 – je aj približná hodnota dvojkového logaritmu z čísla \(1\,000\,000\). Logaritmovanie je v podstate opak umocňovania.

Keď chceme skrátene zapísať súčin veľa dvojok, tak to môžme skrátene napísať pomocou umocnenia: \[2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2 = 2^8\]

Poprípade súčin \(k\) dvojek je \(2^k\).

Logaritmom sa označuje odpoveď na otázku: Na koľkú musíme umocniť číslo 2, aby sme dostali výsledok \(y\)? Ak by sme teda chceli zistiť, na koľkú treba umocniť 2, aby sme dosali číslo 256 (teda hľadáme \(x\) rovnice \(2^x = 256\)), tak odpoveďou by bol práve \(\log_{2}(256)\), čo je 8.

O našom postupe by sme preto mohli povedať, že potrebuje najviac \(2\cdot \log_{2}P\) krokov.

Podúloha d)

Vedeli by ste dokázať, že počiatočné číslo \(p\) delí obe výsledné čísla \(P\) a \(D\)?

Začať môžeme tým, že sa vrátime ku konkrétnym príkladom z úloh a) a b). Všimnime si, že v oboch prípadoch platí, že číslo \(p\) nedelí len výsledné čísla \(P\) a \(D\), ale všetky čísla, ktoré si Dášenka zapísala. V podúlohe a) vidíme iba násobky čísla 5, v podúlohe b) iba násobky čísla 3. To je podozrivé.

Pozrime sa teda, čo sa deje keď Dášenka začne hádzať mincou. Začína s dvoma číslami \(p\) a \(d\), ktoré sú rovnaké, a teda zjavne sú obe deliteľné číslom \(p\). Po prvom hode mincou môže mať Dášenka zapísané čísla \(2p\) a \(p\), ktoré sú opäť deliteľné číslom \(p\). Po druhom hode mincou má buď dvojicu \(3p\) a \(p\), alebo dvojicu \(2p\) a \(3p\), čo sú všetko násobky \(p\).

No a táto vlastnosť sa nezmení. Čo totiž robí Dášenka? Jedno číslo nahradí súčtom a druhé nechá nezmenené. Ale ak sčítame dve čísla deliteľné číslom \(p\), tak opäť dostaneme číslo deliteľné \(p\). Skúsme si to ukázať o niečo formálnejšie. Číslo deliteľné \(p\) si vieme zapísať ako \(a\cdot p\) pre nejaké kladné \(a\). Zoberme si teda ľubovoľné dve čísla deliteľné \(p\), ktoré vieme zapísať ako \(a \cdot p\) a \(b \cdot p\). Ich súčet je \(a\cdot p + b\cdot p = (a + b)\cdot p\). Tento súčet je ale zjavne opäť deliteľný číslom \(p\), lebo sa dá zapísať ako \(c\cdot p\), pre \(c = a + b\).

Keďže Dášenka začína s dvoma číslami deliteľnými číslom \(p\) (dvojica \(p\), \(d\)) a robí iba operáciu sčítanie, všetky čísla, ktoré zapisuje sú naďalej deliteľné číslom \(p\). Tým pádom to platí aj pre výsledné čísla \(P\) a \(D\).

Podúloha e)

Vedeli by ste dokázať, že ak nejaké číslo \(x\) delí obe výsledné čísla \(P\) a \(D\), tak delí aj pôvodné číslo \(p\)?

Skúsme postupovať podobne ako v podúlohe d). Zoberme si číslo \(x\), ktoré delí aj \(P\) aj \(D\). Tieto dve čísla sa teda dajú zapísať ako \(P = a\cdot x\) a \(D = b \cdot x\), pre vhodné \(a\) a \(b\). Čo sa s týmito číslami dialo krok pred tým? V podúlohe a) sme si ukázali, že hodnoty predchádzajúcich čísel získame tak, že menšie číslom nezmeníme a od väčšieho to menšie odčítame. Tvárme sa teda, že \(P > D\), pre opačný prípad by sme robili to isté, akurát naopak.

Hodnota \(D\) ostane rovná \(b \cdot x\), ale hodnota \(P\) sa zmení na rozdiel týchto dvoch čísel. Bude preto platiť, že \(P = a\cdot x - b\cdot x\). To však vieme zapísať ako \(P = (a-b)\cdot x\). Nová hodnota čísla \(P\) bude teda opäť deliteľná číslom \(x\).

Naviac, táto vlastnosť platí všeobecne a vyššie máme uvedený aj jej dôkaz. Ak si zoberieme dve čísla deliteľné \(x\), tak ich rozdiel bude opäť deliteľný číslom \(x\). Pri našom postupe teda budeme celý čas pracovať s číslami, ktoré sú deliteľné číslom \(x\). To bude platiť aj keď sa na konci našeho postupu dostaneme k číslam \(p\) a \(d\). Ak teda číslo \(x\) delí výsledné čísla, delí aj začiatočné \(p\).

Čo vyplýva z vlastností d) a e) o čísle \(p\)?

V podúlohe d) sme ukázali, že číslo \(p\) delí obe čísla \(P\) a \(D\). Takúto hodnotu označujeme ako spoločný deliteľ. Podúloha e) zase hovorí, že každý spoločný deliteľ \(x\) čísel \(P\) a \(D\) delí aj číslo \(p\). Z toho ale vyplýva, že \(x \leq p\). Uvedomme si, že ak nejaké číslo \(a\) delí číslo \(b\), tak \(b\) musí byť väčšie alebo rovné \(a\).

Ak je teda každý spoločný deliteľ menší alebo rovný ako \(p\) tak to značí, že \(p\) je najväčší spoločný deliteľ čísel \(P\) a \(D\).

Na záver

V tejto úlohe sme teda celý čas počítali najväčšie spoločné delitele dvoch čísel. A postup, ktorý ste počas toho vymysleli sa volá Euklidov algoritmus a je to najrýchlejší spôsob ako túto hodnotu vypočítať.

Viac o Euklidovom algoritme si môžete prečítať na Wikipédii (https://sk.wikipedia.org/wiki/Euklidov_algoritmus). Jediný rozdiel s naším riešením je ten, že klasický Euklidov algoritmus skončí, keď je jedno z čísel rovné nule a nie keď sú rovnaké. Vďaka tomu netreba špeciálne ošetrovať podmienku deliteľnosti čísla \(P\) číslom \(D\).