TEORIE ČÍSEL sbírka příkladů. Diplomová práce

Masarykova univerzita

Přírodovědecká fakulta

TEORIE ČÍSEL sbírka příkladů Diplomová práce

Brno 2006

Jiří Růžička

Prohlašuji, že jsem tuto diplomovou práci vypracoval samostatně a použil přitom pouze uvedené literatury. V Brně 8. května 2006

..................

Děkuji vedoucímu diplomové práce Mgr. Michalu Bulantovi, Ph.D. za cenné připomínky, poskytnutou odbornou literaturu a čas, který věnoval konzultacím.

Obsah Úvod 1 Základní pojmy 1.1 Dělitelnost . . . . . . . . . 1.2 Zajímavé úlohy . . . . . . 1.3 Společný dělitel a násobek 1.4 Úlohy a cvičení . . . . . . 1.5 Příklady na procvičení . . 1.6 Nesoudělná čísla . . . . . . 1.7 Zajímavé úlohy . . . . . .

6 . . . . . . .

7 7 8 8 11 11 13 13

2 Prvočísla a čísla složená 2.1 Příklady na procvičení . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Zajímavé úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16 16 17

3 Kongruence 3.1 Základní vlastnosti kongruencí 3.2 Úlohy a cvičení . . . . . . . . 3.3 Příklady na procvičení . . . . 3.4 Zajímavé úlohy . . . . . . . . 3.5 Eulerova funkce ϕ . . . . . . . 3.6 Příklady na procvičení . . . . 3.7 Eulerova a Fermatova věta . . 3.8 Příklady na procvičení . . . . 3.9 Zajímavé úlohy . . . . . . . .

. . . . . . . . .

19 19 24 24 25 26 27 28 29 31

. . . . . .

33 33 40 41 42 46 47

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . . . .

4 Kongruence o jedné neznámé 4.1 Lineární kongruence o jedné neznámé 4.2 Úlohy a cvičení . . . . . . . . . . . . 4.3 Příklady na procvičení . . . . . . . . 4.4 Soustavy lineárních kongruencí . . . 4.5 Úlohy a cvičení . . . . . . . . . . . . 4.6 Příklady na procvičení . . . . . . . . 4

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . .

OBSAH

4.7 4.8 4.9 4.10 4.11 4.12 4.13

Kongruence vyšších stupňů Úlohy a cvičení . . . . . . Příklady na procvičení . . Primitivní kořeny . . . . . Binomické kongruence . . Úlohy a cvičení . . . . . . Příklady na procvičení . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

52 55 56 58 62 65 65

5 E-learning

67

Seznam použité literatury

69

5

Úvod Studium teorie čísel bylo oblíbené již v antickém Řecku. K novému oživení došlo v Evropě v šestnáctém a sedmnáctém století převážně zásluhou matematika Fermata. V devatenáctém století přinesli zásadní příspěvky matematici Euler a Lagrange. Knihy Legendreho (1798) a Gausse přinesly společně první systematické teorie. Dá se říci, že Gaussova Disquisitiones Arithmeticae (1801) odstartovala začátek moderní teorie čísel. Gauss rovněž zavedl pojem kongruence a symbol a ≡ b (mod c). Do teorie čísel velkou měrou přispělo i mnoho dalších významných matematiků jako jsou Cauchy, Dirichlet nebo Jacobi. Teorie čísel se zabývá řešením problémů v oboru přirozených a celých čísel. V mnoha úlohách nás totiž jiné než celočíselné výsledky nezajímají. Například počet lidí zřejmě nebude nikdo vyjadřovat číslem reálným. V tomto směru je tedy takovéto počítání jednodušší než například práce s komplexními čísly. Jednoduchých je i mnoho základních pojmů, neboť s výrazy jako prvočíslo, nesoudělná čísla, dělitelnost nebo společný dělitel se jistě již každý setkal na střední škole. Na první pohled to tedy vypadá, že se nemůžeme setkat s žádnými většími problémy. Je to však jen zdání. I v teorii čísel je mnoho problémů, které se dají snadno formulovat, avšak jejichž řešení není triviální nebo se jej dokonce nepodařilo doposud nalézt. Mezi nejznámější problémy z teorie čísel patří problém prvočíselných dvojčat, Goldbachova hypotéza a velká Fermatova věta. Tato diplomová práce je sbírkou úloh a má čtenářům pomoci při studiu úvodu do teorie čísel. V začátku každé kapitoly jsou zopakovány nejdůležitější definice a věty, bez kterých se při řešení daných úloh neobejdete. Avšak těchto několik definic nemůže nahradit patřičnou literaturu z přednášek. Nenajdete zde ani žádné důkazy vět. Ty opět hledejte v doporučené literatuře. Většina kapitol začíná návodem na řešení jednoduchých úloh z dané oblasti. Následují příklady k samostatnému řešení, které mají studentům pomoci s procvičením základních výpočetních technik na jednoduchých příkladech. Příklady označené jako ”Na procvičení” by měl zvládnout každý student vypracovat samostatně. Podobná zadání se mnohdy objevují na zkouškových písemkách a často předpokládají zažitou znalost předchozích témat. Poslední skupinou jsou příklady ”Zajímavé”, jejichž pochopení by mělo každému pomoci k úspěšnému zvládnutí úvodu teorie čísel.

6

Kapitola 1 Základní pojmy Dříve než se podíváme na zajímavé úlohy z teorie čísel, zopakujme si pojmy, které jsou nezbytné pro studium teoie čísel.

1.1

Dělitelnost

Definice 1.1. Řekneme, že celé číslo a dělí celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a · c = b. Píšeme pak a | b. I bez důkazů je jistě všem čtenářům zřejmé, že platí několik následujících tvrzení: a | b ∧ b | c ⇒ a | c, a | b ∧ a | c ⇒ a | b + c ∧ a | b − c, c 6= 0 ⇒ (a | b ⇔ ac | bc), a | b ∧ b > 0 ⇒ a ≤ b.

Věta 1.1 (O dělení celých čísel se zbytkem). Pro libovolná čísla a ∈ Z, m ∈ N existují jednoznačně určená čísla q ∈ Z, r ∈ {0, 1, . . . , m − 1} tak, že a = qm + r.

Věta 1.2. Pro přirozená čísla a, b platí a|b

⇐⇒

2a − 1 | 2b − 1.

7

1. Základní pojmy

1.2

Zajímavé úlohy

Zajímavé úlohy

Příklad 1.1 Najděte všechna celá čísla x 6= 3, pro která x − 3 | x3 − 3. Řešení Označme x − 3 = t. Tedy t má být celé nenulové číslo takové, aby pro něj platilo t | (t + 3)3 − 3. Protože t dělí každý člen výrazu, který je násobkem t, můžeme výraz zjednodušit vypuštěním těchto členů. Má tedy platit t | 33 − 3, neboli t | 24. To platí, právě když t je dělitelem čísla 24. A to opět platí, právě když t je rovno některému z čísel ±1, ±2, ±3, ±4, ±6, ±8, ±12, ±24. Pro x = t + 3 dostáváme, že x může nabývat hodnot -21, -9, -5, -3, -1, 0, 1, 2, 4, 5, 6, 7, 9, 11, 15, 27. ◦ Příklad 1.2 Najděte všechna kladná celá čísla n taková, pro něž platí, že číslo n2 +1 je dělitelné číslem n + 1. Řešení Upravme si výraz n2 + 1 : n2 + 1 = n(n + 1) − (n − 1). Pokud má platit, že n + 1 | n2 + 1, musí také platit, že n + 1 | n − 1. V oboru přirozených čísel však může větší číslo dělit menší jen tehdy, pokud je tím menším číslem 0. Musí tedy být n − 1 = 0. Výledkem je tedy jediné číslo, a to n = 1.

1.3

◦

Společný dělitel a násobek

Definice 1.2. Mějme celá čísla a1 , a2 . Libovolné celé číslo m takové, že m | a1 , m | a2 (resp. a1 | m, a2 | m) se nazývá společný dělitel (resp. společný násobek) čísel a1 , a2 . Společný dělitel (resp. násobek) m ≥ 0 čísel a1 , a2 , který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel a1 , a2 , se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel a1 , a2 a značí se (a1 , a2 ) (resp. [a1 , a2 ]). S největším (resp. nejmenším) společným dělitelem (resp. násobkem) se jistě již každý z vás někdy setkal. 8

1. Základní pojmy


Způsobů na výpočet společného dělitele je několik, podíváme se nyní na ten nejznámější, tzv. Euklidův algoritmus. Věta 1.3 (Euklidův algoritmus). Nechť a1 , a2 jsou přirozená čísla. Pro každé n ≥ 3, pro které an−1 6= 0, označme an zbytek po dělení čísla an−2 číslem an−1 . Pak po konečném počtu kroků dostaneme ak = 0 a platí ak−1 = (a1 , a2 ). Výpočet největšího společného dělitele tedy spočívá v tom, že neustále dělíme dělitele zbytkem po předchozím dělení. Ve chvíli, kdy nám vyjde zbytek nulový, podíváme se na zbytek v dělení předchozím, a to je právě náš hledaný největší společný dělitel. Ukažme si výpočet na konkrétních příkladech. Příklad 1.3 Najděte největšího společného dělitele čísel 133 a 171. Řešení Vydělme číslo 171 číslem 133 171 = 1 · 133 + 38. Nyní vydělíme dělitele (133) zbytkem po dělení (38) 133 = 3 · 38 + 19, opět pokračujeme v dělení 38 = 2 · 19 + 0. Protože jsme nyní dělili beze zbytku, je největším společným dělitelem předchozí nenulový zbytek. Největším společným dělitelem čísel 133 a 171 je tedy číslo 19.

◦

Příklad 1.4 Nalezněte největšího společného dělitele čísel 240 − 1 a 228 − 1. Řešení Stejně jako v předchozím příkladu začneme dělením čísla většího číslem menším: 240 − 1 = 212 (228 − 1) + (212 − 1). Zbytek je nenulový, dělíme dále 228 − 1 = (216 + 24 )(212 − 1) + (24 − 1), 212 − 1 = (28 + 24 + 1)(24 − 1). 9

1. Základní pojmy


Z výpočtů je vidět, že největší společný dělitel čísel 240 − 1 a 228 − 1 je číslo 24 − 1 = 15. ◦ O největším společném děliteli dvou čísel hovoří následující věta. Věta 1.4 (Bezoutova). Pro libovolná celá čísla a1 , a2 existuje jejich největší společný dělitel (a1 , a2 ), přitom existují celá čísla k1 , k2 tak, že (a1 , a2 ) = k1 a1 + k2 a2 . Vztah mezi největším společným dělitelem a nejmenším společným násobkem charakterizuje následující tvrzení. Věta 1.5. Pro libovolná celá čísla a1 , a2 existuje jejich nejmenší společný násobek [a1 , a2 ] a platí (a1 , a2 ) · [a1 , a2 ] = |a1 · a2 |. Dělitelé a násobky více čísel se definují analogicky. My je však zde uvádět nebudeme, čtenář se o nich dozví více v příslušné literatuře. Výpočet koeficientů v Bezoutově rovnosti je poměrně snadný. Pro malá čísla se dají mnohdy psát z hlavy. Pro čísla větší nejprve spočítáme největšího společného dělitele pomocí Euklidova algoritmu. Poté celý princip výpočtu spočívá ve zpětném dosazování tak, abychom číslo menší (zbytek) vyjádřili pomocí dvou čísel větších (dělitel a dělenec). Ukažme si to na následujícím příkladu. Příklad 1.5 Nalezněte koeficienty v Bezoutově rovnosti pro čísla 308 a 245. Řešení Nejprve spočítáme pomocí Euklidova algoritmu největšího společného dělitele: 308 = 1 · 245 + 63, 245 = 3 · 63 + 56, 63 = 1 · 56 + 7, 56 = 8 · 7. Největším společným dělitelem je (308, 245) = 7. Koeficienty v Bezoutově rovnosti nalezneme pomocí zpětného dosazování Z předposledního řádku výpočtu NSD dostáváme 7 = 63 − 1 · 56. 10

1. Základní pojmy

Úlohy a cvičení

Protože platí 56 = 245 − 3 · 63, můžeme psát 7 = 63 − (245 − 3 · 63) = 4 · 63 − 245. Víme také, že platí 63 = 308 − 245, dostáváme proto 7 = 4(308 − 245) − 245 = 4 · 308 − 5 · 245. Bezoutovu rovnost nyní můžeme psát jako (308, 245) = 4 · 308 − 5 · 245.

1.4

◦

Úlohy a cvičení

1. Nalezněte největšího společného dělitele a koeficienty v Bezoutově rovnosti pro čísla: (a) (b) (c) (d)

1234 a 4321 650 a 702 345 − 1 a 365 − 1 377 − 1 a 321 − 1. [ [ [ [

1.5

(a) (b) (c) (d)

1 = 309 · 4321 − 1082 · 1234 ] 26 = 13 · 650 − 12 · 702 ] 242 = (1 + 325 + 345 ) · (345 − 1) − (325 + 35 ) · (365 − 1) ] 2186 = (321 − 1) · (1 + 321 + 342 + 363 ) − 37 · (377 − 1) ]

Příklady na procvičení

Příklad 1.6 Nalezněte koeficienty v Bezoutově rovnosti pro největšího společného dělitele čísel 123 a 321. Řešení Spočítejme nejprve největšího společného dělitele pomocí Euklidova algoritmu. 321 = 2 · 123 + 75, 123 = 75 + 48, 75 = 48 + 27, 48 = 27 + 21, 27 = 21 + 6, 21 = 3 · 6 + 3, 6 = 2 · 3. 11

