On J \ ((r ö v J \ 1 vT ' ___^1 ____^ ; 1 1 6Qb ) 40QL p • [60 ; Q%) IS'- 1 / / Diskrétní matematika - 1. týden Elementární teorie čísel - dělitelnost /očřsla Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo Obsah přednášky Q Problémy teorie čísel O Dělitelnost Q Společní dělitelé a společné násobky Q Prvočísla Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Problémy teorie čísel Dělitelnost ooo oooo Doporučené zdroje • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Michal Bulant, výukový text k přednášce Elementární teorie čísel, http: //is .muni . cz/el/1431/podzim2019/M6520/ um/main-print.pdf 9 Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. a William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf o Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/-kučera/texty/ATC2014.pdf Společní dělitele a společné násobky ooooooooo Problémy teorie čísel ooo Plán přednášky Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla Q Problémy teorie čísel Problémy teorie čísel •oo Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo Přirozená a celá čísla jsou nejjednodušší matematickou strukturou, zkoumání jejich vlastností však postavilo před generace matematiků celou řadu velice obtížných problémů. Často jsou to problémy, které je možno snadno formulovat, přesto však dodnes neznáme jejich řešení. V několika přednáškách se teď budeme zabývat úlohami o celých číslech. Převážně v nich půjde o dělitelnost celých čísel, popřípadě o řešení rovnic v oboru celých nebo přirozených čísel. God made integers, all else is the work of man. (L. Kronecker) Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla o«o oooo ooooooooo oo Příklady problémů teorie čísel o problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla o«o oooo ooooooooo oo Příklady problémů teorie čísel o problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo • problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla o«o oooo ooooooooo oo Příklady problémů teorie čísel o problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo, • problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla • Goldbachova hypotéza (rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel), Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla o«o oooo ooooooooo oo Příklady problémů teorie čísel o problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo, • problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla • Goldbachova hypotéza (rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel), • velká Fermatova věta (Fermaťs Last Theorem) - rozhodnout, zda existují přirozená čísla n, x, y, z tak, že n > 2 a platí xn + yn — zn; Pierre de Fermat jej formuloval cca 1637, vyřešil Andrew Wiles v roce 1995. <□► -ír^J^ < > -E O Q, O Problémy teorie čísel 00« Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo diofantické rovnice V kouzelném měšci máme neomezené množství dvoukorun a pětikorun. Jaké částky můžeme zaplatit tak, aby nebylo potřeba vracet? Problémy teorie čísel 00« Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo diofantické rovnice V kouzelném měšci máme neomezené množství dvoukorun a pětikorun. Jaké částky můžeme zaplatit tak, aby nebylo potřeba vracet? Ptáme se tedy, pro která přirozená čísla n existují přirozená k, £ tak, aby 2k + 5£ = n. Asi se dá vcelku snadno uvěřit, že libovolnou vyšší částku takto zaplatíme, po pravdě jakoukoliv částku s výjimkou 1 Kč a 3 Kč. Problémy teorie čísel 00« Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo diofantické rovnice V kouzelném měšci máme neomezené množství dvoukorun a pětikorun. Jaké částky můžeme zaplatit tak, aby nebylo potřeba vracet? Ptáme se tedy, pro která přirozená čísla n existují přirozená k, £ tak, aby 2k + 5£ = n. Asi se dá vcelku snadno uvěřit, že libovolnou vyšší částku takto zaplatíme, po pravdě jakoukoliv částku s výjimkou 1 Kč a 3 Kč. S vracením pak zvládneme zaplatit libovolnou částku, tj. každé n lze vyjádřit jako 2k + 5£ = n pro nějaká celá k, £. Umíme to pro jakékoliv hodnoty mincí? Jak by to dopadlo třeba pro 7k + ll£ = nl A jak pro 2k + A£ = nl Problémy teorie čísel ooo Plán přednášky Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla Q Dělitelnost Problémy teorie čísel ooo Dělitelnost •ooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo Definice Řekneme, že celé číslo a c/e//'celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a - c — b. Píšeme pak a b. Problémy teorie čísel ooo Dělitelnost •ooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo Definice Řekneme, že celé číslo a c/e//'celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a - c — b. Píšeme pak a | b. Přímo z definice plyne několik jednoduchých tvrzení : Číslo nula je dělitelné každým celým číslem; jediné celé číslo, které je dělitelné nulou, je nula; pro libovolné číslo a platí a a; Problémy teorie čísel ooo Dělitelnost •ooo Společní dělitelé a společné násobky ooooooooo Prvočísla oo Definice Řekneme, že celé číslo a c/e//'celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a - c — b. Píšeme pak a | b. Přímo z definice plyne několik jednoduchých tvrzení : Číslo nula je dělitelné každým celým číslem; jediné celé číslo, které je dělitelné nulou, je nula; pro libovolné číslo a platí a | a; pro libovolná čísla a, b, c platí tyto čtyři implikace: b A b b A 3 \ c c ŕ 0 b A b > 0 a | b + c A a | b — c (a | b ac | bc) a < b Problémy teorie čísel ooo Dělitelnost o»oo Společní dělitelé a společné násobky ooooooooo Prvočísla oo Příklad Zjistěte, pro která přirozená čísla n je číslo n2 +1 dělitelné číslem Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo o»oo ooooooooo oo Příklad Zjistěte, pro která přirozená čísla n je číslo nz +1 dělitelné číslem 3 ■v Řešení Uvidí se, že záleží pouze na zbytku n po dělení třemi. Problémy teorie čísel ooo Dělitelnost o»oo Společní dělitelé a společné násobky ooooooooo Prvočísla oo Příklad Zjistěte, pro která přirozená čísla n je číslo n2 +1 dělitelné číslem Řešení Uvidí se, že záleží pouze na zbytku n po dělení třemi Příklad Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem n + 1. Problémy teorie čísel ooo Dělitelnost oo«o Společní dělitelé a společné násobky ooooooooo Prvočísla oo Dělení se zbytkem Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a m pak rekurzivně s využitím výsledku pro a — m (podíl je potřeba zvětšit o 1, zbytek zůstane stejný). □ Problémy teorie čísel ooo Dělitelnost ooo« Společní dělitelé a společné násobky ooooooooo Prvočísla oo Číslo q, resp. r z věty se nazýva (neúplný) podíl, resp. zbytek při dělení čísla a číslem m se zbytkem. Vhodnost obou názvů je zřejmá, přepíseme-li rovnost a = mq + r do tvaru a r . r — = q H--, přitom 0 < — < 1. mm m Problémy teorie čísel ooo Dělitelnost ooo« Společní dělitelé a společné násobky ooooooooo Prvočísla oo Číslo q, resp. r z věty se nazýva (neúplný) podíl, resp. zbytek při dělení čísla a číslem m se zbytkem. Vhodnost obou názvů je zřejmá, přepíseme-li rovnost a = mq + r do tvaru a r . r — = q H--, přitom 0 < — < 1. mm m Příklad Dokažte, že jsou-li zbytky po dělení čísel a, b G Z číslem m e N jedna, je jedna i zbytek po dělení čísla ab číslem m. <□► -íŕ^J^ -E O Q, O Problémy teorie čísel ooo Plán přednášky Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla Q Společní dělitelé a společné násobky Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOO OOOO »00000000 oo Největší společný dělitel (gcd) Jedním z nejdůležitějších nástrojů výpočetní teorie čísel je výpočet největšího společného dělitele. Protože jde, jak si ukážeme, o relativně rychlou proceduru, je i v moderních algoritmech velmi často využívána. Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky •oooooooo Prvočísla oo Největšř společný dělitel (gcd) Jedním z nejdůležitějších nástrojů výpočetní teorie čísel je výpočet největšího společného dělitele. Protože jde, jak si ukážeme, o relativně rychlou proceduru, je i v moderních algoritmech velmi často využívána. Definice Mějme celá čísla ai,a2- Libovolné celé číslo m takové, že m | ai, m | a2 se nazývá společný dělitel čísel ai,a2- Společný dělitel m > 0 čísel ai,a2, který je dělitelný libovolným společným dělitelem čísel ai,a2, se nazývá největšíspolečný dělitel čísel ai,a2 a značí se (ai, a2). Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOO OOOO »00000000 oo Největší společný dělitel (gcd) Jedním z nejdůležitějších nástrojů výpočetní teorie čísel je výpočet největšího společného dělitele. Protože jde, jak si ukážeme, o relativně rychlou proceduru, je i v moderních algoritmech velmi často využívána. Definice Mějme celá čísla ai,a2- Libovolné celé číslo m takové, že m | ai, m | a2 se nazývá společný dělitel čísel ai,a2- Společný dělitel m > O čísel ai,a2, který je dělitelný libovolným společným dělitelem čísel ai,a2, se nazývá největší společný dělitel čísel ai,a2 a značí se (ai, a2). Například (12,64) = 4. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo oooo o«ooooooo oo Mějme celá čísla ai,a2- Libovolné celé číslo m takové, že a\ \ m, a2 | m se nazývá společný násobek čísel ai,a2- Společný násobek m > 0 čísel ai, a2, který dělí libovolný společný násobek čísel ai, a2, se nazývá nejmenší společný násobek čísel ai, a2 a značí se [ai, a2]. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo oooo o«ooooooo oo Mějme celá čísla ai,a2- Libovolné celé číslo m takové, že a\ \ m, a2 | m se nazývá společný násobek čísel ai,a2- Společný násobek m > 0 čísel ai, a2, který dělí libovolný společný násobek čísel ai, a2, se nazývá nejmenší společný násobek čísel ai, a2 a značí se [ai, a2]. Poznámka Přímo z definice plyne, že pro libovolné a, b G (a,f>) = (M, [a,b] = [b,a], (a,l) = l, [a, 1] [a,0] = 0. platí |a|, (a,0) Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo oooo o«ooooooo oo Mějme celá čísla ai,a2- Libovolné celé číslo m takové, že a\ \ m, a2 | m se nazývá společný násobek čísel ai,a2- Společný násobek m > 0 čísel ai, a2, který dělí libovolný společný násobek čísel ai, a2, se nazývá nejmenší společný násobek čísel ai, a2 a značí se [ai, a2]. Poznámka Přímo z definice plyne, že pro libovolné a, b G Z platí (a,Ď) = (M. [a,b] = [M, (a,l) = l, [a,l] = |a|, (a,0) = [a,0] = 0. Analogicky se definuje i největší společný dělitel a nejmenší společný násobek více než dvou celých čísel a snadno se následně dokáže, že platí (ai, . . . , an) — ((^1? • • • i än—l)-) &n) [ai,..., an] = [[ai,..., an_i], an] Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky oo«oooooo Prvočísla oo Euklidův algoritmus Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b G Z čísla (a, b) a [a, b] vůbec existují. To si lze hezky představit přes roklad na prvočinitele, ale ten je výpočetně velmi náročný (RSA) navíc k jeho odvození budeme existenci největšího společného dělitele využívat. Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky oo«oooooo Prvočísla oo Euklidův algoritmus Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b G Z čísla (a, b) a [a, b] vůbec existují. To si lze hezky představit přes roklad na prvočinitele, ale ten je výpočetně velmi náročný (RSA) a navíc k jeho odvození budeme existenci největšího společného dělitele využívat. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi, rr?2 £ No totiž podle definice platí, že pokud m\ | rr?2 a zároveň rr?2 | mi, je nutně m\ — tri2. Důkaz existence čísla (a, b) podáme (spolu s algoritmem jeho nalezení) v následující větě. Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky oo«oooooo Prvočísla oo Euklidův algoritmus Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b £ čísla (a, b) a [a, b] vůbec existují. To si lze hezky představit přes roklad na prvočinitele, ale ten je výpočetně velmi náročný (RSA) a navíc k jeho odvození budeme existenci největšího společného dělitele využívat. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi, rr?2 £ No totiž podle definice platí, že pokud m\ | rr?2 a zároveň rr?2 | mi, je nutně m\ — tri2. Důkaz existence čísla (a, b) podáme (spolu s algoritmem jeho nalezení) v následující větě. Věta (Euklidův algoritmus) Necht ai, a2 jsou přirozená čísla. Pro každé n > 3, pro které an-i 7^ 0, označme an zbytek po dělení čísla an-2 číslem an_i po konečném počtu kroků dostaneme a^ = 0 a platí 3k-i = (ai, 3*2)• Pak >0 Q,o Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky OOO0OOOOO Prvočísla oo Euklidův algoritmus Algoritmus a důkaz jeho korektnosti demonstrujeme na příkladu Příklad Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky OOOO0OOOO Prvočísla oo Vlastnosti gcd Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, b) = (a, —b) = (—a, b) = (—a, —b), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo oooo OOOO0OOOO oo Vlastnosti gcd Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, b) = (a, —b) = (—a, b) = (—a, —b), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Věta (Bezoutova) Pro libovolná celá čísla ai, a^ existuje jejich největší společný dělitel (ai, a2), přitom existují celá čísla k±, /c2 ŕa/c, že (ai,a2) = fciai + k2a2. Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky OOOO0OOOO Prvočísla oo Vlastnosti gcd Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, b) = (a, —b) = (—a, b) = (—a, —b), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Věta (Bezoutova) Pro libovolná celá čísla ai, a^ existuje jejich největší společný dělitel (ai, a2), přitom existují celá čísla k±, /c2 ŕa/c, že (ai,a2) = fciai + k2a2. Důsledek Pro libovolná celá čísla ai, a2 /ze 7a/co celočíselné kombinace n = k±ai + k2a2 vyjádřit právě násobky největšího společného dělitele (ai,a2). Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo oooo OOOOO0OOO oo Příklad ■ Výpočet největšího společného dělitele pomocí Euklidova algoritmu je s využitím výpočetní techniky i pro relativně velká čísla poměrně rychlý. V našem příkladu to vyzkoušíme na 2 číslech A,B, z nichž každé je součinem dvou 101-ciferných prvočísel. Všimněme si, že výpočet největšího společného dělitele i takto velkých čísel trval zanedbatelný čas. Příklad v systému SAGE lze vyzkoušet na https://cocalc.com/. Poznámka Euklidův algoritmus a Bezoutova věta jsou základními výsledky elementární teorie čísel a tvoří jeden z pilířů algoritmů algebry a teorie čísel. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOO OOOO OOOOOO0OO oo Nejmenší společný násobek Věta Pro libovolná celá čísla ai, a^ existuje jejich nejmenší společný násobek [ai, a?\ a platí(ai, a^) • [ai, a?\ — \a\-a2. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOO OOOO OOOOOO0OO oo Nejmenší společný násobek Věta Pro libovolná celá čísla ai, a^ existuje jejich nejmenší společný násobek [ai, a?\ a platí(ai, a^) • [ai, a?\ — \a\-a2. Nejlépe se vidí přes rozklad na součin prvočísel. □ Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo oooo ooooooo«o oo Nesoudělnost Definice Čísla ai, a2,..., an £ Z se nazývají nesoudělná, jestliže platí (ai, a2,..., 3n) = 1. Čísla ai, a2,...,an G Z se nazývají po č/\/ol/ nesoudělná, jestliže pro každé ij takové, že 1 < / < j < n, platí (a/,a/) = 1. Poznámka V případě n — 2 oba pojmy splývají, pro n > 2 plyne z nesoudělnosti po dvou nesoudělnost, ne však naopak: například čísla 6, 10, 15 jsou nesoudělná, ale nejsou nesoudělná po dvou, neboť dokonce žádná dvojice z nich vybraná nesoudělná není: (6,10) = 2, (6,15) = 3, (10,15) = 5. Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky 00000000« Prvočísla oo Pro libovolná přirozená čísla a, b, c platí O (ac, bc) = (a, b) • c, O jestliže a \ bc, (a, b) = 1, pa/c a | c, O c/ = (a, b) praVě řebc/y /cc/yž existují qi, (72 £ N řa/c, že a = c%, b = dq2 a (qu q2) = 1- Problémy teorie čísel ooo Plán přednášky Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla Q Prvočísla Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla •o Prvočíslo je jeden z nejdůležitějších pojmů elementární teorie čísel. Jeho důležitost je dána především větou o jednoznačném rozkladu libovolného přirozeného čísla na součin prvočísel, která je silným a účinným nástrojem při řešení celé řady úloh z teorie čísel. Definice Každé přirozené číslo n > 2 má aspoň dva kladné dělitele: 1 a n. Pokud kromě těchto dvou jiné kladné dělitele nemá, nazývá se prvočíslo. V opačném případě hovoříme o složeném čísle. Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla •o Prvočíslo je jeden z nejdůležitějších pojmů elementární teorie čísel. Jeho důležitost je dána především větou o jednoznačném rozkladu libovolného přirozeného čísla na součin prvočísel, která je silným a účinným nástrojem při řešení celé řady úloh z teorie čísel. Definice Každé přirozené číslo n > 2 má aspoň dva kladné dělitele: lan. Pokud kromě těchto dvou jiné kladné dělitele nemá, nazývá se prvočíslo. V opačném případě hovoříme o složeném čísle. V dalším textu budeme zpravidla prvočíslo značit písmenem p. Nejmenší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (zejména číslo 1 za prvočíslo ani za číslo složené nepovažujeme, je totiž invertibilní, neboli tzv. jednotkou okruhu celých čísel). Prvočísel je, jak brzy dokážeme, nekonečně mnoho, máme ovšem poměrně limitované výpočetní prostředky na zjištění, zda je dané číslo prvočíslem (největší známé prvočíslo 282589933 — 1 má pouze 24 862 048 cifer). >0 Q,o Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla Základní věta aritmetiky Uveďme nyní větu, která udává ekvivalentní podmínku prvočíselnosti a je základní ingrediencí při důkazu jednoznačnosti rozkladu na prvočísla. Věta (Euklidova o prvočíslech) rrirozene c/s/i čísla a, b z p o p > 2 je prvočíslo, pn ab plyne p a nebo p í ve když platí: pro každá celá b. Problémy teorie čísel ooo Dělitelnost oooo Společní dělitelé a společné násobky ooooooooo Prvočísla Základní věta aritmetiky Uveďme nyní větu, která udává ekvivalentní podmínku prvočíselnosti a je základní ingrediencí při důkazu jednoznačnosti rozkladu na prvočísla. Věta (Euklidova o prvočíslech) Přirozené číslo p > 2 je prvočíslo, právě když platí: pro každá celá čísla a, b z p ab plyne p I a nebo p b. Věta Libovolné přirozené číslo n > 2 je možné vyjádřit jako součin prvočísel, přičemž je toto vyjádření jediné, nebereme-li v úvahu pořadí činitelů. (Je-li n prvočíslo, pak jde o „ součin'1 jednoho prvočísla.)