Rozklad na prvočísla

Každé prirodzené číslo väčšie ako 1 je buď prvočíslo, alebo sa dá zapísať ako súčin prvočísel — napríklad 360 = 2 · 2 · 2 · 3 · 3 · 5. Ukážeme si, čo sú delitele a násobky, ako spoznať deliteľnosť bez delenia, ako nájsť rozklad stromom aj delením pod sebou a na čo je rozklad dobrý.

Deliteľ a násobok

Ak sa dá číslo a vydeliť číslom b bezo zvyšku, hovoríme, že a je deliteľné číslom b. Číslo b je potom deliteľ čísla a a číslo a je násobok čísla b.

Napríklad 12 : 3 = 4 bezo zvyšku. Preto je 3 deliteľ čísla 12 a 12 je násobok čísla 3. To isté zapíšeme aj súčinom: 12 = 3 · 4.

• Delitele čísla 12 sú 1, 2, 3, 4, 6 a 12. Hľadáme ich po dvojiciach: 12 = 1 · 12 = 2 · 6 = 3 · 4.
• Násobky čísla 4 sú 4, 8, 12, 16, 20, … — je ich nekonečne veľa.
• Číslo 1 je deliteľom každého čísla a každé číslo je deliteľom samého seba.
• Číslo 12 nie je deliteľné piatimi: 12 : 5 = 2, zvyšok 2.

Prvočísla a zložené čísla

• Prvočíslo je prirodzené číslo, ktoré má práve dva rôzne delitele: číslo 1 a samo seba. Napríklad 7 má delitele len 1 a 7.
• Zložené číslo má viac ako dva delitele. Dá sa zapísať ako súčin dvoch menších prirodzených čísel, napríklad 15 = 3 · 5 alebo 9 = 3 · 3.
• Číslo 1 má jediného deliteľa — samo seba. Preto nie je ani prvočíslo, ani zložené číslo.

Prvočísla do 100 (je ich 25):

• 2
• 3
• 5
• 7
• 11
• 13
• 17
• 19
• 23
• 29
• 31
• 37
• 41
• 43
• 47
• 53
• 59
• 61
• 67
• 71
• 73
• 79
• 83
• 89
• 97

Číslo 2 je jediné párne prvočíslo. Každé väčšie párne číslo má aspoň tri delitele (1, 2 a samo seba), takže je zložené.

Prečo 1 nie je prvočíslo? Nemá dva rôzne delitele, len jeden. Je za tým aj dôležitý dôvod, ktorý uvidíš pri rozklade: keby sme 1 považovali za prvočíslo, rozklad čísla na prvočísla by nebol jediný.

Znaky deliteľnosti

Či je číslo deliteľné malým číslom, často zistíme priamo z jeho číslic — deliť netreba. Tieto znaky deliteľnosti nám pomôžu pri hľadaní prvočiniteľov.

Prečo to funguje?

• 2, 5 a 10: každé číslo je súčet celých desiatok a jednotiek, napríklad 1 935 = 193 · 10 + 5. Desiatky sú vždy deliteľné dvoma, piatimi aj desiatimi (lebo 10 = 2 · 5), preto rozhoduje len posledná číslica.
• 4 a 25: 100 = 4 · 25, takže celé stovky sú vždy deliteľné štyrmi aj dvadsiatimi piatimi. Rozhoduje posledné dvojčíslie: 9 324 = 93 · 100 + 24.
• 8: 1 000 = 8 · 125, preto rozhoduje posledné trojčíslie.
• 3 a 9: 10 = 9 + 1, 100 = 99 + 1, 1 000 = 999 + 1. Číslo 5 832 sa preto dá zapísať ako 5 · 999 + 8 · 99 + 3 · 9 + (5 + 8 + 3 + 2). Čísla 9, 99 a 999 sú deliteľné tromi aj deviatimi, takže o deliteľnosti rozhoduje len ciferný súčet 5 + 8 + 3 + 2 = 18.
• 6: 6 = 2 · 3 a 2 a 3 sú rôzne prvočísla. Číslo deliteľné dvoma aj tromi je preto deliteľné aj šiestimi. Pozor, takto sa znaky spájať nedajú vždy: číslo 12 je deliteľné dvoma aj štyrmi, ale ôsmimi nie.

