2. domácí úloha z MIN401, jaro 2024
Příklad 1.
a) Číslo 67 je primitivním kořenem modulo 47, ale nikoliv modulo 472 = 2209. Jaký musí být řád 67 modulo 2209? (Asi se vám bude hodit, že řád každého prvku dělí </?(2209). Žádné mocniny není potřeba počítat explicitně.)
b) Umocněním 4847 = (1+47)47 podle binomické věty určete zbytek 4847 (mod 2209). Jaký musí být řád 48 modulo 2209?
c) Ukažte, že číslo 67 • 48 je primitivní kořen modulo 2209 tím, že nebudete potřebné mocniny počítat přímo, ale zjednodušíte je s využitím předchozích dvou bodů.
Řešení.
a) Protože v?(472) = 2 • 23 • 47 a 67 (mod 47) je primitivní kořen, dostáváme 672'47 = 672 =á 1 (mod 47) a stejně tak 6723'47 = 6723 =É 1 (mod 47), takže nemůže vyjít 1 ani modulo 472, a protože není 67 primitivní kořen modulo 472, zbývá jediná možnost 672'23 = 1 (mod 472) a řád 67 (mod 472) je nějaký dělitel 2 • 23 = 46. Ze stejného důvodu 672 ^ 1 (mod 47) a také 6723 ^ 1 (mod 47), takže ani modulo 472 a tedy řád musí vyjít 46.
b) Dostáváme
4847 = (1 + 47)47 = 1 + • 471 + {^j • 472 + • • • = 1   (mod 472),
a protože exponent 47 je prvočíslo, musí být řád 48 modulo 472 roven 47.
c) Z předchozích bodů dostáváme
(67 • 48)2'47 = 6 72'47 -1^1   (mod 472) (67 • 48)23'47 = 6 723'47 -1^1   (mod 472) (67 • 48)2'23 = 1 • 482'23 £ 1   (mod 472)
□
Příklad 2.
a) Petr zkoumal řády zbytkových tříd modulo 341 a zjistil, že řád zbytku 185 je 10. Spočtěte Jacobiho symbol (|||) a pomocí Eulerova-Jacobiho testu odhalte, že 341 není prvočíslo.
b) Toto zjištění přimělo Petra zkoušením rozložit 341 = 11-31. Dále pak Petr zkoumal řády všech zbytkových tříd nesoudělných s modulem 341. Jaký maximální řád našel? Najděte nějaký zbytek tohoto maximálního řádu. (Mohlo by se vám hodit, že 21 je primitivním kořenem modulo 31.)
Řešení.
i
a) Standardním způsobem spočítáme
(1S5\ _   , /341\ _ ^ 156^ _ (JL\2 = _i_   185\ _ /29\
V 341/      """VISĎ/       V 185/       V 185/   ' \ 185 / V 39 /       V 39/
-1 (-1)2
Protože je řád 185 modulo 341 roven 10, dostáváme
185^ = 185170 = 1 ž (iff)   (mod 341). b) Je-li x (mod 341) nesoudělné s modulem, pak
x10 = 1   (mod 11) x30 = 1   (mod 31)
takže dohromady x30 = 1 (mod 341). Zároveň, protože 21 je primitivní kořen modulo 31, má řád 30 modulo 31, tím spíš modulo 341 a tedy 21 mám maximální možný řád 30.
□