Prvočíselný rozklad (také rozklad na prvočinitele nebo rozklad na součin prvočísel) je zápis čísla jako součinu prvočísel. Například 360 = 2 · 2 · 2 · 3 · 3 · 5. Stejná prvočísla se v rozkladu opakují, a proto se rozklad zapisuje zkráceně pomocí mocnin:

`360=2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5`
`360=2^{3}\cdot 3^{2}\cdot 5`

Každé přirozené číslo větší než 1 se dá rozložit na prvočísla, a to jediným způsobem, pokud nezáleží na pořadí činitelů. Tomu se říká základní věta aritmetiky. Prvočíslo je samo svým rozkladem (13 = 13) a čísla 0 a 1 žádný rozklad nemají.

Rozklad najdete tak, že číslo vydělíte nejmenším prvočíslem, které ho dělí beze zbytku, a s podílem pokračujete stejně, dokud nezůstane 1. Prvočísla, kterými jste dělili, tvoří rozklad. Na papíře se to píše do sloupečku se svislou čarou, jak ukazuje oddíl o postupu níže.

Prvočinitel a rozklad na součin prvočísel

Činitel je číslo, které se násobí, a prvočinitel je činitel, který je prvočíslem. Číslo 360 má tři různé prvočinitele: 2, 3 a 5. Proto se úloze říká „rozklad na prvočinitele“ i „rozklad na součin prvočísel“, obojí znamená totéž co prvočíselný rozklad.

Pozor na rozdíl mezi rozkladem na součin a rozkladem na prvočinitele. Zápis 360 = 18 · 20 je rozklad na součin, ale ne prvočíselný, protože 18 ani 20 nejsou prvočísla. Prvočíselný rozklad končí teprve tehdy, když jsou všechny činitele prvočísla. A „rozklad prvočísla“ neexistuje v tom smyslu, že by šlo prvočíslo dál rozložit: jeho rozklad je ono samo. Co prvočíslo je a jak ho poznat, vysvětluje článek Prvočíslo.

Jak rozložit číslo na prvočísla

Ve škole se rozklad zapisuje do sloupečku:

  1. Napište číslo a vpravo od něj svislou čáru.
  2. Najděte nejmenší prvočíslo, které číslo dělí beze zbytku. Zkoušejte postupně 2, 3, 5, 7, 11, 13 ... Prvočíslo napište za čáru.
  3. Podíl napište pod číslo a pokračujte s ním stejně. Stejné prvočíslo může dělit i několikrát za sebou.
  4. Skončíte, když vlevo zůstane 1. Rozklad je součin všech čísel za čárou.

Rozklad čísla 360:

`\begin{array}{r|l} 360 & 2 \\ 180 & 2 \\ 90 & 2 \\ 45 & 3 \\ 15 & 3 \\ 5 & 5 \\ 1 &  \end{array}`

Čte se to po řádcích: 360 : 2 = 180, 180 : 2 = 90, 90 : 2 = 45. Číslo 45 už dvěma dělitelné není, takže přijde na řadu 3: 45 : 3 = 15, 15 : 3 = 5. Pětka je prvočíslo, 5 : 5 = 1 a konec. Za čárou jsou 2, 2, 2, 3, 3, 5, tedy `360=2^{3}\cdot 3^{2}\cdot 5`.

Dělitele najdete rychle podle znaků dělitelnosti: číslo je dělitelné dvěma, když je sudé, třemi, když je jeho ciferný součet dělitelný třemi, a pěti, když končí nulou nebo pětkou. Pro 7 a 13 jednoduchý znak není, tam prostě zkusíte vydělit. Znaky si můžete procvičit v procvičování znaků dělitelnosti a pro konkrétní číslo je ukáže kalkulačka Čím je číslo dělitelné.

Na konci vždy udělejte zkoušku: prvočinitele vynásobte a musí vyjít původní číslo. U 360 je to 8 · 9 · 5 = 72 · 5 = 360.

Příklad 1

Rozložte na prvočinitele číslo 84.

`\begin{array}{r|l} 84 & 2 \\ 42 & 2 \\ 21 & 3 \\ 7 & 7 \\ 1 &  \end{array}`

84 je sudé, 84 : 2 = 42, a 42 je zase sudé, 42 : 2 = 21. Číslo 21 má ciferný součet 3, takže 21 : 3 = 7, a 7 je prvočíslo.

`84=2^{2}\cdot 3\cdot 7`

Zkouška: 4 · 3 · 7 = 12 · 7 = 84.

Příklad 2

Rozložte na prvočinitele číslo 1584.

`\begin{array}{r|l} 1584 & 2 \\ 792 & 2 \\ 396 & 2 \\ 198 & 2 \\ 99 & 3 \\ 33 & 3 \\ 11 & 11 \\ 1 &  \end{array}`

