23
ř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 podle 13
n = (25+6)18-l = 3818-1 = 318-1 = 276-l = (-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 = l9 - 1 = 0    (mod 16), proto 16 | n. Celkem tedy 112 | n, což jsme měli dokázat. □
příklad. Dokažte, že pro libovolné prvočíslo p a libovolná a, b g z platí
ď + bp = (a + b)p   (mod p).
Řešení. Podle binomické věty platí
(a + bf = ď+ Qď^b + Qap~2b2 + ■■■+ (/Jay-1 + V.
Podle příkladu za větou 6 pro libovolné k g {1,... ,p — 1} platí (^) = 0 (mod p), odkud plyne tvrzení. □
Následující tvrzení je další užitečnou vlastností kongruencí:
Lemma. Dokažte, že pro libovolné přirozené číslo m a libovolná a, b g z taková, že a = b (mod mn), káe n g N, platí, že am = bm (mod mn+1).
DŮKAZ. Platí
am - bm = (a - b)(a"1"1 + am-2b + ■■■ + aW1'2 + 6m_1) (12)
a protože m \ mn, tak podle 13 (7) platí i a = b (mod m). Jsou tedy všechny sčítance ve druhé závorce v (12) kongruentní s am_1 modulo m, a tedy
am-l + am-2h + . . . + abm-2 + &m-l _ m . flm-l _ g      (mod m^
proto je am~1+am~2 + - ■ ■+abm~2+bm~1 dělitelné m. Z a = b (mod mn) plyne, že mn dělí a — b, a tedy mn+1 dělí jejich součin, což vzhledem k (12) vede k závěru, že am = bm (mod mn+1). □
3.2. 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 0, pokud pro některé i platí olí > 1 a rovnu (—\)k v opačném případě. Dále definujeme
Mi) = i-
příklad. /x(4) = /x(22) = 0,M6) = M2-3) = (-i^M2) = A*(3) =
-1.
24
Dokážeme nyní několik důležitých vlastností Môbiovy funkce, zejména tzv. Môbiovu inverzní formulí.
Lemma. Pro n e n \ {1} platí
d\n
DŮKAZ. Zapíšeme-li n ve tvaru n = p"1 ■ ■ -p^.k, pak všechny dělitele d čísla n jsou tvaru d = pf1 •••pffe, kde 0 < < pro všechna i e {1,... ,k}. Proto
$>(<*) = £        ^■■■Pih) =
d\n (/3i,...,/3fe)e(NU{0})fe 0<ft<«í
(/31,...,/3fe)e{0,l}fe
= (S) + (í) • (-i) + G) - (-i)2 + +
= (i + (-i))fc = o.
□
S Môbiovou funkcí úzce souvisí pojem Díríchletův součin:
Definice. Buďte f,g aritmetické funkce. Jejich Dirichletův součin je definován předpisem
(fog)(n) = yJf(d)-g^)= f(di)-g(d2).
d\n did,2=n
Lemma. Dirichletův součin je asociativní. DŮKAZ.
((fog)oh)(n)= f(di)-g(d2)-h(d3) = (fo(goh))(n)
d\d2dz=n
□
příklad. Definujme dvě pomocné funkce I a J předpisem 1(1) = 1, l(n) = 0 pro všechna n > 1, resp. I(n) = 1 pro všechna n g n. Pak pro každou aritmetickou funkci / platí:
/oI = Io/ = /
a
(/o/)(«) = (/o/)(n) = £/(d).
d\n
25
Dále platí Joyu = /ioJ = I) neboť
(J o ^)(n) = £ /(d)M3) = E J(Í)^(d) =
íí|n íí|n
=      /i(cř) = 0   pro všechna n > 1
íí|n
podle lemmatu za definicí Môbiovy funkce (pro n = 1 je tvrzení zřejmé).
věta 14. (Môbiova inverzní formule) Nechť je aritmetická funkce F definovaná pomocí aritmetické funkce f předpisem F(n) = X^|n /(c0-PaA: lze funkci f vyjádřit ve tvaru
/(n) = $>(3)-*W
íí|n
DŮKAZ. Vztah F(n) = Y2d\n /(^) ^ze Jmým způsobem zapsat jako F = f o L Proto F o jjl = (/ o /) o /j = / o (/ o |i) = f ol = f\ což je tvrzení věty. □
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) = <j(n), f(n) = r(n), či f(n) = ^{n) nebo, jak brzy dokážeme i tzv. Eulerova funkce f(n) = <p(n).
3.3. Eulerova funkce ip.
Definice. Nechť n g N. Definujme Eulerovu funkci ip předpisem ip(n) = \{a g N I 0 < a < n, (a, n) = 1}\
příklad. 99(1) = l,</?(5) = 4,(^(6) = 2, je-li p prvočíslo, je zřejmě (p(p) =p-l.
Nyní dokážeme několik důležitých tvrzení o funkci ip: Lemma. Nechť n g n. Pak Y,d\n iP(d) = n.
DŮKAZ. Uvažme n zlomků
12 3        n - 1 n
j   j   j • • • j j •
n n n n n
Zkrátíme-li zlomky na základní tvar a seskupíme podle jmenovatelů, snadno dostaneme právě uvedené tvrzení. □
věta 15. Nechť nGN, jehož rozklad je tvaru n = p"1 ■ ■ -p^.k ■ Pak ,(„) = „. (j-I)... (j-JL).
26
DŮKAZ. S využitím předchozího lemmatu a Môbiovy inverzní formule dostáváme
<p(n) = V Md)^ = n~------- + ••• + (-1)*—^ =
=n.fi-iv..fi-r
V     Pi/      V Pfc,
□
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. Nechi a, b G N, (a, b) = 1. Pak
ip(a • b) = p (a) • <p(b).
DŮKAZ. Zřejmý. □
POZNÁMKA. Rovněž toto tvrzení lze odvodit nezávisle na základě poznatku (n,ab) = 1 -<=>- (n,a) = 1 A (n, b) = 1. Spolu se snadno odvoditelným výsledkem
V(pa)=pa-Pa-I = (p-1)-Pa-1 (14) pak lze odvodit vztah (13) již třetím způsobem.
PŘÍKLAD. Vypočtěte y?(72).
ŘEŠENÍ. 72 = 23 • 32 =>• y?(72) = 72 • (1 - \) ■ (1 - \) = 24, alternativně (p(72) = (p(8) ■ (p(9) = 4 • 6 = 24. □
PŘÍKLAD. Dokažte, že Vn G N : ip(4n + 2) = <p(2n + 1).
ŘEŠENÍ. v?(4n + 2) = v?(2 • (2n + 1)) = ip{2) ■ <f{2n + 1) = v?(2n + 1). □
3.4. Malá Fermatova věta, Eulerova věta. Tvrzení v tomto odstavci patří mezi nej důležitější výsledky teorie čísel.
VĚTA 16 (Fermatova, Malá Fermatova). Nechť a £ Z, p prvočíslo, p\ a. Pak
aT1 = 1   (modp). (15)
DŮKAZ. Tvrzení vyplyne jako snadný důsledek Eulerovy věty 17.
□
DŮSLEDEK. Nechť a e Z, p prvočíslo. Pak
ď = a   (mod p).
DŮKAZ. Pokud p | a, pak jsou obě strany kongruentní s 0 mod p, jinak tvrzení snadno plyne vynásobením obou stran kongruence (15) číslem a. □
27
Definice. Upíná 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á (^(m)-tice čísel nesoudělných s m a po dvou nekongruentních modulo m.
poznámka. Snadno lze vidět, že jsou-li a, b g z, a = b (mod m), a (a, m) = 1, pak i (b,m) = 1.
Lemma. Nechi x\, x2,..., xv{rn) tvoří redukovanou soustavu zbytků modulo m. Je-li a £ Z, (a, m) = 1 pak i čísla tvoří redukovanou soustavu zbytků modulo m.
důkaz. Protože (a,m) = 1 a (xi,m) = 1, platí (a • Xi,m) = 1. Kdyby pro nějaká i, j platilo (mod m), po vydělení
obou stran kongruence číslem a nesoudělným s m dostaneme Xi = x j (mod m). □
věta 17 (Eulerova). Nechi a g z, m g n, {a,m) = 1. Pak
ď(m) = 1   (mod m). (16)
důkaz. Buď x\, X2, ■ ■ ■, xv(rn) libovolná redukovaná soustava zbytků modulo m. Podle předchozího lemmatu je i a ■ x\,..., a ■ x^^ redukovaná soustava zbytků modulo m. Platí tedy, že pro každé i existuje j (oba indexy jsou z množiny {1,2,..., íp(m)}) tak, že a ■ Xi = Xj (mod m). Vynásobením čísel obou redukovaných soustav zbytků dostáváme
(a ■ xi) ■ (a ■ x2) ■ ■ ■ (a ■ x^m)) = xx-x2--- x^m)   (mod m). Po úpravě
av{™) .Xl.X2... x^m) = Xľ ■ X2 ■ ■ ■ X^m)     (moď m)
a protože (x\ ■ x2 ■ ■ ■ ^(m), m) = 1, můžeme obě strany kongruence vydělit číslem X\ ■ x2 ■ ■ ■ x^m^ a dostaneme ríf^ = 1 (mod m). □
poznámka. Eulerova věta je rovněž důsledkem Lagrangeovy věty uplatněným na grupu (z^, •).
přiklad. Nalezněte všechna prvočísla p, pro která 5P +1 = 0 (mod p2).
řešení. Snadno se přesvědčíme, že p = 5 úloze nevyhovuje. Pro p ý 5 platí (p, 5) = 1, a tedy podle Fermatovy věty 5P_1 = 1 (mod p). Umocněním na p + 1 dostaneme 5P _1 = 1 (mod p), odkud 5P = 5 (mod p). Z podmínky 5P +1 = 0 (mod p2) plyne 5P = — 1 (mod p), celkem tedy 5 = —1 (modp), a proto p | 6. Je tedy buď p = 2, nebo p = 3. Pro p = 2 však 54 + l = l4+ 1 = 2^0 (mod 4). Pro p = 3 dostáváme 59 + 1 = 56 • 53 + 1 = 53 + 1 = 126 = 0 (mod 9), kde jsme užili důsledek Eulerovy věty 56 = 1 (mod 9). Jediným prvočíslem, vyhovujícím úloze je tedy p = 3. □
28
příklad. Pro liché číslo m > 1 nalezněte zbytek po dělení čísla
2íp(m)-l číslem m>
řešení. Z Eulerovy věty plyne 2^m) = 1 = 1 + m = 2r (mod m)), kde r = je přirozené číslo, 0 < r < m. Podle 13 (3) platí 2^m)~1 = r (mod m), a tedy hledaný zbytek po dělení je r = ^4^. □
tvrzení 3.1. Je-li p prvočíslo, p = 3 (mod 4), paA; pro libovolná celá čísla a, b z kongruence a2 + b2 = 0 (mod p) plyne a = b = 0 (mod p).
DŮKAZ. Předpokládejme, že pro a, 6 G z platí a2 + o2 = 0 (mod p). Jestliže p | a, platí a = 0 (mod p), proto o2 = 0 (mod p), tedy p | 62, odkud vzhledem k tomu, že p je prvočíslo, dostáváme p | 6, a proto a = b = 0 (mod p), což jsme chtěli dokázat.
Zbývá prošetřit případ, kdy a není dělitelné prvočíslem p. Odtud dostáváme, že p nedělí ani 6 (kdyby p | 6, dostali bychom p | a2). Vynásobíme-li obě strany kongruence a2 = —b2 (mod p) číslem 6P_3, dostaneme podle Fermatovy věty
a2r3 = -Ď^1 = -1 (modp).
Protože p = 3 (mod 4), je p — 3 sudé číslo, a proto      G No- Označme
c = ab^~.
Pak c není dělitelné p a platí c2 = a2bp^3 = — 1 (mod p). Umocníme-li poslední kongruenci na       G N, dostaneme
ď-1 = (—l)^ (modp).
Protože p = 3 (mod 4), existuje celé číslo t tak, že p = 3+4ŕ. Pak ovšem ^ = 1 + 2r, což je číslo liché a proto (-l)^-1)/2 = -1. Podle Fermatovy věty naopak platí cp_1 = 1 (mod p), odkud 1 = — 1 (mod p) a p | 2, spor. □
S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řáá čísla moáulo m - jde přitom pouze o jinak nazvaný řád prvku v grupě invertibilních zbytkových tříd modulo m:
Definice. Nechť a £ Z, m £ N (a, m) = 1. Rááem čísla a moáulo m rozumíme nej menší přirozené číslo n splňující
aa = 1   (mod m).
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 ip(m). Jak později uvidíme, velmi důležitá jsou právě ta čísla, jejichž řád je roven právě ip(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 kongruenci (viz 4.5). Tento pojem je přitom jen jiným názvem pro generátor grupy
(Z£,-)-