Rozklad na prvočinitele

Rozložiť číslo na prvočinitele znamená zapísať ho ako súčin prvočísel. Prvočísla v takom súčine voláme prvočinitele. Napríklad 12 = 2 · 2 · 3. Rozklad hľadáme pri zložených číslach — prvočíslo sa už ďalej rozložiť nedá.

1. postup: strom rozkladu

Číslo zapíšeme ako súčin dvoch menších čísel a nakreslíme od neho dve vetvy. Každé zložené číslo, ktoré takto vznikne, rozložíme rovnako ďalej. Keď na konci vetvy ostane prvočíslo, zakrúžkujeme ho — táto vetva je hotová. Rozklad tvoria všetky zakrúžkované čísla.

Strom si môžeš poskladať aj sám, rozdelenie po rozdelení, v labe Strom rozkladu a sito (Factor Tree & Prime Sieve).

2. postup: delenie pod sebou

Číslo vydelíme najmenším prvočíslom, ktorým sa dá deliť bezo zvyšku, a podiel napíšeme pod neho. S podielom pokračujeme rovnako, až kým nedostaneme 1. Prvočísla v pravom stĺpci tvoria rozklad. Najmenšie prvočíslo hľadáme v poradí 2, 3, 5, 7, 11, … a pomáhame si znakmi deliteľnosti.

Oba postupy dajú ten istý výsledok. Strom je voľnejší (začať môžeme akýmkoľvek súčinom), delenie pod sebou je prehľadnejšie pri veľkých číslach.

Zápis s mocninami

Rovnaké prvočinitele zapíšeme skrátene ako mocninu: súčin 2 · 2 · 2 zapíšeme 2³ (čítame „dva na tretiu“) a 3 · 3 zapíšeme 3² („tri na druhú“). Malé číslo hore — exponent — hovorí, koľkokrát sa prvočíslo v súčine opakuje.

Prvočinitele píšeme od najmenšieho po najväčší a exponent 1 nepíšeme (5 = 5¹). Viac o mocninách nájdeš v téme Mocniny a odmocniny.

Kedy môžeme prestať skúšať

Pri hľadaní prvočiniteľov netreba skúšať všetky prvočísla. Stačí skúšať prvočísla p, pre ktoré p · p nie je väčšie ako číslo, ktoré práve delíme. Ak žiadne z nich nedelí, číslo je prvočíslo. Prečo? Keby sa dalo zapísať ako súčin dvoch čísel, ktoré sú obe väčšie ako takéto p, bol by ich súčin väčší ako naše číslo.

Je 97 prvočíslo? Skúšame 2, 3, 5 a 7. Prvočíslo 11 už skúšať netreba, lebo 11 · 11 = 121 je viac ako 97. Žiadne z čísel 2, 3, 5, 7 číslo 97 nedelí, preto je 97 prvočíslo.

Rozklad je len jeden

Číslo 60 môžeme v strome začať rozkladať rôzne: 60 = 6 · 10, 60 = 4 · 15 alebo 60 = 2 · 30. Strom vyzerá zakaždým inak, ale na konci vetiev sú vždy tie isté prvočísla: 2, 2, 3 a 5.

Teraz vidno aj druhý dôvod, prečo 1 nepočítame medzi prvočísla: keby bola prvočíslom, mohli by sme písať 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3 … a rozklad by nebol jediný. V riešiteľovi na konci stránky si vyskúšaj tlačidlo Iné prvé rozdelenie — strom sa zmení, prvočísla na konci vetiev nie.

Počet deliteľov z rozkladu

Z rozkladu zistíme, koľko deliteľov má číslo, bez toho, aby sme ich všetky hľadali. Vezmime 12 = 2² · 3. Každý deliteľ čísla 12 je súčin, v ktorom je dvojka 0-krát, 1-krát alebo 2-krát (3 možnosti) a trojka 0-krát alebo 1-krát (2 možnosti):

Spolu 3 · 2 = 6 deliteľov: 1, 2, 3, 4, 6 a 12. (Mocnina s exponentom 0 sa rovná 1 — znamená, že prvočíslo v deliteli nie je.) Všeobecne: exponenty z rozkladu zväčšíme o 1 a vynásobíme ich.