Dvojkou dělíme čtyřikrát, než dostaneme liché číslo 99. Jeho ciferný součet je 18, takže 99 : 3 = 33, pak 33 : 3 = 11, a 11 je prvočíslo.

`1584=2^{4}\cdot 3^{2}\cdot 11`

Zkouška: 16 · 9 = 144 a 144 · 11 = 1584.

Příklad 3

Rozložte na prvočinitele číslo 1309.

Číslo je liché, takže 2 nedělí. Ciferný součet je 1 + 3 + 0 + 9 = 13, takže ani 3. Nekončí nulou ani pětkou, takže ani 5. Zkusíme 7: 1309 : 7 = 187 beze zbytku. Číslo 187 sedmi dělitelné není (7 · 26 = 182, zbytek 5), zkusíme 11: 187 : 11 = 17. A 17 je prvočíslo.

`\begin{array}{r|l} 1309 & 7 \\ 187 & 11 \\ 17 & 17 \\ 1 &  \end{array}`

`1309=7\cdot 11\cdot 17`

Zkouška: 7 · 11 = 77 a 77 · 17 = 1309. U lichých čísel bez zjevného dělitele se rozklad neobejde bez zkoušení sedmičky, jedenáctky a třináctky. Na jedenáctku existuje znak: rozdíl součtu cifer na lichých a na sudých místech musí být dělitelný jedenácti. U 187 je to 1 - 8 + 7 = 0, takže 11 dělí.

Kdy přestat: stačí zkoušet do odmocniny

Někdy po pár krocích zbude číslo, u kterého nevíte, jestli je prvočíslo. Nemusíte zkoušet všechna menší prvočísla. Stačí zkoušet prvočísla do jeho druhé odmocniny. Když žádné z nich nedělí, je to prvočíslo a rozklad je hotový.

Proč to platí: kdyby šlo číslo n zapsat jako a · b, kde a je menší z obou činitelů, pak a · a ≤ a · b = n, tedy a ≤ √n. Složené číslo proto vždy má dělitele, který není větší než jeho odmocnina.

Příklad 4

Rozložte na prvočinitele číslo 354.

`\begin{array}{r|l} 354 & 2 \\ 177 & 3 \\ 59 & 59 \\ 1 &  \end{array}`

354 : 2 = 177. Ciferný součet 177 je 15, takže 177 : 3 = 59. Je 59 prvočíslo? Platí `\sqrt{59}\doteq 7{,}7`, stačí tedy vyzkoušet 2, 3, 5 a 7. Číslo 59 je liché, ciferný součet 14 není dělitelný třemi, nekončí 0 ani 5 a 7 · 8 = 56, zbytek 3. Žádné nedělí, takže 59 je prvočíslo.

`354=2\cdot 3\cdot 59`

U menších čísel totéž udělá kalkulačka Je číslo prvočíslo? a celý rozklad s každým dělením zvlášť ukáže kalkulačka Rozklad na prvočinitele.

Rozkladový strom

Druhý způsob zápisu, který se učí na základní škole, je rozkladový strom. Číslo napíšete jako součin libovolných dvou čísel, která vás napadnou, a každé z nich rozkládáte dál, dokud na koncích větví nezůstanou jen prvočísla (na obrázku v kroužku).

236236362510360začátek 36 · 1022248533945360začátek 8 · 45

Oba stromy začínají jinak, a přesto končí u stejných prvočísel: tři dvojky, dvě trojky a jedna pětka. To je právě jednoznačnost rozkladu ze základní věty aritmetiky. Strom je rychlý, když rozklad na dvě čísla hned vidíte (360 = 36 · 10). U čísla, kde nic takového nevidíte, je spolehlivější sloupeček, protože v něm stačí zkoušet prvočísla od nejmenšího.

Zápis rozkladu pomocí mocnin

Když se prvočíslo v rozkladu opakuje, napíšete ho jednou a počet opakování dáte do exponentu: 2 · 2 · 2 · 2 = 24. Prvočísla se píší od nejmenšího a exponent 1 se nepíše.

`1584=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 11`
`1584=2^{4}\cdot 3^{2}\cdot 11`

Pozor, 24 znamená 2 · 2 · 2 · 2 = 16, ne 2 · 4. Při zkoušce nejdřív spočítejte mocniny, pak je vynásobte.

K čemu je prvočíselný rozklad

Největší společný dělitel a nejmenší společný násobek

Z rozkladů dvou čísel se oba hned přečtou. Vezměme 84 a 90:

`84=2^{2}\cdot 3\cdot 7`
`90=2\cdot 3^{2}\cdot 5`

Největší společný dělitel je součin prvočinitelů, které mají obě čísla společné, každý s menším exponentem: D(84, 90) = 2 · 3 = 6. Nejmenší společný násobek je součin všech prvočinitelů, které se vyskytují aspoň v jednom rozkladu, každý s větším exponentem:

