Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky ooo ooooo ooooooooooooooooo Diskrétní matematika - 1. týden Elementární teorie čísel - dělitelnost Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Společní dělitelé a společné násobky ooooooooooooooooo Obsah přednášky Problémy teorie čísel Dělitelnost ooo ooooo Q Problémy teorie čísel Q Dělitelnost Q Společní dělitelé a společné násobky • Faktorizace Společní dělitelé a společné násobky ooooooooooooooooo Doporučené zdroje Problémy teorie čísel Dělitelnost ooo ooooo • 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 ooo ooooo ooooooooooooooooo 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/podzim2012/M6520/ um/main-print.pdf • Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. o 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/~kucera/texty/ATC10.pdf Problémy teorie čísel ooo Plán prednáaky Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooooooooo Problémy teorie čísel v.jyi:, .i / Faktorizace >0 Q,o Problémy teorie čísel •oo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooooooooo 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) Společní dělitelé a společné násobky ooooooooooooooooo Příklady problémů teorie čísel Problémy teorie čísel Dělitelnost o«o ooooo 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, Společní dělitelé a společné násobky ooooooooooooooooo Příklady problémů teorie čísel Problémy teorie čísel Dělitelnost o«o ooooo 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, 9 problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla Společní dělitelé a společné násobky ooooooooooooooooo Příklady problémů teorie čísel Problémy teorie čísel Dělitelnost o«o ooooo 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, 9 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), Společní dělitelé a společné násobky ooooooooooooooooo Příklady problémů teorie čísel Problémy teorie čísel Dělitelnost o«o ooooo 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, 9 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. Společní dělitelé a společné násobky ooooooooooooooooo diofantické rovnice Problémy teorie čísel Dělitelnost oo« ooooo 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? Společní dělitelé a společné násobky ooooooooooooooooo diofantické rovnice Problémy teorie čísel Dělitelnost oo« ooooo 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č. Společní dělitelé a společné násobky ooooooooooooooooo diofantické rovnice Problémy teorie čísel Dělitelnost oo« ooooo 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 + U = nl Problémy teorie čísel ooo Plán prednáaky Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooooooooo Q Dělitelnost v.jyi:, .i / • Faktorizace >0 Q,o Problémy teorie čísel ooo Dělitelnost •oooo Společní dělitelé a společné násobky ooooooooooooooooo Definice Řekneme, že celé číslo a dělí cek číslem a, též b je násobek a), pr že platí a • c = b. Píšeme pak a i číslo b (neboli číslo b je dělitelné ave když existuje celé číslo c tak, b. Problémy teorie čísel ooo Dělitelnost •oooo Společní dělitelé a společné násobky ooooooooooooooooo Definice Řekneme, že celé číslo a dělí cek číslem a, též b je násobek a), pr že platí a • c = b. Píšeme pak a i číslo b (neboli číslo b je dělitelné ave když existuje celé číslo c tak, 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 •oooo Společní dělitelé a společné násobky ooooooooooooooooo Definice Řekneme, že celé číslo a dělí cek číslem a, též b je násobek a), pr že platí a • c = b. Píšeme pak a i číslo b (neboli číslo b je dělitelné ave když existuje celé číslo c tak, 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: a a b A b b A 3 \ c 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«ooo Společní dělitelé a společné násobky ooooooooooooooooo Příklad Zjistěte, pro která přirozená čísla n je číslo n + 1 dělitelné číslem n + 1. Problémy teorie čísel ooo Dělitelnost o«ooo Společní dělitelé a společné násobky ooooooooooooooooo Príklad Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem n + 1. Reaení Platí n2 — 1 = (r? + l)(r? — 1), a tedy číslo n + 1 dělí číslo n2 — 1. Předpokládejme, že n + 1 dělí i číslo n2 + 1. Pak ovšem musí dělit i rozdíl (n2 + 1) - (n2 - 1) = 2. Protože n G N, platí n + 1 > 2, a tedy z r? + 1 | 2 plyne r? + 1 = 2, proto n = 1. Uvedenou vlastnost má tedy jediné přirozené číslo 1. □ -írnJ^ -E O Q, O Společní dělitelé a společné násobky ooooooooooooooooo Dělení se zbytkem Problémy teorie čísel Dělitelnost ooo oo«oo Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a m a že jsme existenci čísel q, r dokázali pro všechna a1 G {0,1, 2,..., a — 1}. Speciálně pro a' — a — m tedy existují r; tak, že a' — q'm + r' a přitom r; G {0,1,..., m — 1}. Zvolíme-li q — q' + 1, r = rf, platí a = a; + m = (q; + l)m + r; = gm + r, což jsme chtěli dokázat. □ Problémy teorie čísel ooo Dělitelnost ooo«o Společní dělitelé a společné násobky ooooooooooooooooo Dokončení důkazu. Existenci čísel q, r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < 0, pak ke kladnému číslu —a podle výše dokázaného existují q' G Z, r' G {0,1,..., m — 1} tak, že —a = q' m + r', tedy a = —q'm — r'. Je-li r; = 0, položíme r — 0, q = — q;; je-1i r > 0, položíme r — m — r', q — —q' — 1. V obou případech a = q • m + r, a tedy čísla q, r s požadovanými vlastnostmi existují pro každé a G Z, m G N. Problémy teorie čísel ooo Dělitelnost ooo«o Společní dělitelé a společné násobky ooooooooooooooooo Dokončení důkazu. Existenci čísel q, r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < 0, pak ke kladnému číslu —a podle výše dokázaného existují q' G Z, r' G {0,1,..., m — 1} tak, že —a = q' m + r', tedy a = —q'm — r'. Je-li r; = 0, položíme r — 0, q = — q;; je-1i r > 0, položíme r — m — r', q — —q' — 1. V obou případech a = q • m + r, a tedy čísla q, r s požadovanými vlastnostmi existují pro každé a G Z, m G N. Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla qi, q2 G Z; ri, ľ2 G {0,1,..., m — 1} platí a = qim + ri = q2ľn + ľ2. Úpravou dostaneme ri — T2 = ((72 <7i)/77, a tedy m | ri — r^- Ovšem z 0 < r± < m, 0 < ľ2 < m plyne —m < r± — ľ2 < m, odkud dostáváme r\ — ľ2 — 0. Pak ale i (q2 — qi)m = 0, a proto qi = q^. r\ — r^- ■v Čísla q, r jsou tedy určena jednoznačně. □ Problémy teorie čísel ooo Dělitelnost oooo* Společní dělitelé a společné násobky ooooooooooooooooo Čí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 ar r — = q H--, přitom 0 < — < 1. mm m Problémy teorie čísel ooo Dělitelnost oooo* Společní dělitelé a společné násobky ooooooooooooooooo Čí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 ar r — = q H--, přitom 0 < — < 1. mm m 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 ooo oooo* ooooooooooooooooo Čí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 ar 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. i Reaení Podle Věty o dělení se zbytkem existují s, ŕ £ Z tak, že a = s m + 1, b — tm + 1. Vynásobením dostaneme ab = (srn + l)(rm + 1) = (sŕm + s + t) m + 1 = gm + r, kde q = stm + s + t, r = 1, které je podle téže věty jednoznačné, a tedy zbytek po dělení čísla ab číslem m je jedna. □ Problémy teorie čísel ooo Plán prednáaky Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooooooooo V I " i I Q Společní dělitelé a společné násobky o Faktorizace Společní dělitelé a společné násobky •oooooooooooooooo Největšř společný dělitel (gcd) Problémy teorie čísel Dělitelnost ooo ooooo 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. Společní dělitelé a společné násobky •oooooooooooooooo Největší společný dělitel (gcd) Problémy teorie čísel Dělitelnost ooo ooooo 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 (resp. a\ \ m, a^ \ m) se nazývá společný dělitel (resp. společný násobek) čísel a\,a2- Společný dělitel (resp. násobek) m > 0 čísel ai,a2, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel ai,a2, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel ai,a2 a značí se (ai,a2) (resp. [ai,a2]). -írnJ^ < >• ^ O Q, o Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooooooooo Poznámka Přímo z definice plyne, že pro libovolné a, b £ (a, b) = (b, a), [a,b] = [b,a], (a,l) = l, [a, 1] [a,0] = 0. platí (a,0) Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky o»ooooooooooooooo Poznámka Přímo z definice plyne, že pro libovolné a, b £ (a, b) = (b, a), [a,b] = [b,a], (a,l) = l, [a, 1] [a,0] = 0. platí (a,0) Poznámka 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) = ((ai,..., a^—i), an) [ai,..., an] = [[ai,..., a^—i], an] Společní dělitelé a společné násobky OO0OOOOOOOOOOOOOO Euklidův algoritmus Problémy teorie čísel Dělitelnost ooo ooooo Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b G čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi, rr?2 G 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ě, důkaz existence čísla [a, b] pak dostaneme snadno ze vztahu mezi (a, b) a [a,b\. Společní dělitelé a společné násobky OO0OOOOOOOOOOOOOO Euklidův algoritmus Problémy teorie čísel Dělitelnost ooo ooooo Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b £ čísla (a, b) a [a, b] vůbec existují. 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ě, důkaz existence čísla [a, b] pak dostaneme snadno ze vztahu mezi (a, b) a [a,b\. Věta (Euklidův algoritmus) Necht ai, a2 jsou přirozená čísla. Pro každé n > 3, pro které an-i 7^ O, označme an zbytek po dělení čísla an-2 číslem an_i po konečném počtu kroků dostaneme a^ = O a p/ar/' 3/c-i = (ai, a2). Pa/c Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky OOO OOOOO OOO0OOOOOOOOOOOOO Podle Věty o dělení se zbytkem platí 32 > 33 > 34 > .... Protože jde o nezáporná celá čísla, je každé následující alespoň o 1 menší než předchozí, a proto po určitém konečném počtu kroků dostáváme 3k — 0, přičemž 3k-i 7^ 0. Z definice čísel 3n plyne, že existují celá čísla qi, q25 • • • ? 9/c-2 tak, že 3i = qi • 32 + a3, 3k-3 = Qk-3 ' 3k-2 + 3k-l 3k-2 = Qk-2 ' 3k-l- Z poslední rovnosti plyne, že 3k-i \ 3k-2, dále 3k-i \ 3ks, atd., je tedy 3k-i společný dělitel čísel 3i,32- Naopak jejich libovolný společný dělitel dělí i číslo 33 = 3\ — gi32, proto i 34 = 32 — 92^3,..., a proto i 3k-i = 3k-3 — qk-33k-2- Dokázali jsme, že 3k-i je největší společný dělitel čísel ai, 32- □ Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky ooo ooooo OOOO0OOOOOOOOOOOO 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 ooo ooooo OOOO0OOOOOOOOOOOO 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 k±, /c2 tak, že (ai,a2) = /ciai + /c2a2. Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky ooo ooooo OOOO0OOOOOOOOOOOO 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 k±, l<2 tak, že (ai,a2) = /ciai + /c2a2. Důsledek Pro libovolná celá čísla ai, a2 /ze 7a/co celočíselné kombinace n = k\a\ + /c2a2 vyjádřit právě násobky největšího společného dělitele (ai, a2). Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky OOOOO0OOOOOOOOOOO Důkaz. Jistě stačí větu dokázat pro ai, a2 G N. Všimněme si, že jestliže je možné nějaká čísla r,sGZ vyjádřit ve tvaru r — r\B\ + ^2, s = s\a\ + S2a2, kde ri, r2, si, S2 G Z, můžeme tak vyjádřit i r + s = (n + si)ai + (r2 + s2)a2 a také c • r = (c • n)ai + (c • r2)a2 pro libovolné c G Z. Protože ai = 1 • ai + 0 • a2, a2 = 0 • ai + 1 • a2, plyne z (5), že takto můžeme vyjádřit i 33 = 3i — qiS2, 34 = a2 — ^2^3» ■ ■ ■ , = 3k-3 9/c-3^/c-2» COŽ je ovšem (ai, a2). □ Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky oooooo«oooooooooo 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 je dostupný na https://sage.math.muni.cz/home/pub/6/. 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. Společní dělitelé a společné násobky OOOOOOO0OOOOOOOOO Nejmenší společný násobek Problémy teorie čísel Dělitelnost ooo ooooo 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. Společní dělitelé a společné násobky OOOOOOO0OOOOOOOOO Nejmenší společný násobek Problémy teorie čísel Dělitelnost ooo ooooo Pro libovolná celá čísla ai, a2 existuje jejich nejmenší společný násobek [ai, a2] a platí (ai, a2) • [ai, a2] = |ai • a2 Důkaz Věta jistě platí, je-li některé z čísel ai,a2 rovno nule. Můžeme navíc předpokládat, že obě nenulová čísla ai,a2 jsou kladná, neboť jejich znaménka se v dokazovaném vzorci neprojeví. Budeme hotovi, ukážeme-li, že q = a± • a2/(ai, a2) je nejmenší společný násobek čísel ai,a2. □ Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky OOOOOOOO0OOOOOOOO Dokončení. Protože (ai, a-i) je společný dělitel čísel a±, a2, jsou ai/(ai, 32) i «32/(31, 32) celá čísla, a proto q = 3ia2 3\ (ai,a2) (ai,a2) • 32 = 32 (3l,32) je společný násobek čísel ai, a2- Podle věty 3 existují ki, l<2 G tak, že (ai, a2) = /qai + ^a2- Předpokládejme, že n € Z je libovolný společný násobek čísel ai,a2 a ukážeme, že je dělitelný číslem q. Je tedy n/ai, n/a2 G Z, a proto je i celé číslo n , n ki + 32 31 k2 = n(kxai + k2a2) n(ai,a2) n 3\32 3\32 To ovšem znamená, že q n, což jsme chtěli dokázat. □ Společní dělitelé a společné násobky OOOOOOOOO0OOOOOOO Nesoudělnost Problémy teorie čísel Dělitelnost ooo ooooo Definice Čísla ai, a2,..., a„ e Z se nazývají nesoudělná, jestliže platí (ai, a2,..., 3n) = 1. Čísla ai, a2,..., an £ Z se nazývají po č/\/ol/ nesoudělná, jestliže pro každé i J takové, že 1 < / < j < n, platí (ah a j) = 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 ooooo Společní dělitelé a společné násobky oooooooooo«oooooo Věta Pro libovolná přirozená čísla a, b, c platí O {ac, bc) = (a, b) • c, O jestliže a | bc, (a, b) = 1, pak a \ c, O d = (a, b) praVě řebc/y /cc/yž existují qi, (72 £ N ta/c, že a = c%, b = dq2 a (qu q2) = 1. Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky OOOOOOOOOOO0OOOOO Důkaz. ad 1. Protože (a, b) je společný dělitel čísel a, b, je (a, b) • c společný dělitel čísel ac, bc, proto (a, b) • c | (ac, bc). Podle Bezoutovy věty existují /c, / G Z tak, že (a, b) — ka + Ib. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo kac + Ibc = (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky OOOOOOOOOOO0OOOOO Důkaz. ad 1. Protože (a, b) je společný dělitel čísel a, b, je (a, b) • c společný dělitel čísel ac, bc, proto (a, b) • c | (ac, bc). Podle Bezoutovy věty existují /c, / G Z tak, že (a, b) — ka + Ib. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo kac + Ibc = (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají, ad 2. Předpokládejme, že (a, b) = 1 a a | bc. Podle Bezoutovy věty existují /c, / G Z tak, že ka -\- íb — 1, odkud plyne, že c = c{ka + Ib) = /cca + lbe. Protože a | bc, plyne odsud, že i a Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky OOOOOOOOOOO0OOOOO Důkaz. ad 1. Protože (a, b) je společný dělitel čísel a, b, je (a, b) • c společný dělitel čísel ac, bc, proto (a, b) • c | (ac, bc). Podle Bezoutovy věty existují /c, / G Z tak, že (a, b) — ka + Ib. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo kac + Ibc = (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. ad 2. Předpokládejme, že (a, b) = 1 a a | bc. Podle Bezoutovy věty existují /c, / G Z tak, že ka -\- íb — 1, odkud plyne, že c = c(/ca + Ib) = /cca + lbe. Protože a | bc, plyne odsud, že i a | c. ad 3. Nechť d = (a, b), pak existují qi, q2 £ N tak, že a = c/qi, b = c/q2. P^k podle 1. části platí d = (a, b) = (c%, c/q2) = d • (qi, q2), a tedy (qi, q2) = 1. Naopak, je-li a = dqi, b = c/q2 a (qi, q2) = 1, pak (a, b) = (c/qi, c/q2) = d(qi, q2) — d - 1 — d (opět užitím 1. části tohoto tvrzení). □ Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky oooooooooooo«oooo 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 ooooo Společní dělitelé a společné násobky oooooooooooo«oooo 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 257885161 — 1 má pouze 17 425170 cifer). Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooooo«ooo 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 ooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooooo-sooo 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. Důkaz. "Předpokládejme, že p je prvočíslo a p \ ab, kde a, b £ Protože (p, a) je kladný dělitel p, platí (p, a) — p nebo (p, a) = 1 V prvním případě p | a, ve druhém p | b podle části 2. předchozí věty. Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky ooooooooooooo«ooo 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. Důkaz. Předpokládejme, že p je prvočíslo a p \ ab, kde a, b £ Protože (p, a) je kladný dělitel p, platí (p, a) — p nebo (p, a) = 1. V prvním případě p | a, ve druhém p | b podle části 2. předchozí věty. "<^" Jestliže p není prvočíslo, musí existovat jeho kladný dělitel různý od 1 a p. Označíme jej a; pak ovšem b — - £ N a platí p = ab, odkud l 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.) Společní dělitelé a společné násobky OOOOOOOOOOOOOO0OO Základní věta aritmetiky Problémy teorie čísel Dělitelnost ooo ooooo 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.) Poznámka Dělitelnost je možné obdobným způsobem definovat v libovolném oboru integrity (zkuste si rozmyslet, proč se omezujeme na obory integrity). V některých oborech integrity přitom žádné prvky s vlastností prvočísla (říkáme jim ireducibilní) neexistují (např. Q), v jiných sice ireducibilní prvky existují, ale zase tam neplatí věta o jednoznačném rozkladu (např. v Z(V^5) máme následující rozklady: 6 = 2 • 3 = (1 + • (1 ~~ \í~5); zkuste si rozmyslet, že všichni uvedení činitelé jsou skutečně v Z(V^5) ireducibilní). Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky OOOOOOOOOOOOOOO0O Důkaz. Nejprve dokážeme indukcí, že každé n > 2 je možné vyjádřit jako součin prvočísel. Je-li n = 2, je n součin jediného prvočísla 2. Předpokládejme nyní, že n > 2 a že jsme již dokázali, že libovolné nf, 2 < n' < n, je možné rozložit na součin prvočísel. Jestliže n je prvočíslo, je součinem jediného prvočísla. Jestliže n prvočíslo není, pak existuje jeho dělitel d, 1 < d < n. Označíme-li c = ^, platí také 1 < c < n. Z indukčního předpokladu plyne, že c i d je možné vyjádřit jako součin prvočísel, a proto je takto možné vyjádřit i jejich součin c • d = n. j Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky OOOOOOOOOOOOOOO0O Důkaz. Nejprve dokážeme indukcí, že každé n > 2 je možné vyjádřit jako součin prvočísel. Je-li n = 2, je n součin jediného prvočísla 2. Předpokládejme nyní, že n > 2 a že jsme již dokázali, že libovolné nf, 2 < n' < n, je možné rozložit na součin prvočísel. Jestliže n je prvočíslo, je součinem jediného prvočísla. Jestliže n prvočíslo není, pak existuje jeho dělitel d, 1 < d < n. Označíme-li c = ^, platí také 1 < c < n. Z indukčního předpokladu plyne, že c i d je možné vyjádřit jako součin prvočísel, a proto je takto možné vyjádřit i jejich součin c • d = n. Nyní dokážeme jednoznačnost. Předpokládejme, že platí rovnost součinů pi • p2.....pm = qi • Q2qs, kde pi,..., pm, <7i,..., qs jsou prvočísla a navíc platí pi < p2 < • • • < pm, 9i < qi < • • • < 9s 3 1 < m < s. Indukcí vzhledem k m dokážeme, že m = s, pi = qri,..., pm = c/m. □ J Problémy teorie čísel Dělitelnost Společní dělitelé a společné násobky ooo ooooo oooooooooooooooo* Je-li m = 1, je pi = q\.....qs prvočíslo. Kdyby s > 1, mělo by číslo pi dělitele q\ takového, že 1 < q\ < pi (neboť Q2Q3 .. • qs > 1), což není možné. Je tedy s = 1 a platí pi = q\. Problémy teorie čísel ooo Dělitelnost ooooo Společní dělitelé a společné násobky oooooooooooooooo* Dokončení. Je-li m = 1, je pi = q\.....qs prvočíslo. Kdyby s > 1, mělo by číslo pi dělitele q\ takového, že 1 < q\ < pi (neboť Q2Q3 ... <7S > 1), což není možné. Je tedy s = 1 a platí pi = q\. Předpokládejme, že m > 2 a že tvrzení platí pro m — 1. Protože Pi ■ P2Pm = <7i • 92<7s. dělí pm součin gi.....qs, což je podle Euklidovy věty možné jen tehdy, jestliže pm dělí nějaké g; pro vhodné / e {1, 2,..., s}. Protože q\ je prvočíslo, plyne odtud Pm — Qi (neboť pm > 1). Zcela analogicky se dokáže, že qs — pj pro vhodné j e {1,2,..., m}. Odtud plyne qs = Pj < Pm = qr/ < qSí takže pm = qs. Vydělením dostaneme pi • P2.....Pm-i — Qi ' Q2Qs-i, 3 tedy z indukčního předpokladu m — 1 = s — 1, pi = qi,..., pm_i = qm-i- Celkem tedy m = s a pi = qi,..., pm_i = pm = qm. Jednoznačnost, a tedy i celá věta, je dokázána. □