Literatura Rozložení prvočísel ooooooooooo Kongruence oooooooooo Diskrétní matematika B - 2. týden Elementární teorie čísel - Kongruence Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 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 Literatura Rozložení prvočísel ooooooooooo Kongruence oooooooooo » Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako 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 N um ber 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 •oooooooooo Kongruence OOOOOOOOOO 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 Literatura Rozložení prvočísel o»ooooooooo Kongruence oooooooooo B 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 oosoooooooo Kongruence oooooooooo 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 splňující n < p < 2n. Literatura Rozložení prvočísel ooo»ooooooo Kongruence oooooooooo 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 | (n + 1)!, a tedy k j (n + 1)! + k, a proto (n + 1)! + /c nemůže být prvočíslo. □ Literatura Rozložení prvočísel oooo«oooooo Kongruence oooooooooo 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ě. Rozložení prvočísel Kongruence OOOOO0OOOOO oooooooooo 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«oooo Kongruence oooooooooo rvočíse 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 ooooooo»ooo Kongruence oooooooooo Věta Je-li P množina všech prvočísel, pak J2peP p = 00• Důkaz. Buď n libovolné přirozené číslo a pi,..., p7r(n) všechna prvočísla nepřevyšující n. Položme x 1 v -1 *»>=nK) • Jednotlivé činitele lze chápat jako součet geometrické řady, proto x 00 1 , 1 A(")=n( e ^7)=e-^— /=1 V—O K' 7 Pl • • • P,r(n) kde sčítáme přes všechny 7r(n)-tice nezáporných celých čísel («1,..., a^n))- Literatura Rozložení prvočísel oooooooo»oo Kongruence oooooooooo Důkaz. Protože každé číslo nepřevyšující n se rozkládá pouze na prvočísla z množiny {pi,..., pn^}, je určitě každé takové číslo v tomto součtu zahrnuto. Tedy X(n) >l + | + -- - + ^,a protože harmonická řada diverguje , je i lim„-xx> = °°- S využitím rozvoje funkce In(1 + x) do mocninné řady dále dostáváme 7r(n) 7r(n) oo in x(n) = -eln(1-i) = ee ("prr1 = i=l i=l m=l 7r(") OO i=l m=2 Literatura Rozložení prvočísel ooooooooo»o Kongruence oooooooooo Důkaz. ir(n) oo in A(n) = pr1 + • • •+Pjn) + ee (^r1 ■ i=l m=2 Protože vnitřní součet lze shora odhadnout jako oo oo £ (mprr1 < e pym = m—2 m—2 umíme shora odhadnout i divergující posloupnost InA(n) < YU=i PT1 + ^ YU=i P\2 ■ Druhý součet přitom zřejmě konverguje (viz konvergence řady Yl^Li n~2)> proto musí nutně divergovat první součet Yll=i PÍ1* což jsme chtěli dokázat. □ Literatura Rozložení prvočísel 0000000000» Kongruence oooooooooo 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) rel. chyba Li(x) rel. chyba 100 25 21,7 0,13 29,1 0,04 1000 168 144,7 0,13 176,6 0,01 10000 1229 1085,7 0,11 1245,1 0,002 100000 9592 8685,9 0,09 9628,8 0,0004 500000 41538 38102,9 0,08 41605,2 0,0001 Li(x) = f* 1^7 značí tzv. logaritmický integrál a za předpokladu tzv. Riemannovy hypotézy platí odhad tt(x) - Li(x)\ = O(Vxlnx). Literatura Rozložení prvočísel ooooooooooo Kongruence •ooooooooo 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 ooooooooooo Kongruence o«oooooooo 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 \ 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í b = mq + r plyne a = m(q + t) + r, tedy a i fa 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 ooooooooooo Kongruence ooo«oooooo • 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 ooooooooooo Kongruence oooo»ooooo 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 ooooooooooo Kongruence ooooo»oooo 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 ooooooooooo Kongruence oooooo»ooo 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 ooooooooooo Kongruence ooooooo»oo ' Příklad Dokažte, že pro libovolné prvočíslo p a libovolná a, b G Z platí ap + bp = (a + b)p (mod p). Řešení Podle binomické věty platí (a + bf = ap+ {^aP-H + (p2)ap-2b2 + ■■■ + (/1)a^-1 + ^. Dále, protože p (£) pro libovolné /c 6 {1,..., p platí (£) = 0 (mod p), odkud plyne tvrzení. - 1} [dokažte]), Rozložení prvočísel Kongruence ooooooooooo oooooooo»o Aritmetické funkce Aritmetickou funkcí zde rozumíme funkci, jejímž definičním oborem je množina přirozených čísel. Definice (Mobiova funkce) Rozložme přirozené číslo n na prvočísla: n = p^1 ■ ■ ■ pkk. 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 ooooooooooo Kongruence ooooooooo» 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 p, = p, o I = 1, neboť (/ o ri(n) = e l(dM%) = e = 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 ooooooooooo Kongruence oooooooooo Věta (Móbiova inverzní formule) Necht je aritmetická funkce F definovaná pomocí aritmetické funkce f předpisem F(n) = J2d\n 'ze funkci f vyjádřit ve tvaru f(n) = J2v(3)-F(d). d\n Důkaz. Vztah F(n) = Yld\nf(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 ooooooooooo Kongruence oooooooooo 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 ooooooooooo Kongruence oooooooooo 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 ooooooooooo Kongruence oooooooooo Vypočtěte (72). Řešení 72 = 23 •32 = ^(72) = 72 • (1 - |) • (1 - |) = 24, alternativně (9) = 4 • 6 = 24. □ Příklad Dokažte, že Vn e N : (4n + 2) = (2n + 1). Řešení ip(4n + 2) = y?(2 • (2n + 1)) = y?(2) • y(2n + 1) = y(2n + 1). □ J Literatura Rozložení prvočísel ooooooooooo Kongruence oooooooooo Tato tvrzení patří mezi nejduležitější výsledky elementární teorie čísel. Věta (Fermatova, Malá Fermatova) Necht a G Z, p prvočíslo, p\ a. Pak a"-1 = 1 (mod p). Důkaz. Tvrzení vyplyne jako snadný důsledek Eulerovy věty. Dá se ale dokázat i přímo (např. matematickou indukcí nebo kombinatoricky) □ Důsledek Necht a G Z, p prvočíslo. Pak ap = a (mod p). Literatura Rozložení prvočísel ooooooooooo Kongruence oooooooooo Příklad (Důkaz Malé Fermatovy věty) Kombinatorický důkaz jde na věc poněkud „od lesa": podobně jako v úlohách využívajících Burnsideovo lemma máme za úkol určit počet náhrdelníků dané délky (ty vzniknou navlečením několika šperků na šňůrku a jejím svázáním) vytvořených z několika typů šperků s tím, že nerozlišujeme náhrdelníky, které je možné na sebe převést otočením (a liší se tedy jen tím, kde je zavázaný „uzlík"). Snadno si lze rozmyslet, že navlékáme-li n šperků, lze v některých konstelacích převést náhrdelník sám na sebe při otočení o určitý počet šperků (vždy ale pouze o počet dělící rí). Předpokládejme nyní, že máme a typů šperků a požadovaný počet použitých šperků na jeden náhrdelník je dán prvočíslem p. Zřejmě pro každý náhrdelník využívající alespoň dvou typů šperků dostáváme různým umístěním uzlíku p různých p-tic šperků na šňůrce (což ale není případ náhrdelníků sestavených pouze z jednoho typu šperku). Vidíme tedy, že počet různých náhrdelníků je roven ap - a - + 3, P což zejména znamená, že musí platit p | ap — a. Literatura Rozložení prvočísel ooooooooooo Kongruence oooooooooo Příklad Například pro hodnoty a = 2, p = 5 tak určujeme počet náhrdelníků dvou typů šperků (A, B) délky pět. Dáme-li ze všech 25 různě navlečených šňůrek stranou 2 náhrdelníky tvořené pouze jedním typem (AAAAA, BBBBB), pak dále máme ^f^ = 6 náhrdelníků, které na sebe nelze převést otáčením (ABBBB, AABBB, AAABB, AAAAB, ABABB, AABAB).