Řešení 1. příkladu. Řešíme kongruenci 37A5x = 686 (mod 1456), která je ekvivalentní kongruenci 833x = 686 (mod 1456). Věta o řešení lineárních kongruenci nám říká, že tato bude řešitelná právě když (833,1456) | 686. Největší společný dělitel je 7, o tom se gambleři buď mohou přesvědčit Euklidovým algoritmem nebo můžeme takto malá čísla rozložit na součin prvočísel - rozklady se budou hodit i později. 833 = 7 - 119 = 72 - 17 1456 = 7 • 208 = 7 • 13 • 16 686 = 7 • 98 Ta stejná věta říká, že modulo 1456 je těch řešení právě 7. Najděme je. Budeme řešit kongruenci (1) 119x = 98 (mod 208). Z ní pak získáme veškerá řešení původního zadání. Mohli bychom hledat inverzi 119 (mod 208) Euklidovým algoritmem a zešílet u toho. Budeme postupovat chytřeji. Hledáme y, že platí 119y = 1 (mod 208), to je ale podle čínské zbytkové věty to samé jako řešit soustavu 119y = 1 (mod 13), 119y = 1 (mod 16). Protože známe rozklady vystupujících čísel, je toto extrémně jednoduché: 119y = 7-17y = 7-Ay = 28y = 2y =1 (mod 13) Vynásobíme-li obě strany sedmičkou (inverze 2 (mod 13)) získáváme y = 7 (mod 13). Obdobně řešme druhou kongruenci: 7 • 17y = 7 • y = 1 (mod 16) =>- y = 7 (mod 16) Máme tedy 119-7= 1 (mod 208). Můžeme se vrátit k řešení samotné kongruence (1). 7- 119x = x = 7-98 = 62 (mod 208) Nyní už získáme řešení původní kongruence jako 62 + 208A; (mod 1456) pro k = 0,1,..., 6. Řešení 2. příkladu. Přepišme si dokazované tvrzení do formy kongruence: Máme ukázat, že pro libovolné přirozené n platí 111+ 22 =0 (mod 127), což je to samé jako 22 = 16 = 24 (mod 127). Nej důležitější je si všimnout, že 127+ 1 = 128 = 27, tj. 27 = 1 (mod 127)! Díky tomuto by nám stačilo zjistit, že mocnina dvojky na levé straně kongruence (22 ™ ) dává po dělení 7 zbytek 4, vskutku: 22^2n-1 = 27k+4 = (27)fc . 24 = 1* • 16 = 16 (mod 127). i 2 Potřebujeme nyní ověřit 222n^=A (mod7). Můžeme zopakovat předešlé úvahy, teď pouze v jiném kontextu. Platí 23 = 1 (7) a tedy by stačilo ukázat, že exponent dvojky v kongruenci splňuje 22n_1 =2 (3). Nyní si zase všimněme 22 = 1 (3). Můžeme zpětně řešit kongruence, které jsme zmínili: 22n-l _ (22yn . 3-! _ . 3 _ 3 (mod 3) ^ ^ = 23fc+2 = (23)fc • 22 = 4 (mod 7) Tento přístup je přirozený; v podstatě jsme v exponentech šplhali nahoru a opakovali stejnou myšlenku - vždy jsme si uvědomili řád dvojky. Kdyby nás ale toto nenapadlo, můžeme postupovat jednoduchou matematickou indukci: Že platí 22"1-1 = 4 (7) se pro n = 1 lehce ověří spočítáním na prstech. V indukci předpokládejme, že fakt platí pro n a snažme se ověřit pravdivost i pro n + 1: 222("+1)-1 = 22"+1 = 222-1+2 = 222"-1'22 = (22a-1)4 i 44 = 256 = 4 (mod 7) Řešení 3. příkladu. Srdceryvný příběh o útrapách cvičenců můžeme chladnokrevně přepsat do tvaru soustavy lineárních kongruenci. Neznámá x značí počet cvičenců. x = 5 (mod 8) x = 2 (mod 9) x = 7 (mod 14) =>- x = 0 (mod 7) 1000 < x < 1500 Poslední kongruence (neboli údaj o lidských pyramidách na sletu) nám také říká, že x = 1 (mod 2), ale že je x liché již víme z první kongruence. Na řešení takové soustavy známe nepoužitelný vzoreček; budeme proto postupovat opět ekvivalentními úpravami a nějakými ad hoc úvahami. Nicméně moduly jsou již nesoudělné, o této situaci nám čínská zbytková věta říká, že existuje jednoznačné řešení modulo 8-9-7 = 504, což nám těsně zaručuje jednoznačnost počtu cvičenců v mezích 1000 až 1500. Poslední kongruence nám říká, že x = 7k, dosaďme do prostřední, tj. 7/c = 2 (mod 9), vynásobením čtyřmi dostáváme k = 8 (mod 9), tedy k = 8 + 9/. Konečně dosaďme do prvního vztahu, dostáváme 7(8 + 9/) = 56 + 63/ = 7/ = —/ = 5 (mod 8). Dosazujme zpětně do vztahů, které jsme postupně získali: / = 3 + 8m, pak k = 8 + 9(3 + 8m) = 35 + 8 • 9m a nakonec x = 7(35 + 8 • 9m) = 245 + 7 • 8 • 9m = 245 + 504m. Do hledaného rozmezí se vejde pouze x = 245 + 504 • 2 = 1253. Na slet se slétlo 1253 cvičenců z celé naší Československé socialistické vlasti Řešení 4. příkladu. Počítejme ^(71 • 79) = (71 - 1)(79 - 1) = 3 • 4 • 5 • 7 • 13 = 5460. Z prvočíselného rozkladu vidíme, že e = 11 má modulo n inverzi d - tu má totiž právě když (e, f(n)) = 1. Toto d můžeme spočítat buď Euklidovým algoritmem nebo převodem na soustavu lineárních rovnic jako v předchozích příkladech. Oběma postupy se dostaneme 3 k číslu d = 3971, které z definice splňuje 11 • 3971 = ed = 1 + rrupn = 1 (n) Nyní nám Eulerova věta(ev) pro všechna a nesoudělná s n zaručuje, že platí (2) (ď)d = aed = a1+m^n) = a ■ (ď{n))m = a (mod n) Poznámka (Toto je diskuze nad rámec úlohy). Platí dokazovaná kongruence i pro čísla a, pro která je (a, n) > 1? Ano: Nechť je tedy a soudělné s n = pq, součinu dvou prvočísel, v našem případě je p = 71 a q = 79. (a, n) může nabývat hodnot p, q nebo n. (a,n) = n odpovídá situaci a = kn, tedy (2) platí triviálně. Nechť tedy (a, n) = p (případ pro q se dokáže stejně), to znamená a = kp a (k,n) = 1. Dosaďme do (2): (kp)ed = kedped (= kped (mod n) Připomínáme, že Eulerovu větu jsme mohli použít vzhledem k definici d. Stačí nám tedy ukázat, že ped = p (n). Všimněme si, že platí pi+k(q-i) _ 0 (mod p^ (3) = p (mod qy První kongruence je bezobsažná a druhá je jednoduché použití malé Fermatovy věty. Čínská zbytková věta nám radí, že modulo pq existuje pouze jedno číslo x, které tyto kongruence splňuje a hned se vidí, že takovým je x = p. Volbou k = p — 1 dostáváme přesně ped = p (n), protože ed = 1 + rrnp(ri) = 1 + (p — l)(q — 1) Poznamenejme ještě, že tento fakt platí i pro obecnější n - konkrétně pro libovolné square-free n. Vyzýváme čtenáře si zkusit toto dokázat. Postup bude obdobný, trochu se obmění soustava kongruencí (3), speciálně v exponentech. Řešení 5. příkladu. Pro výpočet budeme používat větu o kvadratické reciprocitě (qr), faktu že Legendrův symbol je multiplikativní funkce a také si nebudeme příliš dělat starosti, zda náhodou nepracujeme s Jacobiho symbolem - jejich kalkulus a hodnoty jsou stejné; liší se pouze interpretací výsledku. Ale o to nám nyní nejde. Počítejme: /2013\ qr /4049\ _ / 23 \ £ /2013\ _ /12\ ^4049) ~ V2Ô13y ~ V2Ôl3y ~ \~~23~) ~ \ 23J 2*2*3^ ^2^ i ^ \ / \2 (\ (^ , , , , , (±i) — 23 y V23y V23y K J \3J \3, Poslední rovnost platí, protože 2 není kvadratický zbytek modulo 3. Počítat s Legendrovým symbolem, jako by byl Jacobiho, nám ušetřilo dost práce, jinak bychom totiž museli zohledňovat fakt 2013 = 3 • 11 • 61.