1. Základní pojmy


Největší společný dělitel čísel 123 a 321 je tedy 3. Dosazujme nyní zpětně do rovnosti 3 = 21 − 3 · 6, 3 = 21 − 3(27 − 21), 3 = 4 · 21 − 3 · 27, 3 = 4(48 − 27) − 3 · 27, 3 = 4 · 48 − 7 · 27, 3 = 4 · 48 − 7(75 − 48), 3 = 11 · 48 − 7 · 75, 3 = 11(123 − 75) − 7 · 75, 3 = 11 · 123 − 18 · 75, 3 = 11 · 123 − 18(321 − 2 · 123), 3 = 47 · 123 − 18 · 321. Koeficienty Bezoutovy rovnosti pro čísla 123 a 321 jsou čísla 47 a -18.

◦

Příklad 1.7 Nalezněte koeficienty v Bezoutově rovnosti pro největšího společného dělitele čísel 527 a 713. Řešení Napřed spočítáme největšího společného dělitele. 713 = 527 + 186, 527 = 2 · 186 + 155, 186 = 155 + 31, 155 = 5 · 31. Největším společným dělitelem je číslo 31. Nyní budeme hledat koeficienty v Bezoutově rovnosti. 31 = 186 − 155, 31 = 186 − (527 − 2 · 186) = 3 · 186 − 527, 31 = 3(713 − 527) − 527 = 3 · 713 − 4 · 527. Bezoutovu rovnost můžeme psát jako (527, 713) = 3 · 713 − 4 · 527.

◦

Příklad 1.8 Nalezněte koeficienty v Bezoutově rovnosti pro největšího společného dělitele čísel 291 − 1 a 235 − 1. 12

1. Základní pojmy

Nesoudělná čísla

Řešení Spočítejme NSD: 291 − 1 = (256 + 221 )(235 − 1) + (221 − 1), 235 − 1 = (214 )(221 − 1) + (214 − 1), 221 − 1 = (27 )(214 − 1) + (27 − 1), 214 − 1 = (27 + 1)(27 − 1). Největším společným dělitelem je číslo 127. To můžeme psát jako 127 = (221 − 1) − 27 · (214 − 1), 127 = (221 − 1) − 27 · (235 − 1) − 214 · (221 − 1) , 127 = (221 − 1)(221 + 1) − 27 · (235 − 1), 127 = (291 − 1) − (256 + 221 )(235 − 1) (221 + 1) − 27 · (235 − 1), 127 = (221 + 1)(291 − 1) + (235 − 1) −27 − (256 + 221 )(221 + 1) , 127 = (221 + 1)(291 − 1) + (235 − 1)(−27 − 277 − 256 − 242 − 221 ). Největším společným dělitelem čísel 291 − 1 a 235 − 1 je číslo 127. Bezoutovu rovnost můžeme psát jako (291 − 1, 235 − 1) = (221 + 1)(291 − 1) − (27 + 277 + 256 + 242 + 221 )(235 − 1). ◦

1.6

Nesoudělná čísla

Co to jsou soudělná a nesoudělná čísla, ví každý čtenář již ze střední školy. Avšak zopakujme zde definice těchto pojmů. Definice 1.3. Čísla a1 , a2 , . . . , an ∈ Z se nazývají nesoudělná, jestliže platí (a1 , a2 , . . . , an ) = 1. Čísla a1 , a2 , . . . , an ∈ Z se nazývají po dvou nesoudělná, jestliže pro každé i, j takové, že 1 ≤ i < j ≤ n, platí (ai , aj ) = 1.

1.7

Zajímavé úlohy

Následující úloha pochází ze zadání matematické olympiády pro střední školy. Zkusme ji nyní bez nějakých dalších vědomostí vyřešit. 13

1. Základní pojmy

Zajímavé úlohy

Příklad 1.9 Dokažte, že pro všechna přirozená m platí, že výraz m6 − m2 je dělitelný číslem 60. Řešení Protože platí 60 = 3 · 4 · 5 a zároveň jsou čísla 3, 4 a 5 po dvou nesoudělná, stačí dokázat, že daný výraz je dělitelný každým z těchto čísel. Nejprve dokážeme, že m6 − m2 je násobkem čísla 3. Číslo m může dávat po dělení třemi pouze některý z těchto zbytků: 0, 1, 2. Podívejme se, jaké dostaneme zbytky, pokud toto číslo umocníme na šestou nebo druhou a jaký zbytek dostaneme, pokud od sebe mocniny odečteme. Tyto zbytky nám ukazuje následující tabulka. Obsahuje vždy jen zbytky po dělení příslušného výrazu číslem 3. 0 0 0 0

m m2 m6 m6 − m2

1 1 1 0

2 1 1 0

Z tabulky přímo vidíme, že pro kterékoliv přirozené číslo (číslo s libovolným zbytkem) je daný výraz dělitelný třemi. Vytvořme stejnou tabulku pro dělení čtyřmi. Zbytky, které můžeme dostat, jsou 0, 1, 2 a 3. 0 0 0 0

m m2 m6 m6 − m2

1 1 1 0

2 0 0 0

3 1 1 0

Nyní vidíme, že výraz je pro všechna m dělitelný i číslem 4. Podívejme se ješte, jak to vypadá pro dělení pěti. m m2 m6 m6 − m2

0 0 0 0

1 1 1 0

2 4 4 0

3 4 4 0

4 1 1 0

Výraz je tedy dělitelný i číslem 5. Dostali jsme tak, že daný výraz je dělitelný čísly 3, 4 i 5. Protože jsou tato čísla navzájem nesoudělná, je výraz dělitelný i číslem 3 · 4 · 5 = 60. ◦ Příklad 1.10 Dokažte, že pokud jsou a a b různá celá čísla, potom existuje nekonečně mnoho kladných celých čísel n takových, že a + n a b + n jsou čísla nesoudělná.

14

1. Základní pojmy

Zajímavé úlohy

Řešení Nechť a a b jsou dvě různá celá čísla. Bez újmy na obecnosti můžeme předpokládat, že a < b. Nechť n = (b − a)k + 1 − a. Pro k dostatečně velké bude n kladné celé číslo. Dostáváme a + n = (b − a)k + 1, b + n = (b − a)(k + 1) + 1, kde a + n a b + n jsou celá kladná čísla. Jestliže pro nějaké číslo d platí d | a + n a d | b + n, musí také platit d | b − a. Protože d | a + n = (b − a)k + 1 a zároveň d | b − a, musí také platit d | 1. Odtud dostáváme, že d = 1. Čísla a + n a b + n jsou proto nesoudělná. ◦

15

Kapitola 2 Prvočísla a čísla složená Definice 2.1. Pokud má číslo n ≥ 2 pouze triviální kladné dělitele (tedy číslo 1 a n), nazývá se prvočíslo. Pokud má i netrivální dělitele (tedy i nějaké další), nazývá se složené číslo.

Věta 2.1. Přirozené číslo p ≥ 2 je prvočíslo, právě když platí: pro každá celá čísla a, b z p | ab plyne p | a nebo p | b.

Věta 2.2. Libovolné přirozené číslo n ≥ 2 je možné vyjádřit jako součin prvočísel, přičem je toto vyjádření jediné, nebereme-li v úvahu pořadí činitelů.

2.1


Příklad 2.1 Dokažte nebo vyvraťte tvrzení: ”Pro každé prvočíslo p 6= 5 platí, že alespoň jedno z čísel p2 + 4, p2 + 6 není prvočíslo.” Řešení Předpokládejme, že p 6= 5 je prvočíslo. Pokud číslo p dělíme číslem 5, dává zbytek 1, 2, 3 nebo 4. Podívejme se tedy, jaké zbytky dávají po dělení pěti čísla p2 + 4 a p2 + 6. To nám ukazuje následující tabulka.

16

2. Prvočísla a čísla složená

p p2 p2 + 4 p2 + 6

Zajímavé úlohy

1 1 0 2

2 4 4 0

3 4 4 0

4 1 0 2

Z posledních dvou řádků je jasně vidět, že je číslem 5 dělitelný vždy právě jeden z výrazů p2 + 4 nebo p2 + 6. Navíc je každý z těchto výrazů větší než 5 a nemůže tak být prvočíslem. Tím jsme dokázali platnost tvrzení. ◦

2.2

Zajímavé úlohy

Příklad 2.2 Najděte všechna prvočísla, která můžeme vyjádřit zároveň jako součet i rozdíl dvou jiných prvočísel. Řešení Nechť r je takové prvočíslo, které můžeme napsat jako součet i rozdíl dvou jiných prvočísel. Potom je jistě r > 2 a je lichým prvočíslem. Protože součet i rozdíl prvočísel má být opět prvočíslo (liché číslo), musí být jedno z těchto prvočísel sudé, tedy rovno dvěma. Dostáváme tak r = p + 2 = q − 2, kde r, p, q jsou prvočísla. Hledáme proto tři za sebou jdoucí prvočísla. Těmi jsou pouze čísla 3, 5 a 7. Dostáváme tak, že jedině prvočíslo 5 můžeme napsat jako součet i rozdíl jiných dvou prvočísel (5 = 2 + 3 = 7 − 2). ◦ Příklad 2.3 Najděte všechna prvočíselná řešení p, q, r rovnice p(p + 1) + q(q + 1) = r(r + 1). Řešení Rovnice má jediné řešení, a to p = q = 2, r = 3. Ukažme si proč. Najděme nejprve všechna řešení rovnice p(p + 1) + q(q + 1) = n(n + 1), kde p, q jsou prvočísla a n je kladné celé číslo. Naši rovnici můžeme přepsat do tvaru p(p + 1) = n(n + 1) − q(q + 1) = (n − q)(n + q + 1), zároveň musí být n > q. Protože p je prvočíslo, musí platit p | n−q nebo p | n+q+1. Jestliže p | n − q, potom p ≤ n − q, z čehož plyne p(p + 1) ≤ (n − q)(n − q + 1) a tedy n + q + 1 ≤ n − q + 1. To je ovšem nemožné. Proto musí platit, že p | n + q + 1, což znamená, že pro nějaké kladné celé k rovněž platí n + q + 1 = kp, což implikuje p + 1 = k(n − q).

17

2. Prvočísla a čísla složená

Zajímavé úlohy

Pokud je k = 1, potom n + q + 1 = p a p + 1 = n − q, dostáváme tak p − q = n + 1 a zároveň p+q = n+1. To je ovšem nemožné. Proto musí být k > 1. Z předchozího můžeme psát 2q = (n + q) − (n − q) = kp − 1 − (n − q) = = k · [k(n − q) − 1] − 1 − (n − q) = (k + 1) [(k − 1)(n − q) − 1] . Protože k ≥ 2, je k + 1 ≥ 3. Výraz 2q je dělitelný pouze čísly 1, 2, q, 2q. Musí proto být k + 1 = q nebo k + 1 = 2q. Jestliže je k + 1 = q, potom je (k − 1)(n − q) = 3. Odsud (q − 2)(n − q) = 3. Nyní je buď q − 2 = 1, n − q = 3 a proto q = 3, n = 6, k = q − 1 = 2 a p = 5 nebo je q − 2 = 3, n − q = 1 a z tohoto dostáváme q = 5, n = 6, k = 4 a p = 3. Také může být k + 1 = 2q a odtud (k − 1)(n − q) = 2. Proto platí i rovnost 2(q − 1)(n − q) = 2. Tento vztah vede k tomu, že q − 1 = 1 a n − q = 1, neboli q = 2, n = 3 a p = 2. Takže pro kladné celé číslo n dostáváme tato řešení s prvočísly p a q: 1. p = q = 2, n = 3 2. p = 5, q = 3, n = 6 3. p = 3, q = 5, n = 6. Pouze v prvním případě jsou všechna tři čísla prvočísla.

18

◦

Kapitola 3 Kongruence Definice 3.1. Pokud mají dvě celá čísla a, b po dělení přirozeným číslem m stejný zbytek r, kde 0 ≤ r < m, nazýváme je kongruentní modulo m (nebo kongruentní podle modulu m). Zapisujeme to takto: a ≡ b (mod m). Jestliže mají různý zbytek, říkáme, že nejsou kongruentní modulo m, a píšeme: a 6≡ b (mod m).

Věta 3.1. Pro libovolné a, b ∈ Z, m ∈ N jsou následující podmínky ekvivalentní: 1. a ≡ b (mod m), 2. a = b + mt

pro vhodné t ∈ Z,

3. m | a − b.

3.1

Základní vlastnosti kongruencí

Připomeňme zde několik vět o vlastnostech kongruencí. Ty poměrně snadno obdržíme přímo z definice. Důkazy zde uvádět nebudeme, najdete je v patřičné literatuře.

19

3. Kongruence


Věta 3.2. 1. Kongruence podle téhož modulu můžeme sčítat. Libovolný sčítanec můžeme přenést s opačným znaménkem z jedné strany kongruence na druhou. Na libovolnou stranu kongruence můžeme přičíst jakýkoliv násobek modulu. 2. Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence můžeme umocnit na totéž přirozené číslo nebo vynásobit stejným celým číslem. 3. Obě strany kongruence můžeme vydělit jejich společným dělitelem, pokud je tento dělitel nesoudělný s modulem. 4. Obě strany kongruence i její modul můžeme vynásobit tímtéž přirozeným číslem. 5. Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. 6. Pokud kongruence a ≡ b platí podle více modulů m1 . . . mk , platí i podle modulu, který je nejmenším společným násobkem [m1 . . . mk ] těchto modulů. 7. Platí-li kongruence podle modulu m, platí také podle libovolného modulu d, který je dělitelem čísla m. 8. Pokud nějaké číslo dělí jednu stranu kongruence i modul, pak také dělí druhou stranu kongruence.

