Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero\ 'a věta oooooo ooooo oooooooooooooo Diskrétní matematika - 3. týden Elementární teorie čísel - prvočísla a kongruence Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2014 Rozložení prvočísel oooooo Obsah přednášky Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooooo Qi Rozložení prvočísel Q Aritmetické funkce • Eulerova funkce ip Q Malá Fermatova věta, Eulerova věta Rozložení prvočísel oooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooooo • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Rozložení prvočísel oooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta 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 Q Rozložení prvočísel Q Aritmetické funkce • Eulerova funkce tp Qi Malá Fermatova věta, Eulerova věta Nyní se budeme snažit zodpovědět následující otázky: O Je prvočísel nekonečně mnoho? 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? 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? 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? 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 ooooo 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. Rozložení prvočísel 0*0000 Aritmetické funkce ooooo 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. □ Rozložení prvočísel 0*0000 Aritmetické funkce ooooo 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 ooooo 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. Rozložení prvočísel oo»ooo Aritmetické funkce ooooo 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 Rozložení prvočísel oo»ooo Aritmetické funkce ooooo 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. 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 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. Malá Fermatova věta, Eulerova věta oooooooooooooo Prvočísel je vcelku málo Rozloženi prvočísel Aritmetické funkce ooo#oo ooooo 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. 4Ľ3k4l3*4 = k4 = * -š -O^O Malá Fermatova věta, Eulerova věta oooooooooooooo Prvočísel je vcelku málo Rozloženi prvočísel Aritmetické funkce ooo#oo ooooo 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 ooooo 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. Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulerova věta oooo»o ooooo 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 \ = 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 ooooo 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, Eulerc oooooo ooooo oooooooooooooo Plán přednášky Q Rozložení prvočísel Q Aritmetické funkce Q Malá Fermatova věta, Eulerova věta Malá Fermatova věta, Eulerova věta oooooooooooooo Aritmetické funkce Rozloženi prvočísel Aritmetické funkce oooooo ooooo 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. Malá Fermatova věta, Eulerova věta oooooooooooooo Aritmetické funkce Rozloženi prvočísel Aritmetické funkce oooooo ooooo 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 Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero\ 'a věta oooooo ooooo 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. Rozložení prvočísel oooooo Aritmetické funkce ooooo 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\nKd) = 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 • /£{!,..., k}. Proto n jsou tvaru d = p^1 ■ ■ ■ p^k, kde 0 < /3/ < a, pro všechna E (A,...A)e(Nu{0})'< 0 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 Rozložení prvočísel oooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooooo Príklad Definujme dvě pomocné funkce la/ předpisem 1(1) = 1, = 0 pro všechna n > 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 ooooo 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 Rozložení prvočíse oooooo Aritmetické funkce ooooo 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)- ^ak 'ze funkci f vyjádřit ve tvaru f(n) = J2v(3)-F(d). d\n Důkaz. Vztah F(n) = J2d\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 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). Rozložení prvočíse oooooo Aritmetické funkce 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 •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}| Rozložení prvočísel oooooo Aritmetické funkce •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, ^Sí' -š -O^O Rozložení prvočíse oooooo Aritmetické funkce ooo»o Malá Fermatova věta, Eulerova věta oooooooooooooo Poznámka Předchozí výsledek lze obdržet i bez použití Móbiovy inverzní formule pomocí principu inkluze a exkluze na základě zjištění počtu čísel soudělných s n v určitém intervalu. Rozložení prvočíse oooooo Aritmetické funkce ooo»o Malá Fermatova věta, Eulerova věta oooooooooooooo Poznámka Předchozí výsledek lze obdržet i bez použití Móbiovy inverzní formule pomocí principu inkluze a exkluze na základě zjištění počtu čísel soudělných s n v určitém intervalu. Důsledek Necht a, b G N, (a, b) = l. Pak ip{a- b) = ip{a)-ip{b). Poznámka Rovněž toto tvrzení lze odvodit nezávisle na základě poznatku (n, ab) = 1 -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

(72). Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero 'a věta oooooo oooo» oooooooooooooo Vypočtěte (72). Řešení 72 = 23 •32 = ^(72) = 72 • (1 - \) ■ (1 - |) = 24, alternativně (9) = 4 • 6 = 24. □ Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero 'a věta oooooo oooo» 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 : (2n + 1). Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero 'a věta oooooo oooo» 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 : (2n + 1). Řešení y(4n + 2) = x2) • • •)xip(m) libovolná redukovaná soustava zbytků modulo m. Podle předchozího lemmatu je i a • xi,..., a • x^^) redukovaná soustava zbytků modulo m. Platí tedy, že pro každé / existuje j ( /',_/' G {1, 2,..., 2 Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulerova věta OOOOOO OOOOO 00000*00000000 Příklad Určete řád čísla 2 modulo 7. Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero /a věta oooooo ooooo 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. □ 4(5> ^Sř' -š -O^O Rozložení prvočísel oooooo Aritmetické funkce ooooo 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. Rozložení prvočísel oooooo Aritmetické funkce ooooo 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číse oooooo Aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooo»oooooo Lemma Nechi m 6 N, a £ Z, (a, m) = 1. Je-li řád čísla a modulo m roven r • s, (kde r, s 6 N), pak řád čísla ar modulo m je roven s. Rozložení prvočísel Aritmetické funkce Malá Fermatova věta, Eulero /a věta oooooo ooooo ooooooo«oooooo 1 Lemma_ Necht m G N, a G Z, (a, m) = 1. Je-// řád čí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 ooooo 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 ooooo 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 £ N U {0} platí ař = as (mod m) <í=^> t = s (mod r). Rozložení prvočísel oooooo Aritmetické funkce ooooo 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. □ ■0 0.0 Rozložení prvočísel oooooo Aritmetické funkce ooooo 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 Aritmetické funkce Malá Fermatova věta, Eulero /a věta oooooo ooooo 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. Rozložení prvočísel oooooo Aritmetické funkce ooooo 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-^ • k a v J J< \ < (n,rj 1 (n,rj 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 ooooo 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 e N, a, b e 1 ', (a, m) = (b, m) = 1. Jestliže a je řádu r a b je řádu s modulo m, kde (r, s) = 1, pa/c číslo a • b je řádu r ■ s modulo m. Rozložení prvočísel oooooo Aritmetické funkce ooooo 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._□