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 < nk. 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 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, (7cc/e r,s G NJ, pak řád čísla ar modulo m je roven s. Důkaz. Protože žádné z čísel a, a , a ,..., ar 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 oooooooooo«oo 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 řád čísla a modulo m. O Pro libovolné n G N U {0} platí an = 1 (mod m) <^=^> r r?. 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, /?]). 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 rádu r a = 1, pak číslo a • b je rá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. □