Poznámka. Počítání s kongruencemi nevyžaduje žádné zvláštní vědomosti. Spíše jen cvik a představivost, co to znamená, pokud jsou dvě čísla spolu kongruentní. Početních cest vede k cíli obvykle více. Ke zjednodušení výrazu se nejvíce využívá toho, že můžeme libovolné číslo nahradit jeho zbytkem po dělení modulem, případně číslem o modul menším než je zbytek (plyne z 3.2.1). Příklad 3.1 Nalezněte zbytek po dělení čísla 230 číslem 5. Řešení Zjevně platí kongruence 22 = 4 ≡ −1

(mod 5).

20

3. Kongruence


Nyní podle věty 3.2.2 můžeme obě strany kongruence umocnit, tedy 415 = 230 ≡ (−1)15 = −1

(mod 5).

Protože podle definice má pro zbytek platit 0 ≤ r < m, ještě přičteme na pravou stranu jednou modul 230 ≡ −1 + 5 (mod 5), 230 ≡ 4 (mod 5). Zbytek po dělení čísla 230 číslem 5 je tedy 4.

◦

Příklad 3.2 Nalezněte zbytek po dělení čísla 7211 číslem 17. Řešení Číslo 72 si nejprve rozložíme na vhodnější součinitele a zjednodušíme. Například 7211 = (4 · 18)11 ≡ (4 · 1)11 = 411

(mod 17).

Kongruenci budeme dále upravovovat: 7211 ≡ 411 = 4 · 410 = 4 · 165 Protože 16 ≡ −1

(mod 17).

(mod 17), provedeme záměnu 7211 ≡ 4 · (−1)5 = −4

(mod 17).

Neboť je −4 ≡ 13 (mod 17), provedeme ještě jednou záměnu 7211 ≡ 13 (mod 17). Zbytek po dělení čísla 7211 číslem 17 je tedy 13. Příklad 3.3 Nalezněte zbytek po dělení čísla 1325 číslem 7. Řešení Platí, že 13 ≡ −1

(mod 7). 21

◦

3. Kongruence


Musí tedy platit také 1325 ≡ (−1)25 = −1

(mod 7).

A tedy po přičtení modulu na pravou stranu dostáváme výsledek 1325 ≡ 6 (mod 7). Zbytek po dělení čísla 1325 číslem 7 je 6.

◦

Příklad 3.4 Nalezněte zbytek po dělení čísla 1312 + 1211 + 1110 číslem 9. Řešení Vytvořme kongruenci náhradou čísel za zbytky po dělení 9 1312 + 1211 + 1110 ≡ 412 + 311 + 210

(mod 9).

Upravme kongruenci do vhodného tvaru 1312 + 1211 + 1110 ≡ (2)24 + 32 · 39 + 2 · (23 )3

(mod 9).

Po jednoduché úpravě dostaneme 1312 + 1211 + 1110 ≡ 88 + 9 · 39 + 2 · 89

(mod 9).

Opět nahradíme některá čísla menšími zbytky 1312 + 1211 + 1110 ≡ (−1)8 + 0 + 2 · (−1)9

(mod 9).

Nyní stačí už jen upravovat: 1312 + 1211 + 1110 ≡ 1 − 2 (mod 9), 1312 + 1211 + 1110 ≡ 8 (mod 9). Zbytek po dělení čísla 1312 + 1211 + 1110 číslem 9 je tedy 8.

◦

Příklad 3.5 Dokažte, že číslo 1615 + 2914 + 4213 je dělitelné číslem 13. Řešení Dokázat, že číslo 13 dělí číslo jiné, je totéž jako ukázat, že takové číslo dává zbytek nula po dělení třinácti. Tedy, že je kongruentní s nulou modulo 13. 22

3. Kongruence


Nejprve nahradíme základy mocnin zbytky po dělení číslem 13: 1615 + 2914 + 4213 ≡ 315 + 314 + 313

(mod 13).

Kongruenci upravíme: 1615 + 2914 + 4213 ≡ 313 · (9 + 3 + 1) (mod 13), 1615 + 2914 + 4213 ≡ 313 · 13 (mod 13). Číslo 13 na pravé straně můžeme nahradit jeho zbytkem, tedy nulou:

1615 + 2914 + 4213 ≡ 0 (mod 13). Tímto jsme ukázali, že výraz 1615 + 2914 + 4213 je kongruentní s nulou, neboli že je dělitelný číslem 13. ◦ Příklad 3.6 Dokažte, že číslo 215 + 314 + 513 + 212 je dělitelné číslem 22. Řešení Opět ukážeme kongruenci tohoto čísla s nulou modulo 22. Vyřešení však vyžaduje více úprav, než jsme byli doposud zvyklí. Nejprve výraz vhodně upravíme 215 + 314 + 513 + 212 = (23 + 1) · 212 + 5 · (52 )6 + 314 = = 9 · 212 + 5 · (25)6 + 314 . Nyní už řešíme běžným způsobem danou kongruenci 215 + 314 + 513 + 512 ≡ 9 · 212 + 5 · 56 + 314 ≡ 9 · 212 + 36 · (5 + 38 ) ≡ 9 · 212 + 36 · (5 + 812 ) ≡ 9 · 212 + 36 · (5 + 72 ) ≡ 9 · 212 + 36 · 10 ≡ 2 · (9 · 211 + 36 · 5) (mod 22). Ukázat, že je levá strana kongruence kongruentní s nulou modulo 22 je stejné, jako nyní ukázat, že je modulo 11 s nulou kongruentní výraz v závorce na pravé straně 9 · 211 + 5 · 36 ≡ 18 · (25 )2 + 45 · 34 ≡ 7 · (−1)2 + 1 · 34 ≡ 7 + 81 ≡ 0 (mod 11). Z obou kongruencí tedy plyne, že 215 + 314 + 513 + 512 ≡ 0 (mod 22), nebo-li že je daný výraz dělitelný číslem 22. ◦ 23

3. Kongruence

3.2

Úlohy a cvičení

Úlohy a cvičení

1. Jaký zbytek dává číslo: (a) 1325 dělené číslem 6 (b) 2666666 dělené číslem 7 (c) 13 · 2666666 + 7 · 215 dělené číslem 5 (d) 214 + 513 + 212 dělené číslem 22? [ (a) 1; (b) 1; (c) 3; (d) 13 ]

2. Dokažte, že je dělitelné: (a) číslo 812 + 11 · 210 číslem 5 (b) číslo 940 + 730 + 520 + 310 číslem 4 (c) číslo 3330 − 2815 + 520 − 105 číslem 13 (d) číslo 717 · 515 − 1513 číslem 13.

3.3


Příklad 3.7 Určete dvě poslední číslice dekadického zápisu čísla 39876543 . Řešení Zadání příkladu je stejné, jako kdybychom se ptali, jaký zbytek dává dané číslo po dělení stem, neboli s čím je toto číslo kongruentní modulo 100. 39876543 ≡ 273292181 = 27 · 273292180 = 27 · (272 )1646090 ≡ 27 · 291646090 (mod 100) 27 · 291646090 = 27 · (292 )646090 = 27 · (841)1646090 ≡ 27 · 41823045 (mod 100) 27 · 41823045 = 27 · (415 )164609 = 27 · (115856201)164609 ≡ 27 · 1164609 (mod 100) 39876543 ≡ 27 (mod 100) Zjistili jsme, že poslední dvě cifry dekadického zápisu čísla 39876543 jsou 27.

◦

Příklad 3.8 Nalezněte přirozené číslo x splňující x ≡ 448 (mod 97). Řešení Máme najít s čím je 448 kongruentní. Tedy x ≡ 448 = 6416 ≡ (−33)16 = 3316 = 10898 ≡ 228 = 4844 ≡ (−1)4 = 1 Se zadanným číslem je kongruentní číslo 1. 24

(mod 97). ◦

3. Kongruence

3.4

Zajímavé úlohy

Zajímavé úlohy

Příklad 3.9 Dokažte, že pro kladné celé číslo n platí n2 | (n + 1)n − 1. Řešení Z binomické věty dostáváme n n n 2 n n . n +···+ n+ (1 + n) = 1 + n 2 1 n

Navíc pro druhý sčítanec platí n n = n2 . 1 Pokud je tedy n > 1, platí, že všechny členy rozkladu kromě prvního jsou násobkem n, jehož mocnina je ≥ 2. Tedy platí n n n 2 n 2 n . n +···+ n+ n | n 2 1 Odtud tedy plyne závěr, že n2 | (n + 1)n − 1.

◦

Příklad 3.10 Najděte všechna kladná celá čísla a taková, pro která je výraz a10 + 1 dělitelný číslem 10. Řešení Jestliže je a kladné celé číslo a r je jeho zbytek po dělení deseti, potom je a10 + 1 dělitelné číslem 10 tehdy a jen tehdy, když je r 10 + 1 dělitelné deseti. Zbytek r je právě některé z čísel 0, 1, 2, . . . , 9. Pro tato čísla jednoduše ověříme, že pouze 310 + 1 a 710 + 1 jsou dělitelná deseti. 010 + 1 = 1 110 + 1 = 2 210 + 1 = 1025 310 + 1 = 95 + 1 ≡ (−1)5 + 1 = 0 (mod 10) 410 + 1 Toto je jistě liché číslo a proto nemůže být dělitelné deseti. 510 + 1 = 255 + 1 ≡ 5 · 54 + 1 ≡ 5 · 5 + 1 ≡ 6 (mod 10) 610 + 1 Opět dostáváme liché číslo, které nemůže být dělitelné deseti. 710 + 1 = 495 + 1 ≡ (−1)5 + 1 = 0 (mod 10) 810 + 1 I toto číslo je liché. 910 + 1 ≡ (−1)10 + 1 = 2 (mod 10)

25

3. Kongruence

Eulerova funkce ϕ

To znamená, že číslo a, pro které platí 10 | a10 + 1, může být pouze tvaru 10k + 3 nebo 10k + 7 pro k = 0, 1, 2, . . . . ◦ Příklad 3.11 Dokažte, že pokud pro celá čísla a a b platí 7 | a2 + b2 , potom 7 | a a zároveň 7 | b. Řešení Druhá mocnina celého čísla nedělitelného sedmi dává po dělení sedmi zbytek 1, 2 nebo 4. Součet dvou takovýchto zbytků může být 1, 2, 3, 4, 5 nebo 6. Pokud jsou tedy a a b taková čísla, že 7 | a2 + b2 , musí být sedmi dělitelná také obě čísla a i b. ◦ Příklad 3.12 n Dokažte, že pro Fn = 22 + 1 platí Fn | 2Fn − 2 (n = 1, 2, . . . ). Řešení Můžeme jednoduše indukcí ukázat, že pro kladná celá čísla n platí 2n ≥ n + 1, n n+1 2n 2n+1 22 z čehož plyne, že 2 | 2 a z věty 1.2 dostáváme 2 − 1 | 2 − 1. Dále platí n n 2n +1 22 22 2n 2n 2n+1 2n −2. Dohromady −1 = (2 +1)(2 −1) a 2 −1 | 2(2 −1) = 22 2 +1 | 2 n n 22 +1 22 2n+1 2n − 2 = 2Fn − 2, tedy −1 | 2 −1 | 2 tak můžeme psát Fn = 2 + 1 | 2 Fn Fn | 2 − 2. Tímto je důkaz hotov. ◦ Poznámka. Někteří matematici se domnívají, že tento vztah vedl P. Fermata k doměnce, že všechna čísla Fn (n = 1, 2, . . . ) jsou prvočísla. Za Fermata se lidé domnívali, že tzv. Čínská věta je pravdivá, tedy tvrzení, že když m > 1 splňuje vztah m | 2m − 2, pak je m prvočíslo (vztah byl ověřen pro několik prvních stovek celých čísel). Toto tvrzení bylo vyvráceno pro m = 341 = 11 · 31.

3.5

Eulerova funkce ϕ

Definice 3.2. Nechť n ∈ N. Definujeme Eulerovu funkci ϕ předpisem ϕ(n) =| {a ∈ N | 0 < a ≤ n, (a, n) = 1} | . Eulerova funkce ϕ(n) je definována jako počet přirozených čísel menších než n, která jsou nesoudělná s n.

26

3. Kongruence


Věta 3.3. Nechť n ∈ N a jeho rozklad je tvaru n = pα1 1 . . . pαk k . Pak ϕ(n) = (pα1 1 − pα1 1 −1 ) . . . (pαk k − pkαk −1 ). Snadnou úpravou dostaneme, že 1 1 ϕ(n) = n · 1 − ... 1− . p1 pk Z definice platí ϕ(1) = 1. Je zřejmé, že pro prvočíslo p je ϕ(p) = p − 1. Věta 3.4. Pro libovolná dvě nesoudělná přirozená čísla m1 , m2 platí ϕ(m1 , m2 ) = ϕ(m1 ) · ϕ(m2 ). Výpočet Eulerovy funkce je poměrně snadný. Stačí zadané číslo rozložit na součin prvočísel a dosadit do jednoho z výše uvedených vzorců.

3.6


