Kongruence oooooo Prvočísla oooooooooooooooo Diskrétní matematika - 2. týden Elementární teorie čísel - kongruence a prvočísla Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 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 prednášky 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). Kongruence O0OOOO Prvočísla oooooooooooooooo r Lemma i Pro libovolná a, b 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. Ř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. □ 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. Ř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. □ 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. Řešení 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. □ 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 OOOOOOOOOOOOO0OO Prvočísel tvaru 3/c + 2 je nekonečně mnoho Ř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. 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