`n(84, 90)=2^{2}\cdot 3^{2}\cdot 5\cdot 7=1260`

Podrobně to vysvětlují články Největší společný dělitel a Nejmenší společný násobek, spočítají je kalkulačky NSD a NSN a procvičit je můžete v procvičování NSD a NSN.

Krácení zlomků

Zlomek zkrátíte na základní tvar tak, že čitatele i jmenovatele vydělíte jejich největším společným dělitelem. Zlomek 84/90 tedy zkrátíte šesti:

`\dfrac{84}{90}=\dfrac{2^{2}\cdot 3\cdot 7}{2\cdot 3^{2}\cdot 5}=\dfrac{2\cdot 7}{3\cdot 5}=\dfrac{14}{15}`

V rozkladu je vidět, co se zkrátilo (jedna dvojka a jedna trojka), i to, že dál už to nejde: 14 a 15 nemají žádného společného prvočinitele. Víc o zlomcích je v článku Zlomky a zlomek za vás zkrátí kalkulačka Krácení zlomků.

Počet dělitelů

Z rozkladu se dá spočítat, kolik má číslo dělitelů, aniž byste je vypisovali. Ke každému exponentu přičtěte jedničku a výsledky vynásobte. Pro `360=2^{3}\cdot 3^{2}\cdot 5`:

`(3+1)\cdot(2+1)\cdot(1+1)=4\cdot 3\cdot 2=24`

Číslo 360 má 24 dělitelů. Proč: každý dělitel 360 je tvaru `2^{a}\cdot 3^{b}\cdot 5^{c}`, kde a může být 0, 1, 2 nebo 3 (čtyři možnosti), b může být 0, 1 nebo 2 (tři možnosti) a c 0 nebo 1 (dvě možnosti). Všechny dělitele i s jejich počtem vypíše kalkulačka Všichni dělitelé čísla.

Odmocniny a druhé mocniny

Číslo je druhou mocninou celého čísla právě tehdy, když jsou v jeho rozkladu všechny exponenty sudé. A z rozkladu se dá i částečně odmocnit, protože z každé dvojice stejných prvočinitelů vytknete jeden před odmocninu:

`\begin{aligned}\sqrt{1584}&=\sqrt{2^{4}\cdot 3^{2}\cdot 11}\\[6pt]&=2^{2}\cdot 3\cdot\sqrt{11}=12\sqrt{11}\end{aligned}`

Pod odmocninou zůstane 11, protože má exponent 1. Tomuto postupu se věnuje článek Částečné odmocňování.

Tabulka rozkladů čísel do 100

Rozklady všech složených čísel od 4 do 100. Číslo, které v tabulce chybí, je prvočíslo (nebo 1), a jeho rozklad je ono samo.

číslorozkladčíslorozkladčíslorozklad
4`2^{2}`39`3\cdot 13`72`2^{3}\cdot 3^{2}`
6`2\cdot 3`40`2^{3}\cdot 5`74`2\cdot 37`
8`2^{3}`42`2\cdot 3\cdot 7`75`3\cdot 5^{2}`
9`3^{2}`44`2^{2}\cdot 11`76`2^{2}\cdot 19`
10`2\cdot 5`45`3^{2}\cdot 5`77`7\cdot 11`
12`2^{2}\cdot 3`46`2\cdot 23`78`2\cdot 3\cdot 13`
14`2\cdot 7`48`2^{4}\cdot 3`80`2^{4}\cdot 5`
15`3\cdot 5`49`7^{2}`81`3^{4}`
16`2^{4}`50`2\cdot 5^{2}`82`2\cdot 41`
18`2\cdot 3^{2}`51`3\cdot 17`84`2^{2}\cdot 3\cdot 7`
20`2^{2}\cdot 5`52`2^{2}\cdot 13`85`5\cdot 17`
21`3\cdot 7`54`2\cdot 3^{3}`86`2\cdot 43`
22`2\cdot 11`55`5\cdot 11`87`3\cdot 29`
24`2^{3}\cdot 3`56`2^{3}\cdot 7`88`2^{3}\cdot 11`
25`5^{2}`57`3\cdot 19`90`2\cdot 3^{2}\cdot 5`
26`2\cdot 13`58`2\cdot 29`91`7\cdot 13`
27`3^{3}`60`2^{2}\cdot 3\cdot 5`92`2^{2}\cdot 23`
28`2^{2}\cdot 7`62`2\cdot 31`93`3\cdot 31`
30`2\cdot 3\cdot 5`63`3^{2}\cdot 7`94`2\cdot 47`
32`2^{5}`64`2^{6}`95`5\cdot 19`
33`3\cdot 11`65`5\cdot 13`96`2^{5}\cdot 3`
34`2\cdot 17`66`2\cdot 3\cdot 11`98`2\cdot 7^{2}`
35`5\cdot 7`68`2^{2}\cdot 17`99`3^{2}\cdot 11`
36`2^{2}\cdot 3^{2}`69`3\cdot 23`100`2^{2}\cdot 5^{2}`
38`2\cdot 19`70`2\cdot 5\cdot 7`

