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 9 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/c + 11^ = r?? 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, Ď, 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 | Ď- c (a | £> <=^> ac | bc) 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ý). CL » ^ + 10. přednáška Celá čísla a dělitelnost Dělení se zbytkem - pokračování Číslo(^)resp^^ 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 / m m přitom 0 < — < 1. ~ 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. ď = a- b ; 10. přednáška Celá čísla a dělitelnost Největší společný dělitel (gcd) ££C*L CflžfrteQÍ CevU***" OUaasiIs 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 (ai, a2). - Například (12,64) = 4. 10. přednáška Celá čísla a dělitelnost 4/U(+tW y^cč^j oCCUlcL £ 4- 41 - Zz-*b 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 a^, a2 a značí se [a-i, a2]. Poznámka Přímo z definice plyne, že pro libovolné a, b e Z platí (a,Ď) = (Ď,a), [a,b] = [fc,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,..., an) = ((a-i,..., an_i), an) [a-i,..., an] = [[a-i,..., an_i ], an] 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, jsou přirozená čísla. Pro každé n>3, pro které an_-| ťm), označme an zbytek po dělení čísla an_2 číslem an^. 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 ŕ GLle,-i fiŮC Ulfa. 4.4, a4 trs / otta c4( &u.-i a 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. Pro libovolná celá čísla a^, a2 lze jako celočíselné kombinace \n = /c-i a-i + /coaojvviádřit právě násobky největšího společného dělitele (al5a2). <**W^ ^ c*f,*0 Ukázat praktický výpočet pro a^ = 10175, a2 = 2277. 10. přednáška Celá čísla a dělitelnost 15/21 d & ^iLAtfJiQl( k(e fear} k /O ✓ w Ms 111?!- 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. La i, O =■ 10. přednáška Celá čísla a dělitelnost z. Čísla a-i,a2,... ,an e Z se nazývají nesoudělná^jestliže platí Qi, a2,..., an) = 1. Čísla ai, a2,..., an e Z se nazývají po dvou nesoudělná, jestliže pro každé /,/ takové, že 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, 15jsou 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. 1 < / 2 má aspoň dva kladné dělitele:J_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 20/21 /jtetisC p = a, Jb- flee*** a 6- - 4_ b- -í AW z 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 > 2 je 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 ie 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