Příklad 3.13 Spočítejte hodnotu Eulerovy funkce pro číslo 735. Řešení Nejprve si rozložíme číslo 735 na součin prvočísel: 735 = 3 · 245 = 3 · 5 · 49 = 3 · 5 · 72 . Zbývá dosadit do vhodného vzorce. Nejlépe je vzorce dle potřeby kombinovat: ϕ(735) = ϕ(3) · ϕ(5) · ϕ(72 ), ϕ(735) = 2 · 4 · 72 − 71 , ϕ(735) = 336. Eulerova funkce pro číslo 735 má hodnotu 336.

27

◦

3. Kongruence

3.7

Eulerova a Fermatova věta

Eulerova a Fermatova věta

Věta 3.5 (Fermatova, Malá Fermatova). Pro libovolné prvočíslo p a každé celé číslo a platí ap ≡ a (mod p). Je-li navíc (a, p) = 1, platí ap−1 ≡ 1 (mod p).

Věta 3.6 (Eulerova). Nechť a ∈ Z, m ∈ N, (a, m) = 1. Pak aϕ(m) ≡ 1

(mod m).

S Eulerovou větou a Eulerovou funkcí úzce souvisí důležitý pojem řád čísla modulo m. Definice 3.3. Nechť a ∈ Z, m ∈ N, (a, m) = 1. Řádem čísla a modulo m rozumíme nejmenší přirozené číslo n splňující an ≡ 1

(mod m).

Věta 3.7. Nechť a ∈ Z, m ∈ N, (a, m) = 1. Označme r řád čísla a modulo m. Pak pro libovolná t, s ∈ N ∪ {0} platí at ≡ as

(mod m) ⇐⇒ t ≡ s

(mod r).

Věta 3.8. Nechť a ∈ Z, m ∈ N, (a, m) = 1. Označme r řád čísla a modulo m. 1. Pro libovolné n ∈ N ∪ {0} platí an ≡ 1 (mod m) ⇐⇒ r | n. 2. r | ϕ(m).

28

3. Kongruence

3.8



Příklad 3.14 Určete řád čísla 5 modulo 13. Řešení Víme, že má platit 5 | ϕ(m) = 12. Řádem proto bude některé z čísel 1, 2, 3, 4, 6, 12. Budeme prověřovat tato čísla postupně od nejmenšího. 51 52 53 54

≡ 5 (mod 13) ≡ −1 (mod 13) ≡ −1 · 5 = −5 (mod 13) ≡ −5 · 5 ≡ 1 (mod 13)

Řádem čísla 5 modulo 13 je číslo 4.

◦

Příklad 3.15 Rozhodněte, pro která přirozená čísla n je číslo 3n + 4n − 5n dělitelné jedenácti. Řešení Má-li být zadaný výraz dělitelný číslem 11, musí dávat po dělení jedenácti zbytek 0. Budeme modulo 11 zjišťovat, jaké zbytky dávají jednotlivé sčítance a jaký zbytek dostaneme jejich součtem, v závislosti na n. Lze snadno ověit, že modulo 11 mají čísla 3, 4, 5 stejný řád 5 (řád musí dělit ϕ(11) = 10, je to proto některé z čísel 1, 2, 5, 10). Je proto zřejmé, že stačí ověřit zbytky pro n ≤ 5. Poté se budou jejich zbytky opakovat stejným způsobem od začátku. Zapišme si výsledky do přehledné tabulky. n 3n 1 3 2 9 3 5 4 4 5 1

4n 4 5 9 3 1

5n 5 3 4 9 1

3 n + 4n − 5 n 2 0 10 9 1

Z tabulky je vidět, že výraz je dělitelný pouze pro n ≡ 2 (mod 5).

◦

Příklad 3.16 6n+2 Dokažte tvrzení: ”Pro každé přirozené číslo n platí, že číslo 22 − 16 je dělitelné číslem 37.”

29

3. Kongruence


Řešení Platí, že 26 = 64 ≡ 1

(mod 9).

Odtud dostáváme 26n ≡ 1 (mod 9), 26n+2 ≡ 22 (mod 22 · 9), 26n+2 ≡ 4 (mod 36). Kongruenci také můžeme zapsat parametricky: 26n+2 = 36t + 4,

kde t ∈ Z.

Z Fermatovy věty plyne 236 ≡ 1

(mod 37).

Z obou výrazů můžeme psát 6n+2

22

= 236t+4 ≡ 24 = 16 (mod 37),

tedy 6n+2

22

− 16 ≡ 0

(mod 37). 6n+2

Tímto jsme dokázali, že číslo 37 dělí výraz 22

− 16 pro všechna přirozená n. ◦

Příklad 3.17 Dokažte, že pro všechna n ∈ N platí 25 | 42n+1 − 10n − 4. Řešení Podívejme se, jaké zbytky dávají (modulo 25) pro všechna možná n jednotlivé členy výrazu a jaký zbytek dává celý výraz. Protože řád čísla 4 modulo 25 je 5, budou se zbytky vždy po pěti opakovat. Protože (10,25)=5 a 25:5=5, budou se i zbytky členu 10n vždy po pěti opakovat. Stačí se tedy podívat na čísla 1 ≤ n ≤ 5. n 1 2 3 4 5

42n+1 14 24 9 19 4

10n 10 20 5 15 0

42n+1 − 10n − 4 0 0 0 0 0 30

3. Kongruence

Zajímavé úlohy

Z tabulky je patrné, že zadaný výraz je dělitelný číslem 25 pro všechna přirozená čísla n. ◦ Příklad 3.18 22n−1 Dokažte, že pro libovolné přirozené číslo n je číslo 111 + 22 dělitelné číslem 127. Řešení Máme ukázat, že všechna přirozená n splňují kongruenci 22n−1

22

≡ −111 (mod 127).

Tuto kogruenci můžeme upravit 22n−1

22

≡ 16 = 24

(mod 127).

Protože číslo 7 je řád čísla 2 modulo 127. Platí podle věty 3.7 daná kongruence, právě když platí kongruence 2n−1

22

≡ 4 = 22

(mod 7).

Modulo 7 má číslo 2 řád 3. Opět podle věty 3.7 kongruence platí, právě když 22n−1 ≡ 2 (mod 3). Kongruenci můžeme ještě přepsat: (−1)2n−1 ≡ (−1)

(mod 3).

Kongruence je zajisté splněna vždy, když je výraz 2n−1 lichým přirozeným číslem. Tím je ovšem pro libovolné přirozené n, čímž jsme dokázali požadované tvrzení. ◦

3.9

Zajímavé úlohy

Příklad 3.19 Dokažte, že neexistuje žádné celé číslo n > 1 takové, pro které platí n | 2n − 1. Řešení Předpokládejme, že existuje celé číslo n > 1 takové, že n | 2n − 1 a nechť n je nejmenší z takovýchto čísel. Pak je jistě n liché a je proto (n, 2) = 1. Z Eulerovy věty dostáváme n | 2ϕ(n) − 1. 31

3. Kongruence

Zajímavé úlohy

Z věty 1.2 plyne, že největší společný dělitel čísel 2a − 1 a 2b − 1 je číslo 2d − 1, kde d = (a, b). Pro a = n a b = ϕ(n), d = (n, ϕ(n)) dostáváme, že n | 2d − 1. Pro n > 1 však dostáváme 2d − 1 > 1. Z toho plyne d > 1 a 1 < d ≤ ϕ(n) < n. Odtud d | n | 2d − 1, což je v rozporu s naším předpokladem o n. ◦ Příklad 3.20 Dokažte, že pro liché n platí n | 2n! − 1. Řešení Pro n = 1 je vztah zřejmý. Pro n > 1, jehož rozklad na prvočísla je n = q1α1 q2α2 . . . qkαk a ϕ(n) = q1α1 −1 q2α2 −1 . . . qkαk −1 (q1 − 1) . . . (qk − 1), a kde q1 < q2 < · · · < qk platí q1α1 −1 q2α2 −1 . . . qkαk −1 | n, kde q1 − 1 < qk ≤ n. Jistě platí qk − 1 < n a q1 − 1 < q2 − 1 < · · · < qk − 1 jsou různá kladná celá čísla menší než n. Odtud dostáváme (q1 − 1)(q2 − 1) . . . (qk − 1) | (n − 1)! a zároveň tedy musí platit ϕ(n) | (n − 1)! · n = n! Pokud je n liché, potom (z Eulerovy věty) dostáváme n | 2ϕ(n) − 1 | 2n! − 1, tedy n | 2n! − 1. Tím je důkaz hotov. ◦ Příklad 3.21 6k+2 + 3 pro k = 0, 1, 2, . . . Dokažte, že číslo 19 dělí číslo 22 Řešení Platí, že 26 = 64 ≡ 1 (mod 9). Z toho plyne, že pro všechna k = 0, 1, 2, . . . platí 26k ≡ 1 (mod 9). Odtud dostáváme 26k+2 ≡ 22 (mod 9) a protože obě strany jsou sudé, dostáváme 26k+2 ≡ 22 (mod 18). Toto můžeme napsat jako 26k+2 = 18t + 22 , kde t je celé číslo ≥ 0. Z Fermatovy věty plyne 218 ≡ 1 (mod 19) a odtud 218t ≡ 1 6k+2 = 218t+4 ≡ 24 (mod 19). (mod 19) pro t = 0, 1, 2, . . . . Z předchozího plyne 22 Závěrem dostáváme 6k+2

22

+ 3 ≡ 24 + 3 ≡ 0

Tímto je důkaz hotov.

(mod 19). ◦

32

Kapitola 4 Kongruence o jedné neznámé Definice 4.1. Nechť m ∈ N, f (x), g(x) ∈ Z[x]. Zápis f (x) ≡ g(x) (mod m) nazýváme kongruencí o jedné neznámé x. Úkolem nalézt množinu řešení této kongruence rozumíme nalézt množinu čísel c ∈ Z takových, že platí f (c) ≡ g(c) (mod m). Dvě kongruence se nazývají ekvivalentní, mají-li stejnou množinu řešení.

Věta 4.1. Pro libovolná a, b ∈ Z, m ∈ N, f (x) ∈ Z[x] platí a ≡ b (mod m)

4.1

=⇒

f (a) ≡ f (b)

(mod m).

Lineární kongruence o jedné neznámé

Definice 4.2. Lineární kongruencí o jedné neznámé nazýváme kongruenci typu ax ≡ b (mod m), m ∈ N, a, b ∈ Z. (1)

Věta 4.2. Označme d = (a, m). Pak kongruence (1) má řešení právě tehdy, když d | b. Pokud d | b, pak má tato kongruence právě d řešení (modulo m). 33

4. Kongruence o jedné neznámé Lineární kongruence o jedné neznámé

Poznámka. Ověření, zda má daná kongruence řešení je obvykle prvním krokem výpočtu. Na samotné řešení lineárních kongruencí existuje více způsobů, my se zde podíváme na několik nejzákladnějších: 1) Jednoduchými úpravami Tento způsob řešení využívá takových úprav kongruence, že se výsledná množina řešení nezmění. Tento postup vede k výsledku obvykle nejrychleji a nejjednodušeji, avšak není dostatečně dobře algoritmizovatelný. Příklad 4.1 Řešte kongruenci 21x ≡ 6 (mod 9). Řešení Nejprve ověříme, zda má daná kongruence řešení: (21, 9) = 3 | 6. Daná kongruence má tedy tři řešení modulo devět. Kongruenci budeme upravovat základními pravidly 3.2. Nahraďme tedy číslo 21 jeho zbytkem: 3x ≡ 6 (mod 9). Nyní obě strany kongruence vydělíme číslem 3. Toto číslo však dělí i modul, proto jej také podělíme, x ≡ 2 (mod 3). Řešením jsou všechna x, pro která platí x ≡ 2 (mod 3). V úvodu příkladu jsme zjistili, že kongruence má tři řešení modulo 9. My však máme pouze jeden výsledek modulo 3. Převod na tři řešení modulo 9 je však velmi snadný: x ≡ 2 (mod 9), x ≡ 5 (mod 9), x ≡ 8 (mod 9). ◦ Příklad 4.2 Řešte kongruenci 265 x ≡ 16 (mod 11). Řešení Ověříme nejprve, zda má kongruence řešení. (265 , 11) = (26, 11) = 1 | 16 34


Kongruence má jedno řešení modulo 11. Budeme proto pokračovat ve výpočtech. Číslo 26 nahradíme zbytkem po dělení 11 45 x ≡ 16 (mod 11). Obě strany podělíme číslem 16 43 x ≡ 1 (mod 11). Kongruenci dále upravujeme: 16 · 4x ≡ 1 5 · 4x ≡ 1 20 · x ≡ 1 9x ≡ 1

(mod (mod (mod (mod

11), 11), 11), 11).

Potřebujeme se zbavit devítky na levé straně. Ta však nemá žádného netriviálního společného dělitele s jedničkou, proto si přičteme k jedničce modul, 9x ≡ 12 (mod 11). Nyní můžeme obě strany podělit třemi: 3x ≡ 4 (mod 11). Opět nelze žádným číslem dělit pravou a levou stranu kongruence současně. Přičteme si tedy na pravou stranu znovu modul (toto je velmi častý krok při výpočtech kongruencí) 3x ≡ 15 (mod 11). Pokud obě strany znovu podělíme třemi, máme výsledek x ≡ 5 (mod 11). Řešením jsou tedy všechna x, pro která platí x ≡ 5 (mod 11).

◦