Časté chyby

  • Jednička v rozkladu. Zápis 12 = 1 · 2 · 2 · 3 není správný rozklad, protože 1 není prvočíslo. Správně je `12=2^{2}\cdot 3`.
  • Složené číslo v rozkladu. 360 = 23 · 9 · 5 je správně spočítané, ale nedokončené: 9 = 3 · 3, takže rozklad je `2^{3}\cdot 3^{2}\cdot 5`. Zkontrolujte, že je každý činitel prvočíslo.
  • Dělit prvočíslem jen jednou. Po 360 : 2 = 180 je potřeba zkusit dvojku znovu, ne hned přejít na trojku. Kdo po prvním dělení přejde rovnou na trojku a pětku, dostane 180 : 3 = 60, 60 : 3 = 20, 20 : 5 = 4 a čtyřka mu zůstane, protože ji 3 ani 5 nedělí. Zkoušejte jedno prvočíslo, dokud dělí.
  • Prohlásit číslo za prvočíslo moc brzy. 323 není dělitelné 2, 3, 5, 7, 11 ani 13, a přesto to prvočíslo není: 323 = 17 · 19. Protože `\sqrt{323}\doteq 18`, je třeba vyzkoušet i 17. Zkoušejte všechna prvočísla až do odmocniny.
  • Zaměnit rozklad na součin za prvočíselný rozklad. 360 = 18 · 20 je pravda, ale prvočíselný rozklad to není.
  • Zapomenout na zkoušku. Jedno chybné dělení (třeba 1584 : 2 = 782) pokazí všechno, co následuje. Zpětné vynásobení takovou chybu odhalí hned.

Velká čísla a počítače

Postup ze sloupečku, kterému se říká faktorizace zkusmým dělením, funguje pro jakkoli velké číslo, jen je pomalý. Číslo 9991 vypadá nevinně, ale jeho nejmenší prvočinitel je 97, takže byste vyzkoušeli všech 25 prvočísel do 97: 9991 = 97 · 103. (Kdo si všimne, že 9991 = 1002 - 32 = (100 - 3) · (100 + 3), má to hned.)

Počítač takhle rozloží čísla do zhruba patnácti cifer za okamžik. Pro větší čísla existují chytřejší metody, například Pollardův rho algoritmus (John Pollard, 1975), který rychle najde malého dělitele, nebo kvadratické síto a síto v číselném tělese pro opravdu velká čísla. Číslo, které je součinem dvou prvočísel o stovkách cifer, ale dnes neumí v rozumném čase rozložit nikdo. Na tom stojí šifra RSA, kterou se chrání třeba spojení s bankou: veřejně se zná součin, ale ne ta dvě prvočísla.

Zkusmé dělení v Pythonu (vnitřní cyklus dělí stejným číslem, dokud to jde, a d stačí zvyšovat jen do odmocniny ze zbytku):

def rozklad(n):
    cinitele = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            cinitele.append(d)
            n //= d
        d += 1
    if n > 1:
        cinitele.append(n)
    return cinitele

print(rozklad(1584))   # [2, 2, 2, 2, 3, 3, 11]

Funkce zkouší i složená d (4, 6, 9 ...), ale ta nikdy nedělí: jejich prvočinitelé už byli ze zbytku vyděleni dřív.

Příklady k procvičení

1. Rozložte na prvočinitele čísla 72 a 252.

2. Rozložte na prvočinitele číslo 2450.

3. Je 391 prvočíslo? Pokud ne, rozložte ho.

4. Kolik dělitelů má číslo 720?

5. Jakým nejmenším přirozeným číslem je třeba vynásobit 540, aby vznikla druhá mocnina přirozeného čísla?

6. Z 180 čtvercových dlaždic chceme složit obdélník, celé dlaždice, bez mezer a všechny použité. Kolik různých obdélníků jde složit? Obdélník 10 × 18 a 18 × 10 počítáme jako jeden a řada 1 × 180 se také počítá.

Kam dál

Hledání nejmenšího prvočinitele a počtu dělitelů si procvičte v procvičování Dělitelé a prvočinitelé, poznávání prvočísel v procvičování prvočísel.

Rozklad libovolného čísla s celým postupem udělá kalkulačka Rozklad na prvočinitele. Ostatní výpočty kolem dělitelnosti najdete v přehledu Dělitelnost a prvočísla.

Na rozklad navazují články Největší společný dělitel a Nejmenší společný násobek, k prvočíslům samotným se vraťte v článku Prvočíslo.