Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky oo oooo ooooooo Diskrétni matematika - 1. týden Elementární teorie čísel - dělitelnost Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2019 Společní dělitelé a a společné násobky ooooooo Obsah přednášky Problémy teorie čísel Dělitelnost oo oooo Q Problémy teorie čísel 0 Dělitelnost Q Společní dělitelé a a společné násobky □ ť5P Společní dělitelé a a společné násobky ooooooo Doporučené zdroje Problémy teorie čísel Dělitelnost oo oooo • 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 a společné násobky oo oooo ooooooo 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 Společní dělitelé a a společné násobky ooooooo Plán prednášky Problémy teorie čísel Dělitelnost oo oooo Q Problémy teorie čísel s— v-\ i /-I s\ I i -I- s\ I s\ "v "v rnri rtrnn "v <~ l-\ lx \ / Společní dělitelé a a společné násobky ooooooo Příklady problémů teorie čísel Problémy teorie čísel Dělitelnost •o oooo 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 a společné násobky ooooooo Příklady problémů teorie čísel Problémy teorie čísel Dělitelnost •o oooo 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 a společné násobky ooooooo Příklady problémů teorie čísel Problémy teorie čísel Dělitelnost •o oooo 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 a společné násobky ooooooo Příklady problémů teorie čísel Problémy teorie čísel Dělitelnost •o oooo 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 a společné násobky ooooooo diofantické rovnice Problémy teorie čísel Dělitelnost o« oooo Bruče Willis a Samuel Jackson ve filmu Smrtonosná past 3 mají za úkol zlikvidovat bombu pomocí 4 galonů vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonů. Mají tedy vyřešit nad celými čísly rovnici 3/c + bí = 4. To asi zvládneme - např. tak, že si všimneme, že 5£ musí dávat po dělení 3 zbytek 1. Je tedy í — 2 + 3t pro jakékoliv celé t (protože je při počítání "až na násobky tří"pětka totéž co dvojka a ta je sama sobě inverzním prvkem). Dosazením spočteme 3(/c + 5r) = —6 a tedy volba t dá řešení (M) = (-2-5ŕ,2 + 3ŕ). Umíme to pro jakékoliv koeficienty? Jak by to dopadlo třeba pro 2/c | A-£ = 3? Společní dělitelé a a společné násobky ooooooo Plán prednášky Problémy teorie čísel Dělitelnost oo oooo 0 Dělitelnost s— v-\ i /-I s\ I i -I- s\ I s\ "v "v rnri rtrnn "v <~ l-\ lx \ / □ S1 Problémy teorie čísel oo Dělitelnost •ooo Společní dělitelé a a společné násobky ooooooo 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. 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 oo Dělitelnost o«oo Společní dělitelé a a společné násobky ooooooo Příklad Zjistěte, pro která přirozená čísla n je číslo n + 1 dělitelné číslem n + 1. Společní dělitelé a a společné násobky ooooooo Dělení se zbytkem Problémy teorie čísel Dělitelnost oo oo«o Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a 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]). Problémy teorie čísel oo Dělitelnost oooo Společní dělitelé a a společné násobky o«ooooo Poznámka Přímo z definice plyne, že pro libovolné a, b e Z platí (a, 6) = (b, a), [a, b] = [b, a], (a, 1) = 1, [a, 1] = |a|, (a, 0) = a [a,0] = 0. Problémy teorie čísel oo Dělitelnost oooo Společní dělitelé a a společné násobky o«ooooo Poznámka Přímo z definice plyne, že pro libovolné a, b G (a, b) = (b, a), [a,b] = [b,a], (a,l) = l, [a, 1] [a,0] = 0. platí (3,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í (<9l, . . . , an) = ((^1, • • • 5 3n— l)? & n) [<9l, . . . , an] = [[^1, • • • , 3n— 1], an] Společní dělitelé a a společné násobky OO0OOOO Euklidův algoritmus Problémy teorie čísel Dělitelnost oo oooo 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-\. Pak po konečném počtu kroků dostaneme a^ — O a platí 3k-l = (^1, 32). Problémy teorie čísel Dělitelnost Společní dělitelé a a společné násobky oo oooo OOO0OOO 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 a společné násobky oo oooo OOO0OOO 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) = kiai + k2a2. Společní dělitelé a a společné násobky oooo«oo Nejmenšř společný násobek Problémy teorie čísel Dělitelnost oo oooo 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 a společné násobky OOOOO0O Nesoudělnost Problémy teorie čísel Dělitelnost oo oooo Definice Čísla ai, a2,..., a„ e 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 oo Dělitelnost oooo Společní dělitelé a a společné násobky 000000« 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.