2) S využitím Eulerovy věty: Pokud je kongruence tvaru (1) a navíc platí (a, m) = 1 (toho vždy můžeme dosáhnout vydělením), lze psát: ax ≡ b (mod m). 35


Po vynásobení kongruence číslem aϕ(m)−1 dostaneme aϕ(m)−1 · a · x ≡ aϕ(m)−1 · b (mod m), po úpravě aϕ(m) · x ≡ aϕ(m)−1 · b (mod m). Protože aϕ(m) ≡ 1 (mod m) (Eulerova věta), platí x ≡ aϕ(m)−1 · b (mod m). Tento postup výpočtu je poměrně jednoduchý, avšak ke konci řešení může vést k velmi náročným úpravám. Příklad 4.3 Řešte kongruenci 26x ≡ 4 (mod 9). Řešení Jelikož je kongruence ve správném tvaru a (26, 9) = 1, můžeme ji řešit přesně podle návodu. Navíc 1 | 4, a proto bude mít kongruence jedno řešení modulo 9 Spočítejme nejprve Eulerovu funkci pro hodnotu 9: 1 ϕ(9) = 9 · (1 − ) = 6. 3 Nyní vynásobíme obě strany kongruence číslem 265 : 265 · 26x ≡ 265 · 4 (mod 9), 266 x ≡ 265 · 4 (mod 9), Protože je 266 ≡ (−1)6 ≡ 1

(mod 9), můžeme psát x ≡ 265 · 4 (mod 9).

Tímto jsme získali výsledek. Je však třeba jej ještě upravit. To provedeme běžnými úpravami tak, jak jsme zvyklí. Nahradíme číslo 26 jeho zbytkem modulo 9 a ještě jednou od něj modul odečteme: x ≡ (−1)5 · 4 (mod 9), x ≡ −4 (mod 9). 36


Nyní ješte můžeme přičíst modul na pravou stranu kongruence x ≡ 5 (mod 9). Kongruence má tedy řešení pro taková x, pro která platí x ≡ 5 (mod 9).

◦

Příklad 4.4 Řešte kongruenci 76x ≡ 8 (mod 10). Řešení Kongruence je sice ve tvaru (1), ale (76, 10) = 2 a to pro nás není vhodné. Proto kongruenci nejprve upravíme podělením obou stran i modulu číslem 2, 38x ≡ 4 (mod 5). Tato kongruence již splňuje všechny požadavky a bude mít jedno řešení modulo 5. Spočítejme hodnotu Eulerovy fce v čísle 5, ϕ(5) = 4. Nyní obě strany kongruence vynásobíme číslem 383 , 383 · 38x = 384 x ≡ 383 · 4 (mod 5). Jelikož 384 ≡ 1 (mod 5), nahradíme koeficient u neznámé na levé straně jedničkou: x ≡ 383 · 4 (mod 5). Tento mezi-výsledek ještě upravíme. Nahradíme číslo 38 jeho zbytkem po dělení pěti, atd. x ≡ 33 · 4 (mod 5), x ≡ 27 · 4 (mod 5), x ≡ 2 · 4 (mod 5), x ≡ 3 (mod 5). Řešením kongruence jsou tak všechna čísla, pro která platí, že po dělení pěti dávají zbytek tři. ◦ 3) S využitím Bezoutovy věty: 37


Podle Bezoutovy věty existují v kongruenci (1) koeficienty k1 , k2 ∈ Z takové, že platí (a, m) = k1 · a + k2 · m. Čísla k1 , k2 se dají spočítat například Euklidovým algoritmem. Z rovnosti d = k1 · a + k2 · m také plyne kongruence k1 · a + k2 · m ≡ d (mod m). Člen k2 · m můžeme vypustit, protože je zjevně kongruentní s nulou modulo m. Po vynásobení číslem db dostaneme k1 · a ·

b ≡ b (mod m). d

Porovnáním se zápisem (1) dostaneme vždy výsledek ve tvaru x ≡ k1 ·

b d

(mod m).

Poznámka. Pokud má kongruence více řešení, existují i jiná čísla než db , kterými můžeme obě strany násobit. Je tedy lepší na začátku kongruenci ”krátit” tak, aby měla jen jedno řešení a my na nějaké nezapomněli. Postup výpočtu je poměrně snadný. Ve své podstatě stačí spočítat koeficienty Bezoutovy rovnosti a dosadit do výše uvedeného vzorce. Častěji si však každý odvozuje postup znovu. Příklad 4.5 Řešte kongruenci 5x ≡ 7 (mod 8). Řešení Protože (5, 8) = 1 | 7, bude mít kongruence jedno řešení modulo 8. Postupovat budeme podle výše uvedeného postupu. Pomocí Euklidova algoritmu spočítáme koeficienty v Bezoutově rovnosti, (5, 8) = 1 = −3 · 5 + 2 · 8. Tuto rovnost můžeme napsat také jako kongruenci −3 · 5 + 2 · 8 ≡ 1 (mod 8). Druhý sčítanec na pravé straně je kongruentní s nulou, můžeme ho tedy vypustit: −3 · 5 ≡ 1 (mod 8). 38


Nyní vynásobíme obě strany číslem 7, 7 · (−3) · 5 ≡ 7 (mod 8). Když nyní porovnáme tuto kongruenci se zadáním, obdržíme řešení x ≡ 7 · (−3)

(mod 8).

Zbývá už jen drobnost, totiž výsledek upravit: x ≡ (−1) · (−3) (mod 8), x ≡ 3 (mod 8). Řešením jsou všechna čísla x, která dávají po dělení osmi zbytek tři.

◦

Příklad 4.6 Řešte kongruenci 16x ≡ 4 (mod 6). Řešení Platí (16, 6) = 2 | 4, takže kongruence bude mít modulo 6 dvě řešení. Najděme koeficienty v Bezoutovy rovnosti: (16, 6) = 2 = 16 · (−1) + 6 · 3. Každou rovnost můžeme napsat jako kongruenci podle lib. modulu, 16 · (−1) + 6 · 3 ≡ 2 (mod 6). Druhý člen na levé straně můžeme vynechat (je dělitelný modulem), 16 · (−1) ≡ 2 (mod 6). Na pravé straně by se nám hodilo získat číslo 4 (to se totiž vyskytuje v zadání na pravé straně). Vynásobíme tedy obě strany číslem 2. POZOR! Obě strany také můžeme vynásobit číslem 5. Sice je 2 · 5 = 10, ale 10 ≡ 4 (mod 6). Je tedy jedno, kterým z těchto čísel kongruenci vynásobíme. Pokud chceme dostat požadovaný tvar, žádným jiným číslem menším než 6 nyní už násobit nelze. a) Násobíme dvěma 16 · (−2) ≡ 4 39

(mod 6).

4. Kongruence o jedné neznámé

Úlohy a cvičení

Když nyní porovnáme tuto kongruenci s kongruencí zadanou, vidíme, že má řešení právě když x ≡ −2

(mod 6).

Po přičtení modulu na pravou stranu dostaneme x≡4

(mod 6).

b) Násobíme pěti 16 · (−5) ≡ 10 (mod 6). Po odečtení modulu od pravé strany obdržíme 16 · (−5) ≡ 4 (mod 6). Řešením jsou proto taková x, pro která platí: x ≡ −5

(mod 6).

Po přičtení modulu na pravou stranu dostáváme x ≡ 1 (mod 6). Výsledkem jsou proto taková x, pro která platí x ≡ 1 (mod 6) nebo x ≡ 4 (mod 6), což můžeme napsat dohromady jako x ≡ 1 (mod 3). ◦ Poznámka. Kdybychom při výpočtu zapomněli, že můžeme násobit i pěti, přišli bychom o jedno řešení. Je tedy potřeba dávat pozor na to, kolik řešení kongruence má. Pomoci si můžeme i tak, že kongruenci na začátku vždy ”krátíme”, aby koeficient na levé straně a modul byly nesoudělné. V tom případě bude existovat jen jedno řešení vzhledem k nějakému jinému modulu. V našem případě bychom na počátku podělili zadanou kongruenci dvěma a dostali bychom jeden konečný výsledek modulo tři.

4.2

Úlohy a cvičení

1. Řešte kongruence: (a) 4x ≡ 3 (mod 7) (b) 5x ≡ 6 (mod 9) (c) 8x ≡ 4 (mod 12) (d) 14x ≡ 4 (mod 30). [ (a) x ≡ 6 (mod 7); (b) x ≡ 3 (mod 9); (c) x ≡ 2 (mod 3); (d) x ≡ 11 (mod 15) ]

40


4.3



Příklad 4.7 Rozhodněte, zda má kongruence 2x ≡ 1 (mod 12345678910111213) řešení. Řešení Řešitelnost samostatné kongruence ověříme podle věty 4.2. Protože je modul s koeficienty u neznámé nesoudělný, bude mít kongruence jedno řešení podle tohoto modulu. ◦ Příklad 4.8 Rozhodněte, kolik má kongruence 642x ≡ 1844 (mod 1144) řešení a poté ji vyřešte. Řešení Nejprve ověříme počet řešení. Protože (642, 1144) = 2 | 1844, je daná kongruence řešitelná a má dvě řešení modulo 1844 (jedno řešení modulo 572). Zbývá toto řešení nalézt. 642x ≡ 1844 (mod 1144) 642x ≡ 700 (mod 1144) 321x ≡ 350 (mod 572) 321x ≡ −222 (mod 572) 107x ≡ −74 (mod 572) 107x ≡ 498 (mod 572) Protože kongruenci je nyní příliš těžké řešit pomocí jednoduchých úprav, vyřešíme ji pomocí Bezoutovy rovnosti. Bezoutovu rovnost můžeme psát jako (572, 107) = 1 = 139 · 107 − 26 · 572. Můžeme ji napsat také jako kongruenci 139 · 107 − 26 · 572 ≡ 1 (mod 572), 139 · 107 ≡ 1 (mod 572), 139 · 107 · 498 ≡ 498 (mod 572). Porovnáním s kongruencí 107x ≡ 498 (mod 572) můžeme psát řešení jako x ≡ 139 · 498 (mod 572). Zbývá řešení vhodně upravit. x ≡ 139 · 498 = 69222 (mod 572) x ≡ 69222 − 572 · 100 = 12022 (mod 572) x ≡ 12022 − 572 · 20 = 582 (mod 572) x ≡ 10 (mod 572) 41


Soustavy lineárních kongruencí

Řešením zadané kongruence je x ≡ 10 (mod 572).

4.4

◦


Pokud máme soustavu kongruencí o stejné neznámé, můžeme rozhodnout o každé kongruenci zvlášť, zda má řešení. Pokud některá z nich řešení nemá, pak nemá řešení ani celá soustava. Jestliže každá kongruence řešení má, můžeme soustavu upravit do tvaru x ≡ c1 .. . x ≡ ck

(mod m1 ) (2) (mod mk ).

Nejprve se podíváme na řešení soustavy dvou kongruencí o jedné neznámé. Věta 4.3. Nechť c1 , c2 ∈ Z a m1 , m2 ∈ N. Označme d = (m1 , m2 ). Pak soustava dvou kongruencí x ≡ c1 x ≡ c2

(mod m1 ) (mod m2 ),

(3)

v případě c1 6≡ c2 (mod d) nemá řešení. Jestliže naopak c1 ≡ c2 (mod d), pak existuje c ∈ Z tak, že x ∈ Z splňuje soustavu (3), právě když vyhovuje kongruenci x ≡ c (mod [m1 , m2 ]). Soustavu dvou kongruencí o jedné neznáme řešíme obvykle tak, že první kongruenci přepíšeme do ”parametrického” tvaru a dosadíme do kongruence druhé. Druhou kongruenci vyřešíme a přípustné hodnoty parametru opět dosadíme do první kongruence. Nejlépe bude, když si to ukážeme na příkladě. Příklad 4.9 Řešte systém kongruencí: x ≡ −5 (mod 20) x ≡ 2 (mod 13).

42



Řešení S číslem -5 jsou modulo 20 kongruentní všechna čísla tvaru x = 20k − 5, kde k ∈ Z. Tato čísla x musí vyhovovat i druhé kongruenci. Musí tedy platit 20k − 5 ≡ 2 (mod 13). Kongruenci upravíme: 7k ≡ 7 (mod 13), k ≡ 1 (mod 13). Parametr k musí být tvaru k = 13s + 1, kde s ∈ Z. Nyní dosadíme k do parametrického vyjádření x: x = 20(13s + 1) − 5, po úpravě x = 260s + 15. Oběma kongruencím tedy vyhovují čísla tvaru x = 260s + 15 pro libovolné s ∈ Z. To můžeme také zapsat jako x ≡ 15 (mod 260). Tedy jsou to taková x, která po dělení číslem 260 dávají zbytek 15. ◦ Nyní jsme si ukázali, jak se řeší soustava dvou kongruencí o jedné neznámé. Pokud se soustava skládá z více kongruencí než dvou, je postup obdobný. Vždy z jedné kongruence vyjádříme parametricky neznámou a toto vyjádření dosadíme do další kongruence. Příklad 4.10 Řešte systém kongruencí: x≡8 x≡5 x≡1

(mod 11) (mod 8) (mod 3).

Řešení První kongruenci splňují čísla x = 11k + 8, k ∈ Z. Tato čísla dosadíme do druhé kongruence 11k + 8 ≡ 5 (mod 8). 43



