Kongruence oooooo Prvočísla oooooooooooooooo Diskrétní matematika - 2. týden Elementární teorie čísel - kongruence a prvočísla Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Kongruence oooooo Obsah přednášky Prvočísla oooooooooooooooo Q Kongruence o Základní vlastnosti kongruencí Q Prvočísla • Poznámky • Dělitelé znovu • Rozložení prvočísel Kongruence oooooo Doporučené zdroje Prvočísla oooooooooooooooo • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Kongruence Prvočísla oooooo oooooooooooooooo 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 Kongruence oooooo Plán přednáaky Prvočísla oooooooooooooooo Q Kongruence o Základní vlastnosti kongruencí rvoc i s i a • Poznámky • Dělitelé znovu • Rozložení prvočísel Kongruence •ooooo Prvočísla oooooooooooooooo Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah. Kongruence •ooooo Prvočísla oooooooooooooooo Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah. Definice Jestliže dvě celá čísla a, b mají při dělení přirozeným číslem m týž zbytek r, kde 0 < r < m, nazývají se a, b kongruentnímodulo m (též kongruentní podle modulu m), což zapisujeme takto: a = b (mod m). V opačném případě řekneme, že a, b nejsou kongruentní modulo m, a píšeme a ^ b (mod m). -írnJ^ < >• -E o q, o Kongruence O0OOOO Prvočísla oooooooooooooooo r Lemma i Pro libovolná a, b 0 o,o Kongruence oooooo Plán prednáaky Prvočísla oooooooooooooooo • Základní vlastnosti kongruencí Q Prvočísla • Poznámky • Dělitelé znovu • Rozložení prvočísel Kongruence oooooo PRIMES is in P Prvočísla •ooooooooooooooo Poznámka Již jsme se zmínili, že je složité o velkých číslech s jistotou rozhodnout, jde-1i 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). < n ► < r5P ► <■€.*■ < ► -e o Q, o Kongruence oooooo Prvočísla o«oooooooooooooo Is FACTOR in P? Nie podobného se zatím nepodarilo 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). Nejrychlejší obecně použitelný faktorizační algoritmus, tzv. síto v číselném tělese1, je sub-exponenciální časové složitosti Oíe1^10^)17^1^10^)273). Pro podrobnosti navštivte M8190 Algoritmy teorie čísel Kongruence Prvočísla oooooo o«oooooooooooooo Is 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ěří, že je 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 g Kongruence oooooo RSA Challenge Prvočísla OO0OOOOOOOOOOOOO Poznámka ©e je 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). Kongruence oooooo Prvočísla ooo«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 — p11.....pkk je tvaru p™1.....p™k, kde mi,..., mk £ No a mi < n\, rr?2 < r?2, mk < nk. -/ □ 3 - = ěo^o Kongruence oooooo Prvočísla ooo«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 — p11.....pkk je tvaru p™1.....p™k, kde mi,..., £ No a mi < n\, rr?2 < r?2, mk < nk. 9 Číslo a má tedy právě r(a) = (r?i + l)(r?2 + 1)(nk + 1) kladných dělitelů, jejichž součet je pi+1 -1 plk+l-1 cr(a) = —-. . . —--. Kongruence oooooo Prvočísla oooo«ooooooooooo Důsledek (Pokr.) Jsou-H pi,..., p k navzájem různá prvočísla a r?i, ..., m^ G No a označíme-li r; — min{r?;, m,}, t; = max{r?;, m;} pro každé i = 1, 2,..., k, platí , nk, mlr (pí ni p? [pí "i pD = pí1 ŕ/c p/c Kongruence Prvočísla OOOOOO OOOOO0OOOOOOOOOO 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). Kongruence Prvočísla OOOOOO OOOOO0OOOOOOOOOO 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. 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 Kongruence oooooo Hledání velkých prvočísel Prvočísla OOOOOO0OOOOOOOOO 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št Kongruence oooooo Hledání velkých prvočísel Prvočísla OOOOOO0OOOOOOOOO 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). Na druhou stranu popsat lichá dokonalá čísla se dodnes nepodařilo, resp. dodnes se neví, jestli vůbec nějaké liché dokonalé číslo existuje_ 2Viz např. titulek iDnes z 6.února 2013: Největší známé prvočíslo na^světět Kongruence Prvočísla OOOOOO OOOOOOO0OOOOOOOO Jak testovat Mersenneho prvočísla? Přestože zatím nemáme jasno v tom, jak efektivně implementovat použité operace, ani neumíme dokázat jeho správnost, uveďme si pro ilustraci test, kterým lze zjistit, je-li dané Mersenneho číslo prvočíslem. Kongruence Prvočísla OOOOOO OOOOOOO0OOOOOOOO Jak testovat Mersenneho prvočísla? Přestože zatím nemáme jasno v tom, jak efektivně implementovat použité operace, ani neumíme dokázat jeho správnost, uveďme si pro ilustraci test, kterým lze zjistit, je-li dané Mersenneho číslo prvočíslem. Lucas-Lehmerův test Definujme posloupnost (sn)^0 rekurzívně předpisem so — 4, sn+i = s2 — 2. Pak je číslo Mp = 2P — 1 prvočíslo, právě tehdy, když Mp dělí sp_2. Kongruence Prvočísla oooooo OOOOOOOO0OOOOOOO Rozložení prvočísel Nyní se budeme snažit zodpovědět následující otázky O Je prvočísel nekonečně mnoho? Kongruence oooooo Rozložení prvočísel Prvočísla OOOOOOOO0OOOOOOO 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? Kongruence oooooo Rozložení prvočísel Prvočísla OOOOOOOO0OOOOOOO 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? Kongruence oooooo Rozložení prvočísel Prvočísla OOOOOOOO0OOOOOOO 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? Kongruence oooooo Rozložení prvočísel Prvočísla OOOOOOOO0OOOOOOO 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 Kongruence oooooo Prvočísla OOOOOOOOO0OOOOOO Prvočísel je nekonečně mnoho Věta (Eukleidés) Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Kongruence oooooo Prvočísla OOOOOOOOO0OOOOOO Prvočísel je nekonečně mnoho Věta (Eukleidés) Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Předpokládejme, že prvočísel je konečně mnoho a označme je pi, P2,..., pn- Položme A/ = pi • p2 ... pn + 1- Toto číslo je buď 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. □ Kongruence Prvočísla OOOOOO OOOOOOOOO0OOOOOO 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, P2,..., pn- Položme A/ = pi • p2 ... pn + 1- Toto číslo je buď 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. Kongruence oooooo Prvočísel je vcelku hodně Prvočísla oooooooooo«ooooo Příklad Pro celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. Kongruence oooooo Prvočísel je vcelku hodně Prvočísla oooooooooo«ooooo Příklad Pro celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. Reaení 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. □ -írnJ^ < >• e o q, o Kongruence oooooo Prvočísel je vcelku hodně Prvočísla oooooooooo«ooooo Príklad Pro celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. Reaení 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 I (r?! — 1), platí p < n\ — 1, tedy p < n\. Prvočíslo p splňuje podmínky úlohy. □ 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 solňuiící n < o < 2n. Kongruence Prvočísla oooooo OOOOOOOOOOO0OOOO Prvočísel je vcelku málo 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. Kongruence Prvočísla OOOOOO OOOOOOOOOOO0OOOO Prvočísel je vcelku málo 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. Reaení 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. □ -íŕnJ^ < >• -E o q, o Kongruence oooooo Prvočísla OOOOOOOOOOOO0OOO 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ý. Kongruence oooooo Prvočísla OOOOOOOOOOOO0OOO 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ý. 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ě. Kongruence oooooo Prvočísla OOOOOOOOOOOOO0OO Prvočísel tvaru 3k + 2 je nekonečně mnoho Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3/c + 2, kde k e N0. Kongruence Prvočísla OOOOOO OOOOOOOOOOOOOÄOO Prvočísel tvaru 3/c + 2 je nekonečně mnoho Reaení 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. Kongruence oooooo Prvočísla oooooooooooooo«o 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) Necht 7ľ(x) udává počet prvočísel menších nebo rovných číslu x £ IR. Pak tj. podíl funkcí tv(x) a x j In x se pro x —> oc limitně blíží k 1. Kongruence Prvočísla oooooo oooooooooooooo«o 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. 4 i Kongruence oooooo Prvočísla ooooooooooooooo* 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