Motivačn í úvod Dělitelnost Společní dělitelé a a společné násobky 00 ooooo ooooooooooooo Diskrétní matematika - 1. týden Elementární teorie čísel - dělitelnost Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2014 Motivační úvod Dělitelnost Společní dělitelé a a společné násobky 00 ooooo ooooooooooooo Obsah přednášky Motivační úvod Dělitelnost Společní dělitelé a a společné násobky í úvod Dělitelnost Společní dělitelé a a společné násobky ooooo ooooooooooooo Dop oručené zc Iroje • 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. • 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/ATC10.pdf Motivační úvod •O Dělitelnost ooooo Společní dělitelé a a společné násobky ooooooooooooo V několika prednáškach se teď budeme zabývat úlohami o celých číslech. Prevážne 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. Ačkoli jsou přirozená a konec konců i celá čísla v jistém smyslu nejjednodušší matematickou strukturou, zkoumání jejich vlastností 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í. God made integers, all else is the work of man. (L. Kronecker) Uveďme některé z nejznámějších: • 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 • Goldbachovu hypotézu (rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel), • nebo klenot mezi problémy teorie čísel velkou Fermatovu větu (Fermaťs Last Theorem) - rozhodnout, zda existují přirozená čísla n, x, y, z tak, že n > 2 a platí x" + y" = z"; Pierre de Fermat jej formuloval cca 1637, vyřešil Andrew Wiles v roce 1995. Motivační úvod 00 Dělitelnost •oooo Společní dělitelé a a společné násobky ooooooooooooo Definice Řekneme, že celé číslo a dělí 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: a j b A b | c a \ b A a | c a \ b A fa > O a | c a \ b + c A a | b — c (a | b <í=^> ac | fac) a < b Motivační úvod 00 Dělitelnost o«ooo Společní dělitelé a a společné násobky ooooooooooooo Príklad Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem Řešení Platí n2 — 1 = (n + l)(n — 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 n + 1 | 2 plyne n + 1 = 2, proto n = 1. Uvedenou vlastnost má tedy jediné přirozené číslo 1. □ Motivační úvod Dělitelnost Společní dělitelé a a společné násobky 00 oo»oo ooooooooooooo Dělení se zbytkem Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a 6 Z, m £ N existují jednoznačně určená čísla q 6 Z, r £ {0,1,..., m — 1} tak, že a = qm + r. Důkaz. Dokažme nejprve existenci čísel q, r. Předpokládejme, že přirozené číslo m je dáno pevně a dokažme úlohu pro libovolné a 6 Z. Nejprve budeme předpokládat, že a £ No a existenci čísel q, r dokážeme indukcí: Je-li O < a < m, stačí volit q = O, r = a a rovnost a = qm + r platí. Předpokládejme nyní, že a > m a že jsme existenci čísel q, r dokázali pro všechna a' 6 {0,1, 2,..., a — 1}. Speciálně pro a' = a — m tedy existují q', r' tak, že a' = q'm + r' a přitom r' £ {0,1,..., m — 1}. Zvolíme-li q = q' + 1, r = r', platí a = a' + m = (q' + l)m + r' = + r, což jsme chtěli dokázat. □ Motivační úvod 00 Dělitelnost ooo»o Společní dělitelé a a společné násobky ooooooooooooo Dokončení důkazu. Existenci čísel q, r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < O, 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' = O, položíme r = O, q = —q'; je-li r > O, 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 gi, <72 £ Z; 1, r2 G {0,1,..., m — 1} platí a = gim + r\ = (72^ + ^2- Úpravou dostaneme ri — r2 = (<72 — <7i)™, a tedy m | ri — r2. Ovšem z O < ri < m, O < r2 < m plyne —m < ri — r2 < m, odkud dostáváme ri — r2 = 0. Pak ale i (92 — 0 čísel 3i,32, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel 3i,32, se nazývá největšíspolečný dělitel (resp. nejmenšíspolečný násobek) čísel 3i,32 a značí se (31,32) (resp. [31,32]). Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky 0*00000000000 Poznámka Přímo z definice plyne, že pro libovolné a, b G Z platí (a, b) = (b, a), [a, b] = [b, a], (a, 1) = 1, [a, 1] = \a\, (a, 0) = \a [a,0] =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), a„) [ai,..., an] = [[ai,..., a„-i], an] Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky oo«oooooooooo Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b G Z čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla /r?i, /r?2 G No totiž podle definice platí, že pokud m\ \ rri2 a zároveň rr>2 | mi, je nutně m\ = rrt2- 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 3i, 32 jsou přirozená čísla. Pro každé n > 3, pro které än-i Ý O, označme an zbytek po dělení čísla a„_2 číslem a„_i. Pak po konečném počtu kroků dostaneme a^ = O a platí 3k-l = (ai, 32)- Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky 000*000000000 Důkaz. 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 ak = O, přičemž 3/<_i 7^ 0. Z definice čísel an plyne, že existují celá čísla qi, q2,..., qk-2 tak, že 3\ = qi ■ a2 + a3, 3k-3 = qk-3 ■ 3k-2 + 3/r-l 3k-2 = qk-2 ■ 3k-í- Z poslední rovnosti plyne, že 3/<_i | 3/<_2, dále ak-\ \ 3/c-3, atd., je tedy 3/<_i společný dělitel čísel 3i,32- Naopak jejich libovolný společný dělitel dělí i číslo 33 = a\ — q\32, proto i 34 = 32 - 9233,..., a proto i ak-i = ak_3 - qk_3ak-2. Dokázali jsme, že ak-\ je největší společný dělitel čísel a\, 32. □ Motivační úvod Dělitelnost Společní dělitelé a a společné násobky 00 ooooo oooo»oooooooo Vlastnosti gcd Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, fa) = (a, —b) = (—a, fa) = (—a, —fa), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Věta (Bezoutova) Pro libovolná celá čísla a\, 32 existuje jejich největší společný dělitel (ai, 32), přitom existují celá čísla k\, /c2 tak, že (ai, a2) = /qsi + /c232. Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky ooooo»ooooooo Důkaz. Jistě stačí větu dokázat pro a\, 32 G N. Všimněme si, že jestliže je možné nějaká čísla r, s G Z vyjádřit ve tvaru r = r\3\ + ^2, s = s\3\ + S232, 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 • ri)ai + (c • r2)a2 pro libovolné c G Z. Protože 3i = 1 • a\ + O • 32, 32 = O • 3i + 1 • 32, plyne z (5), že takto můžeme vyjádřit i 33 = 3l — <7l32, 34 = 32 — <7233, . . . , 3fr_i = 3fr_3 — qk-3ak-2, C°Ž je ovšem (si, 32). □ Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky oooooo»oooooo 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/. i Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky ooooooo»ooooo 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. To, že znalost těchto základů je občas důležitá i v praktickém životě, dokazuje Bruče Willis a Samuel Jackson ve filmu Smrtonosná past 3, kde mají za úkol zlikvidovat bombu pomocí 4 galonů vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonů. Zde stačí s využitím Euklidova algoritmu najít celá čísla k, I tak, že bude platit 3k + 5/ — 4. Netroufám si tvrdit, že zmínění herci ovládají uvedené základy teorie čísel (tuto konkrétní úlohu jistě snadno vyřešíte experimentálně), nicméně předchozí věty dávají návod, jak vyřešit úlohu tohoto typu s libovolnými zadanými parametry. Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky oooooooo»oooo Věta Pro libovolná celá čísla a\, 32 existuje jejich nejmenší společný násobek [si, 32] a platí (si, 32) • [si, 32] = |si • 321- Důkaz. Věta jistě platí, je-li některé z čísel 3i, 32 rovno nule. Můžeme navíc předpokládat, že obě nenulová čísla 3i,32 jsou kladná, neboť jejich znaménka se v dokazovaném vzorci neprojeví. Budeme hotovi, ukážeme-li, že q = a\ • 32/(31, 32) je nejmenší společný násobek čísel 3i, 32. □ Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky ooooooooo»ooo Dokončení. Protože (ai, 32) je společný dělitel čísel 3i, 32, jsou 31/(31,32) i 32/(31,32) celá čísla, a proto _ 3i32 _ 3i _ 32 (31,32) (31,32) (31,32) je společný násobek čísel a\, 32. Podle věty 3 existují k\, k2 £ Z tak, že (si, 32) = k\3\ + k2a2. Předpokládejme, že n £ Z je libovolný společný násobek čísel 3i,32 a ukážeme, že je dělitelný číslem q. Je tedy n/si, 0/32 6 Z, a proto je i celé číslo n . n n(k1a1 + k2a2) n(a1,a2) n — • K\ H--• «2 = - = - = — ■ 32 3l 3i32 3i32 Í7 To ovšem znamená, že q \ n, což jsme chtěli dokázat. □ —1 Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky oooooooooo»oo Definice Čísla 3i, 32,..., an G Z se nazývají nesoudělná, jestliže platí (si, 32,..., an) = 1. Čísla 3i, 32,..., sn G Z se nazývají po ch/ou nesoudělná, jestliže pro každé /',_/' takové, že 1 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. Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky 00000000000*0 Věta Pro libovolná přirozená čísla a, b, c platí O (ac, bc) = (a, b) • c, 0 jestliže a \ bc, (a, b) = 1, pak a \ c, 0 d = (a, b) právě tehdy, když existujíqi, q2 £ N tak, že a = dqi, b = dq2 a (qi, q2) = 1. Motivační úvod 00 Dělitelnost ooooo Společní dělitelé a a společné násobky 000000000000» 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, fac). Podle Bezoutovy věty existují k, I G Z tak, že (a, Ď) = ka + A£>. Protože (ac, bc) je společný dělitel čísel ac, fac, dělí i číslo kac + A£>c = (a, b) ■ c. Dokázali jsme, že (a, b) ■ c a (ac, fac) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. ad 2. Předpokládejme, že (a, b) = 1 a a | fac. Podle Bezoutovy věty existují It.lsZ tak, že ka + Ib = 1, odkud plyne, že c = c(/ca + A£>) = /cca + lbe. Protože a | fac, plyne odsud, že i a | c. ad 3. Nechť d = (a, fa), pak existují gi, 92 £ N tak, že a = c/qi, fa = c/<72- Pak podle 1. části platí d = (a, b) = (dqi, dq2) = d ■ (qi, q2), a tedy (qi, q2) = 1- Naopak, je-li a = c/<7i, fa = dq2 a (qi, q2) = 1, pak (a, fa) = (dqi, dq2) = d(qi, q2) = d ■ 1 = d (opět užitím 1. části tohoto tvrzení). □