Po úpravě 3k ≡ 5 (mod 8), 3k ≡ −3 (mod 8), k ≡ −1 (mod 8). Tuto kongruenci splňují takové parametry k, které jsou tvaru k = 8s − 1, kde s ∈ Z. Neznámá x tedy musí být tvaru x = 11k + 8 = 11(8s − 1) + 8 = 88s − 3, s ∈ Z. Řešením soustavy kongruencí jsou však taková x, která navíc splňují i třetí kongruenci. Dosadíme tedy do ní 88s − 3 ≡ 1 (mod 3), s ≡ 1 (mod 3). Tuto kongruenci splňují všechna s tvaru s = 3t + 1, t ∈ Z. Nyní dosadíme parametr s do parametrického vyjádření x. x = 88s − 3 = 88(3t + 1) − 3, x = 264t + 85, t ∈ Z. To je již výsledek. Můžeme také napsat, že řešením jsou všechna x, pro která platí x ≡ 85 (mod 264). ◦ Ne vždy se zadaná soustava kongruencí nachází ve tvaru (2). Mnohdy ji musíme nejprve upravit. Příklad 4.11 Řešte systém kongruencí: 272 x ≡ 73 (mod 5) 132 x ≡ 33 (mod 7) 32x ≡ 113 (mod 9).

Řešení Nejprve upravíme zvlášť každou kongruenci, abychom dostali soustavu, která je

44



ve tvaru (2). Pro první kongruenci dostáváme 272 x ≡ 73 (mod 5), 22 x ≡ 23 (mod 5), x ≡ 2 (mod 5). Pro druhou kongruenci (−1)2 x ≡ 9 · 3 (mod 7), x ≡ 6 (mod 7). A konečně pro třetí 32x ≡ 113 (mod 9), 5x ≡ 23 (mod 9), 5x ≡ 8 (mod 9), 5x ≡ 8 + 3 · 9 (mod 9), 5x ≡ 35 (mod 9), x ≡ 7 (mod 9). Řešení původní soustavy tak můžeme převést na řešení nové soustavy x ≡ 2 (mod 5) x ≡ 6 (mod 7) x ≡ 7 (mod 9). Nyní pokračujeme již běžným způsobem. Řešením první kongruence jsou všechna x = 5k + 2, k ∈ Z. Tento výsledek dosadíme do druhé kongruence: 5k + 2 ≡ 6 (mod 7), 5k ≡ 4 (mod 7), 5k ≡ 4 + 3 · 7 (mod 7), 5k ≡ 25 (mod 7), k ≡ 5 (mod 7). Druhou kongruenci splňují všechny parametry k = 7s+5, s ∈ Z. Za tento parametr dosadíme do předchozího řešení: x = 5k + 2 = 5(7s + 5) + 2 = 35s + 27, s ∈ Z. 45


Úlohy a cvičení

Ještě zbývá dosadit za x do poslední kongruence: 35s + 27 ≡ 7 (mod 9), 35s ≡ −20 (mod 9), 35s ≡ 7 (mod 9), 5s ≡ 1 (mod 9), 5s ≡ 1 + 6 · 9 (mod 9), s ≡ 11 (mod 9), s ≡ 2 (mod 9). Třetí kongruenci tedy splňují taková s, pro která platí s = 9t + 2, t ∈ Z. Na závěr zbývá dosadit za s do parametrického vyjádření x x = 35s + 27 = 35(9t + 2) + 27, x = 315t + 97, t ∈ Z, neboli x ≡ 97 (mod 315). Toto je konečné řešení.

4.5

◦

Úlohy a cvičení

1. Řešte systém kongruencí: (a) x ≡ 6 (mod 8) x ≡ 2 (mod 5) (b) x ≡ 3 (mod 9) x ≡ 7 (mod 15) (c) x ≡ 2 (mod 4) x ≡ 4 (mod 6) x ≡ 6 (mod 10) (d) 2x ≡ 3 (mod 5) 3x ≡ 5 (mod 7) 5x ≡ 7 (mod 9). [ (a) x ≡ 2 (mod 30) ] [ (b) x ≡ 82 (mod 126) ] [ (c) x ≡ 46 (mod 60) ] [ (d) x ≡ 284 (mod 315) ] 46


4.6



Příklad 4.12 Když při spartakiádní skladbě vytvořili cvičenci sedmistupy, zbývali 3 navíc, při cvičení v kruzích o 11 lidech přebývali 2 a při tvorbě pyramid (na každou je potřeba 13 lidí), jich 5 jen přihlíželo. Kolik cvičenců se vystoupení zúčastnilo, když jich bylo určitě méně než 1000? Řešení V tomto příkladě se vlastně nejedná o nic jiného, než slovně zadanou úlohu vedoucí k soustavě lineárních kongruencí o jedné neznámé. Zapišme tedy řešení jako soustavu rovnic: x ≡ 3 (mod 7) x ≡ 2 (mod 11) x ≡ 5 (mod 13) x < 1000. Soustavu budeme řešit obvyklým způsobem. První rovnici vyhovují všechna x tvaru x = 7k + 3. Dosadíme za x do druhé rovnice. Dostáváme 7k + 3 ≡ 2 (mod 11), 7k ≡ −1 (mod 11), 7k ≡ 21 (mod 11), k ≡ 3 (mod 11). Nyní dosadíme za parametr k. Dostaneme x = 7k + 3 = 7(11s + 3) + 3 = 77s + 24. Zbývá dosadit za x do třetí rovnice: 77s + 24 ≡ 5 (mod 13), 77s ≡ −19 (mod 13), 9s ≡ −6 (mod 13), 3s ≡ −2 + 26 (mod 13), s ≡ 8 (mod 13). Nyní opět dosadíme do parametrického vyjádření x. Tedy x = 77x + 24 = 77(13t + 8) + 24 = 1001t + 640. Má-li platit, že x < 1000, lze dosadit za parametr jen t = 0 a pro x dostáváme řešení x = 640. Vystoupení se tak muselo zúčastnilo 640 cvičenců.

◦

Příklad 4.13 Šest loupežníků si chtělo rozdělit zlaťáky, které měli na stole. Když je rozdělovali 47



na šest stejných hromádek, tři zlaťáky zbyly. Když je zkusili rozdělit na pět stejných hromádek, jeden zlaťák zbyl. Nakonec se nepoprali, protože se vrátil sedmý loupežník, který z kapsy přidal tři zlaťáky na stůl a všechny zlaťáky pak rozdělil na sedm stejných hromádek. Kolik zlaťáků bylo původně na stole, víte-li, že jich nebylo více než 400 a méně než 100. Řešení Opět se jedná o příklad na řešení soustavy rovnic o jedné neznámé. Zadání proto můžeme přepsat takto: x ≡ 3 (mod 6) x ≡ 1 (mod 5) x ≡ −3 (mod 7) 100 ≤ x ≤ 400. Z první rovnice dostáváme x = 6k + 3. Dosadíme do rovnice druhé 6k + 3 ≡ 1 (mod 5), 6k ≡ −2 + 20 (mod 5), k ≡ 3 (mod 5). Tedy platí, že x = 6(5s + 3) + 3 = 30s + 21. Zbývá dosadit do třetí rovnice: 30s + 21 ≡ −3 (mod 7), 10s ≡ −8 (mod 7), 5s ≡ −4 (mod 7), s ≡ 2 (mod 7). Z poslední rovnice dosazením za x dostáváme x = 30s + 21 = 30(7t + 2) + 21 = 210t + 81. Z nerovnosti, kterou musí x splňovat dostáváme jediné řešení pro t = 1, a to x = 291. ◦ Příklad 4.14 Určete, která z následujících soustav rovnic má řešení. Svoji odpověď stručně zdůvodněte. a) x ≡ 1 (mod 3) x ≡ −1 (mod 9) b) x ≡ 3 (mod 29) x ≡ 5 (mod 47) 48



Řešení O řešitelnosti rozhodneme podle věty 4.3. a) V této soutavě je řešitelná každá z obou kongruencí. Největší společný dělitel modulů je roven (3,9)=3. Pravé strany kongruencí však nejsou kongruentní podle modulu 3 (1 6≡ −1 (mod 3)). Tato soustava proto řešení nemá. b) Každá z kongruencí jistě řešitelná je. Moduly obou kongruencí jsou spolu nesoudělné, (29,47)=1. Platí proto kongruence 3 ≡ 5 (mod 1). Z toho plyne, že tato soustava řešení má. ◦ Příklad 4.15 n 2 Rozhodněte, pro která přirozená čísla n je číslo 22 − 2n dělitelné sedmi. Řešení Podle věty 3.7 je n

22 ≡ 2n

2

(mod m) ⇐⇒ 2n ≡ n2

(mod 3).

Číslo 3 je v tomto případě řád čísla 2 modulo 7. Kongruenci ještě můžeme upravit: (−1)n ≡ n2

(mod 3).

Nyní je vidět, že na levé straně kongruence můžeme dostat buď +1 nebo -1, avšak na pravé straně můžeme dostat pouze kladná čísla. Musí proto být n sudé n ≡ 0 (mod 2). Abychom i na pravé straně kongruence dostali jedničku, musí být n ≡ ±1

(mod 3).

Dostáváme tak dvě soustavy dvou lineárních kongruencí o jedné neznámé. První n ≡ 0 (mod 2) n ≡ +1 (mod 3) a druhou n ≡ 0 (mod 2) n ≡ −1 (mod 3). 49



Jejich vyřešením dostaneme dva výsledeky, a to n ≡ 4 (mod 6), n ≡ 2 (mod 6). ◦ Příklad 4.16 Rozhodněte, pro která přirozená čísla n je číslo n · 2n + 1 dělitelné sedmi. Řešení Hledáme taková n, pro která platí n · 2n ≡ −1

(mod 7).

Řád čísla 2 modulo 7 je 3. Rozdělme nyní výpočet do tří skupin v závislosti na n: 1. n ≡ 0 (mod 3) Pokud je n kongruentní s nulou, pak musí podle věty 3.7 platit 2n ≡ 20 = 1 (mod 7). Když dáme tuto kongruenci dohromady se zadanou, dostaneme, že hledané n musí splňovat n · 1 ≡ −1

(mod 7),

neboli n·1≡6

(mod 7).

Dostáváme, že n musí být tvaru n≡6

(mod 7).

Dejme nyní oba požadavky na tvar dohromady. Dostaneme jednoduchou soustavu kongruencí n≡0 n≡6

(mod 3) (mod 7).

n≡6

(mod 21).

Soustava má řešení

50



2. n ≡ 1 (mod 3) Opět podle věty 3.7 musí platit 2n ≡ 21 = 2 (mod 7). Nahrazením výrazu 2n v zadané kongruenci dostaneme n · 2 ≡ −1

(mod 7),

neboli n·2≡6

(mod 7),

n≡3

(mod 7).

po jednoduché úpravě

Neznámá n tak musí vyhovovat soustavě n≡1 n≡3

(mod 3) (mod 7).

Řešením je n ≡ 10 (mod 21). 3. n ≡ 2 (mod 3) I nyní musí platit, že 2n ≡ 22 = 4 (mod 7). Nahrazením v původní kongruenci dostaneme n · 4 ≡ −1

(mod 7).

Kongruenci vyhovuje n tvaru n≡5

(mod 7).

Protože n musí splňovat i první kongruenci, musí být řešením soustavy: n≡2 n≡5

(mod 3) (mod 7).

Vyřešením obdržíme n ≡ 19 (mod 21). 51


Kongruence vyšších stupňů

Řešením jsou tedy taková n, pro která platí n ≡ 6 (mod 21) nebo n ≡ 10

(mod 21) nebo n ≡ 19 (mod 21). ◦

4.7


Při řešení kongruencí o jedné neznámé stojí v obecnějším případě na obou stranách mnohočleny téže proměnné x. Kongruenci můžeme snadno převést na tvar F (x) ≡ 0

(mod m),

kde F (x) je mnohočlen s celočíselnými koeficienty a m ∈ N. Věta 4.4. Pro libovolný mnohočlen F (x) s celočíselnými koeficienty, přirozené číslo m a celá čísla a, b taková, že a ≡ b (mod m), platí F (a) ≡ F (b) (mod m). Díky této větě víme, že při řešení nám pouze stačí nalézt všechna celá čísla a, 0 ≤ a < m, pro která platí F (a) ≡ 0 (mod m). Řešením pak jsou všechna x kongruentní s takovými a. Příklad 4.17 Řešte kongruenci 2x3 ≡ 5 (mod 7). Řešení Nejprve kongruenci upravíme odečtením pětky od obou stran do tvaru 2x3 − 5 ≡ 0 (mod 7). Spočítáme nyní hodnoty polynomu pro čísla x = 0 . . . 6. Označme F (x) = 2x3 − 5, pak platí F (0) = 2 · 0 − 5 = −5, F (1) = 2 · 1 − 5 = −3, F (2) = 2 · 23 − 5 = 11 ≡ 4 (mod 7), F (3) = 2 · 33 − 5 = 2 · 3 · 9 − 5 ≡ 6 · 2 − 5 ≡ 0 (mod 7), F (4) = 2 · 43 − 5 = 2 · 4 · 16 − 5 ≡ 1 · 2 − 5 ≡ 4 (mod 7), F (5) = 2 · 53 − 5 = 2 · 5 · 25 − 5 ≡ 3 · 4 − 5 ≡ 0 (mod 7) F (6) = 2 · 63 − 5 = 2 · (−1)3 − 5 = −7 ≡ 0 (mod 7). 52



