Diskrétní matematika B - 2. týden Elementární teorie čísel - Kongruence šifrách X)OOO0 Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2013 Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách ooooooooooooooooooooooooooooooooooooo Obsah př ednášky Ql Literatura Q Rozložení prvočísel Ql Kongruence • Základní vlastnosti kongruencí • Aritmetické funkce • Eulerova funkce ip • Malá Fermatova věta, Eulerova věta • Primitivní kořeny Q Pár slov o šifrách Kongruence Pár slov o šifrách ooooooooooooooooooooooooooooooooooooo Doporučené zdroje Rozloženi prvočísel oooooooo • Martin Panák, Jan Slovák, Drsná matematika, průběžně připravovaný e-text. • Předmětové záložky v IS MU • 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. • 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/ATC10.pdf Literatura Rozložení prvočísel •ooooooo Kongruence Pár slov o šifrách ooooooooooooooooooooooooooooooooooooo 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 Rozložení prvočísel Kongruence Pár slov o šifrách o»oooooo ooooooooooooooooooooooooooooooooooooo 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 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. Literatura Rozložení prvočísel 00*00000 Kongruence Pár slov o šifrách ooooooooooooooooooooooooooooooooooooo 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 j (n! — 1), platí p < n! — 1, tedy p < n!. Prvočíslo p splňuje podmínky úlohy. □ Z této věty rovněž vyplýva 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 solňuiící n < o < 2n. Rozložení prvočísel Kongruence Pár slov o šifrách ooo»oooo ooooooooooooooooooooooooooooooooooooo Prvočísel je vcelku málo Prí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 | (n + 1)!, a tedy k j (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo. □ Literatura Rozložení prvočísel oooo»ooo Kongruence Pár slov o šifrách ooooooooooooooooooooooooooooooooooooo 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ě. Literatura Rozložení prvočísel ooooo»oo Kongruence Pár slov o šifrách ooooooooooooooooooooooooooooooooooooo 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 G N0. Ř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, ..., p„. Položme N = 3p2 • P3.....p„ + 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,... ,pn, jak plyne z tvaru čísla N, a to je spor. Literatura Rozložení prvočísel oooooo#o Kongruence Pár slov o šifrách ooooooooooooooooooooooooooooooooooooo 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 7r(x) udává počet prvočísel menších nebo rovných číslu xěí Pak 7r(x) ~--, Inx tj. podíl funkcí tt(x) a x j Inx 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 \ = 00• Přitom např. SneN 7? = T' co^ znamená, že prvočísla jsou v N rozmístěna „hustěji" než druhé mocniny. Literatura Rozložení prvočísel 0000000» Kongruence Pár slov o šifrách ooooooooooooooooooooooooooooooooooooo Příklad O tom, jak odpovídá asymptotický odhad 7r(x) ~ x/ 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 Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách •oooooooooooooooooooooooooooooooooooo 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). Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách o»ooooooooooooooooooooooooooooooooooo Lemma Pro libovolná a, b G Z, m G N jsou následující podmínky ekvivalentní: O a = b (mod m), O a = b + mt pro vhodné ŕ G Z, 0 m I a — b. Důkaz. " (1)=^(3)" Jestliže a = q\m + r, b = q2m + r, pak a - b = (q1- q2)m. " (3)=^(2)" Jestliže m | a — b, pak existuje ŕ G Z tak, že m • t = a — b, tj. a = b + mŕ. " (2)=^(1)" Jestliže a = b + mŕ, pak z vyjádření fa = + r plyne a = m(q + t) + r, tedy a i b mají při dělení číslem m týž zbytek r, tj. a = fa (mod m). □ Přímo z definice plyne, že kongruence podle modulu m je reflexivní (tj. a = a (mod m) platí pro každé a G Z), symetrická (tj. pro každé a,í)6Zz3EÍ) (mod m) plyne b = a (mod m)) a tranzitivní (tj. pro každé a, b, c G Z z a = fa (mod m) a b = c (mod m) plyne a = c (mod m)) relace, jde tedy o ekvivalenci. Dokážeme nyní další vlastnosti: • Kongruence podle téhož modulu můžeme sčítat. Libovolný sčítanec můžeme přenést s opačným znaménkem z jedné strany kongruence na druhou. K libovolné straně kongruence můžeme přičíst jakýkoliv násobek modulu. Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách ooo»ooooooooooooooooooooooooooooooooo • 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. • Jestliže kongruence a = b platí podle modulů m\,..., m^, platí i podle modulu, kterým je nejmenší společný násobek [mj,..., m^] těchto čísel. • Jestliže kongruence platí podle modulu m, platí podle libovolného modulu d, který je dělitelem čísla m. 9 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. Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách oooo«oooooooooooooooooooooooooooooooo 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. Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách ooooo»ooooooooooooooooooooooooooooooo Příklad Nalezněte zbytek po dělení čísla 520 číslem 26. Protože 52 = 25 = -1 (mod 26), platí 520 = (_i)io = 1 (mod 26), a tedy zbytek po dělení čísla 520 číslem 26 je jedna. Příklad Dokažte, že pro libovolné n G N je 37"+2 + 16"+1 + 23" dělitelné sedmi. Platí 37 = 16 = 23 = 2 (mod 7), a tedy podle základních vlastností platí 37n+2 + 16n+l+23n = 2n+2+2n+l+2n = 2"(4+2 + l) = 0 (mod 7). Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách oooooo«oooooooooooooooooooooooooooooo Dokažte, že číslo n = (8355 + 6)18 — 1 je dělitelné číslem 112. Řešení Rozložíme 112 = 7-16. Protože (7,16) = 1, stačí ukázat, že 7 | n a 16 | n. Platí 835 = 2 (mod 7), a tedy n = (25 + 6)18 - 1 = 3818 - 1 = 318 - 1 = = 276 - 1 = (-1)6 - 1 = 0 (mod 7), proto 7 | n. Podobně 835 = 3 (mod 16), a tedy n = (35 + 6)18 - 1 = (3 • 81 + 6)18 - 1 = (3 • 1 + 6)18 - 1 = = 918 — 1 = 819 — 1 = 19 — 1 = 0 (mod 16), proto 16 | n. Celkem tedy 112 | n, což jsme měli dokázat. Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách ooooooo»ooooooooooooooooooooooooooooo ' Příklad Dokažte, že pro libovolné prvočíslo p a libovolná a, b G Z platí ap + iř = (a + b)p (mod p). Řešení Podle binomické věty platí (a + bf = ap+ {^aP-H + (p2)ap-2b2 + ■■■ + {^ab^ + ď. Dále, protože p (£) pro libovolné /c 6 {1,..., p platí (£) = 0 (mod p), odkud plyne tvrzení. - 1} [dokažte]), Aritmetickou funkcí zde rozumíme funkci, jejímž definičním oborem je množina přirozených čísel. Definice Rozložme přirozené číslo n na prvočísla: n = p^1 ■ ■ ■ p^k. Hodnotu Móbiovy funkce fi(n) definujeme rovnu 0, pokud pro některé / platí a, > 1 a rovnu (—l)k v opačném případě. Dále definujeme /i(l) = l. Příklad /i(4) = M22) = 0,/j(6) = /i(2 • 3) = (-l)2,/i(2) = /i(3) = -1. J Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách ooooooooo»ooooooooooooooooooooooooooo Dokážeme nyní několik důležitých vlastností Móbiovy funkce, zejména tzv. Móbiovu inverzní formuli. Lemma Pro n G N\{1} platíZd\nrid) = 0. Důkaz. Zapíšeme-li n ve tvaru n = p^1 ■ ■ ■ p^k, pak všechny dělitele d čísla n jsou tvaru d = p^1 • • • p^k, kde 0 < /3/ < a, pro všechna / 6 {1,..., k}. Proto £>( 1, resp. I(n) = 1 pro všechna n G N. Pak pro každou aritmetickou funkci f platí: foI = Iof = f a (lof)(n) = (fol)(n) = J2f(d)- d\n Dále platí I o n = n o I = 1, neboť d\n d\n = '^^fi(d) = 0 pro všechna n > 1 podle lemmatu za definicí Mobiovy funkce (pro n = 1 je tvrzení zřejmé). Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách oooooooooooo#oooooooooooooooooooooooo Věta (Móbiova inverzní formule) Necht je aritmetická funkce F definovaná pomocí aritmetické funkce f předpisem F(n) = J2d\n Pak lze funkci f vyjádřit ve tvaru f(n) = J2v(3)-F(d). d\n Důkaz. Vztah F(n) = J2d\n^(d) lze jiným způsobem zapsat jako F = f o /. Proto Fo/i = (fo/)o/í = fo(/o/í) = fol = řl což je tvrzení věty. □ Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách ooooooooooooo^ooooooooooooooooooooooo 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). Příklad Multiplikativními funkcemi jsou např. funkce f(n) = a(n), f(n) = r(n), či f(n) = fi(n) nebo, jak brzy dokážeme i tzv. Eulerova funkce f(n) = tp(n). i Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách oooooooooooooo»oooooooooooooooooooooo Definice Nechť n G N Definujme Eulerovu funkci ip předpisem yj(ij) = \{a G N 1 0 < a < n, (a, n) = 1}| Příklad tp(l) = 1, (5) = 4, - (n, a) = 1 A (n, b) = 1. Spolu se snadno odvoditelným výsledkem íp(pa)=pa-pa-1 = (p-l).pa-1 pak lze odvodit vztah pro výpočet ip již třetím způsobem. Literatura Rozložení prvočísel oooooooo Kongruence Pár slov o šifrách oooooooooooooooooo»oooooooooooooooooo Vypočtěte (72). Řešení 72 = 23 •32 = y>(72) = 72 • (1 - |) • (1 - |) = 24, alternativně (9) = 4 • 6 = 24. □ Příklad Dokažte, že Vn e N : ip(4n + 2) = (2n + 1). Řešení ip(4n + 2) = y?(2 • (2n + 1)) =