MATEMATICKÁ ČÍTANKA

Deliteľnosť ^[6]

Na bankete v jednej ZOO vznikla diskusia o tom, kedy treba oslavovať tzv. okrúhle výročia. Opice boli za násobky čísla desať, lebo mali na každej ruke po päť prstov, sliepky navrhovali ako okrúhle výročia násobky čísla šesť, lebo u nich má každá po troch prstoch na oboch nohách a pochopiteľne používajú pozičnú číselnú sústavu so základom šesť, kone navrhovali dvojkovú sústavu, lebo na oboch predných nohách majú po jednom kopyte. Nakoniec sa dohodli (aj vzhľadom na to, že o slovo sa hlásili aj pavúky a stonožky), že výnimočnosť čísla nebude závisieť od používanej číselnej sústavy.

Pri hľadaní vhodného návrhu využime známy fakt, že niektoré čísla sú násobkami iných. Napríklad číslo $66$ sa dá napísať ako: $$66 = 1 \cdot 66 = 2 \cdot 33 = 6 \cdot 11$$

Hovoríme, že $66$ je násobkom čísiel $1, 2, 3, 6, 11, 22, 33, 66$, alebo tiež, že čísla $1, 2, 3, 6, 11, 22, 33, 66$ sú deliteľmi čísla $66$.

Dohodnime sa, že počet deliteľov čísla $\bf{n}$ budeme označovať symbolom $\bf{f(n)}$.

Iste viete, že číslo $\bf{n}$ je prvočíslom práve vtedy, ak $\bf{f(n) = 2}$. Číslo $\bf{n}$ sa volá zložené práve vtedy, keď je $\bf{f(n) > 2}$. Ako uvidíte, prvočísla sú skutočne výnimočné čísla

Koľko existuje prvočísel? Na túto otázku odpovedal už Euklides. Uvažoval asi takto^{[ 7]}:

Keby bol počet prvočísel konečný, napríklad existovali by prvočísla $\bf{p_1, p_2, ... p_n}$, potom číslo $\bf{p_1 \cdot p_2 \cdot ... p_n + 1}$ nie je prvočíslom, lebo je väčšie od každého z prvočísel $\bf{p_i}$, ale nie je ani zloženým číslom, lebo nie je deliteľné žiadnym z prvočísel $\bf{p_i}$. Teda predpoklad, že prvočísel je konečný počet vedie ku sporu a preto je pravda, že počet prvočísel nie je konečný.

Márne boli snahy nájsť nejaký vzorec, ktorý by vypočítal ako vyzerá v poradí podľa veľkosti $n-té$ prvočíslo. Márne boli aj snahy nájsť vzorec, ktorý by po dosadení ľubovoľného čísla $n$ dával ako výsledok prvočíslo.

Prvočísla aj dnes svojim správaním sa vzbudzujú záujem matematikov. Zdanlivý chaos s akým sú rozložené medzi číslami, provokoval matematikov nájsť v tomto chaose nejaké zákonitosti. Hľadaním čo najväčších prvočísel sa testujú schopnosti nových počítačov ^[8]. Rozložiť skutočne veľké číslo na súčin dvoch prvočísel je natoľko obťažná úloha, že sa využíva pri kódovaní prenášaných správ^[9].

Na vyhľadávanie prvočísel sa používali rôzne algoritmy. Prvý, ktorý sa stal známym sa volá Eratosténovo sito. Tento spôsob sa hodí len pre relatívne malé čísla.

Mnoho ďalších zaujímavých poznatkov o prvočíslach sa môžete dozvedieť na:
http://mathworld.wolfram.com/PrimeNumber.html
http://www.cut-the-knot.org/induction.shtml

Postup, ktorý sme použili v hárku 2 zošitu Delitele, svedčí o tom, že každé prirodzené číslo (väčšie ako $1$) sa dá rozložiť na súčin prvočísiel^[10]. Že sa to dá urobiť (až na poradie činiteľov) jediným spôsobom, dokázal už Euklides. Pri dôkaze použil jednoduchý algoritmus na výpočet najväčšieho spoločného delitela dvoch čísel.

Hľadáme $\bf{N \cdot S \cdot D(A;B)}$.

Nech $\bf{A > B}$. Vydelíme číslo $\bf{A}$ číslom $\bf{B}$. $\bf{A = k_1 \cdot B + C}$, keďže $\bf{C = A – k_1 \cdot B}$, tak každý spoločný deliteľ čísiel $\bf{A}$ a $\bf{B}$ je aj deliteľom čísla $\bf{C}$, navyše platí $\bf{C \lt B}$. Postup opakujeme, vydelíme číslo $\bf{B}$ číslom $\bf{C}$. $\bf{B = k_2 \cdot C + D}$, keďže $\bf{D = B – k_2 \cdot C}$, tak každý spoločný deliteľ čísiel $\bf{B}$ a $\bf{C}$ je aj deliteľom čísla $\bf{D}$, navyše platí $\bf{D \lt C}$.

Takto dostávame klesajúcu postupnosť prirodzených čísel, ktorá je preto nutne konečná. Posledný nenulový zvyšok je hľadaným najväčším spoločným deliteľom. Pozrite si to v zošite Euklid.