Z výše uvedeného je vidět, že daný polynom je kongruentní s nulou (modulo 7), když za x dosadíme 3, 5 nebo 6. Podle věty 4.4 tak dostáváme, že řešením jsou všechna x tvaru: x ≡ 3 (mod 7), x ≡ 5 (mod 7), x ≡ 6 (mod 7). ◦ Příklad 4.18 Řešte kongruenci 3 · x4 − 2 · x3 + x − 4 ≡ 0 (mod 9). Řešení Stejně jako v předchozím příkladě budeme zjišťovat, pro která x je polynom kongruentní s nulou modulo 9. F (0) ≡ 5 F (1) ≡ 7 F (2) ≡ 3 F (3) ≡ 8 F (4) ≡ 1 F (5) ≡ 6 F (6) ≡ 2 F (7) ≡ 4 F (8) ≡ 0

(mod (mod (mod (mod (mod (mod (mod (mod (mod

9) 9) 9) 9) 9) 9) 9) 9) 9)

Vidíme, že řešením kongruence jsou taková x, pro která platí x ≡ 8 (mod 9).

◦

Z výše uvedeného plyne, že tato metoda řešení je poměrně pracná, především pak pro větší moduly. Pokud je modulem m velké číslo, můžeme si pomoci tak, že modul rozložíme na součin menších čísel m = m1 · . . . mk a místo jedné kongruence řešíme soustavu kongruencí podle modulů m1 , . . . , mk . Příklad 4.19 Řešte kongruenci x5 + 2 ≡ 0 (mod 35). Řešení Má-li být výraz x5 + 2 dělitelný číslem 35, musí být dělitelný jak číslem 5, tak číslem 7. Řešme tedy soustavu dvou kongruencí x5 + 2 ≡ 0 (mod 5) a x5 + 2 ≡ 0 (mod 7). F (0) ≡ 2 F (1) ≡ 3 F (2) ≡ 4 F (3) ≡ 0 F (4) ≡ 1

(mod (mod (mod (mod (mod

5) 5) 5) 5) 5)

F (0) ≡ 2 F (1) ≡ 3 F (2) ≡ 6 F (3) ≡ 0 F (4) ≡ 4 F (5) ≡ 5 F (6) ≡ 1 53

(mod (mod (mod (mod (mod (mod (mod

7) 7) 7) 7) 7) 7) 7)



Z první kogruence dostáváme, že x ≡ 3 (mod 5), z druhé, že x ≡ 3 (mod 7). Společným řešením obou kongruencí je x ≡ 3 (mod 35). Toto x je proto také řešením zadané kongruence.

◦

Příklad 4.20 Řešte kongruenci x6 − 1 ≡ 0 (mod 35). Řešení Modul je možné opět rozložit na součin čísel 5 a 7. Dostáváme tak opět dvě soustavy kongruencí, které řešíme zvlášť. F (0) ≡ 4 F (1) ≡ 0 F (2) ≡ 3 F (3) ≡ 3 F (4) ≡ 0


5) 5) 5) 5) 5)

F (0) ≡ 6 F (1) ≡ 0 F (2) ≡ 0 F (3) ≡ 0 F (4) ≡ 0 F (5) ≡ 0 F (6) ≡ 0

První kongruenci splňují dvě x, a to x≡1 x≡4

(mod 5), (mod 5).

Druhou kogruenci splňují všechna x taková, že x≡1 x≡2 x≡3 x≡4 x≡5 x≡6

(mod (mod (mod (mod (mod (mod 54

7), 7), 7), 7), 7), 7).

(mod (mod (mod (mod (mod (mod (mod

7) 7) 7) 7) 7) 7) 7)


Úlohy a cvičení

Takové x, které je řešením zadané kongruence, musí splňovat některou z první kongruence a zároveň některou z druhé, tedy kteroukoliv z následujících soustav x≡1 x≡1

(mod 5) (mod 7)

x ≡ 1 (mod 5) x ≡ 2 (mod 7)

x ≡ 1 (mod 5) x ≡ 3 (mod 7)

x≡1 x≡4

(mod 5) (mod 7)

x ≡ 1 (mod 5) x ≡ 5 (mod 7)

x ≡ 1 (mod 5) x ≡ 6 (mod 7)

x≡4 x≡1

(mod 5) (mod 7)

x ≡ 4 (mod 5) x ≡ 2 (mod 7)

x ≡ 4 (mod 5) x ≡ 3 (mod 7)

x≡4 x≡5

x ≡ 4 (mod 5) x ≡ 6 (mod 7).

x ≡ 4 (mod 5) x ≡ 4 (mod 7)

(mod 5) (mod 7)

Řešením jednotlivých soustav jsou tato x: x≡1

(mod 35)

x ≡ 16 (mod 35)

x ≡ 11

(mod 35)

x ≡ 26 (mod 35)

x ≡ 29

(mod 35)

x≡9

x ≡ 4 (mod 35)

(mod 35)

x ≡ 19 (mod 35)

x ≡ 31

(mod 35)

x≡6

(mod 35)

x ≡ 24

(mod 35)

x ≡ 34 (mod 35).

Zapíšeme-li výsledek přehledněji, dostáváme, že řešením příkladu jsou taková x, pro která platí x ≡ a (mod 35), kde a ∈ {1, 4, 6, 9, 11, 16, 19, 24, 26, 29, 31, 34}. ◦

4.8

Úlohy a cvičení

Řešte kongruence: (a) 3x3 ≡ 1 (mod 5), (b) x4 − x3 + x + 1 ≡ 0 (mod 11), (c) x2 − 23 ≡ 0 (mod 77), (d) x3 − 2x2 + 8x ≡ 0 (mod 28). [ (a) x ≡ 3 (mod 5) ] [ (b) x ≡ 2 (mod 11), x ≡ 5 (mod 11) ] [ (c) x ≡ a (mod 77), a ∈ {10, 32, 45, 67} ] [ (c) x ≡ a (mod 28), a ∈ {0, 8, 14, 22} ] 55


4.9



Příklad 4.21 Řešte kongruenci x3 + x + 3 ≡ 0 (mod 169). Řešení Protože 169 = 132 , musí takové x, které je řešením dané kongruence modulo 169, být i řešením stejné kongruence modulo 13. Zjistěme proto nejprve řešení kongruence x3 + x + 3 ≡ 0 (mod 13). Budeme postupovat běžným způsobem: F (0) = 3 F (1) = 5 F (2) ≡ 0 F (3) ≡ 7 F (4) ≡ 6 F (5) ≡ 3 F (6) ≡ 4 F (7) ≡ 2 F (8) ≡ 3 F (9) ≡ 0 F (10) ≡ 12 F (11) ≡ 6 F (12) ≡ 1

(mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13).

Jako řešení tak připadají v úvahu pouze čísla kongruentní s čísly 2 a 9 modulo 13. Parametricky můžeme tato x vyjádřit jako: x = 13t + 2,

x = 13t + 9,

t ∈ (Z).

Toto parametrické vyjádření teď můžeme dosadit do původní kongruence. 1. Pro x = 13t + 2 dostaneme (13t + 2)3 + (13t + 2) + 3 ≡ 0 (mod 169), (169t2 + 52t + 4) · (13t + 2) + 13t + 2 + 3 ≡ 0 (mod 169), (52t + 4) · (13t + 2) + 13t + 5 ≡ 0 (mod 169), 4 · 169t + 104t + 52t + 8 + 13t + 5 ≡ 0 (mod 169), 169t ≡ −13 (mod 169), 0 ≡ −13 (mod 169). Tato kongruence ovšem nemá řešení. 56



2. Pro x = 13t + 9 dostaneme (13t + 9)3 + (13t + 9) + 3 ≡ 0 (169t2 + 18 · 13t + 81) · (13t + 9) + 13t + 9 + 3 ≡ 0 18 · 13 · 9t + 81 · 13t + 81 · 9 + 13t + 12 ≡ 0 78t + 39t + 53 + 13t + 12 ≡ 0 130t + 65 ≡ 0


169), 169), 169), 169), 169).

Tuto kongruenci můžeme vyřešit 10t ≡ −5 (mod 13), 2t ≡ −1 (mod 13), t ≡ 6 (mod 13).

Tento jediný výsledek dosadíme do parametrického vyjádření x, x = 13 · (13s + 6) + 9 = 169s + 87, neboli x ≡ 87 (mod 169). Tímto jsme obdrželi finální řešení tohoto příkladu.

◦

Příklad 4.22 Řešte kongruenci x2 + x − 2 ≡ 0 (mod 49). Řešení pokud má kongruence platit modulo 49, musí platit i modulo 7. Vyřešme ji proto nejprve modulo 7. F (0) = −2 F (1) = 0 F (2) = 4 F (3) ≡ 3 (mod F (4) ≡ 4 (mod F (5) ≡ 0 (mod F (6) ≡ 5 (mod

7) 7) 7) 7)

Dostáváme, že hledané x musí být tvaru x = 7t + 1 nebo x = 7t + 5, kde t ∈ Z. Dosadíme teď za x do zadání. 57


Primitivní kořeny

1. Pro x = 7t + 1 dostaneme (7t + 1)2 + (7t + 1) − 2 ≡ 0 (mod 49), 49t2 + 14t + 1 + 7t − 1 ≡ 0 (mod 49), 21t ≡ 0 (mod 49). Kongruenci vyřešíme 21t ≡ 0 3t ≡ 0 t≡0

(mod 49), (mod 7), (mod 7).

Dosazením do parametrického vyjádření x dostáváme x = 7(7s) + 1 = 49s + 1 neboli x ≡ 1

(mod 49).

2. Pro x = 7t + 5 má platit (7t + 5)2 + (7t + 5) − 2 ≡ 0 (mod 49), 49t2 + 21t + 25 + 7t + 3 ≡ 0 (mod 49), 28t + 28 ≡ 0 (mod 49). Kongruence má řešení pro t ≡ 6 (mod 7). Jestliže dosadíme do parametrického vyjádření za x, dostaneme x = 7(7s + 6) + 5 = 49s + 47 neboli x ≡ 47 (mod 49). Daný příklad má dvě řešení, a to x ≡ 1 (mod 49) a x ≡ 47 (mod 49).

4.10

◦

Primitivní kořeny

Než se podíváme na další typy lineárních kongruencí, řekneme si něco o tzv. primitivních kořenech. Definice 4.3. Má-li číslo a ∈ Z, (a, m) = 1 řád ϕ(m) modulo m, nazývá se primitivní kořen modulo m. Primitivním kořenem ja takové číslo, pro které neexistuje žádný menší exponent než ϕ(m) takový, že po umocnění na tento exponent dostaneme jedničku (modulo m). Příklad 4.23 Pro modul m = 7 platí ϕ(7) = 6. 58

4. Kongruence o jedné neznámé x x1 2 2 3 3

x2 4 2

Primitivní kořeny

x3 1 6

x4 2 4

x5 4 5

x6 1 1

Číslo 2 není primitivní kořen modulo 7. Jeho řád je totiž 3 a to je méně než 6. Číslo 3 je primitivní kořen modulo 7, protože řád čísla 3 modulo 7 je roven šesti. Primitivní kořen však vůbec existovat nemusí. Příklad 4.24 Pro m = 8 dostáváme ϕ(8) = 4. Možnými primitivními kořeny jsou pouze lichá čísla menší než 8, protože sudé číslo umocněné na lib. exponent, mínus sudý modul, nemůže dát lichou jedničku. x 1 3 5 7

x1 1 3 5 7

x2 1 1 1 1

x3 1 3 5 7

x4 1 1 1 1

Z tabulky je vidět, že neexistuje primitivní kořen modulo 8. Věta 4.5 (O existenci primitivního kořene). Nechť m ∈ N, m > 1. Primitivní kořeny existují modulo m, právě když m je tvaru 2, 4, pl , 2pl , kde p je liché prvočíslo, l ∈ N. Nalézt primitivní kořen je obecně obtížný úkol. Nápomocny nám mohou být následující věty. Věta 4.6. Nechť p je liché prvočíslo, l ≥ 1. Nechť m je rovno pl nebo 2pl . Zapišme ϕ(m) = q1α1 · · · · · qkαk . K tomu, aby číslo g ∈ Z, (g, m) = 1 bylo primitivním kořenem modulo m, je nutné a stačí, aby g nesplňovalo žádnou z kongruencí: g

ϕ(m) q1

≡ 1 (mod m), . . . , g

ϕ(m) qk

≡ 1 (mod m).

Věta 4.7. Nechť p je liché prvočíslo, g je primitivní kořen modulo pl , l ∈ N. Pak liché z čísel g, g + pl je primitivní kořen modulo 2pl .

Příklad 4.25 Nalezněte primitivní kořen modulo 41. 59


Primitivní kořeny

Řešení Číslo 41 je prvočíslo. Podle věty 4.5 proto primitivní kořen existuje. Nejprve spočítame Eulerovu funkci pro číslo 41 ϕ(41) = 40 = 23 · 5. Nyní podle věty 4.6 víme, že pro primitivní kořen g musí platit: g 8 6≡ 1 (mod 41), g 20 6≡ 1 (mod 41). Nyní nezbývá než postupně brát čísla od 2 do 40 a ověřovat, zda platí nebo neplatí tyto dvě kongruence. 1. Zkusíme g = 2. 28 = 25 · 23 ≡ −9 · 8 ≡ 10 (mod 41), 2

