MB141 -10. přednáška Celá čísla a dělitelnost Martin Čadek s využitím přednášek pro předmět MB104 Jarní semestr 2021 10. přednáška Celá čísla a dělitelnost Doporučené zdroje k teorii čísel • 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: / / i s.mun i.cz/el/1431/ podzim2 019/M6520/um/main-print.pdf • 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 • Adam Spencer, Why I fell in love with monster prime numbers, video, 17 minut, https://www.ted.com/talks/adam_spencer_why_ i_fell_in_love_with_monster_prime_numbers 10. přednáška Celá čísla a dělitelnost 2/21 Osnova 10. přednášky • Dělitelnost a dělení se zbytkem • Největší společný dělitel, Eukleidův algoritmus • Bezoutova věta • Nesoudělnost • Prvočísla, rozklad čísel na prvočísla 10. přednáška Celá čísla a dělitelnost 3/21 Problémy teorie čísel 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) 10. přednáška Celá čísla a dělitelnost 4/21 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. 10. přednáška Celá čísla a dělitelnost 5/21 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á /c, í tak, aby 2/c + U = 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 2/c + 5£ = n pro nějaká celá /c, L Umíme to pro jakékoliv hodnoty mincí? Jak by to dopadlo třeba pro 7 k + 11 i = n? A jak pro 2/c + U = n? 10. přednáška Celá čísla a dělitelnost 6/21 Dělitelnost Definice Řekneme, že celé číslo a dělí celé číslo b (neboli číslo b je dělitelné číslem a, též b\e 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 \ b A b \ c a \ b A a | c a b A b > 0 a c a|Ď + c A a\b- c (a | £> <=^> ac | Ďc) a < b 10. přednáška Celá čísla a dělitelnost Příklady Příklad Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem 3. 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. 10. přednáška Celá čísla a dělitelnost Dělení se zbytkem Věta (o dělení celých čísel se zbytkem) Pro libovolné zvolená čísla a e Z, m e N existují jednoznačné určená čísla q e Z, r e {0,1,..., m - 1} tak, že a = qm+ r. Důkaz 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ý). 10. přednáška Celá čísla a dělitelnost Dělení se zbytkem - pokračování Číslo g, resp. r z věty se nazývá (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 e Z číslem m e N jedna, je jedna i zbytek po dělení čísla ab číslem m. 10. přednáška Celá čísla a dělitelnost Největší společný dělitel (gcd) Jedním z nedů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 a-i, a2. Libovolné celé číslo m takové, že m | a-i, m | a2 se nazývá společný dělitel čísel a-i, a2. Společný dělitel m > 0 čísel a-i, a2, který je dělitelný libovolným společným dělitelem čísel a-i, a2, se nazývá největší společný dělitel čísel , a2 a značí se (a-i, a2). Například (12,64) = 4. 10. přednáška Celá čísla a dělitelnost Nejmenší společný násobek Definice Mějme celá čísla a-i, a2. Libovolné celé číslo m takové, že a-i | m, a2 | m se nazývá společný násobek čísel a-i, a2. Společný násobek m > 0 čísel a-i, a2, který dělí libovolný společný násobek čísel a-i, a2, se nazývá nejmenší společný násobek čísel , a2 a značí se [a-i, a2]. Poznámka Přímo z definice plyne, že pro libovolné a,b eZ platí (a,Ď) = (Ď,a), [a,Ď] = [Ď,a], (a, 1) = 1, [a, 1] = |a|, (a,0) = |a|, [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í (a-i,..., sn) = ((a-i,..., an_i), sn) [a-i,..., sn] = [[a-i,..., an_i ], sn] 10. přednáška Celá čísla a dělitelnost 12/21 Euklidův algoritmus Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b e čísla (a, b) a [a, b] vůbec existují. To si lze hezky představit přes rozklad 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 a77-|, m2 g N0 totiž podle definice platí, že pokud m1 | m2 a zároveň m2 | m^, je nutně = m2. Důkaz existence čísla (a, b) podáme (spolu s algoritmem jeho nalezení) v následující větě. Věta (Euklidův algoritmus) Nechť a-i, a2 jsou přirozená čísla. Pro každé n>3, pro které an_-| ^ 0, označme an zbytek po dělení čísla an_2 číslem an_-i. Pak po konečném počtu kroků dostaneme ak = 0 a platí a/c-1 = (ai, a2). 10. přednáška Celá čísla a dělitelnost Euklidův algoritmus - příklad Algoritmus a důkaz jeho korektnosti demonstrujeme na příkladu: Příklad Určete nejvetšího společného dělitele čísel 10175 a 2277. 10. přednáška Celá čísla a dělitelnost Vlastnosti největšího společného dělitele Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b e Z platí (a, £>) = (a, -£>) = (-a, £>) = (-a, -£>), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Věta (Bezoutova) Pro libovolná celá čísla a-i, a2 existuje jejich největší společný dělitel (a^,a2), přitom existují celá čísla /c-i, k2 tak, že (ai,a2) = kAaA + k2a2. Důsledek Pro libovolná celá čísla a^, a2 lze jako celočíselné kombinace n = /c-ia-i + /c2a2 vyjádřit právě násobky největšího společného dělitele (al5a2). Ukázat praktický výpočet pro a^ = 10175, a2 = 2277. 10. přednáška Celá čísla a dělitelnost 15/21 Příklad 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/. 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. 10. přednáška Celá čísla a dělitelnost Nejmenší společný násobek Pro libovolná celá čísla a-i, a2 existuje jejich nejmenší společný násobek [a-i, a2] a platí (a^, a2) • [ai, a2] = \a^ • a2|. Důkaz. Nejlépe se vidí pres rozklad na součin prvočísel. □ 10. přednáška Celá čísla a dělitelnost Nesoudělnost Definice Čísla a\, a2,..., an e Z se nazývají nesoudělná, jestliže platí (a-i, a2,..., an) = 1. Čísla a-i, a2,..., an e Z se nazývají po c/vol/ nesoudělná, jestliže pro každé i J takové, že 1 < i 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 10. přednáška Celá čísla a dělitelnost Nesoudělnost - důležité vlastnosti Pro libovolná přirozená čísla a, b, c platí O (ac, bc) = (a, b) • c, Q jestliže a | £>c, (a, Ď) = 1, pak a | c, O d = (a, £>) prává teftdy, /cdyz existují, g2 e N fa/c, ze a = dq^b = dq2a{q^q2) = 1. 10. přednáška Celá čísla a dělitelnost Prvočísla 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. 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). 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). 10. přednáška Celá čísla a dělitelnost 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 (Eukleidova o prvočíslech) Přirozené číslo p>2je prvočíslo, právě když platí: pro každá celá čísla a,bzp\ab plyne p | 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" jednoho prvočísla.) 10. přednáška Celá čísla a dělitelnost 21/21