Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Diskrétni matematika - 1. týden Elementární teorie čísel - dělitelnost Lukáš Vokřínek Masarykova univerzita Fakulta informatiky podzim 2024 □ ť3? - Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooooo ooooooooooo ooo Q Problémy teorie čísel Q Dělitelnost Q Společní dělitelé a společné násobky Q Prvočísla Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo 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 Společní dělitelé a společné násobky Prvočísla oooo ooooo ooooooooooo ooo 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 Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. William Stein, Elementary Number Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC2014.pdf Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla •ooo ooooo ooooooooooo ooo Q Problémy teorie čísel Problémy teorie čísel 0900 Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo 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 oo«o ooooo ooooooooooo ooo Příklady problémů teorie čísel 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 oo«o ooooo ooooooooooo ooo Příklady problémů teorie čísel 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 oo«o ooooo ooooooooooo ooo Příklady problémů teorie čísel 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 oo«o ooooo ooooooooooo ooo Příklady problémů teorie čísel 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. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo» ooooo ooooooooooo ooo 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 Dělitelnost Společní dělitelé a společné násobky Prvočísla ooo» ooooo ooooooooooo ooo 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č. <□► < rnP ► < -E ► < *■ -E O Q, O Problémy teorie čísel 000» Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo 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 4/c + 6£ = nl <□► a c a antisymetrii a b > a = b\ Problémy teorie čísel oooo Dělitelnost o»ooo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Definice Řekneme, že celé číslo a delí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. Snadno se vidí, že dělitelnost je uspořádání na přirozených (tedy nezáporných celých) číslech, tj. splňuje reflexivitu a | a, tranzitivitu > a c a antisymetrii a b > a = b\ Problémy teorie čísel oooo Dělitelnost o»ooo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Definice Řekneme, že celé číslo a delí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. Snadno se vidí, že dělitelnost je uspořádání na přirozených (tedy nezáporných celých) číslech, tj. splňuje reflexivitu a | a, tranzitivitu > a c a antisymetrii a b > a = b\ / -o- \ ±2 • 2 ±2 • 3 ±2 ±3 ±1 Problémy teorie čísel oooo Dělitelnost oo»oo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Dále nás budou zajímat algebraické vlastnosti dělitelnosti b A a a c -b< a ac b + c A a | b — c bc (c ^ 0) Problémy teorie čísel oooo Dělitelnost oo»oo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Dále nás budou zajímat algebraické vlastnosti dělitelnosti b A a a c -b< a ac b + c A a | b — c bc (c ^ 0) Příklad Zjistěte, pro která přirozená čísla n je číslo n2 +1 dělitelné číslem 3 Problémy teorie čísel oooo Dělitelnost oo»oo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Dále nás budou zajímat algebraické vlastnosti dělitelnosti b A a a c - a ac b + c A a | b — c bc (c ^ 0) Příklad Zjistěte, pro která přirozená čísla n je číslo n2 +1 dělitelné číslem 3 Řešení Uvidí se, že záleží pouze na zbytku n po dělení třemi Problémy teorie čísel oooo Dělitelnost oo»oo Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Dále nás budou zajímat algebraické vlastnosti dělitelnosti b A a a c -b< a ac b + c A a | b — c bc (c ^ 0) Příklad Zjistěte, pro která přirozená čísla n je číslo n2 +1 dělitelné číslem 3 Řešení Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooo»o ooooooooooo ooo Dělení se zbytkem Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a 0 indukcí: pro a < m zřejmé, pro 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 oooo Dělitelnost oooo» Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Čí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íšeme-li rovnost a = mq + r do tvaru a r . r — = q H--, přitom 0 < — < 1. mm m Problémy teorie čísel oooo Dělitelnost oooo» Společní dělitelé a společné násobky ooooooooooo Prvočísla ooo Čí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íšeme-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. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOOO OOOOO »0000000000 ooo 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 OOOO OOOOO O0OOOOOOOOO ooo 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. <□► < rnP ► < -E ► < -E ► E O °n O Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOOO OOOOO O0OOOOOOOOO ooo 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 přirozená čísla a, b. Libovolné přirozené číslo m takové, že m | a, m | b se nazývá společný dělitel čísel a, b. Společný dělitel čísel a, b, který je dělitelný libovolným společným dělitelem těchto čísel, se nazývá největší společný dělitel čísel a, b a značí se (a, b). (Jedná se o infimum vzhledem k dělitelnosti.) Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOOO OOOOO O0OOOOOOOOO ooo 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 přirozená čísla a, b. Libovolné přirozené číslo m takové, že m | a, m | b se nazývá společný dělitel čísel a, b. Společný dělitel čísel a, b, který je dělitelný libovolným společným dělitelem těchto čísel, se nazývá největší společný dělitel čísel a, b a značí se (a, b). (Jedná se o infimum vzhledem k dělitelnosti.) Například (12,16) = 4. Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky O0OOOOOOOO Prvočísla ooo Poznámka Přímo z definice plyne, že pro libovolné a, Ď e N platí (a, b) = (b, a), (a,l) = 1, (a,0) = a. Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky O0OOOOOOOO Prvočísla ooo Poznámka Přímo z definice plyne, že pro libovolné a, b e N platí (a, b) = (b, a), (a,l) = 1, (a,0) = a. Definice Mějme přirozená čísla a, b. Libovolné přirozené číslo m takové, že a | m, b | m se nazývá společný násobek čísel a, b. Společný násobek čísel a, b, který dělí libovolný společný násobek těchto čísel, se nazývá nej menší společný násobek čísel a, b a značí se [a,Ď]. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooooo OO0OOOOOOOO ooo Poznámka Přímo z definice plyne, že pro libovolné a, b e N platí (a, b) = (b, a), (a,l) = 1, (a,0) = a. Definice Mějme přirozená čísla a, b. Libovolné přirozené číslo m takové, že a | m, b | m se nazývá společný násobek čísel a, b. Společný násobek čísel a, b, který dělí libovolný společný násobek těchto čísel, se nazývá nej menší společný násobek čísel a, b a značí se [a,Ď]. Poznámka (ai, . . . , an) — ((^1? • • • i än—l)-) &n) [ai,..., an] = [[ai,..., a^—i], an] Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky ooo»ooooooo Prvočísla ooo 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. Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky ooo»ooooooo Prvočísla ooo 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 Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooooo ooo»ooooooo ooo 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 Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOOO OOOOO OOOO0OOOOOO ooo Euklidův algoritmus Algoritmus a důkaz jeho korektnosti demonstrujeme na příkladu Příklad Určete největšího společného dělitele čísel 10175 a 2277. ■ <□► < rnP ► < -E ► < -E ► E O °n O Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooooo ooooo«ooooo ooo Vlastnosti gcd Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b £ platí (a, ti) = (a, — ti) — (—a, ti) — (—a, —ti), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooo«ooooo Prvočísla ooo 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, a2 existuje jejich největší společný dělitel (ai, a2), přitom existují celá čísla /ci, /c2 ŕa/c, že (ai,a2) = fciai + k2a2. Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooo«ooooo Prvočísla ooo Vlastnosti gcd Poznámka | Z definice, z předchozího tvrzení a z toho platí (a, b) = (a, —b) = (—a, b) = (—a, — největší společný dělitel libovolných dvou , že pro libovolná a, fa G Z b), plyne, že existuje celých čísel. J Věta (Bezoutova) 1 Pro libovolná celá čísla ai, a2 existuje jejich největší společný dělitel (ai, a2), přitom existují celá čísla /ci, /c2 ŕa/c, že (ai,a2) = fciai + ^2^2- Důsledek Pro libovolná celá čísla ai, a2 /ze 7a/co celočíselné kombinace n = k±ai + Zc2a2 vyjádřit právě násobky největšího společného dělitele (ai, a2). --' Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky OOOOOO0OOOO Prvočísla ooo Prí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 oooo ooooo ooooooo»ooo ooo Definice Čísla a, b G Z se nazývají nesoudělná, jestliže platí (a, b) = 1. Čísla ai, a2,..., a„ e Z se nazývají po č/\/ol/ nesoudělná, jestliže pro každé / 7^ j platí (a/, ay) = 1. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooooo ooooooo»ooo ooo Definice Čísla a, b G Z se nazývají nesoudělná, jestliže platí (a, b) = 1. Čísla ai, a2,..., a„ e Z se nazývají po č/\/ol/ nesoudělná, jestliže pro každé / 7^ j platí (a/, a/) = 1. Věta Pro libovolná přirozená čísla a, b a jejich největšího společného dělitele (a, b) — d jsou čísla a/d, b/d nesoudělná. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooooo OOOOOOOO0OO ooo r Důkaz Číslo k je společný dělitel čísel a/d, b jd, právě když k a/d, k\b/d^ kd a, kd b ^ kd (a, b) = d ^ k i a jediné takové k je tedy 1 □ kd k Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooooo ooooooooo»o ooo Pro libovolná přirozená čísla a, b, c platí: jestliže c | ab, (c, a) = 1, pak c b. Důkaz Zjevně c | cb a podle předpokladu také c | ab, musí tedy c dělit i jakoukoliv jejich celočíselnou kombinaci; přitom podle Bezoutova lemmatu kc + la = 1, takže c \ (k - cb + I - ab) = (kc + la)b = b. □ Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla oooo ooooo oooooooooo* ooo Nejmenší společný násobek Pro libovolná přirozená čísla ai, a2 existuje jejich nejmenší společný násobek [ai, a?\ a platí(ai, a^) • [ai, a?\ — a\a^. Důkaz 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 OOOO OOOOO OOOOOOOOOOO »00 Q Prvočísla Problémy teorie čísel oooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooo Prvočísla 090 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 oooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooo Prvočísla 090 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). Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOOO OOOOO OOOOOOOOOOO 009 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. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky Prvočísla OOOO OOOOO OOOOOOOOOOO 009 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. 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čin11 jednoho prvočísla.)