Tu e₁, e₂, … sú exponenty prvočiniteľov v rozklade. Číslo 360 = 2³ · 3² · 5 má (3 + 1) · (2 + 1) · (1 + 1) = 4 · 3 · 2 = 24 deliteľov. Prvočíslo má vždy (1 + 1) = 2 delitele — presne ako hovorí jeho definícia.

NSD a NSN z rozkladu

• Najväčší spoločný deliteľ čísel a a b (NSD) je najväčšie číslo, ktoré delí obe. Zapisujeme D(a, b).
• Najmenší spoločný násobok čísel a a b (NSN) je najmenšie číslo, ktoré je deliteľné oboma. Zapisujeme n(a, b).

Obe čísla nájdeme z rozkladov. Pre 24 = 2 · 2 · 2 · 3 a 36 = 2 · 2 · 3 · 3 sú spoločné prvočinitele 2, 2 a 3 — vo Vennovom diagrame ich dáme do prieniku kruhov. V kruhu čísla 24 ostane ešte jedna dvojka, v kruhu čísla 36 jedna trojka.

• D(24, 36) = súčin čísel v prieniku = 2 · 2 · 3 = 12.
• n(24, 36) = súčin všetkých čísel v diagrame = 2 · 2 · 2 · 3 · 3 = 72.

S mocninami: 24 = 2³ · 3 a 36 = 2² · 3². Pre D vezmeme len spoločné prvočísla, každé s menším exponentom: D(24, 36) = 2² · 3. Pre n vezmeme všetky prvočísla, každé s väčším exponentom: n(24, 36) = 2³ · 3².

Vždy platí D(a, b) · n(a, b) = a · b, tu 12 · 72 = 864 = 24 · 36. Ak dve čísla nemajú žiadny spoločný prvočiniteľ, je D(a, b) = 1 a čísla voláme nesúdeliteľné — napríklad 8 a 15.

Najväčší spoločný deliteľ použijeme pri krátení zlomkov: 2436 = 23, lebo čitateľa aj menovateľa vydelíme číslom 12. Najmenší spoločný násobok menovateľov je najmenší spoločný menovateľ. Euklidov algoritmus, ktorým sa D nájde aj bez rozkladu, a ďalšie úlohy nájdeš v téme Deliteľnosť, NSD a NSN.

Eratostenovo sito

Ako nájsť všetky prvočísla do 100 bez toho, aby sme každé číslo skúšali zvlášť? Postup sa pripisuje gréckemu učencovi Eratostenovi z Kyrény (3. storočie pred n. l.), ktorý viedol knižnicu v Alexandrii.

1. Napíšeme čísla od 1 do 100. Číslo 1 hneď vynecháme — nie je prvočíslo.
2. Prvé nevynechané číslo 2 je prvočíslo. Preškrtneme všetky jeho ďalšie násobky: 4, 6, 8, …, 100.
3. Ďalšie nepreškrtnuté číslo 3 je prvočíslo. Preškrtneme jeho násobky. Začať môžeme od 3 · 3 = 9, lebo menší násobok 6 už preškrtla dvojka.
4. Rovnako pokračujeme s prvočíslom 5 (od 5 · 5 = 25) a so 7 (od 7 · 7 = 49).
5. Ďalšie nepreškrtnuté číslo je 11 a 11 · 11 = 121 je viac ako 100. Všetky zložené čísla do 100 sú už preškrtnuté — čísla, ktoré ostali, sú prvočísla.

Prečo stačí začať od p · p? Každý menší násobok čísla p má aj menší prvočiniteľ, a ten ho preškrtol skôr — napríklad 15 = 3 · 5 preškrtla už trojka. Postup sa volá sito, lebo zložené čísla ním „prepadnú“ a prvočísla ostanú. Vyskúšaj si ho na konci stránky.

Riešené príklady

Veľké čísla, aj so stovkami číslic, rozložíš v kalkulačke prvočíselného rozkladu. Strom rozkladu, delenie pod sebou, sito aj NSD a NSN nájdeš aj v labe Strom rozkladu a sito (Factor Tree & Prime Sieve); nadpis labu je po anglicky, ovládanie po slovensky.