Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo OOOOOOOO oo Diskrétní matematika - 2. týden Elementární teorie čísel - kongruence a prvočísla Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2017 Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo oooooooo oo Obsah přednášky Q Kongruence • Základní vlastnosti kongruencí Q Prvočísla • Faktorizace • Poznámky Q Rozložení prvočísel O Dělitelé znovu Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo oooooooo oo 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. Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo oooooooo oo 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 Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu Plán prednášky Kongruence o Základní vlastnosti kongruencí • Faktorizace 9 Poznámky k1 Dělitele znovu >0 0,0 Kongruence •ooooo Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu oo 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 OOOOOOOO Rozložení prvočísel OOOOOOOO Dělitelé znovu oo 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 o«oooo Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu oo Lemma Pro libovolná a, b 0 0,0 Kongruence O0OOOO Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu oo Lemma Pro libovolná a, b 2 (mod m), existují podle lemmatu ti, t2 £ Z tak, že a± = b\ + mti, a2 = £>2 + /7iř2- Pak ovšem 3i + ^2 = b± + i>2 + rn(ri + £2) 3 opět podle lemmatu ai + a2 = bi + £>2 (mod m). Sečteme-li kongruenci a + b = c (mod m) s kongruencí —b = —b (mod m), která zrejme platí, dostaneme a = c — b (mod m). Sečteme-li kongruenci a = b (mod m) s kongruencí mk = 0 (mod m), jejíž platnost je zřejmá, dostaneme a + mk = b (mod m). □ Kongruence oooo«o Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu oo • Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. 9 q,o Kongruence oooo«o Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu oo • Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. • Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooo«o oooooooo OOOOOOOO oo • Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. • Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. • Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooo«o oooooooo OOOOOOOO oo • Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. • Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. • Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. • Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. 9 q,o Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooo«o oooooooo OOOOOOOO oo • Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. • Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. • Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. 9 Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. • Jestliže kongruence a = b platí podle modulů mi,..., m^, platí i podle modulu, kterým je nejmenší společný násobek [mi,..., m^] těchto čísel. Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooo«o oooooooo OOOOOOOO oo • Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. • Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. • Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. 9 Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. • Jestliže kongruence a = b platí podle modulů mi,..., m^, platí i podle modulu, kterým je nejmenší společný násobek [mi,..., m^] těchto čísel. • Jestliže kongruence platí podle modulu m, platí podle libovolného modulu d, který je dělitelem čísla m. Kongruence oooo«o Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu oo • Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. • Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. • Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. 9 Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. • Jestliže kongruence a = b platí podle modulů mi,..., m^, platí i podle modulu, kterým je nejmenší společný násobek [mi,..., m^] těchto čísel. • Jestliže kongruence platí podle modulu m, platí podle libovolného modulu d, který je dělitelem čísla m. • Jestliže je jedna strana kongruence a modul dělitelný nějakým celým číslem, musí být tímto číslem dělitelná i druhá strana. Kongruence ooooo« Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu oo Poznámka Některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli - například příklad z minulého týdne lze přeformulovat do tvaru "jestliže a = 1 (mod m), b = 1 (mod m), pak také ab = 1 (mod m)", což je speciální případ zpředhozího tvrzení. Nejde o náhodu. Libovolné tvrzení používající kongruence můžeme snadno přepsat pomocí dělitelnosti. Užitečnost kongruencí tedy netkví v tom, že bychom pomocí nich mohli řešit úlohy, které bez nich řešit nejsme schopni, ale v tom, že jde o velmi vhodný způsob zápisu. Osvojíme-li si ho, výrazně tím zjednodušíme jak vyjadřování, tak i některé úvahy. Je to typický jev: v matematice hraje vhodná symbolika velmi závažnou úlohu. Kongruence oooooo Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu Plán prednášky • Základní vlastnosti kongruencí Q Prvočísla Faktorizace • Poznámky Kongruence oooooo Prvočísla •ooooooo Rozložení prvočísel oooooooo Dělitelé znovu oo 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. Kongruence oooooo Prvočísla •ooooooo Rozložení prvočísel oooooooo Dělitelé znovu oo 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: lan. 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, je totiž invertibilní, neboli tzv. jednotkou okruhu celých čísel). 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 257885161 — 1 má pouze 17 425170 cifer). Kongruence oooooo Prvočísla OÄOOOOOO Rozložení prvočísel oooooooo Dělitelé znovu oo 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 (Euklidova o prvočíslech) Přirozené číslo p > 2 je prvočíslo, právě když platí: pro každá celá čísla a, b z p ab plyne p I a nebo p b. Kongruence oooooo Prvočísla O0OOOOOO Rozložení prvočísel oooooooo Dělitelé znovu oo 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 (Euklidova o prvočíslech) Přirozené číslo p > 2 je prvočíslo, právě když platí: pro každá celá čísla a, b z p ab plyne p I a nebo p b. Důkaz. "Předpokládejme, že p je prvočíslo a p | ab, kde a, b £ Protože (p, a) je kladný dělitel p, platí (p, a) — p nebo (p, a) — 1. V prvním případě p | a, ve druhém p | b, jak jsme dokázali minulý týden. Kongruence oooooo Prvočísla O0OOOOOO Rozložení prvočísel oooooooo Dělitelé znovu oo 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 (Euklidova o prvočíslech) Přirozené číslo p > 2 je prvočíslo, právě když platí: pro každá celá čísla a, b z p ab plyne p I a nebo p b. Důkaz. Předpokládejme, že p je prvočíslo a p \ ab, kde a, b £ Protože (p, a) je kladný dělitel p, platí (p, a) — p nebo (p, a) — 1. V prvním případě p | a, ve druhém p | b, jak jsme dokázali minulý týden. "<^" Jestliže p není prvočíslo, musí existovat jeho kladný dělitel různý od 1 a p. Označíme jej a; pak ovšem b = - G N a platí p = ab, odkud l 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čin11 jednoho prvočísla.) Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu OOOOOO OO0OOOOO oooooooo oo Základní věta aritmetiky 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čin11 jednoho prvočísla.) Poznámka Dělitelnost je možné obdobným způsobem definovat v libovolném oboru integrity (zkuste si rozmyslet, proč se omezujeme na obory integrity). V některých oborech integrity přitom žádné prvky s vlastností prvočísla (říkáme jim ireducibilní) neexistují (např. Q), v jiných sice ireducibilní prvky existují, ale zase tam neplatí věta o jednoznačném rozkladu (např. v Z(V~5) máme následující rozklady: 6 = 2 • 3 = (1 + V^5) • (1 - ^b). Kongruence oooooo Prvočísla OOOÄOOOO Rozložení prvočísel oooooooo Dělitelé znovu oo Důkaz. Nejprve dokážeme indukcí, že každé n > 2 je možné vyjádřit jako součin prvočísel. Je-li n = 2, je n součin jediného prvočísla 2. Předpokládejme nyní, že n > 2 a že jsme již dokázali, že libovolné nf, 2 < n' < n, je možné rozložit na součin prvočísel. Jestliže n je prvočíslo, je součinem jediného prvočísla. Jestliže n prvočíslo není, pak existuje jeho dělitel d, 1 < d < n. Označíme-li c = ^, platí také 1 < c < n. Z indukčního předpokladu plyne, že c i d je možné vyjádřit jako součin prvočísel, a proto je takto možné vyjádřit i jejich součin c • d = n. Kongruence oooooo Prvočísla OOO0OOOO Rozložení prvočísel oooooooo Dělitelé znovu oo Důkaz. Nejprve dokážeme indukcí, že každé n > 2 je možné vyjádřit jako součin prvočísel. Je-li n = 2, je n součin jediného prvočísla 2. Předpokládejme nyní, že n > 2 a že jsme již dokázali, že libovolné nf, 2 < n' < n, je možné rozložit na součin prvočísel. Jestliže n je prvočíslo, je součinem jediného prvočísla. Jestliže n prvočíslo není, pak existuje jeho dělitel d, 1 < d < n. Označíme-li c = ^, platí také 1 < c < n. Z indukčního předpokladu plyne, že c i d je možné vyjádřit jako součin prvočísel, a proto je takto možné vyjádřit i jejich součin c • d = n. Nyní dokážeme jednoznačnost. Předpokládejme, že platí rovnost součinů pi • p2.....pm = qi • Q2qs, kde pi,..., pm, <7i,..., qs jsou prvočísla a navíc platí pi < p2 < • • • < pm, 9i < 92 < • • • < 9s 3 1 < rn < s. Indukcí vzhledem k m dokážeme, že m = s, pi = qri,..., pm = qm. □ Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo OOOO0OOO oooooooo oo Dokončení. Je-li m = 1, je pi = q\.....qs prvočíslo. Kdyby s > 1, mělo by číslo pi dělitele q\ takového, že 1 < q\ < pi (neboť Q2Q3 ... <7S > 1), což není možné. Je tedy s = 1 a platí pi = q\. Kongruence oooooo Prvočísla OOOO0OOO Rozložení prvočísel oooooooo Dělitelé znovu oo Dokončení. Je-li m = 1, je pi = q\.....qs prvočíslo. Kdyby s > 1, mělo by číslo pi dělitele q\ takového, že 1 < q\ < pi (neboť Q2Q3 ... qs > 1), což není možné. Je tedy s = 1 a platí pi = q\. Předpokládejme, že m > 2 a že tvrzení platí pro m — 1. Protože Pi ■ P2Pm = <7i • 92<7s. dělí pm součin qi.....qs, což je podle Euklidovy věty možné jen tehdy, jestliže pm dělí nějaké q; pro vhodné / e {1, 2,..., s}. Protože q\ je prvočíslo, plyne odtud Pm — Qi (neboť pm > 1). Zcela analogicky se dokáže, že qs — pj pro vhodné j e {1,2,..., m}. Odtud plyne qs = Pj < Pm = qf/ < qSí takže pm = qs. Vydělením dostaneme pi • P2.....Pm-i — Qi ' Q2Qs-i, 3 tedy z indukčního předpokladu m — 1 = s — 1, pi = qi,..., pm-i = qm-i- Celkem tedy at? = s a pi = c/i..... pm_i = qm-i, pm = qm. Jednoznačnost, a tedy i celá věta, je dokázána. □ Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo ooooo«oo oooooooo oo PRIMES is in P 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). Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooo«o oooooooo oo 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-9^^173^1^^273). Pro podrobnosti navštivte M8190 Algoritmy teorie čísel g Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooo«o oooooooo oo 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 Prvočísla Rozložení prvočísel Dělitelé znovu oooooo ooooooo* oooooooo oo RSA Challenge 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 Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo oooooooo oo Plán prednášky • Základní vlastnosti kongruencí • Faktorizace 9 Poznámky Q Rozložení prvočísel Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo •ooooooo oo 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 Prvočísla Rozložení prvočísel Dělitelé znovu OOOOOO OOOOOOOO «0000000 oo 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? Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu OOOOOO OOOOOOOO «0000000 oo 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? Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu OOOOOO OOOOOOOO «0000000 oo 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? Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu OOOOOO OOOOOOOO «0000000 oo 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 Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo OOOOOOOO o«oooooo oo Prvočísel je nekonečně mnoho Věta (Eukleidés) Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo o«oooooo oo 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. □ Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo o«oooooo oo 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 Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo oo«ooooo oo Prvočísel je vcelku hodně Příklad Pro celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo oo«ooooo oo Prvočísel je vcelku hodně Příklad Pro celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. ■v Ř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 I (r?! — 1), platí p < n\ — 1, tedy p < n\. Prvočíslo p splňuje podmínky úlohy. □ Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo oo«ooooo oo Prvočísel je vcelku hodně 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 I (r?! — 1), platí p < n\ — 1, tedy p < n\. Prvočíslo p splňuje podmínky úlohy. □ Z věty plyne nekonečnost prvočísel, její tvrzení je ale velice slabé. Následující tvrzení, uvedené bez důkazu, je podstatně silnější. 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. V) o^ o Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo ooo«oooo oo 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. Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo ooo«oooo oo 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. □ -íŕnJ^ < >• e o q, o Kongruence oooooo Prvočísla oooooooo Rozložení prvočísel OOOOÄOOO Dělitelé znovu oo Naznačili jsme, 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"(uvádíme bez důkazu): 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 —> oo limitně blíží k 1 Kongruence oooooo Prvočísla oooooooo Rozložení prvočísel OOOOÄOOO Dělitelé znovu oo Naznačili jsme, 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"(uvádíme bez důkazu): 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 —> oo 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 p = °°- (důkaz v textu, relativně složitý). Přitom např. J^neN \ — \-> c°ž znamená, že prvočísla jsou v N rozmístěna „hustěji" než druhé mocniny (protože J2n ~ \)- Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo OOOOO0OO oo 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 Kongruence Prvočísla Rozložení prvočísel Dělitelé znovu OOOOOO OOOOOOOO OOOOOO0O oo 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 Rozložení prvočísel Dělitelé znovu OOOOOO OOOOOOOO OOOOOO0O oo 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 Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo 0000000« oo Hledání velkých prvočísel 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 Prvočísla Rozložení prvočísel Dělitelé znovu oooooo oooooooo 0000000« oo Hledání velkých prvočísel 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 oooooo Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu Plán prednášky • Základní vlastnosti kongruencí • Faktorizace 9 Poznámky O Dělitelé znovu Kongruence oooooo Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu •o 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. -/ Kongruence oooooo Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu •o 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 mi,..., mk £ No a m\ < n\, rr?2 < r?2, mk < nk. • Číslo a má tedy právě r(a) = (r?i + l)(r?2 + 1) • • • • kladných dělitelů, jejichž součet je (nk + 1) "00 = Pľ1+1 -1 Pl-l pnkk+1 -1 Pk -1 Kongruence oooooo Prvočísla oooooooo Rozložení prvočísel OOOOOOOO Dělitelé znovu o« Důsledek (Pokr.) Jsou-li pi,..., p k navzájem různá prvočísla a r?i, ..., m^ G No a označíme-li r\ — min{r?;, m,}, ti = max{r?;, m;} pro každé i = 1, 2,..., k, platí , nk, mlr (pí ni [pí "i p.rpp pD = pí1 Pk