220 = 28 · 24 ≡ 100 · 16 ≡ 18 · 16 = 288 ≡ 1 (mod 41). Protože číslo 2 splňuje druhou kongruenci, nemůže být primitivním kořenem. 2. Zkusíme g = 3. 38 = (34 )2 ≡ (−1)2 = 1 (mod 41). Číslo 3 splňuje již první kongruenci, nemůže proto být primitivním kořenem. 3. Zkusíme g = 4. 48 = (22 )8 = (28 )2 ≡ 102 ≡ 18 (mod 41), 420 = 240 = (220 )2 ≡ 1 (mod 41). Číslo 4 splňuje druhou kongruenci, nemůže proto být primitivním kořenem. 4. Zkusíme g = 5. 58 = (53 )2 · 52 ≡ 22 · 52 ≡ 18 (mod 41), 520 = (53 )6 · 52 ≡ 26 · 52 ≡ −9 · 2 · 25 ≡ 1

(mod 41).

Číslo 5 splňuje druhou kongruenci, nemůže proto být primitivním kořenem. 5. Zkusíme g = 6. 68 = 28 · 38 ≡≡ 10 · 1 = 10 (mod 41), 620 = 220 · 320 ≡ −1 (mod 41). Číslo 6 nesplňuje žádnou z daných dvou kongruencí. 60


Primitivní kořeny

Číslo 6 je primitivní kořen modulo 41.

◦

Příklad 4.26 Spočítejte primitivní kořen modulo 7. Řešení Protože ϕ(7) = 6 a protože řád čísla musí dělit 6, budeme zkoušet čísla od 2 do 6 a zjištovat, které z nich po umocnění na 2 ani 3 není kongruentní s jedničkou modulo 7. 22 = 4 23 ≡ 1 (mod 7) 2 není primitivní kořen modulo 7 32 ≡ 2 (mod 7) 33 ≡ 6 (mod 7) Primitivní kořen modulo 7 je 3.

◦

Příklad 4.27 Spočítejte primitivní kořen modulo 29. Řešení Jistě je ϕ(29) = 28 = 22 · 7. Podle věty 4.6 nesmí primitivní kořen modulo 29 splňovat žádnou z kongruencí g 14 ≡ 1 (mod 29) g 4 ≡ 1 (mod 29). Budeme postupně zkoušet, které číslo splňuje naši podmínku. (27 )2 ≡ 122 ≡ 28 6≡ 1 (mod 29) 24 ≡ 16 6≡ 1 (mod 29). Protože číslo 2 nesplňuje žádnou z obou daných kongruencí, je primitivním kořenem modulo 29. ◦

61


4.11

Binomické kongruence


Podívejme se nyní na speciální typ kongruencí vyšších řádů. Definice 4.4. Binomickou kongruecí nazýváme kongruenci tvaru xn ≡ a (mod m), kde a ∈ Z, m ∈ N.

Poznámka. Lze ukázat, že pokud je (a, m) 6= 1, můžeme daný příklad převést tak, aby platilo (a, m) = 1. Omezíme se proto jen na příklady, v nichž je (a, m) = 1. Věta 4.8 (O řešitelnosti binom. kongruencí). Nechť existují primitivní kořeny modulo m, kde m ∈ N. Pak kongruence xn ≡ a (mod m), kde a ∈ Z ϕ(m) a (a, m) = 1, je řešitelná právě tehdy, když platí a d ≡ 1 (mod m), d = (n, ϕ(m)). Pokud je řešitelná, má právě d řešení. Při řešení binomických kongruencí se nejčastěji používá následující postup. Nejprve ověříme zda a kolik má daná kongruence řešení. Poté si zavedeme substituci x ≡ gy

(mod m),

b

(mod m),

a≡g

kde g je primitivní kořen modulo m. Pak podle věty 3.7 platí ekvivalence: (g y )n ≡ g b

(mod m)

⇐⇒

n · y ≡ b (mod ϕ(m)).

Tímto převedeme binomickou kongruenci na řešení lineární kongruence. Tu již řešit umíme. Na závěr zpětně dosadíme. Příklad 4.28 Řešte binomickou kongruenci x3 ≡ 3 (mod 17). Řešení Abychom ověřili zda má kongruence řešení, musíme nejprve najít primitivní kořen modulo 17. Ten budeme potřebovat i k následnému řešení kongruence. Snadno bychom ověřili, že 3 je primitivní kořen modulo 17. Protože (3,16)=1 a 316 ≡ 1 (mod 17) (podle Fematovy věty), bude kongruence mít jedno řešení. Podíváme se nyní na samotné řešení. Zaveďme substituci x ≡ 3a 3 ≡ 31

(mod 17), (mod 17). 62



Dosadíme do původní kongruence (3a )3 = 33a ≡ 31

(mod 17).

Podle věty 3.7 tato kongruence platí právě tehdy, když platí kongruence 3a ≡ 1

(mod 16).

Tuto kongruenci vyřešíme: 3a ≡ −15 (mod 16) a ≡ −5 ≡ 11 (mod 16), můžeme také psát

a = 16k + 11, k ∈ Z.

Nyní dosadíme zpět do substituce x ≡ 316k+11 ≡ 311 (mod 17), x ≡ 7 (mod 17). Řešením jsou všechna x ≡ 7 (mod 17).

◦

Příklad 4.29 Řešte kongruenci x3 ≡ 1 (mod 17). Řešení Z předchozího příkladu již víme, že 3 je primitivní kořen modulo 17. Protože (3,16)=1 a 116 ≡ 1 (mod 17), bude mít daná kongruence jedno řešení. Již na první pohled je zřejmé, že tím řešením je x ≡ 1 (mod 17). ◦ Příklad 4.30 Řešte kongruenci x10 ≡ 10 (mod 13). Řešení Nejprve rozhodneme, zda má vůbec kongruence řešení a pokud ano, tak kolik. ϕ(13) = 12 = 22 · 3 (10, 12) = 2 12

10 2 = 106 ≡ 93 ≡ 1 63

(mod 13)



Právě jsme ukázali, že daná kongruence je řešitelná a bude mít dvě řešení. Při tomto tvrzení se opíráme i o to, že víme, že k prvočíselnému modulu vždy existuje primitivní kořen. Pojďme jej tedy nyní najít. Budeme postupně brát čísla od 2 do 12 a ověřovat, zda je toto číslo primitivním kořenem modulo 13. K ověření můžeme použít větu 4.6. My však raději zjistíme zbytky po umocnění daného čísla na všechny exponenty 1, . . . , 12, bude se nám to hodit později. Zkusíme g = 2. 21 22 23 24 25 26 27 28 29 210 211 212

=2 =4 =8 ≡3 ≡6 ≡ 12 ≡ 11 ≡9 ≡5 ≡ 10 ≡7 ≡1

(mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13) (mod 13).

Zjistili jsme, že řád čísla 2 modulo 13 je 12. Číslo 2 je proto primitivním kořenem modulo 13. Přistupme nyní k samotnému řešení kongruence. Zavedeme substituci x ≡ 2a (mod 13), 10 ≡ 210 (mod 13). Zjistit, na jaký exponent máme umocnit primitivní kořen, abychom dostali jiné dané číslo je obecně problém. Jak jsme tedy zjitili, že platí 10 ≡ 210 (mod 13)? To jsme právě vyčetli z předchozího výpočtu. Teď dosadíme do zadané kongruence: (2a )10 = 210a ≡ 210

(mod 13).

Z věty 3.7 víme, že je tato kongruence splněna, právě když platí 10a ≡ 10 (mod 12). Kongruenci vyřešíme 5a ≡ 5 a≡1 64

(mod 6), (mod 6).


Úlohy a cvičení

Řešení můžeme zapsat také parametricky: a = 6k + 1, k ∈ Z. Více se nám ale bude hodit zapsat řešení jako dva výsledky: a = 12k + 1, a = 12k + 7,

k ∈ Z, k ∈ Z.

Dosadíme za a do naší substituce. Z prvního řešení dostaneme: x ≡ 2a = 212k+1 = 2 · 212k ≡ 2 (mod 13),

k ∈ Z.

Pro druhé řešení obdržíme: x ≡ 2a = 212k+7 = 27 · 212k ≡ 27 ≡ 11 (mod 13),

k ∈ Z.

Řešením zadané kongruence jsou taková x, pro něž platí x ≡ 2 (mod 13) nebo x ≡ 11 (mod 13). ◦

4.12

Úlohy a cvičení

1. Řešte kongruence: (a) x7 ≡ 8 (mod 13) (b) x5 ≡ 11 (mod 17) (c) x6 ≡ 1 (mod 10). [ (a) x ≡ 5 (mod 13) ] [ (b) x ≡ 7 (mod 17) ] [ (c) x ≡ 1 (mod 10), x ≡ 9 (mod 10) ]

4.13


Příklad 4.31 Určete počet řešení kongruence 3x12 ≡ 31 (mod 41). Řešení Protože 41 je prvočíslo, bude k němu existovat primitivní kořen. Abychom mohli

65



rozhodnout o řešitelnosti dané kongruence, musíme ji nejprve upravit do vhodného tvaru: 3x12 ≡ 31 (mod 41), 3x12 ≡ 72 (mod 41), x12 ≡ 24 (mod 41). Také víme, že ϕ(41) = 40, (12, 40) = 4. Nyní se podíváme, s čím je kongruentní výraz 2410 modulo 41. 2410 = (242 )5 ≡ 25 ≡ 32 6≡ 1

(mod 41)

Podle věty 4.8 nemá daná kongruence řešení.

◦

Příklad 4.32 Určete počet řešení kongruence 7x17 ≡ 11 (mod 41). Řešení Budeme postupovat stejně jako v předchozím příkladě. Nejprve kongruenci upravíme:

6 · 7x17

7x17 ≡ 11 (mod 41), = 42x17 ≡ 6 · 11 = 66 (mod 41), x17 ≡ 25 (mod 41).

Dále platí ϕ(41) = 40, (17, 40) = 1. Protože je podle Fermatovy věty 2540 ≡ 1 (mod 41), je také podle věty 4.8 kongruence řešitelná a má jedno řešení. ◦

66

Kapitola 5 E-learning Pod často diskutovaným pojmem e-learning se ukrývá nové pojetí výuky. Při studiu se využívá výpočetní techniky, e-mailu a internetu. Učitel a žák spolu komunikují elektronicky. Studijní kurzy jsou tvořeny pomocí elektronických multimediálních nástrojů. E-learning má obvykle dva cíle. Prvním cílem je rozvinout distanční studium, nahradit zde chybějícího učitele a dát studentům dobré nástroje pro úspěšné zvládnutí kurzu. Tento úkol se řeší pomocí propracovaných elektronických studijních textů, nástrojů na procvičování, agend pro komunikaci s tutorem a spolužáky a různých hodnotících či statistických aplikací. Druhým cílem e-learningu je podpora bežné formy výuky. I když se s e-learningem může každý v informačním systému Masarykovy univerzity setkat již delší dobu, dovolím si říci, že jsou tyto aplikace spíše na začátku svého vývoje. Větší kroky pro rozvoj e-learningu v ISu byly podniknuty teprve před pár měsíci na počátku tohoto roku. Informační systém MU nabízí několik nástrojů k tvorbě e-learningových kurzů. Především zde najdeme správce souborů, pomocí kterého můžeme nahrávat do systému elektronické materiály a dále s nimi pracovat. Najdeme zde i nástroje pro vytváření sad testových otázek. To je, řekl bych, klíčový nástroj. S pomocí již hotových sad otázek se dají tvořit různá bodovaná i nebodovaná cvičení, průzkumy, cvičná zkoušení, oživené texty a mnoho dalšího. Celý balík souborů pak můžeme uspořádat do interaktivní osnovy a zveřejnit studentům jako celek. K tomu všemu lze nastavit práva pro čtení, jež se mohou měnit i v průběhu času. Systém také obsahuje nástroje pro provoz tzv. poskytovny, webu, složek se sdílenými dokumenty, diskuzních fór a mnoho dalších užitečných aplikací. Protože se domnívám, že je e-learning velice užitečný, vytvořil jsem tuto diplomovou práci jako elektronický kurz zpracovaný do konkrétní interaktivní osnovy. Najít ji můžete v autentizované části ISu na adrese https://is.muni.cz/ auth/el/1431/jaro2005/M6520/index.qwarp. Celá osnova je členěna na kapitoly podle tématu. Každá kapitola obsahuje soubor ve formátu PDF s teoretickým výkladem. Podle typu příkladů je u některých témat pomocí nástroje Oživený text vytvořeno cvičení s příklady. Toto řešené cvičení se skládá ze zadání a osnovy pro 67

5. E-learning

řešení. Po kliknutí na klíč se jednotlivé části řešení rozbalují a zobrazují tak detailní postup. Většina kapitol má i nějaké cvičné neřešené úlohy, které se sestavují ze sady otázek. Po zodpovězení dotazníku je student ohodnocen a je mu ukázáno, které úkoly vyřešil správně a které ne. U všech odpovědí je zobrazen správný výsledek.

68

Seznam použité literatury [1] HERMAN J., KUČERA R., ŠIMŠA J., Metody řešení matematických úloh I, Masarykova univerzita v Brně, Brno 2001 [2] SIERPINSKI W., 250 Problems in elementary number theory, PWN-Polish scientific publishers, Waršava 1970 [3] BULANT M., Algebra 2 - Teorie čísel http://www.math.muni.cz/~bulik/vyuka/Algebra-2/alg2-screen.pdf [4] FREEPEDIA, Number theory http://en.freepedia.org/Number_theory.html

69

TEORIE ČÍSEL sbírka příkladů. Diplomová práce

Recommend Documents