Diskrétní matematika - 3. týden Elementární teorie čísel - Eulerova věta, řád prvku věta Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Malá Fermatova věta, Eulerova věta oooooooooooo Obsah přednášky Prvočísla Aritmetické funkce oooooooooooooooooo ooooo Q Prvočísla • Poznámky • Dělitelé znovu • Rozložení prvočísel Q Aritmetické funkce • Eulerova funkce cp Q Malá Fermatova věta, Eulerova věta Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo 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. Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo 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 9 Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. a 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/-kučera/texty/ATC10.pdf Prvočísla oooooooooooooooooo Plán přednášky Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Q Prvočísla • Poznámky • Dělitelé znovu • Rozložení prvočísel • Eulerova funkce cp □ s Prvočísla •ooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Připomenutí - věta o jednoznačném rozkladu 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'1 jednoho prvočísla.) •d i Prvočísla O0OOOOOOOOOOOOOOOO PRIMES is in P Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Poznámka Již jsme se zmínili, že je složité o velkých číslech s jistotou rozhodnout, jde-li o prvočíslo (na druhou stranu je o naprosté většině složených čísel snadné prokázat, že jsou skutečně složená). Přesto se v roce 2002 podařilo indickým matematikům (Agrawal, Saxena, Kayal: http://www.cse.iitk.ac.in/users/manind.ra/ algebra/primality_v6 .pdf) dokázat, že problém prvočíselnosti je možné rozhodnout algoritmem s časovou složitostí polynomiálně závislou na počtu cifer vstupního čísla. Nic podobného se zatím nepodařilo v otázce rozkladu čísla na prvočísla (třebaže se obecně nevěří, že je to možné, exaktní důkaz zatím nebyl podán). Prvočísla OO0OOOOOOOOOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo s FACTOR in P? v\ i--? f f* - - - f£*> Nic podobného se zatím nepodařilo v otázce rozkladu čísla na prvočísla (třebaže se obecně nevěří, zeje to možné, exaktní důkaz zatím nebyl podán). Nejrychlejší obecně použitelný faktorizační algoritmus, tzv. síto v číselném tělese1, je sub-exponenciální časové složitosti Oíe1-9^^173^1^^273). Pro podrobnosti navštivte M8190 Algoritmy teorie čísel g Prvočísla OO0OOOOOOOOOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo s FACTOR in P? Nic podobného se zatím nepodařilo v otázce rozkladu čísla na prvočísla (třebaže se obecně nevěří, zeje to možné, exaktní důkaz zatím nebyl podán). Nejrychlejší obecně použitelný faktorizační algoritmus, tzv. síto v číselném tělese1, je sub-exponenciální časové složitosti Oíe1-9^^173^1^^273). Poznámka Peter Shor v roce 1994 vymyslel algoritmus, který faktorizuje v kubickém čase (tj. 0((log A/)3)) na kvantovém počítači. Je k tomu nicméně třeba sestrojit počítače s dostatečným počtem qubits -jak je to obtížné, lze vysledovat z toho, ze v roce 2001 se IBM podařilo pomocí kvantového počítače rozložit číslo 15 a v roce 2012 byl dosažen další faktorizační rekord rozkladem čísla 21. Pro podrobnosti navštivte M8190 Algoritmy teorie čísel rs> Prvočísla OOO0OOOOOOOOOOOOOO RSA Challenge Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Zeje problém rozkladu přirozeného čísla na prvočísla výpočetně složitý, o tom svědčí i (již neplatná) výzva učiněná v roce 1991 firmou RSA Security (viz http: //www. rsasecurity. com/rsalabs/node. asp?id=2093). Pokud se komukoliv podařilo rozložit čísla označená podle počtu cifer jako RSA-100, ..., RSA-704, RSA-768, ..., RSA-2048, mohl obdržet 1000_____ 30 000, 50 000, ..., resp. 200 000 dolarů (číslo RSA-100 rozložil v temže roce Arjen Lenstra, číslo RSA-704 bylo rozloženo v roce 2012, některá dosud rozložena nebyla). Prvočísla OOOO0OOOOOOOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Díky jednoznačnosti rozkladu na prvočísla jsme schopni (se znalostí tohoto rozkladu) snadno odpovědět i na otázky ohledně počtu či součtu dělitelů konkrétního čísla. Stejně snadno dostaneme i (z dřívějška intuitivně známý) postup na výpočet největšího společného dělitele dvou čísel ze znalosti jejich rozkladu na prvočísla. • Každý kladný dělitel čísla a — p11.....pkk je tvaru , kde at?i. ..., rrik £ Nq a m\ < r?i, rr?2 < r?2, Prvočísla OOOO0OOOOOOOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Díky jednoznačnosti rozkladu na prvočísla jsme schopni (se znalostí tohoto rozkladu) snadno odpovědět i na otázky ohledně počtu či součtu dělitelů konkrétního čísla. Stejně snadno dostaneme i (z dřívějška intuitivně známý) postup na výpočet největšího společného dělitele dvou čísel ze znalosti jejich rozkladu na prvočísla. Důsledek • Každý kladný dělitel čísla a = p"1.....pnkk je tvaru p™1.....p™k, kde at?i. ..., rrik £ No a m\ < r?i, rr?2 < r?2, ■ ■ ■ mk < nk. • Číslo a má tedy právě r(a) = (r?i + l)(r?2 + 1)(nk + 1) kladných dělitelů, jejichž součet je "00 = Pľi+1 -1 pi-i Pnkk+1 -1 Pk -1 >0 Q,o Ts* J1 I ^ r n i * _ i fv* \ v - (m 1 \ 0 Prvočísla ooooo«oooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Důsledek (Pokr.) • Jsou-li pi,..., pi< navzájem různá prvočísla a r?i, ..., m^ G No a označíme-li r\ — min{r?;, m,}, , nk, mi, % t; = max{r?;, 171 i ^Pro každé i = ^1. 2,..., k, platí ^^iv^k (pí.....p/c> Pi .....Pk ) = Pi.....Pk ■ [pí ni pI^pT p7\ = pí1 Pk >0 0,0 Malá Fermatova věta, Eulerova věta oooooooooooo Mersenneho prvočísla a dokonalá čísla Prvočísla Aritmetické funkce 000000*00000000000 ooooo S pojmem součet všech kladných dělitelů čísla a souvisí pojem tzv. dokonalého čísla a, které splňuje podmínku a(a) = 2a, resp. slovně: součet všech kladných dělitelů čísla a menších než a samotné je roven číslu a. Takovými čísly jsou např. 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 +14, 496 a 8128 (jde o všechna dokonalá čísla menší než 10 000). Prvočísla OOOOOO0OOOOOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Mersenneho prvočísla a dokonalá čísla S pojmem součet všech kladných dělitelů čísla a souvisí pojem tzv. dokonalého čísla a, které splňuje podmínku a(a) = 2a, resp. slovně: součet všech kladných dělitelů čísla a menších než a samotné je roven číslu a. Takovými čísly jsou např. 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 +14, 496 a 8128 (jde o všechna dokonalá čísla menší než 10 000). Poznámka Lze ukázat, že sudá dokonalá čísla jsou v úzkém vztahu s tzv. Mersenneho prvočísly. Platí totiž: a je sudé dokonalé číslo, právě když je tvaru a = 2q~ľ • (2q — 1), kde 2q — 1 je prvočíslo. p^1 -i *?m íl J- J- T 'Í Vvl 1 v * - Prvočísla OOOOOO0OOOOOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Mersenneho prvočísla a dokonalá čísla S pojmem součet všech kladných dělitelů čísla a souvisí pojem tzv. dokonalého čísla a, které splňuje podmínku a(a) = 2a, resp. slovně: součet všech kladných dělitelů čísla a menších než a samotné je roven číslu a. Takovými čísly jsou např. 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 +14, 496 a 8128 (jde o všechna dokonalá čísla menší než 10 000). Poznámka Lze ukázat, že sudá dokonalá čísla jsou v úzkém vztahu s tzv. Mersenneho prvočísly. Platí totiž: a je sudé dokonalé číslo, právě když je tvaru a = 2q~ľ • (2q — 1), kde 2q — 1 je prvočíslo. Na druhou stranu popsat lichá dokonalá čísla se dodnes nepodařilo, resp. dodnes se neví, jestli vůbec nějaké liché dokonalé číslo existuje. Prvočísla OOOOOOO0OOOOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Hledání velkých prvočísel Mersenneho prvočísla jsou právě prvočísla tvaru 2k — 1. Bez zajímavosti není ani to, že právě Mersenneho prvočísla jsou mezi všemi prvočísly nejlépe „vidět" - pro Mersenneho čísla existuje poměrně jednoduchý a rychlý postup, jak ověřit, že jde o prvočísla. Malá Fermatova věta, Eulerova věta oooooooooooo Hledání velkých prvočísel Prvočísla Aritmetické funkce OOOOOOO0OOOOOOOOOO ooooo Mersenneho prvočísla jsou právě prvočísla tvaru 2 — 1. Bez zajímavosti není ani to, že právě Mersenneho prvočísla jsou mezi všemi prvočísly nejlépe „vidět" - pro Mersenneho čísla existuje poměrně jednoduchý a rychlý postup, jak ověřit, že jde o prvočísla Lucas-Lehmerův test Definujme posloupnost (sn)^0 rekurzívně předpisem j íy%/~- so — 4, sn+i = — 2. Pak je číslo Mp = 2P — 1 prvočíslo, právě tehdy, když[Mp dělí sp_2 Prvočísla OOOOOOOO0OOOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Proto není náhodou, že největší známá prvočísla jsou obvykle tvaru 2k — 1 (viz např. http://www.utm.edu/research/primes/largest.html). Jakkoliv může být hledání největšího známého prvočísla chápáno jako pochybná zábava bez valného praktického užitku2, jednak posunuje hranice matematického poznania zdokonaluje použité metody (a často i hardware), jednak může přinést benefit i samotným objevitelům (Electronic Frontier Foundation vypsala odměny EFF Cooperative Computing Awards za nalezení prvočísla majícího alespoň 106,107,108 a 109 číslic - odměny 50, resp. 100 tisíc $ za první dvě kategorie byly vyplaceny v letech 2000, resp. 2009 - v obou případech projektu GIMPS - na další odměny si ještě zřejmě nějaký čas počkáme). 2Viz např. titulek iDnes z 6.února 2013: Největší známé prvočíslo na světě má 17 milionů číslic a je k ničemu Prvočísla OOOOOOOOO0OOOOOOOO Rozložení prvočísel Nyní se budeme snažit zodpovědět následující otázky: O Je prvočísel nekonečně mnoho? Aritmetické funkce ooooo Mala Fermatova věta, Eulerova věta oooooooooooo Malá Fermatova věta, Eulerova věta oooooooooooo Rozložení prvočísel Prvočísla Aritmetické funkce OOOOOOOOO0OOOOOOOO ooooo Nyní se budeme snažit zodpovědět následující otázky: O Je prvočísel nekonečně mnoho? O Je prvočísel nekonečně mnoho v každé (nebo aspoň některé aritmetické posloupnosti? Malá Fermatova věta, Eulerova věta oooooooooooo Rozložení prvočísel Prvočísla Aritmetické funkce OOOOOOOOO0OOOOOOOO ooooo Nyní se budeme snažit zodpovědět následující otázky: O Je prvočísel nekonečně mnoho? O Je prvočísel nekonečně mnoho v každé (nebo aspoň některé aritmetické posloupnosti? O Jak jsou prvočísla rozložena mezi přirozenými čísly? Prvočísla OOOOOOOOO0OOOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Rozložení prvočísel Nyní se budeme snažit zodpovědět následující otázky: O Je prvočísel nekonečně mnoho? O Je prvočísel nekonečně mnoho v každé (nebo aspoň některé) aritmetické posloupnosti? O Jak jsou prvočísla rozložena mezi přirozenými čísly? There are two facts about the distribution of prime numbers. The first is that, [they are] the most arbitrary and ornery objects studied by mathematicians: they grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision. Don Zagier Prvočísla OOOOOOOOOO0OOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísel je nekonečně mnoho Věta (Eukleidés) Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Prvočísla OOOOOOOOOO0OOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísel je nekonečně mnoho Věta (Eukleidés) Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Důkaz. Předpokládejme, že prvočísel je konečně mnoho a označme je Pi•> Pí-) • • • •> Pn- Položme N — p\ - P2 - - - Pn + 1. Toto číslo je bud samo prvočíslem neboje dělitelné nějakým prvočíslem různým od pi,..., pn (čísla pi,..., pn totiž dělí číslo N — 1), což je spor. □ Prvočísla OOOOOOOOOO0OOOOOOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísel je nekonečně mnoho Věta (Eukleidés) Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Důkaz. Předpokládejme, že prvočísel je konečně mnoho a označme je Pi•> Pí-) • • • •> Pn- Položme N — p\ - P2 - - - Pn + 1. Toto číslo je bud samo prvočíslem neboje dělitelné nějakým prvočíslem různým od pi,..., pn (čísla pi,..., pn totiž dělí číslo N — 1), což je spor. □ Poznámka Existuje mnoho variant důkazů nekonečnosti prvočísel z různých oblastí matematiky, uveďme ještě alespoň některá tvrzení, z nichž zároveň získáme alespoň částečnou informaci o rozložení prvočísel mezi přirozenými čísly. Prvočísla ooooooooooo«oooooo Aritmetické funkce ooooo Prvočísel je vcelku hodně Malá Fermatova věta, Eulerova věta oooooooooooo Příklad Pro celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. ■ □ 3 ► < ► 4 = >0 Q,o Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísel je vcelku hodně Prvočísla Aritmetické funkce ooooooooooo«oooooo ooooo Příklad Pro celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. Řešení Označme p libovolné prvočíslo dělící číslo n\ — 1 (takové existuje podle Základní věty aritmetiky, protože n\ — 1 > 1). Kdyby p < n, muselo by p dělit číslo n\ a nedělilo by n\ — 1. Je tedy n < p. Protože p | (r?! — 1), platí p < n\ — 1, tedy p < n\. Prvočíslo p splňuje podmínky úlohy. □ Prvočísla oooooooooooo«ooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Z této věty rovněž vyplývá nekonečnost prvočísel, její tvrzení je ale velice slabé. Následující tvrzení, uvedené bez důkazu, je podstatně silnejší. Věta (Čebyševova, Bertrandův postulát) Pro libovolné číslo n > 1 existuje alespoň jedno prvočíslo p splňující n < p < 2n. Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísel je vcelku málo Prvočísla Aritmetické funkce OOOOOOOOOOOOO0OOOO ooooo Příklad Dokažte, že pro libovolné přirozené číslo n existuje n po sobě jdoucích přirozených čísel, z nichž žádné není prvočíslo. Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísel je vcelku málo Prvočísla Aritmetické funkce OOOOOOOOOOOOO0OOOO ooooo Příklad Dokažte, že pro libovolné přirozené číslo n existuje n po sobě jdoucích přirozených čísel, z nichž žádné není prvočíslo. Zkoumejme čísla {n + 1)! + 2, {n + 1)! + 3,..., {n + 1)! + {n + 1). Mezi těmito n po sobě jdoucími čísly není žádné prvočíslo, protože pro libovolné k G {2, 3,..., n + 1} platí k | (r? + 1)!, a tedy k I (r? + 1)! + k, a proto (r? + 1)! + k nemůže být prvočíslo. □ Prvočísla OOOOOOOOOOOOOO0OOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísla jsou relativně rovnoměrně rozložena v tom, smyslu, že v libovolné „rozumné" aritmetické posloupnosti je jich nekonečně mnoho. Například zbytek 1 po dělení čtyřmi, stejně jako zbytek 3 po dělení čtyřmi dá vždy nekonečně mnoho prvočísel (zbytek 0 nedá samozřejmě žádné a zbytek 2 pouze jediné). Obdobná situace je pak při uvažování zbytků po dělení libovolným jiným přirozeným číslem, jak uvádí následující věta, jejíž důkaz je ovšem velmi obtížný. Prvočísla OOOOOOOOOOOOOO0OOO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísla jsou relativně rovnoměrně rozložena v tom, smyslu, že v libovolné „rozumné" aritmetické posloupnosti je jich nekonečně mnoho. Například zbytek 1 po dělení čtyřmi, stejně jako zbytek 3 po dělení čtyřmi dá vždy nekonečně mnoho prvočísel (zbytek 0 nedá samozřejmě žádné a zbytek 2 pouze jediné). Obdobná situace je pak při uvažování zbytků po dělení libovolným jiným přirozeným číslem, jak uvádí následující věta, jejíž důkaz je ovšem velmi obtížný. 2 /tó 7 Kic Věta (Dirichletova o prvočíslech v aritmetické posloupnosti) Jsou-li a, m nesoudělná přirozená čísla, existuje nekonečně mnoho přirozených čísel k tak, že mk + a je prvočíslo. Jinými slovy, mezi čísly 1 • m + a, 2 • m + a, 3 • m + a,... existuje nekonečně mnoho prvočísel. Uveďme proto alespoň důkaz ve speciálním případě. □ 3 ► < ► 4 = Prvočísla OOOOOOOOOOOOOOO0OO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísel tvaru 3k + 2 je nekonečně mnoho Příklad Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3/c + 2, kde k e N0. Prvočísla OOOOOOOOOOOOOOO0OO Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Prvočísel tvaru 3k + 2 je nekonečně mnoho Příklad Řešení Předpokládejme naopak, že existuje pouze konečně mnoho prvočísel tohoto tvaru a označme je pi = 2, P2 = 5, P3 = 11, .. ., pn. Položme N — 3p2 • P3.....pn + 2. Rozložíme-li N na součin prvočísel, musí v tomto rozkladu vystupovat aspoň jedno prvočíslo p tvaru 3/c + 2, neboť v opačném případě by bylo N součinem prvočísel tvaru 3/c + 1 (uvažte, že N není dělitelné třemi), a tedy podle dřívějšího příkladu by bylo i N tvaru 3/c + 1, což není pravda. Prvočíslo p ovšem nemůže být žádné z prvočísel pi, p2,..., pm jak plyne z tvaru čísla A/, a to je spor. Prvočísla OOOOOOOOOOOOOOOO0O Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Asymptotické chování prvočísel Z tvrzení uvedených v této kapitole je možné si udělat hrubou představu o tom, jak "hustě"se mezi přirozenými čísla prvočísla vyskytují. Přesněji (i když " pouze"asymptoticky) to popisuje velmi důležitá tzv. "Prime Number Theorem": Věta (Prime Number Theorem, věta o hustotě prvočísel) Nechť 7r(x) udává počet prvočísel menších nebo rovných číslu x e R. Pak dŕ \ 2-^?- * > v otí*Sr y- cca tt(x) x In x' tj. podíl funkcí 7i(x) a x j In x se pro x —> oc limitně blíží k 1 Prvočísla OOOOOOOOOOOOOOOO0O Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Asymptotické chování prvočísel Z tvrzení uvedených v této kapitole je možné si udělat hrubou představu o tom, jak "hustě"se mezi přirozenými čísla prvočísla vyskytují. Přesněji (i když " pouze"asymptoticky) to popisuje velmi důležitá tzv. "Prime Number Theorem": Věta (Prime Number Theorem, věta o hustotě prvočísel) Nechť 7r(x) udává počet prvočísel menších nebo rovných číslu x e IR. Pak 7t(x) x In x' tj. podíl funkcí 7i(x) a x j In x se pro x —> oc limitně blíží k 1 Poznámka To, jak jsou prvočísla hustě rozmístěna v množině přirozených čísel, rovněž udává Eulerův výsledek J2pep = oc. Přitom např. SneN \ — \-> c°ž znamená, že prvočísla jsou v N rozmístěna „hustěji" než druhé mocniny. Prvočísla 00000000000000000« Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Příklad O tom, jak odpovídá asymptotický odhad 7r(x) ~ xj ln(x), v některých konkrétních příkladech vypovídá následující tabulka: x tt(x) x/ln(x) relativní chyba 100 25 21.71 0.13 1000 168 144.76 0.13 10000 1229 1085.73 0.11 100000 9592 8685.88 0.09 <ř— 500000 41538 38102.89 0.08 ----TTOO Malá Fermatova věta, Eulerova věta oooooooooooo Plán přednášky Prvočísla Aritmetické funkce oooooooooooooooooo ooooo • Poznámky • Dělitelé znovu • Rozložení prvočísel Q Aritmetické funkce • Eulerova funkce cp Prvočísla Aritmetické funkce Malá Fermatova věta, Eulerova věta oooooooooooooooooo •oooo oooooooooooo Aritmetické funkce Aritmetickou funkcí zde rozumíme funkci, jejímž definičním s \ oborem je množina přirozených čísel. f\ --^ ^ éi*^ r Definice i 1 Multiplikativní funkcí přirozených čísel rozum aritmetickou funkci, která splňuje, že pro vše nesoudělných čísel a, b G N platí Jf{a>b) = f (a) • f (b). íme takovou chny dvojice >0 Q,o Prvočísla oooooooooooooooooo Aritmetické funkce •oooo Malá Fermatova věta, Eulerova věta oooooooooooo Aritmetické funkce Aritmetickou funkcí zde rozumíme funkci, jejímž definičním oborem je množina přirozených čísel. Definice Multiplikativní funkcí přirozených čísel rozumíme takovou aritmetickou funkci, která splňuje, že pro všechny dvojice nesoudělných čísel a, b G N platí f (a ■ b) = f (a) ■ f (b) Príklad Multiplikativními funkcemi jsou např. funkce f (n) = cr(n), f (n) = r(r?) nebo, jak brzy dokážeme i tzv. Eulerova funkce f (n) = rtn^S t^M\-'-(A£\)_ Malá Fermatova věta, Eulerova věta oooooooooooo Eulerova funkce Prvočísla Aritmetické funkce oooooooooooooooooo o«ooo Definice Nechť n G N. Definujme Eulerovu funkci y> předpisem ň - Wfi^ (p(n) = \{a G N | 0 < a < n VO' v ^ (lépe počet zbytkových tříd nesoudělných s n nebo také těch, které mají modulo n inverzi). ^ 5" 5 (O 1 I I \ <(«>) t t f Malá Fermatova věta, Eulerova věta oooooooooooo Eulerova funkce Prvočísla Aritmetické funkce oooooooooooooooooo o«ooo Definice Nechť n £ N. Definujme Eulerovu funkci cp předpisem cp(n) = |{a G N I 0 < a < n, (a, n) = 1}| (lépe počet zbytkových tříd nesoudělných s n nebo také těch, které mají modulo n inverzi). Příklad 1 ) = p-i. l = 4, (p{6) = 2, je-li p prvočíslo, je zřejmě 1 z - □ ^ > 4 ^ >■ 4 .= >0 0,0 Prvočísla oooooooooooooooooo Aritmetické funkce oo«oo Malá Fermatova věta, Eulerova věta oooooooooooo Nyní dokážeme několik důležitých tvrzení o funkci cp\ Lemma Platí(p(pa) = pa - p""1 = pa_1(p - 1) = Pa(l - □ 3 ► < ► 4 = >0 o,o Aritmetické funkce oo«oo Malá Fermatova věta, Eulerova věta oooooooooooo Nyní dokážeme několik důležitých tvrzení o funkci cp\ Lemma Platí(f(pa) = pa - p""1 = pa_1(p - 1) = Pa(l - J) Důkaz. Mezi čísly {1,..., pa} jsou soudělná s pa právě násobky p, tedy a těch je pa 1. Nesoudělných je proto pa — p a—l □ Aritmetické funkce OOO0O Malá Fermatova věta, Eulerova věta oooooooooooo Eulerova funkce (p je multiplikativní. Nechť n G N, jehož rozklad je tvaru n ip(n) = n- 1 - Pi P? 1 - ■■Pkk- Pak Pk Prvočísla oooooooooooooooooo Aritmetické funkce OOO0O Malá Fermatova věta, Eulerova věta oooooooooooo Eulerova funkce

(x (mod a), x (mod b)) Stačí proto ukázat, že x (mod a • b) má inverzi, právě když obě složky obrazu mají inverzi - takových dvojic je totiž přesně . (72) = (f(8) • p(9) = 4 • 6 = 24. □ Příklad Dokažte, že Vn G N : ^(4n + 2) = ^(2n + 1) Prvočísla oooooooooooooooooo Aritmetické funkce oooo* Malá Fermatova věta, Eulerova věta oooooooooooo Příklad Vypočtěte (f{72) Řešení 72 = 23 • 32 (p(72) = 72 • (1 - \) ■ (1 - §) = 24, alternativně y>(72) = (f(8) • p(9) = 4 • 6 = 24. □ Příklad Dokažte, že Vn G N : ^(4n + 2) = ^(2n + 1) Řešení y(4n + 2) = y(2 • {2n + 1)) = tygf • y(2n + 1) = y(2n +1). □ J Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo Plán přednášky • Poznámky • Dělitelé znovu • Rozložení prvočísel • Eulerova funkce cp Q Malá Fermatova věta, Eulerova věta □ 3 ► < ► 4 = Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta •ooooooooooo Úplná a redukovaná soustava zbytků Definice Upíná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1,..., m — 1). Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta •ooooooooooo Upíná a redu kovaná soustava zbytků Definice Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1,..., m — 1). Redukovaná soustava zbytků modulo m je libovolná (p(m)-ť\ce čísel nesoudělných s m a po dvou nekongruentních modulo m. if (O IMfflti (i) Malá Fermatova věta, Eulerova věta •ooooooooooo Upíná a redukovaná soustava zbytků Prvočísla Aritmetické funkce oooooooooooooooooo ooooo Definice Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1,..., m — 1). Redukovaná soustava zbytků modulo m je libovolná (p(m)-ť\ce čísel nesoudělných s m a po dvou nekongruentních modulo m. Lemma Nechť xi, x2,..., x^(m) tvoří redukovanou soustavu zbytků modulo m. Je-li a £ Z, (a, m) = 1 pa/c / čísla a • xi,..., a • x^(m) r\/on redukovanou soustavu zbytků modulo m. x, r os.' 41/ -i * Kl' >0 Q,o Malá Fermatova věta, Eulerova věta •ooooooooooo Upíná a redukovaná soustava zbytků Prvočísla Aritmetické funkce oooooooooooooooooo ooooo Definice Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1,..., m — 1). Redukovaná soustava zbytků modulo m je libovolná (p(m)-ť\ce čísel nesoudělných s m a po dvou nekongruentních modulo m. Lemma Nechť xi, x2,..., tvoří redukovanou soustavu zbytků modulo m. Je-li a £ Z, (a, m) = 1 pa/c / čísla a • xi,..., a • x^(m) r\/on redukovanou soustavu zbytků modulo m. Důkaz. Protože (a, m) — 1 a (x,-, m) — 1, platí (a • x,-, m) = 1. Kdyby pro nějaká i J platilo a • x; = a • xy (mod rn), po vydělení obou stran kongruence číslem a nesoudělným s rn dostaneme x; = xy (mod rn). □ Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta O0OOOOOOOOOO Eulerova věta Věta (Eulerova) Necht a G Z, m G N, (a, m) = 1. Pak g\JLm '------ [f (luV 1 a^ = 1 (mod m). ^ 2 Prvočísla Aritmetické funkce Malá Fermatova věta, Eulerova věta OOOOOOOOOOOOOOOOOO OOOOO 00000*000000 Příklad Určete řád čísla 2 modulo 7. □ rS1 = Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta 00000*000000 Příklad Určete řád čísla 2 modulo 7 ■ Řešení 2° = 1 21 = 2^1 (mod 7) 22 = 4^1 (mod 7) 23 = 8 = 1 (mod 7) 7.*~ Řád číslaj 2 modulo 7 je tedy roven 3 >0 o,o Prvočísla Aritmetické funkce Malá Fermatova věta, Eulerova věta oooooooooooooooooo ooooo OOOOOO0OOOOO Přesný popis závislosti řádu na exponentu dávají následující 2 věty: Věta i Nechť m 6 N, a £ Z, (a. m) = 1. Označme r řác/ č/s/a a modulo m. Pak pro libovolná ř, s £ N U {0} platí ař = as (mod m) t = s (mod r). ví/ /ŕ ■s- s. ( -Ír A-} <-) Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta OOOOOOO0OOOO Důkaz. Bez újmy na obecnosti lze předpokládat, že t > s. Vydělíme-li číslo t — s číslem r se zbytkem, dostaneme t — s = q • r + z, kde q, z G No, 0 < z < r. Protože t = s (mod r), máme z = 0, a tedy 7 ľ 7 7 at s _ aqr _ (y)9 = (mod m). Vynásobením obou stran kongruence číslem as dostaneme tvrzení. Z aŕ = as (mod m) plyne as • aqr+z = as (mod m). Protože je ar = 1 (mod rn), je rovněž aqr+z = az (mod m). Celkem po vydělení obou stran kongruence číslem as (které je nesoudělné s modulem), dostáváme az = 1 (mod m). Protože z < r, plyne z definice řádu, že z = 0, a tedy r t — s. □ Prvočísla Aritmetické funkce Malá Fermatova věta, Eulerova věta oooooooooooooooooo ooooo OOOOOOOO0OOO Zřejmým důsledkem předchozí věty a Eulerovy věty je následující tvrzení Důsledek Nechť m 6 N, a £ Z, (a. m) = 1. Označme r řád čísla a modulo m. O Pro libovolné r? £ N U {0} platí an = 1 (mod m) <^=^> r | n. (uo JI Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta OOOOOOOOO0OO Následující věta je zobecněním předchozího Lemmatu Nechť m, n £ N, a £ Z, (a, m) = 1. Je-// řac/ č/s/a a modulo m roven r £ N, /e řác/ č/s/a an modulo m roven -r^- Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta OOOOOOOOO0OO Následující věta je zobecněním předchozího Lemmatu Nechť m, n £ N, a £ Z, (a, m) = 1. Je-// řac/ č/s/a a modulo m roven r £ N, /e řác/ č/s/a an modulo m roven -r^- Důkaz. Protože jy^j = [r, r?], což je zřejmě násobek r, máme (a")(^) = a^ = 1 (mod m) (plyne z předchozího Důsledku, neboť r | [r, /?]). Na druhou stranu, je-li /c £ N libovolné takové, že (an)k — an'k = 1 (mod m), dostáváme (r je řád a), že r n • k a dále víme, že I • /c a V J 7' ' (n,r) I (n,r) díky nesoudělnosti čísel -r-^ a -r1^ dostáváme -r-^ k. Proto je y {n,r) (n,r) (n,r) J řádem čísla an modulo m. □ >0 0,0 Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooo«o Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: Lemma Nechť m 6 N, a, b e Z, (a, m) = (b, m) = 1. Jestliže a je řac/i/ r a b je řádu s modulo m, kde (r, s) = 1, pa/c č/s/o a • b je řádu r • s modulo m. vi ■==0 / ^ 9 fc|ir£ Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooo«o Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: r -m Lemma Nechť m G N, a, b G Z b je řádu s modulo m, modulo m. , (a, m) = kde (r, s) (b, m) = 1. Jestliže a je řádu r a í Důkaz. Označme S řád čísla a • b. Pak (ab)^ = 1 (mod m) a umocněním obou stran kongruence dostaneme arSbrS = 1 (mod m). Protože je r řádem čísla a, je ar = 1 (mod m), tj. brS = 1 (mod m), a proto s | rS. Z nesoudělnosti ras plyne s | S. Analogicky dostaneme i r | ô, a tedy (opět s využitím nesoudělnosti r, s) r • s | S. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto S | rs. Celkem tedy ô = rs. □ Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta 00000000000« Důsledek Nechi m 6 N a r je nejmenší společný násobek všech řádů modulo m. Pak existuje číslo řádu r modulo m. Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta 00000000000« Důsledek Necht m 6 N a r je nejmenší společný násobek všech řádů modulo m. Pak existuje číslo řádu r modulo m. Důkaz. Stačí pro a řádu s, b řádu t najít prvek řádu [s, t]. Nechť d = (s, t), pak tímto prvkem je ad • b. □ Prvočísla oooooooooooooooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta 00000000000« Důsledek Necht m 6 N a r je nejmenší společný násobek všech řádů modulo m. Pak existuje číslo řádu r modulo m. Důkaz. Stačí pro a řádu s, b řádu t najít prvek řádu [s, t]. Nechť d = (s, t), pak tímto prvkem je ad • b. □ Věta Necht p e N je prvočíslo. Pak existuje prvek řádu p — 1 modulo p, tzv. primitivní kořen.