Aritmetické funkce Multiplikativní aritmetické funkce Malá Fermatova věta, Eulerova věta oooooo ooooo ooooooooooooo Diskrétni matematika - 3. týden Elementární teorie čísel - prvočísla, Eulerova věta, rád prvku Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2017 Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooooooooo Obsah přednášky Q Aritmetické funkce Q Multiplikativní aritmetické funkce • Eulerova funkce cp Q Malá Fermatova veta, Eulerova věta Aritmetické funkce Multiplikativní aritmetické funkce Malá Fermatova věta, Eulerova věta oooooo ooooo ooooooooooooo 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 Malá Fermatova věta, Eulerova věta ooooooooooooo Aritmetické funkce Aritmetické funkce Multiplikativní aritmetické funkce •ooooo 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 Mobiovy funkce ji(n) definujeme rovnu 0, pokud pro některé / platí a.i > 1 a rovnu (—1)^ v opačném případě. Dále definujeme Mi) = i- Příklad /z(4) = M22) = 0, M6) = M2 • 3) = (-1)2, M2) = M3) = -1 ] Aritmetické funkce o«oooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooooooooo Dobrým příkladem aritmetických funckí jsou počty dělitelů a součty dělitelů, r(r?) a cr(n). Důsledek pnkk je tvaru 9 Každý kladný dělitel čísla a = p"1 • • • ■ p™1.....p™k, kde at?i. rn^ G No a mi < r?i, rn2 < r?2, nik < "k- 9 Číslo a má tedy právě r(a) = (r?i + l)(r?2 + 1).....(r?/c + 1) kladných dělitelů, jejichž součet je a(a) = Pľ1+1 ~ 1 Pi-1 Pnkk+1 ~ 1 P/c - 1 Aritmetické funkce OOÄOOO Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooooooooo Möbiova funkce se objevuje v tzv. Mobiově inverzní formuli. Lemma Pro n eN\{l} platíZd\n»(d) = <>■ 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 /£{!,..., /c}. Proto e din (Ä,-A)e(Nu{0})'< 0 □ Aritmetické funkce ooo«oo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooooooooo Potřebujeme ještě specifickou kovoluci, tzv. Dirichletův součin. Definice Buďte f,g aritmetické funkce. Jejich Dirichletův součin je definován předpisem (fog)(n) = Y/f(d)-g(^)= £ f(d1).g(d2). d\n d\d2=n Lemma Dirichletův součin je asociativní. Důkaz. Aritmetické funkce oooo«o Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooooooooo Dvě pomocné "jednotkové"funkce Definujme dvě pomocné funkce la/ předpisem 1(1) = 1, I(r?) = 0 pro všechna n > 1, resp. /(r?) = 1 pro všechna r? G N. Pak pro každou aritmetickou funkci f platí: fol = lof=f a (/o f)(n) = (ŕ o l)(n) = ^ f (c/). c/|n Dále platí I o ji = jio I = I, neboť (/o^)(n) = x;/(rf)M5) = e/(W) = d\n d\n = //(c/) = 0 pro všechna n > 1 c/|n podle lemmatu za definicí Móbiovy funkce (pro n = 1 je tvrzení zřejmé). Aritmetické funkce 00000« Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooooooooo Věta (Móbiova inverzní formule) Necht je aritmetická funkce F definovaná pomocí aritmetické funkce f předpisem F(r?) = Yld\n ^(^)- 'ze funkci f vyjádřit ve tvaru d\n Důkaz. Vztah F(r?) = J2d\n f{d) lze jiným způsobem zapsat jako F — f o /. Proto F o /i = (f o /) o /i = /ro(/o/i) = f ol— fcož je tvrzení věty. □ Aritmetické funkce Multiplikativní aritmetické funkce Malá Fermatova věta, Eulerova věta oooooo •oooo ooooooooooooo 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) Príklad Multiplikativními funkcemi jsou např. funkce f (n) = cr(n), f (n) = r(r?), či f (n) = ji(n) nebo, jak brzy dokážeme i tzv. Eulerova funkce f (n) = (p(n). Malá Fermatova věta, Eulerova věta ooooooooooooo Eulerova funkce Aritmetické funkce Multiplikativní aritmetické funkce oooooo o«ooo Definice Nechť n £ N. Definujme Eulei (!) = 1, >l = n " ^-----7" + """ + d\n n Pi • • • Pk = n • 1 - 1 - Pi Pk Aritmetické funkce oooooo Multiplikativní aritmetické funkce oooo« Malá Fermatova věta, Eulerova věta ooooooooooooo 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 snv určitém intervalu. Důsledek Nechť a, b e N, (a, b) = l. Pak = 1 (mod m). Důkaz. Buď xi,x2,... 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 ( i J e {1, 2,..., (p(m)}) tak, že a • x; = xy (mod m). Vynásobením dostáváme (a • xi) • (a • x2) • • • (a • x^(m)) = xi • x2 • • • x^(m) (mod rrc). Po úpravě a^(m) • xi • x2 • • • x^(m) = xi • x2 • • • x^(m) (mod m) vydělení číslem x\ • x2 • • • x^(m) dostaneme požadované. □ Aritmetické funkce oooooo Řád čísla Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooo«ooooooooo S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řád čísla modulo m: Definice Necht a £ Z, m 6 N (a, m) = 1. Řádem čísla a modulo m rozumíme nejmenší přirozené číslo n splňující an = 1 (mod m). 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 (p(m). Jak později uvidíme, velmi důležitá jsou právě ta čísla, jejichž řád je roven právě (p(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 6 N má číslo 1 modulo m rád 1. Číslo —1 má řád • 1 pro m — 1 nebo m — 2 • 2 pro m > 2 Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta OOOOO0OOOOOOO Uveďme nyní několik zásadních tvrzení udávajících vlastnosti řádu čísla modulo m\ Lemma Necht m 6 N, a, b e Z, (a, m) — {b. m) — 1. Jestliže a = b (mod m), pak obě čísla a, b mají stejný rád modulo m. Důkaz. Umocnením kongruence a = b (mod m) na r?-tou dostaneme an = bn (mod m), tedy an = 1 (mod m) <^=^> bn = 1 (mod m). □ Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta OOOOOO0OOOOOO Lemma Necht m 6 N, a £ Z, (a, m) = 1. Je-// řac/ čísla a modulo m roven r • s, (kde r,s G NJ, pa/c řác/ č/s/a ar modulo m je roven s. Důkaz. Protože žádné z čísel a, a , a ,..., ars~ není kongruentní s 1 modulo m, není ani žádné z čísel ar, a2r, a3r,..., a^s~^r kongruentní s 1. Platí ale (ar)s = 1 (mod m), proto je řád ar modulo m roven s. □ Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta OOOOOOO0OOOOO 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), b3 = -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. Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta OOOOOOOO0OOOO Přesný popis závislosti řádu na exponentu dávají následující 2 věty: Věta Necht m 6 N, a £ Z, (a, m) = 1. Označme r řác/ čísla a modulo m. Pak pro libovolná £, s £ N U {0} platí ař = as (mod m) t = s (mod r). Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta OOOOOOOOO0OOO Důkaz. 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 q, z G N0, O < z < r. "<^" Protože t = s (mod r), máme z = O, 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 rn). Protože je ar = 1 (mod m), je rovněž aqr+z = az (mod rn). 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 = O, a tedy r t — s. □ Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooooooooo Zřejmým důsledkem předchozí věty a Eulerovy věty je následující tvrzení r Důsledek _ Necht m G N, a G Z «, (a, m) — 1. Označme r rád čísla a modulo m. O Pro libovolné n G N U {0} platí an = 1 (mod m) <^=^> r n. O r (fi(m) Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta ooooooooooo«o Následující věta je zobecněním předchozího Lemmatu Necht m, n 6 N, a e Z, (a, m) = 1. Je-// řac/ č/s/a a modulo m roven r 6 N, /e řác/ č/s/a an modulo m roven -r^- Důkaz Protože jy^j = [r, r?], což je zřejmě násobek r, máme (a")(^) = a^ = 1 (mod m) (plyne z předchozího Důsledku, neboť r | [r, r?]). Na druhou stranu, je-li /c G N libovolné takové, že (an)k — an'k = 1 (mod m), dostáváme (r je řád a), že r n • k a dále víme, že -r-^ I • k a V J 7' ' (n,r) I (n,r) díky nesoudělnosti čísel a dostáváme k. Proto je y {n,r) (n,r) (n,r) J řádem čísla an modulo m. □ Aritmetické funkce oooooo Multiplikativní aritmetické funkce ooooo Malá Fermatova věta, Eulerova věta oooooooooooo* Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu: Lemma_J Necht m £ N, a, b £ Z b je řádu s modulo m, modulo m. , (a, m) = kde (r, s) (b, m) = 1. Jestliže a je řádu r a = 1, pak číslo a • b je řádu r • s Důkaz. i Označme S řád čísla a • b. Pak (ab)s = 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. brS = 1 (mod m), a proto s | rS. Z nesoudělnosti ras plyne s | S. Analogicky dostaneme i r | ô, a tedy (opět s využitím nesoudělnosti r, s) r • s | S. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto S | rs. Celkem tedy ô = rs. □