Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero\ 'a věta oooooo ooooooooooo oooooooooooooo Diskrétní matematika - 3. týden Elementární teorie čísel - prvočísla, Eulerova věta, řád prvku Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2015 Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero\ 'a věta oooooo ooooooooooo oooooooooooooo Q Rozložení prvočísel Q Aritmetické funkce • Eulerova funkce ip Q Malá Fermatova věta, Eulerova věta Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero\ 'a věta oooooo ooooooooooo oooooooooooooo • 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. • 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 Rozložení prvočísel •ooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooooooooooo 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 0*0000 Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooooooooooo 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. Rozložení prvočísel oo»ooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooooooooooo 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. □ i 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. Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulerova věta 000*00 ooooooooooo oooooooooooooo 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 | (n + 1)!, a tedy k j (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo. □ Rozložení prvočísel oooo»o Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooooooooooo 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ěí Pak 7r(x) ~--, In x tj. podíl funkcí tt(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 = 00• (důkaz v textu, relativně složitý). Přitom např. X]neN 7? = T' co^ znamená, že prvočísla jsou v n rozmístěna „hustěji" než druhé mocniny (protože ^n = t)' Rozložení prvočísel 00000» Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooooooooooo 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 Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulerova věta OOOOOO »0000000000 oooooooooooooo Aritmetické funkce 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 O, 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 Rozložení prvočísel oooooo Aritmetické funkce o»ooooooooo Malá Fermatova věta, Eulerova věta oooooooooooooo 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ť = ^^/i(c/) = 0 pro všechna n > 1 d\n podle lemmatu za definicí Mobiovy funkce (pro n = 1 je tvrzení zřejmé). Rozložení prvočíse oooooo Aritmetické funkce OOOO0OOOOOO Malá Fermatova věta, Eulerova věta oooooooooooooo Věta (Mobiova inverzní formule) Necht je aritmetická funkce F definovaná pomoci aritmetické funkce f předpisem F(n) = J2d\n f {d)- '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. □ Rozložení prvočíse oooooo Aritmetické funkce ooooo»ooooo Malá Fermatova věta, Eulerova věta oooooooooooooo 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 Rozložení prvočísel oooooo Aritmetické funkce oooooo»oooo Malá Fermatova věta, Eulerova věta oooooooooooooo Definice Nechť n G N Definujme Eulerovu funkci ip předpisem yj(ij) = \{a G N | 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. Rozložení prvočísel oooooo Aritmetické funkce 0000000000» Malá Fermatova věta, Eulerova věta oooooooooooooo Vypočtěte (72). Řešení 72 = 23 •32 = ^(72) = 72 • (1 - \) ■ (1 - |) = 24, alternativně (9) = 4 • 6 = 24. □ Príklad Dokažte, že Vn G N : (4n + 2) = (2n + 1). Řešení ip(4n + 2) = y?(2 • (2n + 1)) = y?(2) • y(2n + 1) = y(2n + 1). □ J Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta •ooooooooooooo Tato tvrzení patří mezi nejdúlež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). Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta ©•oooooooooooo Úplná a redukovaná soustava zbytků Definice Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1,..., m — 1). Redukovaná soustava zbytků modulo m je libovolná tp(m)-ť\ce čísel nesoudělných srna po dvou nekongruentních modulo m. Lemma Nechť xi, X2,..., x^m) tvoří redukovanou soustavu zbytků modulo m. Je-li a (z Z, (a, m) = 1 pak i čísla a ■ xi,..., a ■ x^mj tvoří redukovanou soustavu zbytků modulo m. Protože (a, m) = 1 a (x,-, m) = 1, platí (a • x,-, m) = 1. Kdyby pro nějaká i J platilo a • xf- = a • xj (mod m), po vydělení obou stran kongruence číslem a nesoudělným s m dostaneme xf- = xj (mod m). □ Věta (Eulerova) Necht a G Z, m G N, (a, m) = 1. Pak 3^(m) = 1 (mod m). Důkaz. Bud xi>x2) • • •)xip(m) libovolná redukovaná soustava zbytků modulo m. Podle předchozího lemmatu je i a • xi,..., a ■ x^m^ redukovaná soustava zbytků modulo m. Platí tedy, že pro každé / existuje j ( /,_/' G {1,2,..., tp(m)}) tak, že a ■ x; = xj (mod m). Vynásobením dostáváme (a-xi) • (a-x2) • • • (a-x^)) = x1 ■ x2 ■ ■ -x^ (mod m). Po úpravě a^™) • xi • x2 • • • x(p(m) = xi • x2 • • • x(p(m) (mod m) vydělení číslem xi • X2 • • -x^^) dostaneme požadované. □ Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta ooosoooooooooo S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řád čísla modulo m: Definice Nechť 3 6Z, m £ N (a, m) = 1. Řádem čísla a modulo m rozumíme nejmenší přirozené číslo n splňující a" = 1 (mod m). Rozložení prvočíse oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta OOOO0OOOOOOOOO Poznámka To, že je řád definován, plyne z Eulerovy věty - pro každé číslo nesoudělné s modulem je totiž jistě jeho řád nejvýše roven tp(m). Jak později uvidíme, velmi důležitá jsou právě ta čísla, jejichž řád je roven právě tp(m) - tato čísla nazýváme primitivními kořeny modulo m a hrají důležitou roli mj. při řešení binomických kongruencí. Příklad Pro libovolné m £ N má číslo 1 modulo m řád 1. Číslo —1 má řád • 1 pro m = 1 nebo m = 2 • 2 pro m > 2 Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta 00000*00000000 Príklad Určete řád čísla 2 modulo 7. Řešení 21 = 2 £ 1 (mod 7) 22 = 4 £ 1 (mod 7) 23 = 8 = 1 (mod 7) Řád čísla 2 modulo 7 je tedy roven 3. □ Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooo»ooooooo Uveďme nyní několik zásadních tvrzení udávajících vlastnosti řádu čísla modulo m: Lemma Nechi m 6 N, a, b £ Z, (a, m) = (b, m) = 1. Jestliže a = b (mod m), pak obě čísla a, b mají stejný řád modulo m. Důkaz. Umocněním kongruence a = b (mod m) na n-tou dostaneme a" = bn (mod m), tedy a" = 1 (mod m) -t=ŕ b" = 1 (mod m). □ Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta ooooooo«oooooo 1 Lemma_ Necht m G N, a G Z, (a, m) = 1. Je-// řac/ čísla a modulo m roven r ■ s, (kde r, s G N), pak řád čísla ar modulo m je roven s. Důkaz. Protože žádné z čísel a, a2, a3,... ,ars 1 není kongruentní s 1 modulo m, není ani žádné z čísel ar, a2r, a3r,..., a^-1^ kongruentní s 1. Platí ale (ar)s = 1 (mod m), proto je řád ar modulo m roven s. □ Rozložení prvočíse oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooooo»ooooo Poznámka Opak obecně neplatí - z toho, že řád čísla ar modulo m je roven s ještě neplyne, že řád čísla a modulo m je r ■ s. Např pro m = 13 máme: a = 3, a2 = 9 (mod 13), a3 = 27 = 1 (mod 13) => 3 má řád 3 mod 13. b = -4, b2 = 16 ^ 1 (mod 13), fa3 = -64 = 1 (mod 13) => -4 má řád 3 mod 13. Přitom (—4)2 = 16 = 3 (mod 13) má stejný řád 3 jako číslo 3, ale číslo —4 nemá řád 2 • 3. Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta ooooooooo»oooo Přesný popis závislosti řádu na exponentu dávají následující 2 věty: Věta Nechi m 6 N, a £ Z, (a, m) = 1. Označme r řád čísla a modulo m. Pak pro libovolná t, s 6 N U {0} platí ař = as (mod m) t = s (mod r). Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooooooo»ooo Bez újmy na obecnosti lze předpokládat, že t > s. Vydělíme-li číslo t — s číslem r se zbytkem, dostaneme t — s = q ■ r + z, kde g, z G N0,0 < z < r. "<í=" Protože t = s (mod r), máme z = 0, a tedy ař~s = aqr = (ar)q = lq (mod m). Vynásobením obou stran kongruence číslem as dostaneme tvrzení. Z ař = as (mod m) plyne as ■ aqr+z = as (mod m). Protože je aľ = 1 (mod m), je rovněž aqr+z = az (mod m). Celkem po vydělení obou stran kongruence číslem as (které je nesoudělné s modulem), dostáváme az = 1 (mod m). Protože z < r, plyne z definice řádu, že z = 0, a tedy r \ t — s. □ Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta ooooooooooo»oo Zřejmým důsledkem předchozí věty a Eulerovy věty je následující tvrzení Důsledek Necht m G N, a G Z , (a, m) = 1. Označme r řád čísla a modulo m. O Pro libovolné n G N U {0} platí a" = 1 (mod m) -4=>- r n. 0 r | (p(m) Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta oooooooooooo»o Následující věta je zobecněním předchozího Lemmatu. ' Věta Nechť m, n G N, a G Z, (a, m) = 1. Je-li řád čísla a modulo m roven r G N, je řád čísla a" modulo m roven t-^t. Důkaz. Protože -fjr^ = [r,n], což je zřejmě násobek r, máme (a")(^T = aM = 1 (mod m) (plyne z předchozího Důsledku, neboť r | [r,n]). Na druhou stranu, je-li k G N libovolné takové, že (an)k = ank = 1 (mod m), dostáváme (r je řád a), že r i n • k a dále víme, že t-^ i 7-^ • /c a v J J< \ < (n,rj 1 (n,r) díky nesoudělnosti čísel 7-^ a 7-^ dostáváme i /c. Proto je řádem čísla a" modulo m. □ Rozložení prvočísel oooooo Aritmetické funkce ooooooooooo Malá Fermatova věta, Eulerova věta 0000000000000» Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: ■1 Lemma Nechť m G N, a, b G 2 ', (a, m) = (b, m) = 1. Jestliže a je řádu r a b je řádu s modulo m, kde (r, s) = 1, pa/c č/s/o a • b je řádu r • s modulo m. Důkaz. Označme ô řád čísla a • b. Pak (a£>) = 1 (mod m) a umocněním obou stran kongruence dostaneme arSbrS = 1 (mod m). Protože je r řádem čísla a, je ar = 1 (mod m), tj. Z/á = 1 (mod m), a proto s | rô. Z nesoudělnosti ras plyne s | ô. Analogicky dostaneme i r | ô, a tedy (opět s využitím nesoudělnosti r, s) r ■ s | ô. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto ô | rs. Celkem tedy S = rs._□