Elementární teorie čísel Michal Bulant Ústav matematiky a statistiky, Přírodovědecká fakulta, rykova univerzita, kotlářská 2, 611 37 brno Email address: bulant@math.muiii.cz Abstrakt. Na této přednášce se budeme zabývat úlohami o celých číslech. Převážně v nich půjde o dělitelnost celých čísel, popřípadě o řešení rovnic v oboru celých nebo přirozených čísel. Ačkoli jsou přirozená a konec konců i celá čísla v jistém smyslu nejjednodušší matematickou strukturou, zkoumání jejich vlastností postavilo před generace matematiků celou řadu velice obtížných problémů. Často jsou to problémy, které je možno snadno formulovat, přesto však dodnes neznáme jejich řešení. Uveďme některé z nej známějších: • problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo (tato otázka stále patří mezi otevřené problémy - v roce 2013 ale Yitang Zhang publikoval důkaz slibného tvrzení, že pro některé n < 7 ■ 107 existuje nekonečně mnoho dvojic prvočísel lišících se právě o n. Viz Y. Zhang, Bounded gaps between primes, Annals of Mathematics, 2013). • prvočísla Sophie Germainové - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i 2p + 1 je prvočíslo, • problém existence lichého dokonalého čísla - tj. čísla, jehož součet dělitelů je roven dvojnásobku tohoto čísla, • Goldbachova hypotéza - jde o to rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel, • klenot mezi problémy teorie čísel velkou Fermatovu včtu (Fermaťs Last Theorem) - jde o otázku, zda existují přirozená čísla n, x, y, z tak, že n > 2 a platí xn + yn = zn; Pierre de Fermat ji formuloval kolem roku 1637, vyřešil ji po značném úsilí celých generací (a s pomocí výsledků z mnoha oblasti matematiky) Andrew Wiles až v roce 1995. Tento text výrazně čerpá z knih [2], [4] a [5], pro zájemce o bližší seznámení s některými tématy doporučujeme knihu [3], dostupnou v knihovně PřF MU. Obsah 1. Základní pojmy 6 1.1. Úvodní poznámky 6 1.2. Dělitelnost 6 1.3. Největší společný dělitel a nejmenší společný násobek 10 1.4. Dělitelé a násobky mnoha čísel 15 1.5. Nesoudělnost 17 2. Prvočísla 19 2.1. Dokonalá čísla a jejich vztah k prvočíslům 25 2.2. Rozložení prvočísel 27 3. Kongruence 37 3.1. Základní vlastnosti kongruencí 38 3.2. Aritmetické funkce 44 3.3. Eulerova funkce (p 47 3.4. Malá Fermatova věta, Eulerova věta 50 4. Řešení kongruencí o jedné neznámé 58 4.1. Lineární kongruence o jedné neznámé 60 4.2. Soustavy lineárních kongruencí o jedné neznámé 64 4.3. Kongruence vyšších stupňů 72 4.4. Kongruence s prvočíselným modulem 79 Home Page Title Page 4.5. Binomické kongruence a primitivní kořeny 80 4.6. Kvadratické kongruence a Legendreův symbol 94 4.7. Jacobiho symbol 104 4.8. Aplikace Legendreova a Jacobiho symbolu. 107 5. Aplikace teorie čísel 112 5.1. Výpočetní aspekty teorie čísel 112 5.2. Testy na složenost 116 5.3. Testy na prvočíselnost 122 5.4. Hledání dělitele 126 5.5. Kryptografie s veřejným klíčem 126 6. Diofantické rovnice 131 6.1. Lineární diofantické rovnice 132 6.2. Diofantické rovnice lineární vzhledem k některé neznámé 137 6.3. Rovnice jiného tvaru 142 6.4. Řešení diofantických rovnic pomocí nerovností 145 6.4.1. Některé nerovnosti 150 6.5. Řešení diofantických rovnic metodou rozkladu 154 6.5.1. Pythagorova rovnice 157 6.6. Řešitelnost diofantických rovnic 159 6.6.1. Neexistence řešení 160 6.6.2. Zmenšování ad absurdum 164 Contents 44 _«J. Page 4 of175 Go Back Full Screen Close Quit 1. Základní pojmy 1.1. Úvodní poznámky. V mnoha problémech je výhodné vyzkoušet chování algoritmů na reálných příkladech. K tomu lze využít SW nainstalovaný na počítačích Ústavu matematiky a statistiky. Doporučujeme zejména: • PARI-GP : specializovaný SW na teorii čísel, při výpočtech s většími čísly obvykle výrazně efektivnější než obecně orientované balíky. Spouští se příkazem gp. Nej důležitější příkazy: \q - ukončení, ? - help, ?? - kompletní uživatelský manuál, ?? tutorial - tutoriál pro úvodní seznámení. Viz také pari.math.u-bordeaux.fr. • SAGE: obecně koncipovaný open-source systém, který mj. zahrnuje interface do Pari-GP a díky jeho prostředí je tak výrazně usnadněna práce. Protože jeho vývoj řídí William Stein, odborník na teorii čísel, je tato část balíku jednoznačně nej propracovanější. Existuje rovněž mnoho výukových worksheetů. Spustit lze např. na http://sage.math.muiii.cz • Maple: vhodný zejména kvůli existenci mnoha výukových pracovních listů (worksheets, i pro teorii čísel), např. na www.mapleapps.com. 1.2. Dělitelnost. Definice. Ř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. Přímo z definice plyne několik jednoduchých tvrzení, jejichž důkaz přenecháváme čtenáři jako cvičení s návodem v [2, §12]: Číslo nula je dělitelné každým celým číslem; jediné celé číslo, které je dělitelné nulou, je nula; pro libovolné číslo a platí a | a; pro libovolná čísla a, b, c platí tyto čtyři implikace: a | b A b | c ==> a \ c (1) a | b A a \ c ==> a\b + c ř\ a\b — c (2) c 7^ 0 (a | 6 <=^ ac | 6c) (3) a\b A 6 > 0 a < b (4) příklad. Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem rz + 1. Řešení. Platí n2 — 1 = (rz + l)(n — 1), a tedy číslo rz + 1 dělí číslo n2 — 1. Předpokládejme, že rz + 1 dělí i číslo rz2 + 1. Pak ovšem musí dělit i rozdíl (rz2 + 1) — (rz2 — 1) = 2. Protože n G N, platí n +1 > 2, a tedy z rz +1 | 2 plyne rz +1 = 2, proto rz — 1. Uvedenou vlastnost má tedy jediné přirozené číslo 1. □ věta 1. (Věta o děleni celých ěísel se zbytkem) Pro libovolně zvolená čísla a G Z, m G N existují jednoznačně určená čísla g G Z, r G {0,1,..., rrz — 1} tak, že a — grrz + r. DŮKAZ. Dokažme nejprve existenci čísel q,r. Předpokládejme, že přirozené číslo m je dáno pevně a dokažme úlohu pro libovolné a £ Z. Nejprve budeme předpokládat, že a £ N0 a existenci čísel q,r dokážeme indukcí: Je-li 0 < a < m, stačí volit q — 0, r — a a rovnost a — qm + r platí. Předpokládejme nyní, že a > m a že jsme existenci čísel q1 r dokázali pro všechna o! £ {0,1, 2,..., a — 1}. Speciálně pro a' — a — m tedy existují q', r' tak, že a' — g'm + r' a přitom r; £ {0,1,..., m — 1}. Zvolíme-li q — q' + 1, r — r', platí a — a' + m — (g' + l)m + r' — + r, což jsme chtěli dokázat. Existenci čísel q1 r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < 0, pak ke kladnému číslu —a podle výše dokázaného existují q' £ Z, r' £ {0,1,..., m— 1} tak, že —a — g'm + r', tedy a — —q'm — r'. Je-li r' — 0, položíme r — 0, q — —g'; je-li r > 0, položíme r = m — r', q = —q' — 1. V obou případech a — q • m + r, a tedy čísla g, r s požadovanými vlastnostmi existují pro každé a £ Z, m £ N. Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla qi,q2 £ Z; 7*1, t2 £ {0,1,..., m — 1} platí a — gim + ri — + ^2- Úpravou dostaneme ri — r2 — — (?i)m> a tedy m | r\ — r2. Ovšem z 0 < r\ < m, 0 < r2 < m plyne —m < r\ — r2 < m, odkud podle (4) platí ri — r2 — 0. Pak ale i (q2 — qi)m — 0, a proto gi — q2, r± — r2. Čísla q, r jsou tedy určena jednoznačně. Tím je důkaz ukončen. □ Číslo q, resp. r z věty se nazývá (neúplný) podíl, resp. zbytek při dělení čísla a číslem m se zbytkem. Vhodnost obou názvů je zřejmá, přepíšeme-li rovnost a — mq + r do tvaru a r . r — — q H--, přitom 0 < — < 1. mm m Je vhodné též si uvědomit, že z věty 1 plyne, že číslo m dělí číslo a, právě když zbytek r je roven nule. příklad. Dokažte, že jsou-li zbytky po dělení čísel a, b g Z číslem m g N jedna, je jedna i zbytek po dělení čísla ab číslem m. Řešeni. Podle věty 1 existují s, í g Z tak, že a — srn + 1, = ŕra + 1. Vynásobením dostaneme vyjádření a6 — (5777, + l)(ím + 1) — [stm + 5 + í)m + 1 — + r, kde q — síra + s + í, r — 1, které je podle věty 1 jednoznačné, a tedy zbytek po dělení čísla ab číslem m je jedna. □ SW ukázka. Vydělením čísla 1234567890 číslem 321 se zbytkem dostáváme 3846005, zbytek 285 - jak vidíme v PARI: ? divremC1234567890,321) 7.2 = [3846005, 285] ~ nebo i jinak: ? 1234567890X321 7.3 = 3846005 ? 12345678907.321 7.4 = 285 1.3. Nej větší společný dělitel a nejmenší společný násobek. Definice. Mějme celá čísla ai,a2. Libovolné celé číslo m takové, že m \ a±, m | a2 (resp. a± | m, a2 | m) se nazývá společný dělitel (resp. společný násobek) čísel ai,a2. Společný dělitel (resp. násobek) m > 0 čísel ai,a2, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel a±, a2, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel d\, d2 a značí se (ai,a2) (resp. [ai,a2]). Poznámka. Přímo z definice plyne, že pro libovolné a, 6 G Z platí (a, 6) — (6, a), [a, b] — [6, a], (a, 1) — 1, [a, 1] — |a|, (a, 0) — |a|, [a, 0] —0. Ještě však není jasné, zda pro každou dvojici a, b £ Z čísla (a, 6) a [a, 6] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi, m2 G N0 totiž podle (4) platí, že pokud m\ \ m2 a zároveň m2 | mi, je nutně m\ — m2. Důkaz existence čísla (a, 6) podáme (spolu s algoritmem jeho nalezení) ve větě 2, důkaz existence čísla [a, b] a způsob jeho určení pak popíšeme ve větě 4. VĚTA 2. (Euklidův algoritmus) Nechí ai,a2 jsem přirozená čísla. Pro každé n > 3; ]?ro &čere an_i 7^ 0; označme an zbytek po dělení čísla an_2 číslem an-\. Pak po konečném počtu kroků dostaneme — 0 a platí a^-x — (ai, a2). DŮKAZ. Podle věty 1 platí a2 > a3 > > .... Protože jde o nezáporná celá čísla, je každé následující alespoň o 1 menší než předchozí, a proto po určitém konečném počtu kroků dostáváme — 0, přičemž cik-i ^ 0. Z definice čísel an plyne, že existují celá čísla qi, q2,..., qk-2 tak, že di = qi • Ci2 + Ci3, Ci2 = 0 čísel ai, a2,..., an, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) těchto čísel, se nazývá největší společný dělitel (resp. nejmenši společný násobek) čísel a±, a2,..., an a značí se (ai, a2,..., an) (resp. [ai,a2,... ,an]). Snadno se přesvědčíme, že platí (ai,..., an_i, an) = ((ai,..., an_i), an), (6) ]• (7) Největší společný dělitel (ai,..., an) totiž dělí všechna čísla ai,..., an, a tedy je společným dělitelem čísel ai, ..., an_i, a proto dělí i největšího společného dělitele (ai,..., on_i), tj. (ai,..., an) | ((ai,..., on_i), an). Naopak největší společný dělitel čísel (ai,..., an_i), an musí kromě čísla an dělit i všechna čísla a±,..., an_i, protože dělí jejich největšího společného dělitele, a proto ((ai,..., on_i), an) | (ai,..., an). Dohromady dostáváme rovnost (6) a zcela analogicky se dokáže (7). Pomocí (6) a (7) snadno dokážeme existenci největšího společného dělitele i nej menšího společného násobku libovolných n čísel indukcí vzhledem k n: pro rz — 2 je jejich existence dána větami 2 a 4, jestliže pro některé rz > 2 víme, že existuje největší společný dělitel i nejměnší společný násobek libovolných rz — 1 čísel, podle (6) a (7) existuje i pro libovolných rz čísel. 1.5. Nesoudělnost. Definice. Čísla a\,a^,... ,an G Z se nazývají nesoudělná, jestliže pro ně platí (ai, a2,..., an) — 1. Čísla a\, a2,..., an G Z se nazývají po duoit nesoudělná, jestliže pro každé ž,j takové, že 1 < i < j < n, platí (o^, a,j) — 1. Poznámka. v případě n — 2 oba pojmy splývají, pro rz > 2 plyne z ne-soudělnosti po dvou nesoudělnost, ne však naopak: například čísla 6, 10, 15 jsou nesoudělná, ale nejsou nesoudělná po dvou, neboť dokonce žádná dvojice z nich vybraná nesoudělná není: (6,10) — 2, (6,15) — 3, (10,15) — 5. příklad. Nalezněte nej větší společný dělitel čísel 263 — 1 a 291 — 1. řešení. Užijeme Euklidův algoritmus. Platí 291-l = 228(263 -l) + 228 -l, 263 -l = (235 + 27)(228 -l) + 27-l, 228 - 1 = (221 + 214 + 27 + 1)(27 - 1). Hledaný největší společný dělitel je tedy 27 — 1 — 127. □ věta 5. Pro libovolná přirozená čísla a, b, c platí (1) (ac, bc) — (a, b) • c, (2) jestliže a \ bc a (a, b) — 1, pak a \ c, (3) d — (a, 6) právě tehdy, když existují q\1 q2 G N tak, že a — dqi, b — dg^ Q> DŮKAZ, ad 1. Protože (a, 6) je společný dělitel čísel a, b, je (a, 6) • c společný dělitel čísel ac, 6c, proto (a, 6) • c | (ac, 6c). Podle věty 3 existují e Z tak, že (a, 6) — ka + /6. Protože (ac, 6c) je společný dělitel čísel ac, 6c, dělí i číslo kac + /6c — (a, b) • c. Dokázali jsme, že (a, b) • c a (ac, 6c) jsou dvě přirozená čísla, která dělí jedno druhé, proto se podle (4) rovnají. ad 2. Předpokládejme, že (a, 6) — 1 a a \ bc. Podle Bezoutovy věty (věta 3) existují 6 Z tak, že ka + lb — 1, odkud plyne, že c — c(ka + /6) — kca + /6c. Protože a | 6c, plyne odsud, že i a | c. ad 3. Nechť d — (a, 6), pak existují qi,q2 G N tak, že a — dgi, 6 — dg2- Pak podle části (1) platí d — (a, 6) — (dqi,dq2) — d-(qi,q2), a tedy (qi,q2) — 1. Naopak, je-li a — dgi, 6 — dq2 a (gi, g2) — 1, pak (a, 6) — (dgi, dq2) — d(qi,q2) = d • 1 = d (opět užitím 1. části tohoto tvrzení). □ 2. Prvočísla Prvočíslo je jeden z nej důležitějších pojmů elementární teorie čísel. Jeho důležitost je dána především větou o jednoznačném rozkladu libovolného přirozeného čísla na součin prvočísel, která je silným a účinným nástrojem při řešení celé řady úloh z teorie čísel. Definice. Každé přirozené číslo n > 2 má aspoň dva kladné dělitele: lan. Pokud kromě těchto dvou jiné kladné dělitele nemá, nazývá se prvočíslo. V opačném případě hovoříme o složeném čísle. V dalším textu budeme zpravidla prvočíslo značit písmenem p. Nej menší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (zejména číslo 1 za prvočíslo ani za číslo složené nepovažujeme, je totiž invertibilní, neboli jednotkou okruhu celých čísel). Prvočísel je, jak brzy dokážeme, nekonečně mnoho, máme ovšem poměrně limitované výpočetní prostředky na zjištění, zda je dané číslo prvočíslem; číslo 282 589 933 _ které bylo v roce 2018 nej větším známým prvočíslem, má pouze 24 862 048 cifer a jeho dekadické vyjádření by se tak vešlo na kdejaký prehistorický datový nosič, při tisku knihy o 60 řádcích na stránku a 80 znacích na řádek by nicméně i tak zabralo 5 180 stran. Uveďme nyní větu, která udává ekvivalentní podmínku prvočíselnosti a je základní ingrediencí při důkazu jednoznačnosti rozkladu na prvočísla. věta 6 (Euklidova o prvočíslech). 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. důkaz. Předpokládejme, že p je prvočíslo a p \ ab, kde a, b G Z. Protože (p, a) je kladný dělitel p, platí (p, a) — p nebo (p, a) — 1. v prvním případě p | a, ve druhém p \ b podle věty 5. „<=" Jestliže p není prvočíslo, musí existovat jeho kladný dělitel různý od 1 a p. Označíme jej a; pak ovšem b — ^ G N a platí p — a6, odkud 1 < a < p, 1 < b < p. Našli jsme tedy celá čísla a, 6 tak, že p \ ab a přitom p nedělí ani a, ani 6. □ příklad. Nalezněte všechna čísla k G No, pro která je mezi deseti po sobě jdoucími čísly fc + l,fc + 2,...,fc + 10 nejvíce prvočísel. Řešeni. Pro k — 1 je mezi našimi čísly pět prvočísel: 2, 3, 5, 7, 11. Pro k — 0 a & — 2 pouze čtyři prvočísla. Jestliže & > 3, není mezi zkoumanými čísly číslo 3. Mezi deseti po sobě jdoucími celými čísly pět sudých a pět lichých čísel, mezi kterými je zase aspoň jedno dělitelné třemi. Našli jsme tedy mezi čísly k + 1, + ..., k+ 10 aspoň šest složených, jsou tedy mezi nimi nejvýše čtyři prvočísla. Zadání proto vyhovuje jediné číslo k — 1. □ příklad. Dokažte, že pro libovolné prvočíslo p a libovolné k G N, k < p, je kombinační číslo (^) dělitelné p. Řešení. Podle definice kombinačního čísla AA = p\ = p ■ (p - 1).....(p - k + 1) Vfcy fc!(p-fc)! 1-2.....' a tedy fc! | p • a, kde jsme označili a — (p — 1).....(p — + 1). Protože k < p, není žádné z čísel 1, 2,..., k dělitelné prvočíslem p1 a tedy podle věty 6 není ani k\ dělitelné prvočíslem p, odkud (k\,p) — 1. Podle věty 5 platí k\ | a, a tedy b = y je celé číslo. Protože Q — |f — p6, je číslo (^) dělitelné číslem p. □ VĚTA 7. Libovolné přirozené číslo n 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ů. (Je-li n prvočíslo, pak jde o „součin" jednoho prvočísla, n — 1 je součinem prázdné množiny1 prvočísel) Poznámka. Dělitelnost je možné obdobným způsobem jako v 1.2 definovat v libovolném oboru integrity (zkuste si rozmyslet, proč se omezujeme na obory integrity). V některých oborech integrity přitom žádné prvky s vlastností prvočísla (říkáme jim ireducibilní) neexistují (např. Q), v jiných sice ireducibilní prvky existují, ale zase tam neplatí věta o jednoznačném rozkladu (např. v Z(V—5) máme následující rozklady: 6 — 2 • 3 — (1 + ^/—5) • (1 — ^/—5); zkuste si rozmyslet, že všichni uvedení činitelé jsou skutečně v Z(-\/—5) ireducibilní). ''"V řeči teorie okruhů jde o jedničku okruhu celých čísel, která je dle obvyklé konvence součinem prázdné množiny prvků okruhu. důkaz. Nejprve dokážeme indukcí, že každé rz > 2 je možné vyjádřit jako součin prvočísel. Je-li rz — 2, je rz součin jediného prvočísla 2. Předpokládejme nyní, že rz > 2 a že jsme již dokázali, že libovolné n'', 2 < rz' < rz, je možné rozložit na součin prvočísel. Jestliže rz je prvočíslo, je součinem jediného prvočísla. Jestliže rz prvočíslo není, pak existuje jeho dělitel d, 1 < d < rz. Označíme-li c — ^, platí také 1 < c < rz. Z indukčního předpokladu plyne, že c i d je možné vyjádřit jako součin prvočísel, a proto je takto možné vyjádřit i jejich součin c • d — rz. Nyní dokážeme jednoznačnost. Předpokládejme, že platí rovnost součinů p\ • p2.....Pm — Qi • Q2Qs, kde pi,... ,pm, q±,... ,qs jsou prvočísla a navíc platí Pí < ^2 < • • • < Pm, <7i < #2 < • • • < #s a 1 < rrz < s. Indukcí vzhledem k rrz dokážeme, že rrz — s, p\ — qi,... ,pm — gm. Je-li ra = 1, je pi = (/i.....gs prvočíslo. Kdyby 5 > 1, mělo by číslo p\ dělitele qi takového, že 1 < q\ < p\ (neboť q2q^ ... qs > 1), což není možné. Je tedy 5 — 1 a platí pi — qi. Předpokládejme, že rrz > 2 a že tvrzení platí pro rrz — 1. Protože p\ -p2.....pm — qi • q2.....qs, dělí pm součin qi.....qs, což je podle věty 6 možné jen tehdy, jestliže pm dělí nějaké qi pro vhodné i G {1,2,..., s}. Protože qi je prvočíslo, plyne odtud pm — qi (neboť pm > 1). Zcela analogicky se dokáže, že qs — p j pro vhodné Home Page Title Page j £ {1,2,..., m}. Odtud plyne qs = Pj 2/3^ _ Peter Shor v roce 1994 vymyslel algoritmus, který číslo faktorizuje v kubickém čase (tento algoritmus je tedy časové složitosti O (log3 N)) na kvantovém počítači. Je k tomu nicméně třeba sestrojit počítače s dostatečným počtem kvantových bitů (tzv. qubits) - jak je to obtížné, lze vysledovat z toho, ze v roce 2001 Contents 44 _«J. Page 23 of 175 Go Back Full Screen Close Quit se IBM podařilo pomocí kvantového počítače rozložit číslo 15, v roce 2012 byl dosažen další faktorizační rekord rozkladem čísla 21, následovali čínští fyzikové (s využitím jistého triku jim stačil NMR kvantový počítač s pouhými čtyřmi qubity k rozkladu čísla 143) a v závěru roku 2014 bylo ukázáno, že tentýž počítač je schopný rozložit i číslo 56 153 (viz https : //en. wikipedia. org/wiki/Timeline_ of _quantum_ comput ing). Ze je problém rozkladu přirozeného čísla na prvočísla výpočetně složitý, o tom svědčí i (již neplatná) výzva učiněná v roce 1991 firmou RSA Security (viz http: // www.rsasecu.rity. com/rsalabs/node. asp?id=2093). Pokud se komukoliv podařilo rozložit čísla označená podle počtu cifer jako RSA-100, ..., RSA-704, RSA-768, ..., RSA-2048, mohl obdržet 1 000,..., 30 000, 50 000, ..., resp. 200 000 dolarů (číslo RSA-100 rozložil v temže roce Arjen Lenstra, číslo RSA-704 bylo rozloženo v roce 2012, některá další ale dosud rozložena nebyla). Díky jednoznačnosti rozkladu na prvočísla jsme schopni (se znalostí tohoto rozkladu) snadno odpovědět i na otázky ohledně počtu či součtu dělitelů konkrétního čísla. Stejně snadno dostaneme i (z dřívějška intuitivně známý) postup na výpočet největšího společného dělitele dvou čísel ze znalosti jejich rozkladu na prvočísla. DŮSLEDEK. (1) Jsou-li pi,... ,Pk navzájem různá prvočísla a rzi,..., £ N0; je každý kladný dělitel čísla a — p\x.....pJJfe tvaru p™1.....P™k > kde mi,..., nik GN0 a m\ < ri\, m2 < n2, ..., rrik < n^. Číslo a má tedy právě r (a) = (ni + l)(n2 + l) kladných dělitelů, jejichž součet je {nk + 1) a (a) pi -1 Pk -1 (2) Jsou-li pi,..., pk navzájem různá prvočísla a n\, ..., rik, m\, ..., nik G N0 a označíme-li Tí — minj^, m^\, ti — max{?^,mi} pro každé i — 1, 2,..., k, platí {p? ■ ■ nu mi rnu\ ri pk ,P\ Pk ) =P\ K1 nu mi Pk iPl mu Pk Á1 'Pk: tu Pk- 2.1. Dokonalá čísla a jejich vztah k prvočíslům. Se součtem všech kladných dělitelů daného čísla souvisí pojem tzv. dokonalého čísla. Řekneme, že a je dokonalé, pokud splňuje podmínku a (a) — 2a, resp. slovně, pokud součet všech kladných dělitelů čísla a menších než a samotné je roven číslu a. Takovými čísly jsou např. 6 - 1 + 2 + 3, 28 - 1 + 2 + 4 + 7 + 14, 496 a 8128 (jde o všechna dokonalá čísla menší než 10 000). Lze ukázat, že sudá dokonalá čísla jsou v úzkém vztahu s tzv. Mersenného prvočísly. Platí totiž následující fakt. Tvrzení 2.1. Přirozené číslo a je sudé dokonalé číslo, práve když je tvaru a — 2q~1(2q — 1); kde 2^ — 1 je prvočíslo. důkaz. Je-li a — 2q~1(2q — 1), kde p — 2q — 1 je prvočíslo, pak z předchozího tvrzení plyne a (a) = • (p + 1) = (2* - 1) • 2« = 2a. Takové číslo a je tedy dokonalé. Pro důkaz opačného směru uvažme libovolné sudé dokonalé číslo a a pišme a = 2k • m, kde m, k G N a 2 f m. Protože je funkce cr multiplikativní (viz 3.2), je a (a) — cr(2fe) • cr(ra) — (2fe+1 — 1) • cr(ra). Přitom ale z dokonalosti čísla a plyne cr(a) — 2a — 2fe+1 • m, odkud 2fe+1-m = (2fe+1-l)-o-(m). Protože je 2k+1 — 1 liché, nutně 2k+1 — 1 | m a můžeme položit m — (2fe+1 — 1) -n pro vhodné rz G N. Úpravou dostáváme 2k+1 ■ n — a (m). Mezi dělitele čísla m přitom patří čísla m i n (a protože ^ — 2fe+1 — 1 > 1, jsou tato čísla nutně různá), proto 2k+1 ■ n = a (m) >m + n = 2k+1 ■ n, a tedy cr(ra) — m + rz. To znamená, že m je prvočíslo s jedinými děliteli man - 1, odkud a — 2k • (2k+1 — 1), kde 2k+l — 1 — m je prvočíslo. □ Poznámka. Na druhou stranu, popsat lichá dokonalá čísla se dodnes nepodařilo, dokonce se ani neví, jestli vůbec nějaké liché dokonalé číslo existuje. Mersenneho prvočísla jsou právě prvočísla tvaru 2k — 1. Není bez zajímavosti, že právě Mersenneho prvočísla jsou mezi všemi prvočísly nejlépe „vidět" - pro Mersenneho čísla existuje poměrně jednoduchý a rychlý postup, jak ověřit, že jde o prvočísla. Proto není náhodou, že nej větší známá prvočísla jsou obvykle tvaru 2k - 1. Jakkoliv může být hledání největšího známého prvočísla chápáno jako pochybná zábava bez valného praktického užitku2, jednak posunuje hranice matematického poznání a zdokonaluje použité metody (a často i hardware), navíc může přinést benefit i samotným objevitelům (Electronic Frontier Foundation vypsala odměny EFF Cooperative Computing Awards za nalezení prvočísla majícího alespoň 106,107,108 a 109 číslic odměny 50, resp. 100 tisíc dolarů za první dvě kategorie byly vyplaceny v letech 2000, resp. 2009 - v obou případech projektu GIMPS - na další odměny si ještě zřejmě nějaký čas počkáme). 2.2. Rozložení prvočísel. There are two facts about the distribution of prime numbers. The first is that, [they are] the most arbitrary and ornery objects studied Viz např. titulek iDnes z 6.února 2013: Největši známé prvočíslo na světě má 17 milionů číslic a je k ničemu by mathematicians: they grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision. Don Zagier příklad. Dokažte, že pro libovolné přirozené číslo n existuje n po sobě jdoucích přirozených čísel, z nichž žádné není prvočíslo. řešení. Zkoumejme čísla (n + 1)! + 2, (n + 1)! + 3,..., (n + 1)! + (n + 1). Mezi těmito n po sobě jdoucími čísly není žádné prvočíslo, protože pro libovolné k g {2, 3,..., n + 1} platí k \ (n + 1)!, a tedy k \ (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo. □ příklad. Dokažte, že pro každé celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. řešení. Označme p libovolné prvočíslo dělící číslo n\ — 1 (takové existuje podle věty 7, protože n\ — 1 > 1). Kdyby p < n, muselo by p dělit číslo n\ a nedělilo by n\ — 1. Je tedy n < p. Protože p \ (n\ — 1), platí p < n\ — 1, tedy p < n\. Prvočíslo p splňuje podmínky úlohy. □ Nyní uvedeme několik důkazů toho, že existuje nekonečně mnoho prvočísel (i když tvrzení v podstatě vyplývá už z předchozího příkladu). věta 8. Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. důkaz. (Eukleides) Předpokládejme, že prvočísel je konečně mnoho a označme je P11P21 ■ ■ ■ ,Pn- Položme TV — pi -p2 .. .pn + 1. Toto číslo je buď samo prvočíslem nebo je dělitelné nějakým prvočíslem různým od pi,... ,pn (čísla pi,... ,pn totiž dělí číslo TV — 1), což je spor. (Kummer, 1878): Předpokládejme, že prvočísel je konečně mnoho a označme je pi < P2 < ■ ■ ■ < pn- Položme TV — pi ■ p2 • • -pn > 2. Číslo TV — 1 je podle věty 7 dělitelné některým prvočíslem pil které dělí zároveň číslo TV a tedy i TV — (TV — 1) — 1. Spor. (Fúrstenberg, 1955): V této poznámce uvedeme elementární „topologickýa důkaz existence nekonečné mnoha prvočísel. Zavedeme topologii prostoru celých čísel pomocí báze tvořené aritmetickými posloupnostmi (od —00 do +00). Lze snadno ověřit, že jde skutečně o topologický prostor, navíc lze ukázat, že je normální a tedy metrizovatelný. Každá aritmetická posloupnost je uzavřená i otevřená množina (její komplement je sjednocení ostatních aritmetických posloupností se stejnou diferencí). Dostáváme, že sjednocení konečného poctu aritmetických posloupností je uzavřená množina. Uvažme množinu A — UAP, kde Ap je tvořena všemi násobky p a p probíhá všechna prvočísla. Jediná celá čísla nepatřící do A jsou —lala protože množina {—1,1} zřejmě není otevřená, množina A nemůže být uzavřená. A tedy není konečným sjednocením uzavřených množin, což znamená, že musí existovat nekonečně mnoho prvočísel. příklad. Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3fc + 2, kde k g N0. Řešení. Předpokládejme naopak, že existuje pouze konečně mnoho prvočísel tohoto tvaru a označme je p\ — 2, p2 — 5, p3 — 11, pn. Položme TV — 3p2 -p3.....pn + 2. Rozložíme-li TV na součin prvočísel podle věty 7, musí v tomto rozkladu vystupovat aspoň jedno prvočíslo p tvaru 3^+2, neboť v opačném případě by bylo TV součinem prvočísel tvaru 3k + 1 (uvažte, že TV není dělitelné třemi), a tedy podle příkladu na str. 9 by bylo i TV tvaru 3fc + 1, což neplatí. Prvočíslo p ovšem nemůže být žádné z prvočísel Pi,p2, ■ ■ ■ ,Pn, jak plyne z tvaru čísla TV, a to je spor. □ Poznámka. Analogicky se dokáže i tvrzení o prvočíslech tvaru 4fc + 3, bohužel na obecný případ nám naše omezené prostředky nestačí. V kapitole o kvadratických kongruencích budeme alespoň schopni dokázat obdobné tvrzení pro prvočísla tvaru 4k + 1. Poslední příklad (o nekonečnosti počtu prvočísel tvaru 3k + 2) zobecňuje Di-richletova věta o aritmetické posloupnosti: věta 9. (Dirichletova) Jsou-li a, m nesoudělná přirozená čísla, existuje nekonečně mnoho přirozených čísel k tak, že mk + a je prvočíslo. Jinými slovy, mezi čísly 1-ra + a, 2-ra + a, 3-ra + a,... existuje nekonečně mnoho prvočísel. důkaz. Jde o hlubokou větu teorie čísel, k jejímuž důkazu je zapotřebí aparát značně přesahující její elementární část. Viz např. [3, kap. 16, s. 249-257] □ Poznámka. Dirichletovo tvrzení je ve skutečnosti daleko hlubší, říká totiž, že zvolíme-li libovolnou zbytkovou třídu modulo m, pak v ní buď není (až na jednu možnou výjimku) žádné prvočíslo, nebo je ve všech takových třídách prvočísel „zhruba stejně" (tj. pravděpodobnost, že náhodně zvolené prvočíslo bude patřit do konkrétní třídy, je pro všechny třídy stejná a je rovna ^^y)- Předchozí příklady je možné značně zobecnit. Platí totiž tvrzení, které bývá nazýváno Bertrandovým postulátem nebo Cebyševovou větou: věta 10. (Čebyševova) (1) libovolné přirozené číslo n > 5 existují mezi čísly n a 2n alespoň dvě prvočísla. (2) Pro každé číslo n > 3 existuje mezi čísly n a 2n—2 alespoň jedno prvočíslo. důkaz. Důkaz lze provést elementárními prostředky, je však poměrně dlouhý, proto zde není uveden. □ Z tvrzení uvedených v této kapitole je možné si udělat hrubou představu o tom, jak „hustě" se mezi přirozenými čísla prvočísla vyskytují. Přesněji (i když „pouze" asymptoticky) to popisuje tzv. „prime number theorem", dokázaná nezávisle J. Hadamardem a Ch. J. de la Vallée-Poussinem v roce 1896. věta 11. (o hustotě prvočísel) Nechť n(x) udává počet prvočísel menších nebo rovných číslu x G 1. Pak 7ľ(x) ln x tj. podíl funkcí ti {x) a x/lnx se pro x —> oo limitně blíží k 1. Hustotu rozmístění prvočísel v množině přirozených čísel, rovněž částečně popisuje následující Eulerův výsledek. Home Page Title Page VĚTA 12. (Euler) Je-li P množina všech prvočísel, pak T1- / > p 00. Contents I Poznámka. Přitom např. x]neN ^2 — ^j", c°ž znamená, že prvočísla jsou v N rozmístěna „hustěji" než druhé mocniny. DŮKAZ. Buď n libovolné přirozené číslo api,... jP^n) všechna prvočísla nepřevyšující n. Položme A(«)^n(i-- Page 33 of 175 Jednotlivé činitele lze chápat jako součet geometrické řady, proto 7r(n) Í = l VQ!,=0 ft / Pi ■■■P^n) Go Back Full Screen kde sčítáme přes všechny 7r(rz)-tice nezáporných celých čísel ..., a^n)). Protože každé číslo nepřevyšující n se rozkládá pouze na prvočísla z množiny [pí,..., p^n)}, je určitě každé takové číslo v tomto součtu zahrnuto. Tedy \{n) > 1 + | + • • • + ^, a protože harmonická řada diverguje, je i limn_^oo X(n) — oo. Close Quit S využitím rozvoje funkce ln(l + x) do mocninné řady dále dostáváme 7r(n) 7r(n) oo ln A(n) = " eln i1 " = e e ^"'T1 = i=l i=l m=l 7r(n) oo =p~il + -- -+p~u + e e (^rr1 • i=l m=2 Protože vnitřní součet lze shora odhadnout jako oo oo e (mpTT1 < e íT" = m=2 m=2 = PÍ2 (l-ft1)"1<2p-2, umíme shora odhadnout i divergující posloupnost ln A(rz) < YTi=í Pi1^ Y7i=í PÍ2-Druhý součet přitom zřejmě konverguje (viz konvergence řady Y^=in~2)i proto musí nutně divergovat první součet Yli=i Pí1 •> c°ž jsme chtěli dokázat. □ SW ukázka. O tom, jak odpovídá asymptotický odhad tx{x) ~ rr/ln(rr), v některých konkrétních příkladech vypovídá následující tabulka (získaná s využitím funkce primepi (x) v Pari-GP. ? v= [100,1000,10000,100000,500000]; ? f or(k=l ,5,print (v[k] , "&" ,primepi(v[k]), ■■&■■ ,\ v[k]/log(v [k] ),"&", \ (primepi(v [k])-v [k]/log(v[k]))/primepi(v[k]))) x 7ľ(x) x/ ln(rr) relativní chyba 100 25 21.71 0.13 1000 168 144.76 0.13 10000 1229 1085.73 0.11 100000 9592 8685.88 0.09 500000 41538 38102.89 0.08 Označení. Pro libovolné prvočíslo p a libovolné přirozené číslo n je podle věty 7 jednoznačně určen exponent, se kterým vystupuje p v rozkladu čísla n na prvočinitele (pokud p nedělí číslo n, považujeme tento exponent za nulový). Budeme jej označovat symbolem vp(n). Pro záporné celé číslo n klademe vp(n) — vp(-n). Podle důsledku 2 můžeme právě zavedené označení vp(n) charakterizovat tím, že pvp(n^ je nejvyšší mocninou prvočísla p, která dělí číslo rz, nebo tím, že n — pvp(n) . m^ kole m je ceié číslo, které není dělitelné číslem p. Odtud snadno plyne, že pro libovolná nenulová celá čísla a, b platí vp(ab) = vp(a) + vp(b) (8) vp(a) < vp(b) A a + b ^ 0 ==> -yp(a + 6) > %,(a) (9) vp(a) < vp(b) ==> vp(a + b) — vp(a) (10) Vp(a) vp((a,b)) = Vp(a) A vp([a,b]) = vp(b) (11) Na následujícím příkladu demonstrujme užitečnost zavedeného označení. příklad. Dokažte, že pro libovolná přirozená čísla a, b1 c platí ([a,b], [a,c], [b,c]) = [(a,b),(a,c),(b,c)] Řešení. Podle věty 7 budeme hotovi, ukážeme-li, že vp(L) — vp(P) pro libovolné prvočíslo p1 kde L, resp. P značí výraz na levé, resp. pravé straně. Nechť je tedy p libovolné prvočíslo. Vzhledem k symetrii obou výrazů můžeme bez újmy na obecnosti předpokládat, že vp(a) < vp(b) < vp(c). Podle (11) platí Vp([a,b}) = vp(b), vp([a,c]) = vp([b,c]) = vp(c); vp((a,b)) = vp((a,c)) = vp(a), vp((b, c)) — vp(b), odkud vp(L) — vp(b) — vp(P), což jsme měli dokázat. □ 3. Kongruence Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah. Definice. Jestliže dvě celá čísla a, b mají při dělení přirozeným číslem m týž zbytek r, kde 0 < r < m, nazývají se a, b kongruentni modulo m (též kongruentni podle modulu m), což zapisujeme takto: a = b (mod m). V opačném případě řekneme, že a, b nejsou kongruentni modulo m, a píšeme a ^ b (mod m). Lemma. Pro libovolná a, b g Z, m g N jsou následující podmínky ekvivalentní: (1) a = b (mod m), (2) a — b + mt pro vhodné t g Z, f3) m j a — 6. důkaz. „(1)=>(3)" Jestliže a — gim + r, 6 — + pak a — b= (qi — q2)m. „(3)=>(2)" Jestliže m | a — b, pak existuje í e Z tak, že m • í — a — b, tj. a — b + mí. „(2)=>(1)" Jestliže a — b+mt1 pak z vyjádření 6 — mq+r plyne a — m(g+/;)+r, tedy a i 6 mají při dělení číslem m týž zbytek r, tj. a = b (mod m). □ 3.1. Základní vlastnosti kongruencí. Přímo z definice plyne, že kongruence podle modulu m je reflexivní (tj. a = a (mod m) platí pro každé a G Z), symetrická (tj. pro každé a, b G Z z a = 6 (mod m) plyne 6 = a (mod m)) a tranzitivní (tj. pro každé a,b,c G Z z a = b (mod m) & b = c (mod m) plyne a = c (mod m)) relace, jde tedy o ekvivalenci. Dokážeme nyní další vlastnosti: VĚTA 13. (Základní vlastnosti kongruencí) (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. K libovolné straně kongruence můžeme přičíst jakýkoliv násobek modulu. DŮKAZ. Je-li a\ = bi (mod m) a a2 = b2 (mod m), existují podle lemmatu ti,t2 G Z tak, že a\ — b\ + mti, a2 — b2 + mt2. Pak ovšem ai + a2 — 6i + b2 + m(£i + /;2) a opět podle lemmatu ai + a2 = 6i + b2 (mod m). Sečteme-li kongruencí a+b = c (mod m) s kongruencí —b = —b (mod m), která zřejmě platí, dostaneme a = c — b (mod m). Sečteme-li kongruencí a = b (mod m) s kongruencí mk = 0 (mod m), jejíž platnost je zřejmá, dostaneme a + mfc = b (mod m). □ Home Page Title Page (2) Kongruence podle téhož modulu můžeme násobit. Obě strany kon-gruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. DŮKAZ. Je-li ai = bi (mod m) a a2 = b2 (mod m), existují podle ti, t2 £ Z tak, že a\ — b\ + mti, a2 = b2Jr mt2. Pak ovšem aia2 = (bi + mti)(b2 + ra£2) = M2 + m(tib2bit2 + mtit2), odkud podle dostáváme aia2 = b\b2 (mod m). Je-li a = b (mod m), dokážeme indukcí vzhledem k přirozenému číslu n1 že platí an = bn (mod m). Pro rz — 1 není co dokazovat. Platí-li an = bn (mod m) pro nějaké pevně zvolené n1 vynásobením této kongruence a kongruence a = b (mod m) dostáváme an • a = bn • b (mod m), tedy an+1 = 6n+1 (mod m), což je tvrzení pro n + 1. Důkaz indukcí je hotov. Jestliže vynásobíme kongruenci a = b (mod m) a kongruenci c = c (mod m), dostaneme ac = bc (mod m). □ Contents 44 Page 39 of 175 Go Back Full Screen (3) Obé strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. Close DŮKAZ. Předpokládejme, že a = b (mod m), a — a\ • d, b — b\ • d a (m, d) — 1. Podle lemmatu je rozdíl a — b — (ai — b\) • d dělitelný číslem Quit m. Protože (m, d) — 1, je podle věty 5 číslo a\ — b\ také dělitelné číslem m, odtud podle lemmatu plyne a\ = b\ (mod m). □ (4) Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. DŮKAZ. Je-li a = b (mod m), existuje podle lemmatu celé číslo t tak, že a — b + mt, odkud pro c G N platí ac = bcJr mc • t, odkud opět podle lemmatu plyne ac = bc (mod mc). □ (5) Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. DŮKAZ. Předpokládejme, že a = b (mod m), a — a± • d, b — b± • d, m — mi • d, kde d G N. Podle lemmatu existuje ŕ £ Z tak, že a — 6 + mí, tj. ai-d — bi-d+midt, odkud ai — b± + mií, což podle lemmatu znamená, že ai = fei (mod mi). □ Jestliže kongruence a = b platí podle modulů mi,... ,rrik, platí i podle modulu, kterým je nejmenší společný násobek [mi,..., mj těchto čísel. DŮKAZ. Jestliže a = b (mod mi), a = b (mod m2),..., a = b (mod m^), podle lemmatu je rozdíl a — b společný násobek čísel mi,m2,..., rafc a tedy je dělitelný jejich nejmenším společným násobkem [mi,m2,..., mj, odkud plyne a = b (mod [mi,..., mj). □ (7) Jestliže kongruence platí podle modulu m, platí podle libovolného modulu d, který je dělitelem čísla m. důkaz. Jestliže a = b (mod m), je a — b dělitelné m, a proto také dělitelem d čísla m, odkud a = b (mod d). □ Jestliže je jedna strana kongruence a modul dělitelný nějakým celým číslem, musí být tímto číslem dělitelná i druhá strana kongruence. důkaz. Předpokládejme, že a = b (mod m), b — b\d, m — m\d. Pak podle lemmatu existuje ŕ £ Z tak, že a — 6 + mí — Oia7 + m\dt — (61 + m\ť)d, a tedy d | a. □ Poznámka. Některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli - například příklad ze strany 9 lze přeformulovat do tvaru „jestliže a = 1 (mod m), b = 1 (mod m), pak také ab = 1 (mod m)", což je speciální případ tvrzení věty 13 (2). Nejde o náhodu. Libovolné tvrzení používající kongruence můžeme snadno přepsat pomocí dělitelnosti. Užitečnost kongruencí tedy netkví v tom, že bychom pomocí nich mohli řešit úlohy, které bez nich řešit nejsme schopni, ale v tom, že jde o velmi vhodný způsob zápisu. Osvojíme-li si ho, výrazně tím zjednodušíme jak vyjadřování, tak i některé úvahy. Je to typický jev: v matematice hraje vhodná symbolika velmi závažnou úlohu. příklad. Nalezněte zbytek po dělení čísla 520 číslem 26. Řešení. Protože 52 = 25 = -1 (mod 26), platí podle věty 13 (2) 52o = (_^io = ľ (mod 26^ a tedy zbytek po dělení čísla 520 číslem 26 je jedna. □ příklad. Dokažte, že pro libovolné n g n je 37n+2 + 16n+1 + 23n dělitelné sedmi. řešení. Platí 37 = 16 = 23 = 2 (mod 7), a tedy podle 13 (2) a (1) platí 37n+2 + lgn+l + 23n = 2n+2 + 2n+l + T = 2^(4+2+1) = 2n . 7 = 0 (mod 7), což jsme chtěli dokázat. □ příklad. Dokažte, že číslo n = (8355 + 6)18 — 1 je dělitelné číslem 112. Ř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 - 1 - 3818 - 1 = 318 - 1 - 276 - 1 = (-1)6 - 1 - 0 (mod 7), proto 7 j 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í ď + W = (a + b)p (modp). Řešení. Podle binomické věty platí (a + bf = ď+ (J)ap_16 + (l)ap-2b2 + • • • + (/^aď'1 + V. Podle příkladu za větou 6 pro libovolné £ {1,... ,p — 1} platí (p) = 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), kde n G N, platí, že am — bm (mod mn+1). DŮKAZ. Platí am-bm = {a- b)^™-1 + am~2b + • • • + abm~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-2b + . . . + abm-2 + ftm-l = m . flm-l = Q (mod m)? proto je am_1 + am~2 + • • • + abm~2 + 6m_1 dělitelné m. Z a = b (mod mn) plyne, že mn dělí a —6, a tedy mn+1 dělí jejich součin, což vzhledem k (12) vede k závěru, že am = bm (mod mn+l). □ 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 (—l)fe v opačném případě. Dále definujeme — 1. příklad. /x(4) - /x(22) - 0, /x(6) - fi(2 • 3) - (-1)2, /x(2) - /x(3) - -1. Dokážeme nyní několik důležitých vlastností Môbiovy funkce, zejména tzv. Môbiovu inverzní formuli. Lemma. Pro n e N \ {1} platí $>M = o. d\n důkaz. Zapíšeme-li n ve tvaru n — p^1 • • •pjľ*, pak všechny dělitele d čísla n jsou tvaru d — pf1 • • -pffe, kde 0 < < atj pro všechna ž G {1,..., k}. Proto d\n (/3!,...,/3fc)G(NU{0})fc 0 1, resp. I(n) — 1 pro všechna n £ N. Pak pro každou aritmetickou funkci / platí: /oI = Io/ = / a (/o/)(„) = (/o J)(„)=]T/(d). d\n Dále platí /o/i-pí-I, neboť (/ o Mn) = £1(dU^) = £ /(X<í) = 1 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) — J2d\nf(d). Pak lze funkci f vyjádřit ve tvaru /(«) = E ^s) •*■(<*)• d\n DŮKAZ. Vztah F(n) — Yld\n fW ^ze Jmým způsobem zapsat jako F = f o L Proto Fo/i = (/o/)o/i = /o(/o/i) = /oI = /, 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 £ N platí f(a-b) = f(a)-f(b). příklad. Multiplikativními funkcemi jsou např. funkce f in) — cr(rz), f(n) — r(rz), či f(n) — fi(n) nebo, jak brzy dokážeme i tzv. Eulerova funkce f(n) — (p(n). 3.3. Eulerova funkce cp. Definice. Nechť n £ N. Definujme Eulerovu funkci

•> n n n n — 1 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í n £ N, jehož rozklad je tvaru n — p^1 • • -p^k. Pak <-f(n) — n • í 1-- Pi Pk důkaz. S využitím předchozího lemmatu a Môbiovy inverzní formule dostáváme d\n n • ^n) = Y,Kd)'ÍJ = n-------+ ... + (_!)*. ^ d pi pk P\---Pk n n Pi i-l Pk, (13) □ 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. Nechí a, b G N, (a, b) = 1. Pak (p(a • b) — (p(a) • (p(b). důkaz. Zřejmý. □ Poznámka. Rovněž toto tvrzení lze odvodit nezávisle na základě poznatku (rz, ab) — 1 <í=> (rz, a) — 1A (rz, b) — 1. Spolu se snadno odvoditelným výsledkem 1 nalezněte zbytek po dělení čísla 2^m)_1 číslem m. Řešeni. Z Eulerovy věty plyne 2^m) = l = l + 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 — 14p. □ Tvrzení 3.1. Je-li p prvočíslo, p = 3 (mod 4), pro libovolná celá čísla a, 6 z kongruence a2 + 62 = 0 (mod p) pZí/ne a = b = 0 (mod p). důkaz. Předpokládejme, že pro a, b G Z platí a2 + b2 = 0 (mod p). Jestliže p | a, platí a = 0 (modp), proto 62 = 0 (modp), tedy p | b2, odkud vzhledem k tomu, že p je prvočíslo, dostáváme p \ b, 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 b (kdyby p | b1 dostali bychom p | a2). Vynásobíme-li obě strany kongruence a2 = —b2 (mod p) číslem 6ř>~3, dostaneme podle Fermatovy věty a2^-3 = -W'1 = -1 (mod p). Protože p = 3 (mod 4), je p — 3 sudé číslo, a proto G N0. Označme c = ao 2 . Pak c není dělitelné p a platí c2 — a2^-3 = — 1 (mod p). Umocníme-li poslední kongruenci na G N, dostaneme ď"1 = (—1)~2~ (mod p). Protože p = 3 (mod 4), existuje celé číslo t tak, že p — 3 + At. Pak ovšem — 1 + 2í, což je číslo liché a proto (—l)^-1)/2 — —1. Podle Fermatovy věty naopak platí ď~x = 1 (mod p), odkud 1 = — 1 (mod p) a p | 2, spor. □ Home Page Title Page S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řád čísla modulo m - jde přitom pouze o jinak nazvaný řád prvku v grupě invertibilních zbytkových tříd modulo m: Definice. Nechť a G Z, m G N (a, m) — 1. Řádem čísla a modulo m rozumíme nej menší přirozené číslo n splňující an = 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 (p(m). Jak později uvidíme, velmi důležitá jsou právě ta čísla, jejichž řád je roven právě (p(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 kongruencí (viz 4.5). Tento pojem je přitom jen jiným názvem pro generátor grupy (Z^, •). příklad. Pro libovolné m G N má číslo 1 modulo m řád 1. Číslo —1 má řád • 1 pro m — 1 nebo m — 2 • 2 pro m > 2 Contents 44 Page 54 of 175 Go Back I Full Screen Close příklad. Určete řád čísla 2 modulo 7. Quit Řešení. 21 = 2^1 (mod 7) 22 = 4^1 (mod 7) 23 = 8 = 1 (mod 7) Řád čísla 2 modulo 7 je tedy roven 3. □ Uveďme nyní několik zásadních tvrzení udávajících vlastnosti řádu čísla modulo m: Lemma. Nechí m g N, a, b g Z, (a, m) = (6, m) = 1. Jestliže a = b (mod m), pafc o6ě čzsZa a, b mají stejný řád modulo m. důkaz. Umocněním kongruence a = b (mod m) na rz-tou dostaneme an =. 6n (mod m), tedy an = 1 (mod m) <í=> 6n = 1 (mod m). □ Lemma. Nechí m g N, a g Z, (a, m) = 1. Je-Zi řád ask a modulo m roven r • s, (kde r,s g Nj, pafc rarf čzsZa ar modulo m je roven s. důkaz. Protože žádné z čísel a, a2, a3,..., ars_1 není kongruentní s 1 modulo m, není ani žádné z čísel ar, a2r, a3r,..., a^-1^ kongruentní s 1. Platí ale (ar)s = 1 (mod m), proto je řád ar modulo m roven 5. □ Poznámka. Opak obecně neplatí - z toho, že řád čísla ar modulo m je roven s ještě neplyne, že řád čísla a modulo m je r • s. Např pro m — 13 máme: a — 3, a2 — 9 (mod 13), a3 — 27 = 1 (mod 13) 3 má řád 3 mod 13. 6 = —4, 62 = 16 ^ 1 (mod 13), b3 = -64 = 1 (mod 13) => -4 má řád 3 mod 13. Přitom (—4)2 — 16 = 3 (mod 13) má stejný řád 3 jako číslo 3, ale číslo —4 nemá řád 2 • 3. Přesný popis závislosti řádu na exponentu dávají následující 2 věty: věta 18. Nechť m G N, a G Z, (a, m) — 1. Označme r řád čísla a modulo m. Pak pro libovolná í,sGNU{0} platí ať = as (mod m) <í=^ t = s (mod r). důkaz. Bez újmy na obecnosti lze předpokládat, že t > s. Vydělíme-li číslo t — s číslem r se zbytkem, dostaneme t — s = q • r + z, kde g, z G N0, 0 < z < r. „<=" Protože t = s (mod r), máme z — 0, a tedy aí_s — a9r — (ar)q = lq (mod m). Vynásobením obou stran kongruence číslem as dostaneme tvrzení. Z ať = as (mod m) plyne as • aqr+z = as (mod m). Protože je ar = 1 (mod m), je rovněž aqr+z = az (mod m). Celkem po vydělení obou stran kongruence číslem as (které je nesoudělné s modulem), dostáváme az = 1 (mod m). Protože z < r, plyne z definice řádu, že z — 0, a tedy r | í — s. □ Zřejmým důsledkem předchozí věty a Eulerovy věty je následující tvrzení (jehož druhá část je přeformulováním Lagrangeovy věty z Algebry pro naši situaci): DŮSLEDEK. Nechť m £ N, a £ Z, (a, m) — 1. Označme r řád čísla a modulo m. (1) Pro libovolné n £ N U {0} platí an = 1 (mod m) <í=> r | 7Z. fiy r | 1 je prvočíslo, právě když (n-l)\ = -l (modrz) (18) Contents 44 Page 63 of 175 Go Back Full Screen Close Quit DŮKAZ. Dokážeme nejprve, že pro libovolné složené číslo n > 4 platí n \ (n — 1)!, tj. (n — 1)! = 0 (mod n). Nechť 1 < d < n je netriviální dělitel n. Je-li d n/d, pak protože 1 < d, n/d < n — 1, je n — d • n/d \ (n — 1)!. Pokud d — n/d, tj. n — d2, pak protože je rz > 4, je i d > 2 a rz | (d • 2d) \ (n — 1)!. Pro rz — 4 snadno dostáváme (4 — 1)! = 2^—1 (mod 4). Necht je nyní p prvočíslo. Čísla z množiny {2,3,... ,p — 2} seskupíme do dvojic vzájemně inverzních čísel modulo p, resp. dvojic čísel, jejichž součin dává zbytek 1 po dělení p. Pro dané číslo a z této množiny existuje podle předchozí věty jediné řešení kongruence a • x = 1 (mod p). Protože a ^ 0,1,p — 1, je zřejmé, že rovněž pro řešení c této kongruence platí c ^ 0,1, —1 (mod p). Číslo a nemůže být ve dvojici samo se sebou; kdyby totiž a • a = 1 (mod p), pak nutně a = ±1 (mod p). Součin všech čísel uvedené množiny je tedy tvořen součinem (p — 3)/2 dvojic (jejichž součin je vždy kongruentní s 1 modulo p). Proto je (p - 1)! = l^"3)/2 • (p - 1) = -1 (mod p). □ 4.2. Soustavy lineárních kongruencí o jedné neznámé. Máme-li soustavu lineárních kongruencí o téže neznámé, můžeme podle Věty 21 rozhodnout o řešitelnost každé z nich. V případě, kdy aspoň jedna z kongruencí nemá řešení, nemá řešení ani celá soustava. Naopak, jestliže každá z kongruencí řešení má, upravíme ji do tvaru x = Ci (mod nrii). Dostaneme tak soustavu kongruencí x = C\ (mod mi) x = Ck (mod nik) (19) Zkoumejme nejprve případ k — 2, který - jak uvidíme později - má stěžejní význam pro řešení soustavy (19) s k > 2. VĚTA 23. Nechť Ci, c2 jsou celá čísla, mi,m2 přirozená. Označme d — (mi,m2). Soustava dvou kongruencí x = Ci (mod mi) h (20) rr = c2 (mod m2J v případě Ci ^ c2 (mod d) nemá řešení. Jestliže naopak C\ = c2 (mod d), pak existuje celé číslo c tak, že x G Z splňuje soustavu (19), právě když vyhovuje kongruenci x = c (mod [mi, m2]). DŮKAZ. Má-li soustava (20) nějaké řešení x G Z, platí nutně x = C\ (mod d), x = c2 (mod d), a tedy i C\ = c2 (mod ď). Odtud plyne, že v případě C\ ^ c2 (mod d) soustava (20) nemůže mít řešení. Předpokládejme dále c\ = c2 (mod d). První kongruenci soustavy (20) vyhovují všechna celá čísla x tvaru x = c\ + tmi, kde t G Z je libovolné. Toto rr bude vyhovovat i druhé kongruenci soustavy (20), právě když bude platit c\ + tm\ = c2 (mod m2), tj. tmi = c2 — Ci (mod m2). Podle Věty 21 má tato kongruence (vzhledem k ť) řešení, neboť d = (mi,m2) dělí c2 — Ci, aíeZ splňuje tuto kongruenci právě když t j. právě když c2 - Ci d c2 - Ci d kde r G Z je libovolné. Dosazením x = ci + tmi = ci + (c2 — ci) mi mi T mi mod + r m2 m2 T a—) mim2 + r--— — c + r • mi, m2 a kde c — Ci + (c2 — Ci) • (mi/'d)^m2//d), neboť mim2 — d • [mi, m2]. Našli jsme tedy takové c G Z, že libovolné x G Z splňuje soustavu (20), právě když rr = c (mod [mi, m2]), což jsme chtěli dokázat. □ Všimněme si, že důkaz této věty je konstruktivní, tj. udává vzorec, jak číslo c najít. Věta 23 nám tedy dává metodu, jak pomocí jediné kongruence zachytit podmínku, že x vyhovuje soustavě (20). Podstatné je, že tato nová kongruence je téhož tvaru jako obě původní. Můžeme proto tuto metodu aplikovat i na soustavu (19) - nejprve z první a druhé kongruence vytvoříme kongruenci jedinou, které vyhovují právě ta x, která vyhovovala původním dvěma kongruencím, pak z nově vzniklé a z třetí kongruence vytvoříme další atd. Při každém kroku se nám počet kongruenci soustavy sníží o 1, po k — 1 krocích tedy dostaneme kongruenci jedinou, která nám bude popisovat všechna řešení soustavy (19). Poznamenejme ještě, že číslo c z Věty 23 není nutné určovat pomocí uvedeného vzorce. Můžeme vzít libovolné í G Z vyhovující kongruenci a položit c — Ci + tmi. DŮSLEDEK (Čínská zbytková věta). Nechť rai,,...,rafc G N jsou po dvou nesoudělná, ai,...,Ojt € Z. Pak platí: soustava x = ai (mod mi) x = ak (mod rrik) (21) má jediné řešení modulo m\ • m2 • • • rrik-PŘÍKLAD. Řešte systém kongruencí x = — 3 (mod 49) x = 2 (mod 11). Řešeni. První kongruencí splňují právě všechna celá čísla x tvaru x 49t, kde í G Z. Dosazením do druhé kongruence dostáváme -3 + 49^ = 2 (modli), odkud 5t = 5 (mod 11), tedy, vzhledem k (5,11) — 1, po vydělení pěti t = 1 (modli), neboli t — 1 + lis pro libovolné s G Z. Proto x — —3 + 49(1 + lis) — 46 kde s G Z, což můžeme také zapsat jako rr = 46 (mod 539). PŘÍKLAD. Řešte systém kongruencí rr = 1 (mod 10) x = 5 (mod 18) x = —4 (mod 25). ŘEŠENÍ. Z první kongruence dostáváme x = 1 + lOt pro í G Z. Dosazením do druhé kongruence získáme l + 10í = 5 (mod 18), tedy lOt = 4 (mod 18). Protože (10,18) = 2 dělí číslo 4, má tato kongruence podle věty 4.2 řešení t = 2 • 55 (mod 9), přičemž 2 • 55 = 10 • 252 = 1 • (—2)2 = 4 (mod 9), a tedy t = 4 + 9s, kde 5 e Z. Dosazením rr = 1 + 10(4 + 9s) = 41 + 905. Z třetí kongruence pak vychází 41 + 90s = -4 (mod 25), tedy 90s = —45 (mod 25). Vydělením pěti (včetně modulu, neboť 5 | 25) 185 = -9 (mod 5), odkud —25 = 1 (mod 5), tedy 25 = 4 (mod 5), 5 = 2 (mod 5), a proto 5 = 2 + 5r, kde r e Z. Dosazením x = 41 + 90(2 + 5r) = 221 + 450r, tedy x = 221 (mod 450). □ příklad. Řešte systém kongruencí x = 18 (mod 25) x = 21 (mod 45) rr = 25 (mod 73). ŘEŠENÍ. Z první kongruence x — 18 + 25£, kde ŕ £ Z. Dosazením do druhé kongruence 18 + 25^ = 21 (mod 45), tedy 25^ = 3 (mod 45). Tato kongruence však podle Věty 21 nemá řešení, neboť (25,45) — 5 nedělí číslo 3. Proto nemá řešení ani celý systém. Tento výsledek bychom také dostali přímo z Věty 23, neboť 18 ^ 21 (mod (25,45)). □ příklad. Řešte kongruenci 23 941rr = 915 (mod 3564). ŘEŠENÍ. Rozložme 3564 = 22 • 34 • 11. Protože ani 2, ani 3, ani 11 nedělí číslo 23 941, platí (23 941,3564) — 1 a tedy podle Věty 23 má kongruence řešení. Protože (^(3564) - 2 • (33 • 2) • 10 - 1080, je řešení tvaru x = 915 • 23 9411079 (mod 3564). Úprava čísla stojícího na pravé straně by však vyžádala značné úsilí. Proto budeme kongruenci řešit poněkud jinak. Podle Věty 13 (6) je x £ Z řešením dané kongruence právě když je řešením soustavy 23941rr = 915 (mod 22) 23941rr = 915 (mod 34) (22) 23941rr = 915 (mod 11) Vyřešíme nyní každou z kongruencí soustavy (22) zvlášť. První z nich je splněna, právě když odkud vynásobením dvěma 92x = 48 (mod 81), tj. llx = —33 (mod 81) a po vydělení jedenácti x = — 3 (mod 81). Třetí kongruence je splněna, právě když 5x = 2 (mod 11), odkud vynásobením číslem —2 dostaneme — lOx = —4 (mod 11), tedy x = —4 (mod 11). Libovolné x £ Z je tedy řešením soustavy (22), právě když je řešením soustavy x = 3 (mod 4) x 3 (mod 4) druhá, právě když 46rr 24 (mod 81) x x 3 (mod 81) 4 (mod 11) (23) Z druhé kongruence dostáváme, že x — —3 + 81/;, kde í G Z. Dosazením do třetí kongruence soustavy (23) dostaneme -3 + 81r = -4 (mod 11), tedy 81t = —1 (mod 11), tj. 4t = 32 (mod 11), odkud t = 8 (mod 11), a proto t = -3 + 115, kde 5 G Z. Dosazením x = -3 + 81(-3 + lls) = -3 - 3 • 81 + 11 • 81s do první kongruence soustavy (23) dostaneme -3 - 3 • 81 + 11 • 815 = 3 (mod 4), tedy 1 + 1 • 1 + (-1) • ls = 3 (mod 4), tj. —5 = 1 (mod 4) a proto 5 — — 1 + 4r, kde r G Z. Je tedy x = -3 - 3 • 81 + 11 • 81(-1 + 4r) = -3 - 14 • 81 + 4 • 11 • 81r - -1137 + 3564r, neboli x = —1137 (mod 3564), což je také řešení zadané kongruence. □ 4.3. Kongruence vyšších stupňů. Vraťme se k obecnějšímu případu, kdy na obou stranách kongruence stojí mnohočleny téže proměnné x s celočíselnými koeficienty. Snadno můžeme tuto kongruenci odečtením upravit na tvar F(x) = 0 (mod m), (24) kde F{x) je mnohočlen s celočíselnými koeficienty a m G N. Věta 20 nám poskytuje sice pracnou, ale univerzální metodu řešení této kongruence. Při řešení kongruence (24) totiž stačí zjistit, pro která celá čísla a, 0 < a < m, platí F (a) = 0 (mod m). Nevýhodou této metody je její pracnost, která se zvyšuje se zvětšující se hodnotou m. Je-li m složené, m — p\x .. -P^, kde pi, ..., pk jsou různá prvočísla, a je-li navíc k > 1, můžeme nahradit kongruenci (24) soustavou kongruencí F(x) = G (modpí1) i (25) F(x) = 0 (mod p^), která má stejnou množinu řešení, a řešit každou kongruenci této soustavy zvlášť. Tím získáme obecně několik soustav kongruencí (19), které už umíme řešit. Výhoda této metody spočívá v tom, že moduly kongruencí soustavy (25) jsou menší než modul původní kongruence (24). příklad. Řešte kongruenci xb + 1 = 0 (mod 11). Řešení. Označme F(x) = x5 + 1. Pak platí F(0) = 1, F(l) = 2 a dále platí F(2) - 33 = 0 (mod 11), F(3) = 35 + l = 9- 9- 3 + l = (-2)2 - 3 + 1 = 12+ 1 = 2 (mod 11), F(4) =45 + l = 210 + l = l + l = 2 (mod 11), kde jsme využili Fermatovu větu 16, podle které 210 = 1 (mod 11). Podobně dále F(b) = 55 + l = 165 + 1 = 410 + 1 = 1 + 1 = 2 (mod 11), F(6) = 65 + l = (-5)5 + 1 = -165 + 1 = -410 + 1 = 0 (mod 11) F(7) = 75 + l = (-4)5 + 1 - -210 + 1 =-1 + 1 = 0 (mod 11), F(8) = 85 + l = 25 • 210 + 1 = 32 + 1 = 0 (mod 11), F(9) = 95 + l = 310 + 1 = 1 + 1 = 2 (mod 11), F(10) = - 105 + 1 = (-1)5 + 1 -0 (mod 11), a tedy řešením kongruence xb + 1 = 0 (mod 11) jsou právě všechna x, vyhovující některé z kongruencí x = 2 (mod 11), x = 6 (mod 11), x = 7 (mod 11), rr = 8 (mod 11), x = 10 (mod 11). □ PŘÍKLAD. Řešte kongruenci rr3 — 3x + 5 = 0 (mod 105). Řešeni. Kdybychom postupovali obdobně jako dříve pro m = 105, museli bychom spočítat pro F(x) = x3 — 3x + 5 sto pět hodnot F(0), ^(1), • • •, F(104). Proto raději rozložíme 105 = 3-5-7 a budeme řešit kongruence F{x) = 0 postupně pro moduly 3, 5, 7. Platí F(0) - 5, F(l) - 3, F(2) - 7, F(3) - 23, F(-l) - 7, F(—2) — 3, F(—3) — —13 (pro snadnější výpočty jsme počítali například F(—l) místo F(6) - využijeme toho, že F(6) = F(—l) (mod 7) podle předchozího Tvrzení a podobně). Kongruence F(x) = 0 (mod 3) má tedy řešení x = 1 (mod 3); kongruence F{x) = 0 (mod 5) má řešení x = 0 (mod 5); řešením kongruence F(x) = 0 (mod 7) jsou x £ Z splňující rr = 2 (mod 7) nebo x = — 1 (mod 7). Zbývá tedy vyřešit dvě soustavy kongruenci: x = 1 (mod 3), x = 1 (mod 3), rr = 0 (mod 5), a x = 0 (mod 5), rr = 2 (mod 7) x = — 1 (mod 7). Protože první dvě kongruence jsou u obou soustav stejné, budeme se nejprve zabývat jimi. Ze druhé kongruence dostáváme x — bt pro í E Z, dosazením do první 5í = 1 (mod 3), tedy —t = l (mod 3), odkud í — — 1 + 3s pro s £ Z, odkud rr — —5 + 15s. Dosaďme nejprve do třetí kongruence první soustavy: -5 + 155 = 2 (mod 7), odkud 5 = 0 (mod 7), tj. 5 — 7r pro r £ Z a proto rr — —5 + 105r. Dosadíme-li rr — —5 + 155 do třetí kongruence druhé soustavy, dostaneme —5 + 155 = —1 (mod 7), odkud 5 = 4 (mod 7), tj. s — 4 + 7r pro r G Z, a proto x — — 5 + 15(4 + 7r) — 55+105r. Celkem jsou tedy řešením dané kongruence F(x) = 0 (mod 105) všechna celá čísla x, splňující x = — 5 (mod 105) nebo x = 55 (mod 105). □ Postup pro řešení kongruencí, kde modulem je mocnina prvočísla, udává důkaz následující věty. věta 24 (Henselovo lemma). Nechť p je prvočíslo, f(x) G Z[rr], a G Z je takové, že p | /(o), p f f (cl)- Pak platí: pro každé n G N má soustava x = a (mod p) f(x) = 0 (mod pn) ^ právě jedno řešení modulo pn. důkaz. Indukcí vzhledem k n. Případ n — 1 je zřejmý. Nechť dále n > 1 a věta platí pro n — 1. Je-li rr řešením (26) pro n, je řešením (26) i pro n — 1. Libovolné řešení (26) pro rz je tedy tvaru x — cn-i + • pn_1, kde G Z. Je třeba zjistit, zda/(cn_i+fc-pn~1) = 0 (mod pn). Víme, žepn_1 | f(cn-iJrk-pn~1) a užijme binomickou větu pro f(x) — amxm + • • • + a\x + a0, kde a0,..., am G Z. Pak (cn_! + fc • p""1)1 = 4_! + ž • C_\ • fc^"1 (mod pn). Platí tedy /(Cn_! + k ■ pn~l) = /(Cn_!) + k ■ ^"VíCn-l), tj- /(cn_! + k ■ p71'1) = O (mod pn) <=> Protože cn_i = a (mod p), dostaneme f'(cn-\) = f (a) ^ 0 (mod p), tedy (f'(cn-i),p) 1. Užitím Věty 21 o řešitelnosti lineárních kongruencí dostáváme, že existuje právě jedno řešení k (modulo p) této kongruence a protože cn_i bylo podle indukčního předpokladu jediné řešení modulo pn~x, je číslo cn_i + k • pn~x jediným řešením (26) modulo pn. □ příklad. Řešte kongruencí x4 + 7x + 4 = 0 (mod 27). Řešení. Řešme nejprve tuto kongruencí modulo 3 (např. dosazením) - snadno zjistíme, že řešení je x = 1 (mod 3). Zapišme řešení ve tvaru x — 1 + 3/;, kde í G Z Home Page Title Page a řešme kongmenci modulo 9. xA + 7 x + 4 = 0 (mod 9 (1 + 3t)4 + 7(1 + St) + 4 = 0 (mod 9 1 + 4-3^ + 7 + 7-3^ + 4 = 0 (mod 9 33r = -12 (mod 9 lit = -4 (mod 3 ee 1 (mod 3 Zapsáním t — 1 + 3s, kde s G Z dostaneme x = 4 + 9s a po dosazení (4 + 9s)4 + 7(4 + 9s) + 4 ee 0 (mod 27) 44 + 4 • 43 • 9s + 28 + 63s + 4 ee 0 (mod 27) 256 • 95 + 635 ee -288 (mod 27) 2565 + 75 ee -32 (mod 3) 25 ee 1 (mod 3) 5 ee 2 (mod 3) Celkem dostáváme řešení ir = 4 + 95 = 4 + 9(2 + 3r) = 22 + 27r, kde r 6 Z, neboli x ee 22 (mod 27). □ Contents 44 Page 78 of 175 Go Back Full Screen Close Quit Řešení obecných kongruencí vyššího stupně jsme tedy převedli na řešení kon-gruencí modulo prvočíslo. Ukazuje se, že zde je největší „kámen úrazu", protože pro tyto kongruence žádný obecný postup (s výjimkou postupu podle Věty 20, tj. vyzkoušení všech možností) není znám. Uvedeme alespoň několik obecných tvrzení ohledně řešitelnosti a počtu řešení takových kongruencí a v dalších částech skript podrobnější výsledky v některých speciálních případech. 4.4. Kongruence s prvočíselným modulem. věta 25. Buď p prvočíslo, f(x) G Z[x]. Libovolná kongruence f(x) = 0 (mod p) je ekvivalentní s kongruencí stupně nejvýše p — 1. důkaz. Protože pro libovolné a G Z platí p \ ap — a (důsledek Malé Fermatovy věty), jsou řešením kongruence xp — x = 0 (mod p) všechna celá čísla. Vydělíme-li polynom f(x) se zbytkem polynomem xp — x1 dostaneme f(x) — q(x) • [xP — x) + r[x) pro vhodné f(x),r(x) G Z, kde stupeň r(x) je menší než stupeň dělitele tedy než p. Dostáváme tak, že kongruence r(x) = 0 (mod p) je ekvivalentní kongruencí f(x) = 0 (mod p) a je přitom stupně nejvýše p — 1. □ věta 26. Buď p prvočíslo, f(x) G Z[rr]. Má-li kongruence f(x) = 0 (mod p) více než st(f) řešení, pak jsou všechny koeficienty polynomu f násobkem p. DŮKAZ. V jazyce algebry jde vlastně o počet kořenů nenulového polynomu nad (konečným) tělesem Zp, kterých je nejvýše st(/). □ DŮSLEDEK. (Jiný důkaz Wilsonovy věty) Pro každé prvočíslo p platí (p — 1)! = — 1 (mod p). DŮKAZ. Pro p — 2 je tvrzení zřejmé, dále uvažujme jen lichá prvočísla p. Řešením kongruence (x - l)(x - 2) • • • (ir - (p - 1)) - (xp-1 - 1) = 0 (mod p) je podle Malé Fermatovy věty libovolné a G Z, které není násobkem p, tj. kongruence má p — 1 řešení. Přitom je ale její stupeň menší než p — 1, proto jsou podle předchozí věty všechny koeficienty polynomu na levé straně kongruence násobkem p, speciálně absolutní člen, kterým je (p — 1)! + 1. Tím je Wilsonova věta dokázána. □ 4.5. Binomické kongruence a primitivní kořeny. V této části se zaměříme na řešení speciálních typů polynomiálních kongruencí vyššího stupně, tzv. binomických kongruencí. Jde o analogii binomických rovnic, kdy polynomem f(x) je dvoj člen xn — a. Snadno se ukáže, že se můžeme omezit na případ, kdy je a nesoudělné s modulem kongruence - v opačném případě totiž vždy můžeme pomocí ekvivalentních úprav kongruencí na tento případ převést nebo rozhodnout, že kongruence není řešitelná. příklad. Řešte kongruenci x2 = 18 (mod 63). Řešení. Protože je (18,63) — 9, musí platit 9 | x2, tj. 3 | x. Položíme-li x — 3xi, x\ G Z, dostáváme ekvivalentní kongruenci x\ = 2 (mod 7), která již splňuje omezení na nesoudělnost modulu a pravé strany kongruence. Podle Věty 26 víme, že má nejvýše 2 řešení a snadno se vidí, že jimi jsou x\ = ±3 (mod 7), tj. xx = ±3, ±10, ±17, ±24, ±31, ± 38, ±45, ±52, ±59 (mod 63). Řešeními původní kongruence jsou tedy (mod 63), tj. x = ±9, ±12, ±30 (mod 63). příklad. Řešte kongruenci x3 = 3 (mod 18). Řešeni. Protože je (3,18) — 3, nutně 3 | x. Užijeme-li, podobně jako výše, substituci dostáváme kongruenci 27 x\ = 3 (mod 18), která zřejmě nemá řešení, protože (27,18) { 3. Definice. Nechť m G N, a G Z, (a, m) — 1. Číslo a nazveme n-tým mocninným zbytkem modulo m, pokud je kongruence xn = a (mod m) Home Page Title Page řešitelná. V opačném případě nazveme a n-tým mocninným nezbytkem modulo m. Pro n — 2,3,4 používáme termíny kvadratický, kubický a bikvadratický zbytek, resp. nezbytek modulo m. V tomto odstavci ukážeme, jakým způsobem řešit binomické kongruence modulo m, pokud modulo m existují tzv. primitivní kořeny. Definice. Nechť m G N. Celé číslo a G Z, (a,m) — 1 nazveme primitivním kořenem modulo m, pokud je jeho řád modulo m roven (p(m). Lemma. Je-li g primitivní kořen modulo m, pak pro každé číslo a G Z, (a, m) — 1 existuje jediné xa G Z, 0 < xa < (p(m) s vlastností gXa = a (mod m). Funkce a —>> xa se nazývá diskrétní logaritmus, příp. index čísla x (vzhledem k danému m a zafixovanému primitivnímu kořeni g) a je bijekcí mezi množinami [a G Z; (a, m) — 1, 0 < a < m} a [x G Z; 0 < x < (p(m)}. důkaz. Stačí ukázat tvrzení o bijekci a protože obě množiny mají stejný počet prvků, stačí dokázat injektivitu uvedeného zobrazení. Předpokládejme, že pro x, y G Z, 0 < x, y < (p(m) je gx = gy (mod m). Podle Věty 18 pak x = y (mod { a, p \ n. Je-li kongruence xn = a (mod p) řešitelná, je řešitelná i kongruence xn = a (mod pa) pro libovolné přirozené číslo a a má stejný počet řešení jako kongruence modulo p. DŮKAZ. Plyne z Henselova lemmatu pro kongruencí f(x) = 0 (mod p)1 kde f(x) — xn — a. Pak totiž f'(x) — n • xn~x a pokud b G Z splňuje f(b) = 0 (mod p), pak jistě p \ b, a proto p \ f'(b). VĚTA 29. Bud7 n G M, a G Z, 2 { a. Označme dále l G N0 největší takové, že 2l | n. Je-li kongruence xn = a (mod 22l+1) řešitelná, je řešitelná i kongruence DŮKAZ. Zřejmý. □ □ xn = a (mod 2a) pro libovolné « G N, « > 21 + 1 a má stejný počet řešeni jako kongruence modulo 22l+1. důkaz. Prozatím neuveden. □ Poznámka. Uvážíme-li v předchozí větě přirozené číslo n = 2 (mod 4), pak je l = 1. Pro liché a je kongruence xn = a (mod 8) řešitelná právě když je a = 1 (mod 8) (a má 4 řešení). Díky přechozí větě víme, že pro a = 1 (mod 8) má řešení libovolná kongruence tvaru xn = a (mod 2a) pro a > 3 a má 4 řešení. V předchozích odstavcích jsme se zabývali řešitelností binomických kongruencí podle modulů, pro které existuje primitivní kořen. Ve zbytku této části se budeme zabývat tím, pro která čísla primitivní kořeny existují. Postupně dokážeme následující větu: věta 30. Buď m £ n, m > 1. Primitivní kořeny modulo m existují právě tehdy, když m splňuje některou z následujících podmínek: • m = 2 nebo m = 4, • m je mocnina lichého prvočísla • m je dvojnásobek mocniny lichého prvočísla. Poznámka. Pokud pro přirozené číslo existují primitivní kořeny, tak jich mezi čísly 1,2, ...,m existuje právě (p((p(m)). Je-li totiž g primitivní kořen a a G {1,2,..., <-f(m)} libovolné, pak ga je podle Věty 19 řádu ^^m)) > co^ Je rovno (p(m) právě tehdy, je-li (a, p—1. Přitom ô | p—1 (jakožto řád čísla g)1 proto zejména 8 < p—1, a celkem 8 — p — 1. □ Nyní ukážeme, že primitivní kořeny existují dokonce modulo mocniny lichých prvočísel. K tomuto budeme potřebovat dvě pomocná tvrzení. Lemma. Buď p liché prvočíslo, l > 2 libovolné. Pak pro libovolné a G Z platí J-2 (1 + apY * = 1 + apl 1 (mod pl). důkaz. Plyne snadno z binomické věty s využitím matematické indukce. I. Pro / — 2 tvrzení zřejmě platí. II. Nechť tvrzení platí pro /, dokážeme jej i pro Z + 1. S využitím Lemmatu na str. 43 tak umocněním na p-tou tvrzení pro / (s navýšením modulu) dostaneme (1 + apf'1 = (1 + ap1'1)1? (mod pm). Z binomické věty přitom plyne fc (Z-l)fc (1 + apl-1)p = 1 + p • a • p1'1 + (fy ahP Home Page Title Page a vzhledem k tomu, že pro 1 < k < p platí p \ Q, stačí ukázat pl+1 \ p1+(l-1)k? což je ekvivalentní s 1 < (k — 1)(Z — 1). Rovněž pro k = p dostáváme díky l > 3 vztah pl+l | p(l~^p. □ Lemma. Buď p liché prvočíslo, l > 2 libovolné. Pak pro libovolné a G Z, splňující p \ a platí, že řád čísla 1 + ap modulo pl je roven pl~x. důkaz. Podle předchozího Lemmatu je (1 + apÝ~X = 1 + ap1 (mod pl+1), a uvážíme-li tuto kongruenci modulo pl, dostaneme (1 + ap)pl 1 = 1 (moáp1). Přitom přímo z předchozího Lemmatu a faktu p \ a plyne (l-\-ap)p ^ 1 (mod pl), což dává požadované. □ Tvrzení 4.2. Buď p liché prvočíslo. Pak pro každé l G n existuje primitivní kořen modulo pl. důkaz. Nechť g je primitivní kořen modulo p. Ukážeme, že pokud gv~x ^ 1 (mod p2), je g dokonce primitivním kořenem modulopl pro libovolné l G N. (Pokud by platilo gv~x = 1 (mod p2), pak (g + p)ř>_1 = 1 + (p — l)gp~2p ^ 1 (mod p2), a tedy místo g můžeme volit za původní primitivní kořen číslo g Nechť tedy g splňuje gv~x ^ 1 (mod p2). Pak existuje a G Z, p \ a tak, že gP-i _ i -|- p . a_ Ukážeme, že p je modulo pz řádu ip(pl) = (p — l)pl~ľ. Buď I I Contents 44 Page 88 of 175 Go Back Full Screen Close Quit n g N nejmenší číslo, splňující gn = 1 (mod pl). Podle předchozího Lemmatu je gP-i _ i + p . a řádu modulo pl. Pak ale (pP-1)" - {gn)p~1 ee 1 (mod pl) p1"1 | n. Zároveň z gn ee 1 (mod p) plyne p—1 \ n. Protože jsou čísla p—1 a^-1 nesoudělná, dostáváme (p — l)^-1 | n. Proto n = <-f(pl) a g je tedy primitivní kořen modulo pl. □ Tvrzení 4.3. Buď p liché prvočíslo a g primitivní kořen modulo pl pro l g n. Pak liché z čísel g,g + pl je primitivním kořenem modulo 2pl. důkaz. Nechť c je liché přirozené číslo. Pak pro libovolné n g N platí cn ee 1 (mod^), právě když cn ee 1 (mod 2pl). Protože <-f(2pl) = <-f(pl), je každý lichý primitivní kořen modulo pl rovněž primitivním kořenem modulo 2pl. □ Další tvrzení popisuje případ mocnin sudého prvočísla. K tomu využijeme obdobných pomocných tvrzení jako v případě lichých prvočísel. Lemma. Buď l g N, l > 3. Pak 52*"3 ee 1 + 21'1 (mod 2l). důkaz. Obdobně jako výše pro 2 \p. □ Lemma. Buď l g n, / > 3. Pak řád čísla 5 modulo 2l je 2l~2. důkaz. Snadný z předchozího Lemmatu. □ Tvrzení 4.4. Nechí l g n. Primitivní kořeny existují modulo 2l právě tehdy, když l < 2. důkaz. Buď l > 3. Pak množina S = {{-l)a • 56; a g {0,1}, 0 < b < 2l~2- b g Z} tvoří redukovanou soustavu zbytků modulo 2l (má totiž ip(2l) prvků o kterých se snadno ukáže, že jsou po dvou nekongruentní modulo 2l). Přitom zřejmě (s využitím předchozího Lemmatu) řád každého prvku S dělí 2l~2, proto v této (a tedy ani v žádné jiné) redukované soustavě nemůže existovat prvek řádu (p(2l) — 2l~l. □ Posledním kamínkem do mozaiky tvrzení, která společně dokazují Větu 30, je tvrzení popisující neexistenci primitivních kořenů pro složená čísla, která nejsou mocninou prvočísla (ani jejím dvojnásobkem). Tvrzení 4.5. Nechí m g n je dělitelné alespoň 2 prvočísly a není dvojnásobkem mocniny lichého prvočísla. Pak modulo m neexistují primitivní kořeny. důkaz. Buď rozklad m na prvočísla tvaru 2ap^1 ■■■p^k, kde a g n0,«i g n, 2 \pi a buď platí > 2 nebo k >laa>2. Označíme-li ô = [(p(2a),(p(p^),... ^{pT\ pak se snadno vidí, že ô < (p(2a) • ^(Pi1) • • • ^(Pi1) — tp(m) a že pro libovolné a g Z, (a,m) — 1 platí a6 = 1 (mod m). Proto modulo m neexistují primitivní kořeny. □ Nyní máme dokázáno tvrzení přesně charakterizující ty moduly, pro které existují primitivní kořeny. Obecně je ale pro daný modul nalezení primitivního kořene velmi výpočetně náročná operace. Následující věta nám udává ekvivalentní podmínku pro to, aby zkoumané číslo bylo primitivním kořenem, jejíž ověření je o něco snazší než přímý výpočet řádu tohoto čísla. věta 31. Buď m takové, že modulo m existují primitivní kořeny. Zapišme (p(m) — q^1 • • • q^k. Pak pro libovolné g £ Z, (g,m) — 1 platí, že g je primitivní kořen modulo m, právě když Lp(m) y(m) g qi ^ 1 (mod m),... ,g qk ^ 1 (mod m). DŮKAZ. Pokud by platila některá z uvedených kongruencí, znamenalo by to, že řád g je menší než cp(m). Obráceně, pokud g není primitivní kořen, pak existuje d £ N, d \ ip(m), kde d < (p(m) a gd = 1 (mod m). Je-li u — > 1, nutně existuje i G {1,..., k} tak, že qi \ u. Pak ale g qí = g qí = 1 (mod m). □ příklad. Postupně určíme primitivní kořeny modulo 41, 412 a 2 • 412. ŘEŠENÍ. Protože v?(41) — 40 — 23 • 5, je libovolné celé číslo g, které je s 41 nesoudělné, primitivním kořenem modulo 41 právě tehdy, když g20 ž 1 (mod 41) A^l (mod 41). g = 2 : 28 = 25 • 23 = -9 • 8 = 10 (mod 41) 220 = ^5)4 = (_g)4 = gl2 = (_-q2 = ľ (mod p = 3 : 38 - (34)2 = (-1)2 = 1 (mod 41) g — 4 : řád 4 — 22 vždy dělí řád 2 p = 5 : 58 - (52)4 = (-24)4 - 216 = (28)2 = 102 = 18 (mod 41) 520 = (52}10 = (_24}10 = 240 = (220)2 = x (mod 41) p - 6 : 68 = 28 • 38 = 10 • 1 = 10 (mod 41) 620 = 220 . 32o = 220 . (38)2 .^ = 1.1. = _ľ (mod 41) Dokázali jsme tak, že 6 je (nejmenší kladný) primitivní kořen modulo 41 (pokud by nás zajímaly i ostatní primitivní kořeny modulo 41, tak bychom je dostali umocněním 6 na všechna čísla od 1 do 40, která jsou se 40 nesoudělná - je jich právě k • a = ±1 • a (mod p) ==> k = ±1 (mod p), což nelze jinak, než že k = l). Home Page Title Page Proto splývají množiny {1, 2,..., ^y^} a {mi,m2,..., m^}. Vynásobením kongruencí 1 • a = ±mi (mod p) 2 • a = ±m2 (mod p) p — 1 a = impj. (mod p) dostáváme p-ľ> a^ = (-ir p 1 (mod p) 2 v 7 2 (mezi pravými stranami je jich právě fi záporných). Po vydělení obou stran číslem p—i ((p—1)/2)! dostáváme díky vztahu (a/p) = a 2 (mod p) požadované tvrzení. □ S využitím Gaussova lemmatu dokážeme hlavní větu této části, tzv. zákon kvadratické reciprocity. VĚTA 32. Nechť p, q jsou lichá prvočísla. Pak i- (f) = (-i); (I) = (-1)^ 2-1 2 Contents Page 99 of 175 Go Back Full Screen Close Quit DŮKAZ. Věta se v tomto tvaru uvádí zejména proto, že pomocí těchto tří vztahů a základních pravidel pro úpravy Legendreova symbolu jsme schopni vypočítat hodnotu (a/p) pro libovolné celé číslo a. První část tvrzení již máme dokázánu, v dalším nejprve odvodíme mezivýsledek, který využijeme k důkazu zbylých částí. Poznamenejme rovněž, že v literatuře existuje mnoho různých důkazů této věty (v roce 2010 uváděl F. Lemmermeyer 233 důkazů), obvykle ovšem využívajících (zejména u těch stručnějších z nich) hlubších znalostí z algebraické teorie čísel. Nechť je dále a G Z, p { a, G Na nechť [x] (resp. (x)) značí celou (resp. necelou) část reálného čísla x. Pak ~2ak ak + 2( 'ak\ ak n/ ak\ — 2 — — ) = 2 — + 2( —) . P . . P . \ P 1 . P . _ \ P 1 _ Tento výraz je lichý právě tehdy, když je (—) > |, tj. právě tehdy, je-li nej menší zbytek (v absolutní hodnotě) čísla ak modulo p záporný (zde by měl pozorný čtenář zaznamenat návrat od výpočtů zdánlivě nesouvisejících výrazů k podmínkám souvisejícím s Legendreovým symbolem). Proto je =(-!)" = (-1)^1^1. Je-li navíc a liché, je a + p číslo sudé a dostáváme Í2a \p '2a + 2p 2 2 P p—l p—i ■šp~2~ r ("+p)fci . . rafci ■(-l)E P-l 2 ŕ fc=l K -) = (_i)ESľ[f] (-1) P2-1 p J \ p — (_l)^fc=i Lv p" J — Celkem tak dostáváme (pro liché a) což pro a — 1 dává požadované tvrzení z bodu 2. Podle již dokázané části 2 a ze vztahu (28) dostáváme pro lichá čísla a = (-l)SSľ[f]. Uvažme nyní pro daná prvočísla p ^ q množinu T = [q ■ x; x G Z, 1 < x < {p - l)/2} x [p ■ y; y G Z, 1 < y < (q - l)/2} Zřejmě je |T| — • a ukážeme, že rovněž (-1)\T\ = {_1)x£[*].{_1)^[f]i čímž budeme vzhledem k předchozímu hotovi. Protože pro žádna x, y z přípustného rozsahu nemůže nastat rovnost qx — py, můžeme množinu T rozložit na dvě disjunktní podmnožiny T\ a T2 tak, že T\ — T n {[u, v]; u, v G Z, u < v}, T2 — T \ T\. Zřejmě je T\ počet dvojic [qx,py], kde x < £y. Protože -qy <-q- ^ < |, je [^y] < Pro pevné y tedy v T\ leží právě ty dvojice [qx,py], pro které 1 < x < [Ey], a tedy |Xí| — Y^y=i^2[EV\- Analogicky Proto (|) — (—l)'Tl' a (J) — (—1)'T2' a zákon kvadratické reciprocity je dokázán. □ DŮSLEDEK. 1. — 1 je kvadratický zbytek pro prvočísla p splňující p = 1 (mod 4) a nezbytek pro prvočísla splňující p = 3 (mod 4). 2. 2 je kvadratický zbytek pro prvočísla p splňující p = ±1 (mod 8) a nezbytek pro prvočísla splňující p = ±3 (mod 8). 3. Je-li p = 1 (mod 4) nebo q = 1 (mod 4), je (p/q) — (q/p), jinak (tj. p = q = 3 (mod 4)J je (p/g) — — (q/p)- PŘÍKLAD. Určete (^-). Řešení. 79 101 /íor VŤ9 '22N 79 2 79, lť 79 lť 79 neboť 101 dává po děleni 4 zbytek 1 neboť 79 dává po dělení 8 zbytek -1 neboť 11 i 79 dávají po dělení 4 zbytek 3 neboť 11 dává pod dělení 8 zbytek 3 4.7. Jacobiho symbol. Vyčíslení Legendreova symbolu (jak jsme viděli i v předchozím příkladu) umožňuje používat zákon kvadratické reciprocity jen na prvočísla a nutí nás tak provádět faktorizaci čísel na prvočísla, což je výpočetně velmi náročná operace. Toto lze obejít rozšířením definice Legendreova symbolu na tzv. Jacobiho symbol s podobnými vlastnostmi. Definice. Nechť a g Z, b g N, 2 \ b. Nechť b = piP2---Pk je rozklad b na (lichá) prvočísla (výjimečně neseskupujeme stejná prvočísla do mocniny, ale vypisujeme každé zvlášť, např. 135 — 3 • 3 • 3 • 5). Symbol se nazývá Jacobiho symbol. Dále ukážeme, že Jacobiho symbol má podobné vlastnosti jako Legendreův symbol (s jednou podstatnou odchylkou). Neplatí totiž obecně, že z (a/b) — 1 plyne řešitelnost kongruence x2 = a (mod b). příklad. = (-1) •(-!) = ! a přitom kongruence x2 = 2 (mod 15) není řešitelná (není totiž řešitelná kongruence x2 = 2 (mod 3) a není ani řešitelná kongruence x2 = 2 (mod 5)). Home Page Tvrzení 4.7. Nechi 6, b' G N jsow lichá, aJaÍJa2 G Z libovolná. Pak platí: 1. ai = a2 (mod 6) (f) = (f), 3- (ů) = (!)(£)• 77t/e Page Contents 44 ►► Lemma. Buďte a, 6 G N /zc/id p/aü' 7. %± = ^ + ^± (mod2); 2. 2 a2ó2-l ^ + ^ (mod 2). DŮSLEDEK. Pro ai,..., am G N lichá platí 1- Ľľ=i ^ = nľ=12°fc"1 (mod 2), Ľľ^i^-11^ (mod 2). VĚTA 33. Nechi a, 6 G N jsow řzc/iá. 2. (f) = (-i)^1, 3- (!)(!) = (-i)V*. DŮKAZ. Snadný. □ Page 105 ofl75 Go Back Full Screen Close Quit 4.8. Aplikace Legendreova a Jacobiho symbolu. Primární motivací k zavedení Jacobiho symbolu byla potřeba vyčíslení Legendreova symbolu (a tedy rozhodnutí o řešitelnosti kvadratických kongruencí) bez nutnosti rozkladu čísel na prvočísla. Ukažme si proto příklad takového výpočtu. příklad. Rozhodněte o řešitelnosti kongruence x2 = 219 (mod 383). ŘEŠENÍ. 383 je prvočíslo, proto bude kongruence řešitelná, bude-li Legendreův symbol (219/383) - 1. '219N 383 '383N ,219, 164N 219 41 ,219, '219N Jl 14N 41 2 7 41/ V 41 7 ,41, '4ť 7 -r (Jacobi) 383 i 219 dávají po dělení 4 zbytek 3 164 - 22 • 41 (Jacobi) neboť 41 dává po dělení 4 zbytek 1 neboí 41 dává pod dělení 8 zbytek 1 neboí 41 dává pod dělení 4 zbytek 1 Další aplikací je v jistém smyslu opačná otázka: Pro která prvočísla je dané číslo a kvadratickým zbytkem? (tuto otázku již umíme odpovědět např. pro a — 2). Prvním krokem je zodpovězení této otázky pro prvočísla. VĚTA 34. Nechť q je liché prvočíslo. • je-li q = 1 (mod 4), pak je q kvadratický zbytek modulo ta prvočísla p, která splňují p = r (mod q), kde r je kvadratický zbytek modulo q. • je-li q = 3 (mod 4), pak je q kvadratický zbytek modulo ta prvočísla p, která splňují p = ±62 (mod 4q), kde b je liché a nesoudělné s q. DŮKAZ. První tvrzení plyne triviálně ze zákona kvadratické reciprocity. Nechť tedy q = 3 (mod 4), tj. (q/p) — (—l)~(p/q). Nechť nejprve p = +b2 (mod 4g), kde b je liché. Pak p = b2 = 1 (mod 4) a p = b2 (mod q). Tedy (—1)~ — 1 a (p/q) — 1, odkud (q/p) — 1. Je-li nyní p = —b2 (mod 4g), pak obdobně p = —b2 = 3 (mod 4) a p = —b2 (mod q). Tedy (—1)^2" = —1 a (p/q) — —1, odkud opět (q/p) — 1. p_i Obráceně, mějme (q/p) — 1. Máme dvě možnosti - buď (—1)~ — 1 a (p/q) — p—i 1, nebo (—1)~2~ = — 1 a (p/q) — — 1. V prvním případě je p = 1 (mod 4) a existuje b tak, že p = b2 (mod q) (lze přitom předpokládat, že b liché). Pak ale b2 = 1 = p (mod 4) a celkem p = b2 (mod 4g). V druhém případě je p = 3 (mod 4) a existuje 6 liché tak, že p = —62 (mod g). Tedy — b2 = 3 = p (mod 4) a celkem p = —62 (mod 4g). □ příklad. Určete modulo která prvočísla je a) 3 b) -3 c) 6 kvadratickým zbytkem. Následující tvrzení ukazuje, že pokud je modul kvadratické kongruence prvočíslo splňující p = 3 (mod 4), pak umíme nejen rozhodnout o řešitelnosti kongruenci, ale rovněž popsat všechna řešení. Tvrzení 4.8. Nechť p = 3 (mod 4), a g Z splňují (a/p) — 1. Pak má kongruence x2 = a (mod p) řešení x = ±a 4 (mod p). důkaz. Ověříme snadno zkouškou (mod p). □ Pro dokreslení obrazu o kvadratických zbytcích a nezbytcích formulujeme ještě jedno tvrzení (pro nepříliš obtížný důkaz euklidovského typu viz [3]). VĚTA 35. Nechť a £ N není druhou mocninou. Pak existuje nekonečně mnoho prvočísel, pro která je a kvadratickým nezbytkem. Home Page Title Page Contents 44 ►► Page 110 of 175 Go Back Full Screen Close Quit Home Page Title Page 5. Aplikace teorie čísel 5.1. Výpočetní aspekty teorie čísel. V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů: Contents 44 (1) běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech, (2) zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m. (3) inverzi celého čísla a modulo m £ N, (4) největší společný dělitel dvou celých čísel (a případně koeficienty do Bez-outovy rovnosti), (5) rozhodnout o daném čísle, je-li prvočíslo nebo složené, (6) v případě složenosti rozložit dané číslo na součin prvočísel. Page 111 of 175 Go Back Základní aritmetické operace se i na velkých číslech obvykle provádějí _ obdobně jako jsme se to učili na základní a střední škole, kdy umíme sčítat v lineárním, násobit a dělit se zbytkem v kvadratickém čase. Pro násobení, které je základem mnoha dalších operací, existují asymptoticky rychlejší algoritmy — (typu rozděl a panuj) - např. první takový Karatsubův (1960) časové náročnosti 0(rzlog23) nebo algoritmus Schonhage-Strassenův (1971) časové náročnosti 0(rzlogrzlog logn). který využívá tzv. Fast Fourier Transform. Ten je ale přes svou asymptotickou — Full Screen Close Quit převahu výhodný až pro násobení čísel majících alespoň desítky tisíc cifer (a používá se tak např. v GIMPS). Pěkný přehled je např. na http: //en. wikipedia. org/wiki/Computational. complexity_of_mathematical_operations GCD a modulární inverze. Jak už jsme ukazovali dříve, výpočet řešení kon-gruence a • x = 1 (mod m) s neznámou x lze snadno (díky Bezoutově větě) převést na výpočet největšího společného dělitele čísel a a m a na hledání koeficientů k, l do Bezoutovy rovnosti k • a + l • m — 1 (nalezené k je pak onou hledanou inverzí a modulo m). function extended_gcd (a , m) i f m —— 0 return (1, 0) else (q, r) :— divide (a, m) (k, 1) :— extended_gcd(m, r) return (1, k — q * 1) Podrobná analýza (viz např. [Knuth] nebo [Wiki]) ukazuje, že tento algoritmus je kvadratické časové složitosti. Modulární umocňování je, jak jsme již viděli dříve, velmi využívaná operace mj. při ověřování, zda je dané číslo prvočíslo nebo číslo složené. Jedním z efektivních algoritmů je tzv. modulární umocňování zprava doleva: function modular_pow (base , exponent, modulus) result :— 1 while exponent > 0 if (exponent mod 2 = 1): result :— (result * base) mod modulus exponent :— exponent » 1 base — (base * base) mod modulus return result Algoritmus modulárního umocňování je založen na myšlence, že např. při počítání 264 (mod 1000) • není třeba nejprve počítat 264 a poté jej vydělit se zbytkem číslem 1000, ale lépe je postupně násobit „dvojky" a kdykoliv je výsledek větší než 1000, provést redukci modulo 1000, • ale zejména, že není třeba provádět takové množství násobení (v tomto případě 63 naivních násobení je možné nahradit pouze šesti umocněními na druhou, neboť 264 = ^^yyyyy^ příklad (Ukázka průběhu algoritmu). Vypočtěme 2560 (mod 561). Protože 560 — (1000110000)2, dostaneme uvedeným algoritmem exponent base result exp's last digit 560 2 1 0 280 4 1 0 140 16 1 0 70 256 1 0 35 460 1 1 17 103 460 1 8 511 256 0 4 256 256 0 2 460 256 0 1 103 256 1 0 511 1 0 A tedy 2560 = 1 (mod 561). V průběhu algoritmu se pro každou binární číslici exponentu provede umocnění základu na druhou modulo n (což je operace proveditelná v nejhůře kvadratickém čase), a pro každou „jedničku" v binárním zápisu navíc provede jedno násobení. Celkově jsme tedy schopni provést modulární umocňování nejhůře v kubickém čase. 5.2. Testy na složenost. Přestože platí základní věta aritmetiky, která nám garantuje, že každé přirozené číslo se dá jednoznačným způsobem rozložit na součin prvočísel, praktické nalezení tohoto rozkladu je obvykle velmi výpočetně náročná operace, obvykle prováděná v několika krocích: (1) nalezení všech dělitelů nepřevyšujících určitou hranici (metodou pokusného dělení všemi prvočísly až do této hranice, typicky je touto hranicí cca 106) (2) otestování zbylého faktoru na složenosti (tzv. test na složenost, testující některou nutnou podmínku prvočíselnosti) a) pokud test složenosti prohlásil, že zkoumané číslo je asi prvočíslo, pak testem na prvočíselnost ověřit, že je to opravdu prvočíslo. b) pokud test složenosti prohlásil, že zkoumané číslo je složené, pak nalézt netriviálního dělitele. Takto je posloupnost kroků prováděna z toho důvodu, že jednotlivé algoritmy mají postupně (výrazně) rostoucí časovou složitost. V roce 2002 Agrawal, Kayal a Saxena publikovali algoritmus, který testuje prvočíselnost v polynomiálním čase, prakticky je ale zatím stále efektivnější používat výše uvedený postup. Takzvané testy na složenost testují některou nutnou podmínku prvočíselnosti. Nejjednodušší takovou podmínkou je Malá Fermatova věta. Tvrzení 5.1. Fermatův test Existuje-li pro dané N nějaké a ^ 0 (mod N) takové, že aN~ľ ^ 1 (mod N), pak N není prvočíslo. Bohužel nemusí být pro dané složené A" snadné najít takové a, že Fermatův test odhalí složenost N; pro některá výjimečná A" dokonce jediná taková a jsou ta soudělná s N; jejich nalezení je tedy ekvivalentní s nalezením dělitele, a tedy i s rozkladem A" na prvočísla. Carmichaelova čísla. Skutečně existují taková nehezká (nebo extrémně hezká?) složená čísla N, která splňují, že pro libovolné a nesoudělné s A" platí aN~ľ = 1 (mod N). Taková čísla se nazývají Carmichaelova, nejmenší z nich je 561 — 3T1-17 a teprve v roce 1992 se podařilo dokázat, že jich je dokonce nekonečně mnoho (v OEIS jde o posloupnost A002997: 561,1105,1729, 2465, 2821,...). příklad. Dokážeme, že 561 je Carmichaelovo, tj. že pro každé a g n, které je nesoudělné s 3 • 11 • 17, platí a560 = 1 (mod 561). Z vlastností kongruencí víme, že stačí dokázat tuto kongruenci modulo 3,11 i 17. To ale dostaneme přímo z Malé Fermatovy věty, protože takové a splňuje a2 = 1 (mod 3), a10 = 1 (mod 11), a16 = 1 (mod 17), přičemž 2,10 i 16 dělí 560 (viz též Korseltovo kritérium). VĚTA 36 (Korseltovo kritérium). Složené číslo n je Carmichaelovým číslem, právě když je nedělitelné čtvercem (square-free) a pro všechna prvočísla p dělící n platí p — 1 | n — 1. příklad. Dokažte, že čísla 2465 a 2821 jsou Carmichaelova. Eulerův test (též Euler-Jacobi, Solovay-Strassen). Fermatův test lze zlepšit s využitím kvadratických zbytků na Eulerův test, ale výše zmíněný problém se ani tak zcela neodstraní. Tvrzení 5.2 (Eulerův test). Je-li N prvočíslo a a g Z, N \ a, pak N-l . a— = (a/N) (mod TV). příklad. Uvažme3 a = 5: Pak 5280 = 1 (mod 3),5280 = 1 (mod 11), přitom 5280 = —1 (mod 17), proto určitě 5280 ^ ±1 (mod 561). Zde došlo k tomu, že neplatilo a~^~ = ±1 (mod TV), proto ani nebylo třeba testovat hodnotu Jacobiho symbolu, často ale právě Eulerův test může odhalit složené číslo i v případě, kdy tato mocnina je rovna ±1. příklad. Test, zda a^1 = ±1 (mod TV), neodhalí například TV — 1729 — 7 • 13 • 19, neboť ^f1 = 864 - 25 • 33 je dělitelné 6, 12 i 18 a tedy z Fermatovy věty plyne, že pro všechna celá čísla a nesoudělná s TV platí a~^~ = 1 (mod TV). Přitom ale pro a — 11 dostaneme (y^g) — —1 a Eulerův test tedy složenost čísla 1729 odhalí. Poznamenejme, že hodnotu Legendreova nebo Jacobiho symbolu (£) lze díky zákonu kvadratické reciprocity spočítat v lepším než kubickém čase. Definice (Pseudoprvočísla). Složené číslo n se nazývá pseudoprvočíslo, pokud projde testem na složenost a není jím odhaleno jako složené. Máme tak (1) Fermatova pseudoprvočísla o základu a (2) Eulerova pseudoprvočísla Testování by selhalo už pro a = 3, ale to je dělitel, my chceme ukázat, že test může uspět i bez nalezení dělitele. (3) silná (strong) pseudoprvočísla o základu a, pokud projdou následujícím testem na složenost. Tvrzeni 5.3 (Test na složenost - zesílení Malé Fermatovy věty). Nechi p je liché prvočíslo. Pišme p — 1 — 2ť ■ q, kde t je přirozené číslo a q je liché. Pak pro každé celé číslo a nedělitelné p bud? platí aq = 1 (mod p)) nebo existuje e £ {0,1, — 1} splňující a2eq = —1 (mod p)). Ukazuje se, že tento snadný test výrazně zesiluje schopnost rozpoznávat složená čísla. Nej menší silné pseudoprvočíslo o základu 2 je 2047 (přitom nej menší Ferma-tovo o základu 2 bylo již 341) a při otestování základů 2, 3 a 5 dostaneme nejmenší pseudoprvočíslo 25326001. Jinými slovy, pokud nám stačí testovat pouze čísla do 2 • 10 , pak stačí tento test na složenost provést pouze pro základy 2, 3 a 5. Pokud číslo není odhaleno jako složené, pak je určitě prvočíslem. Na druhou stranu, bylo dokázáno, že žádná konečná báze není dostatečná. Test Millera a Rabína je praktickou aplikací předchozího testu, kdy jsme navíc schopni omezit pravděpodobnost neúspěchu. VĚTA 37. Nechť N > 10 je liché složené číslo. Pišme N — 1 — 2ť ■ q, kde t je přirozené číslo a q je liché. Pak nejvýše čtvrtina z čísel množiny [a G Z; 1 < a < TV, (a, TV) — 1} splňuje následující podmínku: aq = 1 (mod N) nebo existuje e G {0,1, — 1} splňující a2Ěq = -1 (mod TV). V praktických implementacích se obvykle testuje cca 20 náhodných základů (příp. nejmenších prvočíselných základů). V takovém případě dostáváme z předchozí věty, že pravděpodobnost neodhalení složeného čísla je menší než 2~40. Časová náročnost algoritmu je asymptoticky stejná jako složitost modulárního umocňování, tedy nejhůře kubická. Je ale třeba si uvědomit, že test je nedeterministický a spolehlivost jeho deterministické verze závisí na tzv. zobecněné Rie-mannově hypotéze (GRH). 5.3. Testy na prvočíselnost. Testy na prvočíselnost přicházejí na řadu obvykle ve chvíli, kdy testy na složenost prohlásí, že jde pravdepodobne o prvočíslo, případně se provádějí rovnou u speciálních typů čísel. Uveďme nejprve přehled nejznámějších testů. (1) AKS (2002) - obecný polynomiální test na prvočísla (2) Pocklington-Lehmerův test - test na prvočíselnost subexponenciální složitosti (3) Lucas-Lehmerův test - test prvočíselnosti pro Mersenneho čísla (4) Pépinův test (1877) - test prvočíselnosti pro Fermatova čísla (5) ECPP - test prvočíselnosti založený na tzv. eliptických křivkách Speciální testy — Mersenneho čísla. Tvrzeni 5.4 (Lucas-Lehmerův test). Definujme posloupnost (sn)^=0 rekurzívně předpisem s0 — 4, sn+í — s2n — 2. Pak je číslo Mp — 2P — 1 prvočíslo, právě tehdy, když Mp dělí sv-2. II Determine if Mp — 2P — 1 is prime Lucas—Lehmer (p) var 5 — 4 var M = 2P — l repeat p — 2 times : s = s2 -2 (mod M) if 5-0 return PRIME else return COMPOSITE Časová složitost testu je asymptoticky stejná jako v případě Miller-Rabinova testu, v konkrétních případech je ale efektivnější. Speciální testy — Fermatova čísla. Fermatova čísla jsou čísla tvaru Fn — 22n + 1. Pierre de Fermat v 17. století vyslovil hypotézu, že všechna čísla tohoto tvaru jsou prvočísly (zřejmě veden snahou zobecnit pozorování pro F0 — 3, F\ — 5, F2 — 17, F3 — 257 a F4 — 65537. V 18. století ale Leonhard Euler zjistil, že F5 — 641 x 6700417 a dodnes se nepodařilo nalézt žádné další Fermatovo prvočíslo. Vzhledem k rychle rostoucí velikosti těchto čísel je počítání s nimi velmi časově náročné (a ani následující test tak není příliš používán). V současné době nejmenší netestované Fermatovo číslo je F33, které má 2 585 827973 číslic, a je tak výrazně větší než největší dosud nalezené prvočíslo. Tvrzení 5.5 (Pépinův test). Označme Fn — 22n + 1 tzv. n-té Fermatovo číslo. Pak Fn je prvočíslo, práve když 3^ = _i (mod Fn). Vidíme, že jde o velmi jednoduchý test, který je vlastně pouze malou částí Eulerova testu na složenost. důkaz korektnosti pépinova testu. Platí-li 3 "2 = —1 (mod Fn), je nutně Fn — 1 řádem čísla 3 modulo Fn, proto je Fn prvočíslo. Obráceně, nechť je Fn prvočíslo. Z Eulerova kritéria dostáváme, že 3^2~ = (jr) (mod Fn), tj. stačí nám určit hodnotu (y-)- To je ale snadné, protože Fn = 2 (mod 3) a tedy (^f) — —1. Dále Fn = 1 (mod 4), proto díky zákonu kvadratické reciprocity dostáváme — —1. □ Pocklington-Lehmerův test. Na závěr uveďme i obecný test na prvočíselnost, který použijeme, pokud chceme vysokou pravděpodobnost Miller-Rabínova algoritmu proměnit v jistotu (ta jistota je ale relativní - udává se, že pravděpodobnost selhání Miller-Rabinova algoritmu je nižší než HW chyba během výpočtu). věta 38. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělící N — 1. Předpokládejme dále, že existuje ap g Z tak, že af-1 = 1 (mod N) a (app - 1, N^j = 1. Nechť pap je nejvyšší mocnina p dělící N — 1. Pak pro každý kladný dělitel d čísla N platí d=l (mod pap). důkaz věty Pocklingtona a Lehmera. Každý kladný dělitel d čísla tv je součinem prvočíselných dělitelů čísla tv, větu dokažme pouze pro d prvočíslo. JV-1 Podle Fermatovy věty platí a^-1 = 1 (mod d), neboť (ap, N) — 1. Protože (ap p — 1, N) = 1, platí app ^ 1 (mod d). Označme e řád ap modulo d. Pak platí e|d — 1, e | A/" — 1 aej Kdyby { e, z e | A^ — 1 by plynulo e | spor. Je tedy pap | e, a tedy i pap | d - 1. □ Užití věty Pocklingtona a Lehmera. Tvrzení 5.6. Nechí N g N, A" > 1. Předpokládejme, že můžeme psát N — 1 — F • U, kde (F, ř7) = 1 a F > ^/N, přičemž známe rozklad čísla F na prvočinitele. Pak platí: • jestliže pro každé prvočíslo p \ F můžeme najít ap g Z z předchozí věty, pak je N prvočíslo; • je-li N prvočíslo, pak pro libovolné prvočíslo p \ N — 1 existuje ap g Z s požadovanými vlastnostmi. důkaz, ad 1. Podle Věty je d = 1 (mod pap) pro všechny prvočíselné faktory F, proto je d = 1 (mod F), a tedy d > \/N. ad 2. Stačí za ap zvolit primitivní kořen modulo prvočíslo A" (nezávisle na p). □ Poznámka. Předchozí test v sobě zahrnuje Pépinův test (totiž pro N — Fn máme p — 2, kterému vyhovuje svědek prvočíselnosti ap — 3). 5.4. Hledání dělitele. Máme-li testem na složenost potvrzeno, že jde o číslo složené, obvykle chceme najít netriviálního dělitele. Jde ale o výrazně obtížnější úkol (což je na druhé straně výhodné pro RSA a podobné protokoly), proto si k tématu uvedeme jen stručný přehled používaných metod. (1) Pokusné dělení - v krajním případě je možné testovat potenciální (prvočíselné) dělitele až do y/n, tedy v nej horším případě vykonáme až 0(y/n) dělení. (2) Pollardova p-metoda (3) Pollardova p — 1 metoda (4) faktorizace pomocí eliptických křivek (5) Metoda kvadratického síta (QS) (6) Metoda síta v číselném tělesa (NFS) Podrobnosti viz předmět M8190 Algoritmy teorie čísel. 5.5. Kryptografie s veřejným klíčem. Dva hlavní úkoly pro kryptografie s veřejným klíčem (PKC - public key cryptography) jsou zajistit • šifrování, kdy zprávu zašifrovanou veřejným klíčem příjemce není schopen rozšifrovat nikdo kromě něj (resp. držitele jeho soukromého klíče) • podepisování, kdy integrita zprávy podepsané soukromým klíčem odesílatele může být ověřena kýmkoliv s přístupem k veřejnému klíči odesílatele Nejčastěji používané systémy PKC: • RSA (šifrování) a odvozený systém pro podepisování zpráv • Digital signatuře algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA) • Rabinův kryptosystém (a podepisování) • ElGamal kryptosystém (a podepisování) • Kryptografie eliptických křivek (ECC) • Diffie-Hellmanův protokol na výměnu klíčů (DH) Princip digitálního podpisu. Proces podepisování a ověření podpisu zprávy M probíhá obvykle v následujících krocích. Podepisování (1) Vygeneruje se otisk (hash) Hm zprávy pevně stanovené délky (např. 160 nebo 256 bitů). (2) Podpis zprávy Sa(Hm) je vytvořen (pomocí dešifrování) z tohoto hashe s nutností znalosti soukromého klíče podepisujícího. (3) Zpráva M (případně zašifrovaná veřejným klíčem příjemce) je spolu s podpisem odeslána. Ověření podpisu (1) K přijaté zprávě M se (po jejím případném dešifrování) vygeneruje otisk (2) S pomocí veřejného klíče (deklarovaného) odesílatele zprávy se rekonstruuje původní otisk zprávy Va(Sa(Hm)) — HM- (3) Oba otisky se porovnají HM — H'M1. RSA Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks, GCHQ -1973) • každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a • generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n — pq, (f(n) — (p — l)(q — 1) [n je veřejné, ale ip(n) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e, <-f(n)) — 1 • např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod (p(n)) • zašifrování numerického kódu zprávy M: C — Ce(M) = Me (mod n) • dešifrování šifry C: OT — Dd(C) = Cd (mod n) Rabínův krypt osy stém je prvním veřejným kryptosystémem, k jehož prolomení je prokazatelně potřeba faktorizovat modul. Uvedeme si jej ve zjednodušené verzi: • každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a • generování klíčů: A zvolí dvě podobně velká prvočísla p,q = 3 (mod 4), vypočte n — pq. • VA = n, SA = (p, q) • zašifrování numerického kódu zprávy M: C = Ce(M) = M2 (mod n) • dešifrování šifry C: vypočtou se (čtyři) odmocniny z C modulo n a snadno se otestuje, která z nich byla původní zprávou. Výpočet druhé odmocniny z C modulo n — pq, kde p =. q =. 3 (mod 4) . • vypočti r — c^1)/4 (mod p) as - C^q+l^A (mod g) • vypočti a, 6 tak, že ap + 6g — 1 • polož4 x — (aps + bqr) (mod n), y = (aps — bqr) (mod rz) • druhými odmocninami z c modulo n jsou ±rr, ±í/. příklad. V Rabinově kryptosystému Alice zvolila za svůj soukromý klíč p — 23, q — 31, veřejným klíčem je pak n — pq — 713. Zašifrujte zprávu m — 327 pro Alici a ukažte, jak bude Alice tuto zprávu dešifrovat. Řešení, c = 692, kandidáti původní zprávy jsou ±4 • 23 • 14 ± 3 • 31 • 18 (mod 713). 4Uvědomte si, že jde vlastně o aplikaci Čínské zbytkové věty! Dime-Hellman key exchange. Whitfield Diffie, Mariin Hellman (1976; M. Williamson, GCHQ - 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, ...). • Dohoda stran na prvočísle p a primitivním kořenu g modulo p (veřejné) • Alice vybere náhodné a a pošle ga (mod p) • Bob vybere náhodné b a pošle gb (mod p) • Společným klíčem pro komunikaci je gab (mod p). Kryptosystém ElGamal. Z protokolu DH na výměnu klíčů je odvozen šifrovací algoritmus ElGamal: • Alice zvolí prvočíslo p spolu s primitivním kořenem g • Alice zvolí tajný klíč x, spočítá h — gx (mod p) a zveřejní veřejný klíč (P, 9, h) • šifrování zprávy M: Bob zvolí náhodné y a vypočte C\ — gy (mod p) a C2 = M -hy (mod p) a pošle (d, C2) • dešifrování zprávy: OT — C2/C^ Poznámka. Analogicky jako v případě RSA lze odvodit podepisování. Eliptické křivky jsou rovinné křivky o rovnici tvaru y2 — x3 + ax + b a zajímavé jsou tím, že na jejich bodech lze definovat operace tak, že výslednou strukturou bude komutativní grupa. Přitom uvedené operace lze efektivně provádět a navíc se ukazuje, že mají (nejen) pro kryprografii zajímavé vlastnosti - srovnatelné bezpečnosti jako RSA lze dosáhnout již s podstatně kratšími klíči. Výhodou je rovněž velké množství použitelných eliptických křivek (a tedy grup různé struktury) podle volby parametru a, b . Některé protokoly: • ECDH - přímá varianta DH na eliptické křivce (jen místo generátoru se vybere vhodný bod na křivce) • ECDSA - digitální podpis pomocí eliptických křivek. Poznámka. Problém diskrétního logaritmu (ECDLP). Navíc se ukazuje, že eliptické křivky jsou velmi dobře použitelné při faktorizaci prvočísel. 6. Diofantické rovnice Už ve třetím století našeho letopočtu se řecký matematik Diofantos zabýval řešením rovnic, ve kterých za řešení připouštěl jen celá čísla. Není se čemu divit, vždyť v mnoha praktických úlohách, vedoucích k rovnicím, nemusí mít neceločíselná řešení rozumnou interpretaci. (Jde například o úlohu, jak pomocí pětilitrové a sedmilitrové nádoby odměřit do třetí nádoby osm litrů vody, která vede na rovnici 5rr + 7 y — 8.) Na Diofantovu počest se rovnice, ve kterých hledáme jen celočíselná řešení, nazývají diofantické. Pro řešení těchto rovnic bohužel neexistuje žádná univerzální metoda. Dokonce neexistuje ani metoda (jinými slovy algoritmus), která by určila, jestli má obecná polynomiální diofantická rovnice řešení. Tato otázka je známá pod názvem 10. Hilbertův problém a důkaz neexistence algoritmu podal íOpuM MaTHHceBEnq (Yuri Matiasevič) v roce 1970 (viz elementárně psaný text [1]). Přesto však uvedeme několik nej obvyklejších metod, které v řadě konkrétních případů povedou k výsledku. 6.1. Lineární diofantické rovnice. a\X\ + a2x2 +----h anxn = 6, (30) kde Xi,... ,xn jsou neznámé, a±,..., an, b daná celá čísla. Budeme předpokládat, že cii 0 pro každé i — 1,..., n (je-li — 0, pak neznámá x i z rovnice „zmizí"). K řešení těchto rovnic je možné užít kongruencí. Nejprve si všimněme, kdy má rovnice (30) řešení. Jestliže číslo b není dělitelné číslem cl — (ai,..., an), nemůže mít (30) žádné řešení, protože pro libovolná celá čísla x±,... ,xn je levá strana (30) dělitelná číslem cl. Jestliže naopak d \ 6, můžeme celou rovnici (30) vydělit číslem cl. Dostaneme tak ekvivalentní rovnici a[x1 + a'2x2 + • • • + a'nxn = 6', kde a[ — a^/d pro i — 1,..., n a b' — b/d. Přitom platí d • (a'l7..., a'n) — (da[,..., da'n) — (ai,..., an) — d, a tedy (a[,... ,an) — 1. V následující větě ukážeme, že taková rovnice má vždy řešení, a proto naše úvahy můžeme shrnout takto: rovnice (30) má celočíselné řešení, právě když číslo b je dělitelné největším společným dělitelem čísel a±, a2,..., a. VĚTA 39. Nechť n>2. Rovnice a1x1 + a2x2 + • • • + anxn = b, (31) kde ai, a2,..., an, b jsou celá čísla taková, že (ai,..., an) — 1, má vždy celočíselné řešení. Všechna celočíselná řešení této rovnice je možné popsat pomocí n — 1 celočíselných parametrů. DŮKAZ. Provedeme indukcí vzhledem k počtu n neznámých Xi v rovnici (31). Je výhodné formálně začít s případem n — 1, kdy podmínka (ai) — 1 znamená, že ai — ±1. Tehdy rovnice (31) má tvar buď x\ — b, nebo — x\ — b, a tedy jediné řešení, které zřejmě nezávisí na žádném parametru, což odpovídá tomu, že rc - 1 = 0. Předpokládejme, že n > 2 a že věta platí pro rovnice o n — 1 neznámých; dokážeme ji pro rovnici (31) o n neznámých. Označme d — (ai,... ,an_i). Pak libovolné řešení x±,... ,xn rovnice (31) triviálně splňuje kongruenci a\X\ + a2x2 + • • • + anxn = b (mod d). Vzhledem k tomu, že d je společný dělitel čísel a±,..., an_i, je tato kongruence tvaru anxn = b (mod d). Protože platí, že (d, an) — (ai,..., an_i, an) — 1, má podle věty 21 tato kongruence řešení xn = c (mod d), kde c je vhodné celé číslo, neboli xn = c + d • t, kde t £ Z je libovolné. Dosazením do (31) a úpravou dostaneme a\X\ + • • • + an-ixn-i — b — anc — andt. Protože anc = b (mod d), je číslo (b — anc)/d celé a poslední rovnici můžeme vydělit číslem d. Dostaneme pak rovnici a[xi + • • • + a'n^Xn-i = b', kde a\ — a^já pro i — 1,... ,n — 1 a b' — ((6 — anc)/d) — ant. Protože (ai,..., a^-J - (dai,..., da^i) • \ = (ai,..., an_i) • J = 1, podle indukčního předpokladu má tato rovnice pro libovolné í G Z řešení popsa-telné pomocí n — 2 celočíselných parametrů. Přidáme-li k tomuto řešení podmínku xn — c + dt, dostaneme řešení rovnice (31) popsané pomocí n — 2 původních parametrů a nového parametru t. Důkaz indukcí je hotov. □ Metodu z důkazu věty 39 použijeme na řešení následujících diofantických rovnic, v nichž z důvodů přehlednosti zápisu budeme neznámé značit x,y,z,... místo příklad. 5x + 7í/ = 8. Řešeni. Libovolné řešení této rovnice musí splňovat kongruenci 5x + 7y = 8 (mod 5), tedy 2í/ = —2 (mod 5)), odkud y = — 1 (mod 5)), tj. í/ — —1 + 5/; pro í g Z. Dosazením do dané rovnice dostaneme 5ir + 7(-l + 5ť) -8, odkud vypočítáme x = 3 — 7t. Řešením naší rovnice je tedy x — 3 — 7t, y — — 1 + 5í, kde í je libovolné celé číslo. □ příklad. 91x - 28y = 35. řešení. Protože (91,28) — 7 a 7 | 35, má rovnice celočíselné řešení. Vydělme ji sedmi: 13rr — 4y — 5. Libovolné řešení této rovnice musí splňovat kongruenci 13x — 4y = 5 (mod 13), tj. — 4y = —8 (mod 13), odkud y = 2 (mod 13) a y — 2+13Í pro ŕ £ Z. Dosazením 13x - 4(2 + 13ť) - 5, odkud vypočteme x — 1 + 4í. Řešením je tedy rr — 1 + 4í, í/ = 2 + 13í, kde í je libovolné celé číslo. Tentýž výsledek bychom samozřejmě dostali, i kdybychom uvažovali kongruenci podle modulu 4 místo 13. Protože řešit kongruenci podle menšího modulu bývá snadnější, je vhodné na to pamatovat a uspořádat si výpočet tak, aby nebylo nutné pracovat s kongruencemi podle velkých modulů. □ příklad. 18rr + 20y + 15z - 1. ŘEŠENÍ. Protože (18,20,15) — 1, má rovnice celočíselné řešení. Libovolné řešení musí splňovat kongruenci (za modul volíme nej větší společný dělitel čísel 18, 20) 18rr + 20y + 15z = 1 (mod 2), tedy z = 1 (mod 2), odkud z — 1 + 2s, kde s G Z. Dosazením 18rr + 20y + 15(1 + 2s) = 1 odkud po vydělení dvěma a úpravě dostaneme rovnici, 9x + 10y = -7 - 155 kterou budeme řešit pro libovolné s £ Z. Je-li tato rovnice splněna, musí platit 9x + 10y = -7 - 155 (mod 9), odkud y = 2 + 35 (mod 9), a proto y — 2 + 35 + 9t, kde ŕ £ Z. Dosazením 9z + 10(2 + 35 + 9í) - -7 - 155, odkud po úpravě x — —3 — 55 — 10í. Řešení dané rovnice jsou tedy trojice x — —3 — 55 — 10t y = 2 + 35 + 9t Z = 1 + 25 kde 5, t jsou libovolná celá čísla. příklad. 15rr - 12y + 48z - 51« = 1. □ Řešení. Protože (15,12,48, 51) — 3 není dělitel čísla 1, nemá rovnice celočíselné řešení. □ 6.2. Diofantické rovnice lineární vzhledem k některé neznámé. Jde o rovnice, které můžeme upravit do tvaru mxn F^Xi,..., xn—\)1 (32) kde m je přirozené číslo a F(x±,..., xn-i) mnohočlen s celočíselnými koeficienty. Je zřejmé, že má-li být x±, x2l ■ ■ ■, xn celočíselným řešením rovnice (32), musí platit F(xi,..., xn-i) = 0 (mod m). (33) Naopak, je-li x±,..., xn-i řešení kongruence (33), pak pro xn — F(x±,..., xn-i)/m dostaneme celočíselné řešení ,rrn_i,rrn rovnice (32). Proto pro řešení rov- nice (32) postačí vyřešit kongruenci (33). V případě n — 2, tj. v případě, kdy je mnohočlen F{x\) mnohočlenem jedné proměnné, jde o úlohu, kterou jsme se zabývali v části 4. Případ n > 2 je však možné řešit zcela analogicky pomocí následující věty. VĚTA 40. Pro libovolný mnohočlen F(x±,... ,xs) s celočíselnými koeficienty, přirozené číslo m a celá čísla a±,..., as, b±,..., bs taková, že a± = b± (mod m), ..., as = bs (mod m), platí F(a±,..., a8) = F(b±,..., bs) (mod m). DŮKAZ. Snadný. □ Pro nalezení všech řešení kongruence (33) tedy postačí dosazovat do mnohočlenu F(xi,..., xn-i) za #1,..., xn-i nezávisle na sobě postupně čísla 0,1, 2,..., m — 1 (tj. celkem mn_1-krát). A právě tehdy, když pro čísla ai,...,an_i je splněna podmínka F(a±,..., an_i) = (mod m), dostáváme řešení kongruence (33) ve tvaru x\ = a1 + míi, • • •, Xn-i = a-n-i + mtn-i, kde íi,..., tn-\ mohou nabývat libovolných celočíselných hodnot. Tak dostaneme i řešení rovnice (32): x\ — ai + míi, xn—\ an—\ -\- rrntn—\1 xn = —F(ai + míi, • • •, an-i + mín_i). m příklad. Řešte diofantickou rovnici 7x2 + 5?/ + 13 — 0. ŘEŠENÍ. Rovnici upravíme na tvar by — — 7x2 — 13 a budeme řešit kongruenci -7x2 - 13 = 0 (mod 5), tj. 3x2 = 3 (mod 5), odkud x2 = 1 (mod 5). Dosadíme-li za x čísla 0, 1, 2, 3, 4, zjistíme, že kongruence je splněna pro čísla 1 a 4. Řešením této kongruence jsou tedy podle 4.11 právě čísla x — 1 + 5í nebo x — 4 + 5í, kde t e Z. Dosazením dostaneme v prvním případě 52/ - -7(1 + 5í)2 - 13 - -7 - 70t - 17bt2 - 13 13, a tedy 2/ = —4 — 14í — 35t2, ve druhém případě 52/ - -7(4 + btf - 13 - -112 - 280ŕ - 175£2 a proto í/ = -25 - 56í-35í2. Řešením dané rovnice jsou tedy právě všechny dvojice čísel x, y tvaru a; = 1 + 5í, í/ = -4 - 14í - 35£2 nebo x = 4 + 5t,y = -25 - 56í - 35t2, kde í je libovolné celé číslo. □ příklad. Řešte diofantickou rovnici x(x + 3) — Ay — 1. Řešení. Rovnici upravíme na tvar Ay — rr2 + 3rr +1 a budeme řešit kongruenci rr2 + 3rr + l = 0 (mod 4). Dosazením čísel 0, 1, 2, 3 zjistíme, že kongruenci nesplňuje žádné z nich, a tedy tato kongruence nemá řešení. Řešení proto nemá ani daná rovnice. □ příklad. Řešte diofantickou rovnici x2 + Az2 + 6x + 7y + 8z — 1. ŘEŠENÍ. Rovnici upravíme na tvar 7y — — x — 6x — Az — 8z + 1 a doplníme na čtverce 7y = -(x + 3)2 - (2z + 2)2 + 14. Proto budeme řešit kongruenci (x + 3)2 + (2z + 2)2 = 0 (mod 7) (34) Nyní bychom mohli za uspořádanou dvojici (x\ z) postupně dosazovat uspořádané dvojice (0; 0), (0; 1), ..., (0; 6), (1; 0), (1; 1), ..., (6; 5), (6; 6) a spočítat pro všech 49 hodnot výraz stojící na levé straně kongruence (34). Výhodnější ale bude využít tvaru kongruence (34) a odvolat se na tvrzení 3.1, odkud pro p = 7, a — rr + 3, b — 2z + 2 dostaneme, že z kongruence (34) plyne rr + 3 = 2z + 2 = 0 (mod 7), a tedy všechna řešení kongruence (34) jsou tvaru x — — 3 + 7t, z — — 1 + 7s, kde t, 5 jsou celá čísla. Dosazením do rovnice dostaneme 7y = -(x + 3)2 - (2z + 2)2 + 14 - -49ŕ2 - 19652 + 14, odkud y = -7t2 - 28s2 + 2. Řešením dané rovnice jsou tedy právě všechny trojice čísel x,y,z tvaru x = -3 + 7t, y = -7t2 - 28s2 + 2, z = -1 + 7s, kde 5, í jsou libovolná celá čísla. □ 6.3. Rovnice jiného tvaru. Metodu, kterou jsme řešili předchozí příklady, je možno popsat také takto: „vyjádři některou z neznámých pomocí ostatních a zkoumej, kdy je celočíselná". Skutečně, vyjádříme-li z rovnice (32) neznámou xni dostaneme F(x\,..., xn—\) •En i m což je celé číslo, právě když m \ F(x±,..., £n-i), tj. právě když je splněna kongru-ence (33). Ukážeme si na příkladech, že tento postup je použitelný i na rovnice, které nejsou tvaru (32). V příkladech uvedeme i případ, kdy je vhodné vyjádřit namísto některé neznámé nějaký jiný vhodný výraz a zkoumat, za jakých okolností bude celočíselný. příklad. Řešte diofantickou rovnici 3^ — 4^ + 5. ŘEŠENÍ. Vyjádřeme z této rovnice neznámou y: v = \(3X - 5). Je-li x < O, je O < 3^ < 1, a tedy \(3X - 5) £ Z. Pro x > 0 platí 3" -5 ee (-lf - 1 (mod 4); číslo (—l)x — 1 je kongruentní s nulou podle modulu 4 právě tehdy, když x je sudé, tj. x — 2fc, kde k g n0. Řešením této diofantické rovnice jsou tedy právě všechny dvojice 9fe-5 x = 2k, y = —-—, kde k g n0 je libovolné. □ příklad. Řešte v Z rovnici x(y + l)2 = 2A3y . Řešení. Vyjádřeme neznámou x: 243;/ x (y +1)2' Aby x g Z, musí (t/ + 1)2 být dělitelem čísla 243y. Protože y a y+l jsou nesoudělná čísla pro libovolné y g Z, musí být (t/ + l)2 dělitelem čísla 243 — 35. Toto číslo má však jen tři dělitele, kteří jsou druhou mocninou celého čísla: 1,9 a 81. Proto musí nastat některá z těchto možností: y + 1 = ±1,t/ + 1 — ±3 nebo y + 1 — ±9. Dostáváme tedy šest řešení dané rovnice: o, x = 0 -2, x = -2 • 243 - -486 2, rr = 2 • 27 - 54 -4, rr = -4 • 27 - -108 8, x = 8 • 3 - 24 -10, rr = -10 • 3 - -30 Jiná řešení daná diofantická rovnice nemá. □ příklad. Řešte v Z rovnici y/x + y/y = ^1988 . Řešeni. Odečteme-li od obou stran rovnice y/y a umocníme-li na druhou, dostaneme x = 1988 - 4^7-71-í/ + y. Jsou-li x, y celá čísla, je i 4^/7 • 71y celé číslo, a tedy \/7 • 71y je racionální číslo. Pak je y/7 • 71y — k nezáporné celé číslo. Platí tedy 7 • 71y — k2, odkud plyne, že k2 a tedy i k je dělitelné prvočísly 7, 71. Je tedy k — 7 • 71í pro vhodné í G N0 a tedy k2 Zcela analogicky je možné odvodit, že existuje s g n0 tak, že x = 497s2. Dosazením do původní rovnice dostáváme odkud po vydělení plyne s + t — 2. Jsou tedy tři možnosti: s — 0, t — 2 nebo s = £ = 1 nebo s = 2, £ = 0, takže daná diofantická rovnice má tři řešení: x — 0, 2/ — 1988 nebo x — y — 497 nebo rr — 1988, 7/ — 0. □ 6.4. Řešení diofantických rovnic pomocí nerovností. Tato metoda je založena na tom, že pro libovolná reálná čísla a, b existuje jen konečně mnoho celých čísel x tak, že a < x < b. Proto při řešení dané rovnice hledáme taková čísla a, 6, aby nerovnosti a < x < b pro některou neznámou x byly důsledkem této rovnice. Konečně mnoho celých čísel ležících mezi čísly a, b pak můžeme jedno po druhém dosadit do rovnice za x a tím ji zjednodušit. Ukažme si to na následujících příkladech. příklad. Řešte diofantickou rovnici 6x2 + by2 — 74. Řešení. Protože pro libovolné y g Z platí by2 > 0, musí libovolné řešení x, y dané rovnice splňovat 74 - 6x2 + hy2 > 6rr2, odkud x2 < y, tedy — 3 < x < 3, proto x2 je některé z čísel 0, 1,4, 9. Dosazením do rovnice postupně dostáváme 5y2 — 74, 5?/2 — 68, 5y2 — 50, 5t/2 — 20. První tři případy jsou ve sporu s y G Z, z posledního dostáváme t/2 — 4, tj. 7/ — ±2. Rovnice má tedy čtyři řešení: x — 3, y — 2; rr — 3, y — —2; rr — —3, y = 2; x = -3, y = -2. □ příklad. Řešte v Z rovnici x2 + xy + y2 = x2y2. Řešení. Protože jsou v dané rovnici neznámé x, y zastoupeny symetricky, můžeme předpokládat, že x2 < y2, odkud plyne xy < y2, a tedy x2y2 — x2 + xy + y2 0 a proto 2^ — 1 + 3y > 2, odkud rr > 1. Ukážeme, že také platí x < 2. Kdyby totiž bylo x > 3, platilo by l + 3v = 2a: = 0 (mod 8), odkud bychom dostali 3y = -1 (mod 8), což však není možné, neboť pro sudá čísla y je 3y = 1 (mod 8) a pro lichá čísla y platí 3y = 3 (mod 8). Zbývá tedy vyřešit případ 1 < x < 2. Pro rr — 1 dostáváme 3^ = 21 - 1 - 1, a tedy y — 0. Z rr — 2 plyne 3y = 22 - 1 - 3, takže y — 1. Rovnice má tedy dvě řešení: rr — 1, y = Oarr — 2, í/ = 1. □ příklad. Řešte rovnici x + y + z — ir^ v oboru přirozených čísel. Řešení. Protože jsou v dané rovnici neznámé zastoupeny symetricky, můžeme předpokládat x < y < z. Pak ale xyz — x + y + z < z + z + z — 3z, odkud ir?/ < 3. Je tedy xy — 1, nebo rr?/ — 2, nebo rr?/ — 3. Je-li xy — 1, platí rr — 1, 7/ — 1, odkud dostaneme dosazením do rovnice 2 + z = z, což není možné. Je-li xy — 2, platí x — 1, y — 2 (předpokládáme x < y), odkud 3 + z — 2z, a tedy z — 3. Je-li aľč/ — 3, platí x — 1, y — 3, odkud 4 + z — 3z, tedy z — 2, což je ve sporu s předpokladem y < z. Rovnice má tedy jediné řešení x = l,y = 2, z = 3 splňující x < y < z. Všechna řešení v oboru přirozených čísel dostaneme všemi záměnami pořadí čísel 1, 2, 3: (x; y-z) G {(1; 2; 3), (1; 3; 2), (2; 1; 3), (2; 3; 1), (3; 1; 2), (3; 2; 1)}. □ Často je možné s výhodou ukázat sporem, že množina hodnot neznámé x je konečná a omezená nerovnostmi a < x < b; přitom z předpokladu x < a (resp. x > b) odvodíme nepravdivé tvrzení. V následujících příkladech bude takovým nepravdivým tvrzením dvojice nerovností cn < dn < (c+ l)n, kde c, d jsou celá a n přirozené číslo. příklad. Řešte diofantickou rovnici x(x + l)(x + 7)(x + 8) — y2. Řešení. Úpravou y2 = (x2 + 8rr)(rr2 + 8rr + 7). Označíme-li x2 + 8x — z1 je naše rovnice tvaru y2 = z2 + 72. Ukážeme, že z < 9. Předpokládejme naopak z > 9. Pak platí (2 + 3)2 - z2 + 6z + 9 < z2 + 7z - t/2 < z2 + 82 + 16 - (z + 4)2, což je spor, neboť z + 3, y, z + 4 jsou celá čísla a z těchto nerovností by plynulo \z + 3| < < |2 + 4|. Je tedy z < 9, tj. x2 + 8rr < 9, odkud (z + 4)2 - x2 + 8rr + 16 < 25, a proto —5 < x + 4 < 5, neboli —9 < rr < 1. Dosazením těchto hodnot do rovnice dostaneme všechna řešení: (x; y) G {(-9; 12), (-9; -12), (-8; 0), (-7; 0), (-4; 12), (-4; -12), (-1; 0), (0; 0), (1; 12), (1; -12)}. □ příklad. Řešte diofantickou rovnici (x + 2)4 — x4 — y3. Řešení. Úpravou získáme y3 = Sx3 + 24rr2 + 32rr + 16 - 8(rr3 + 3rr2 + 4x + 2), odkud plyne, že y je sudé. Položme y — 22, z G Z. Platí tedy z3 = x3 + 3rr2 + 4rr + 2. Je-li x > O, platí (x + l)3 = x3 + 3x2 + 3x + 1 < x3 + 3rr2 + Ax + 2 - = z3 < ir3 + 6rr2 + 12rr + 8 - (x + 2)3, odkud x + 1 < z < x + 2, což není možné. Daná rovnice tedy nemá řešení x, y G Z takové, že rr > 0. Předpokládejme, že má nějaké řešení G Z takové, že #i < —2. Pak platí a dosadíme-li rr2 — —x\ — 2, t/2 — ~Vii dostaneme x\-(x2 + 2)A = -yl a proto x2, y2 je také řešení dané rovnice. Ovšem x2 — — x\ — 2 > 0 a z předchozích úvah plyne, že tato situace nastat nemůže. Dohromady tedy — 2 < x < 0, tj. rr — — 1. Pro x — — 1 vychází z původní rovnice y — 0; dvojice rr — —1, 7/ — Oje jediným řešením úlohy. □ .4.1. Některé nerovnosti. Při řešení diofantických rovnic jsou někdy užitečné i některé složitější postupy a nerovnosti. Uveďme si některé z nejčastěji používaných. VĚTA 41 (AG-nerovnost). Pro libovolná čísla a±, a2l..., an G Mg plutí nerov- nost fll + CL2 + • • • + Q>r n > yaxa2 a. n 7 (35) přitom rovnost v (35) nastane, jen když a± — a2 — • • • — an. DŮKAZ. Prozatím neuveden. □ VĚTA 42 (Bernoulliova nerovnost). Vrr G M, x > — 1, Vn G N platí: (l + x)n>l + n-x. DŮKAZ. Pro n — 1 nebo rr — 0 je tvrzení zřejmé. Pro reálná A > B > 0 a přirozené číslo n > 2 platí: rz(A - B)Bn~1 B > 0, rz > 2), z čehož po dosazení A = 1 + rrai? — 1 (pro rr > 0), resp. A — 1, B = 1 + rr (pro — 1 < x < 0) dostaneme požadované tvrzení. □ příklad. V oboru přirozených čísel řešte rovnici x y z - + - + - = 3. y z x Řešení. Podíl přirozených čísel je číslo kladné, a proto můžeme pro čísla |, | a - použít nerovnost mezi aritmetickým a geometrickým průměrem (viz Věta 41). Geometrický průměr těchto tří čísel je 1, a proto pro jejich aritmetický průměr platí 1 /x y z\ ô- + - + ->!5 3 \y z xj kde rovnost nastane právě tehdy, když x y z y z x Porovnáme-li získanou nerovnost s danou rovnicí, dostáváme, že rovnice má nekonečně mnoho řešení x — y — z1 kde z je libovolné přirozené číslo, a žádné jiné řešení nemá. □ příklad. Dokažte, že pro libovolné přirozené číslo n > 2 rovnice xn + (x + l)n = (x + 2)n nemá řešení v oboru přirozených čísel. Řešení. Předpokládejme naopak, že pro nějaká přirozená čísla x1 n1 kde n > 2, je daná rovnice splněna, a označme y — x + 1 > 2. Pak platí (2, - 1)" + 2," = (2, + 1)", (36) odkud dostáváme 0 = (y + l)n-yn-(y-l)n = l- (-l)n (mod y). Připusťme, že n je liché, pak 0 = 2 (mod y), tedy y — 2 a 0 = 3n-2n-l, což platí pouze pro rz — 1. Je tedy n sudé a podle binomické věty platí (j, + 1)» = (Ijy + + 1 (mody3), („-l)»=gy + 1 (mody3), odkud plyne 0 = (2/ + ir-2/n-(2/-ir = 2n2/ (mod ?/3), tedy 0 = 2n (mod y2), a proto 2n > y2. Vydělíme-li (36) číslem ?/n, dostaneme 1 + V, n 2/. < 2. Naopak podle Bernoulliovy nerovnosti (viz Věta 42) platí 1 n 2n y 1 + - >1 + - = 1 + — >l + ^ = l + ^>2 2/, 2/ 22/ 22/ Shrneme-li předchozí úvahy, vychází, že pro žádné přirozené číslo n > 2 nemá daná rovnice řešení v oboru přirozených čísel. 6.5. Řešení diofantických rovnic metodou rozkladu. Tato metoda spočívá v úpravě dané rovnice do tvaru AľA2.....An = BJ (37) kde Ai,...,An jsou výrazy obsahující neznámé, které pro celočíselné hodnoty neznámých nabývají celočíselných hodnot, a i? je číslo (případně výraz), jehož rozklad na prvočísla známe. Pak totiž existuje pouze konečně mnoho rozkladů čísla B na n celočíselných činitelů (1\, . . . , 0Ln. Vyšetříme-li pak pro každý z těchto rozkladů soustavu rovnic A\ — ai, A2 — a2l ..., An — ani získáme všechna řešení rovnice (37). Ukažme si to na příkladech. příklad. Řešte diofantickou rovnici y3 — x3 = 91. Řešení. Rozložme levou stranu rovnice: (y — x)(y2 + xy + x2) — 91. Protože 2 y2 + xy + x2 - (y + |^ + -x2 > 0, musí být také y — x > 0. Číslo 91 můžeme rozložit na součin dvou přirozených čísel čtyřmi způsoby: 91 — 1 • 91 — 7 • 13 — 13 • 7 — 91 • 1. Budeme proto odděleně řešit čtyři systémy rovnic: (1) y — x — 1, y2 + xy + x2 — 91. Dosazením 7/ — x + 1 z první do druhé rovnice dostaneme x2 + x — 30 — 0, odkud rr — 5 nebo x — —6. Příslušné hodnoty druhé neznámé jsou pak y — 6, y — —5. (2) y-x = 7, y2 + xy + x2 = 13. Pak rr2 + 7rr + 12 = 0, tedy rr - -3 a í/ = 4 nebo x — —4 a y — 3. (3) y — x = 13, y2 + xy + x2 — 7. Nyní rr2 + 13rr + 54 — 0. Tato rovnice však nemá řešení v oboru reálných čísel, a proto ani v oboru čísel celých. (4) y — x — 91, y2 + xy + x2 — 1. V tomto případě rr2 + 91rr + 2760 — 0. Ani tato rovnice nemá řešení v oboru reálných čísel. Daná rovnice má tedy čtyři řešení: {x- y) G {(5; 6), (-6; -5), (-3; 4), (-4; 3)}. □ příklad. Reste diofantickou rovnici x4 + 2x7y — xu — y2 — 7. Řešeni. Upravme nejprve levou stranu rovnice: x +2xy — x —y =x — (x —y) — (x —x + y){x + x —y) a uvažme, že číslo 7 můžeme rozložit čtyřmi způsoby na součin dvou celých čísel: 7=1-7 = 7-1 = (—1) • (—7) = (—7) • (—1). Budeme proto řešit čtyři soustavy rovnic. (1) x2 — x7 + y — 1, x2 + x7 — y — 7. Sečtením obou rovnic dostaneme rr2 — 4, odkud rr — 2 a 7/ — 125, nebo x = —2 a, y = —131. (2) x2 — x7 + 2/ — 7, rr2 + rr7 — 7/ — 1. Nyní rr2 — 4, a tedy x = 2, y = 131 nebo rr — —2, 7/ — —125. (3) x2 — x7 + y = —1, rr2 + rr7 — y — —7. Sečtením x2 — —4, což je spor. (4) x2 — rr7 + y — —7, rr2 + rr7 — 7/ — —1. Opět spor rr2 — —4. Rovnice má tedy čtyři řešení: (x; y) G {(-2; -131), (-2; -125), (2; 125), (2; 131)}. □ příklad. Řešte diofantickou rovnici 1 1 _ 1 x y p1 kde p je libovolné prvočíslo. Řešení. Vynásobením číslem xyp a další úpravou dostaneme xy — px — py — 0. Úprava do tvaru (37) vyžaduje nyní umělý obrat: přičteme k oběma stranám rovnice p2, aby bylo možno její levou stranu zapsat jako součin: (x-p)(y -p) =p2. Protože p je prvočíslo, lze p2 rozložit na součin dvou celých čísel jen těmito šesti způsoby: p2 — 1 • p2 — p • p — p2 • 1 — (—1) • (— p2) — (—p) • (—p) — (~P2) ' (~ !)• Budeme proto řešit šest systémů rovnic: (1) X -p = ^,y-p = p2 , a tedy x — p + 1, y = p2+p\ (2) X -p = p,y-p = p, a tedy x = 2p, y = 2p- (3) X -p = p2,y-p = ^ , a tedy x — p2 + p y=p+l\ (4) X -p = -l,y-p = - -p2, a tedy x = p - -^,y = p-p2\ (5) X -p = -p,y-p = - -p, a tedy x = y = 0, což nevyhovuje (6) X -p = -p2, y-p = — 1, a tedy x = p - -P2> 2/ = P- 1- Daná rovnice má tedy pět řešení, popsaných v případech (l)-(4) a (6). □ 5.1. Pythagorova rovnice. Pythagorova rovnice se zabývá otázkou hledání všech pravoúhlých trojúhelníků s celočíselnými délkami stran. PŘÍKLAD. V oboru přirozených čísel řešte rovnici 2 , 2 x + y Řešení. Označme t — (x, y, z), x\ — ■ f, 2/i = í ? 2i = f ■ Pak platí odkud po vydělení číslem t2 (38) a navíc (#1,2/1,21) — 1. Ukážeme nyní, že čísla #1,2/1,21 jsou dokonce po dvou nesoudělná: kdyby nějaké prvočíslo p dělilo dvě z čísel #1,2/1, 21, vyšlo by z (38), že dělí i třetí, což vzhledem k (#1,2/1,21) — 1 není možné. Z čísel #1, 2/1 je tedy nejvýše jedno sudé. Připusťme, že jsou obě lichá. Pak z kongruence z\ = x\ + y\ = 1 + 1 (mod 8) plyne, že z\ je sudé číslo, které není dělitelné 4, což není možné. Je tedy z čísel #1, 2/i právě jedno sudé. Protože v rovnici (38) vystupují #1 a 2/1 symetricky, můžeme pro určitost předpokládat, že sudé je #1 — 2r, r £ N. Z (38) pak plyne /i 2 2 2 4r - 2i - 2/1 a tedy 2 21 + 2/1 21 - 2/1 r —-•-. 2 2 Označme u — |(21 + 2/1), v — \(z\ — y±). Pak ^i — u + v, 2/1 = u — v. Protože jsou 2/i, 21 nesoudělná čísla, jsou i u, v nesoudělná čísla. Z rovnice pak plyne, že existují nesoudělná přirozená čísla a, b tak, že u — a2, v — b2, navíc vzhledem k u > v platí a > b. Celkem tedy dostáváme x — tx\ — 2tr — 2tab1 y — tyi — t(u — v) — t(a2 — b2), z — tzi — t(u + v) — t(a2 + 62), což skutečně pro libovolné íGNa libovolná nesoudělná a, b G N taková, že a > b, vyhovuje dané rovnici. Zbylá řešení bychom dostali záměnou x a y (v průběhu řešení jsme předpokládali, že právě Xi je sudé): x = t(a2-b2)J y = 2tab, z = t(a2 + b2)J kde opět í,a,i)ÉN jsou libovolná taková, že a > b, (a, b) — 1. □ 6.6. Řešitelnost diofantických rovnic. V předchozí čáasti jsme viděli, že řešení většiny diofantických rovnic není snadné, a ačkoli jsme se naučili několik metod, v mnoha konkrétních případech se nám nepodaří diofantickou rovnici vyřešit ani jednou z nich. Přesto se nám v těchto případech může podařit něco o řešení zjistit. Například nalézt nekonečnou množinu řešení a tím dokázat, že množina všech řešení, i když ji celou neumíme popsat, je nekonečná. Nebo naopak ukázat, že množina všech řešení je prázdná (a tím vlastně danou rovnici vyřešit), popřípadě konečná. 6.1. Neexistence řešení Při důkazu, že nějaká diofantická rovnice nemá žádné řešení, je často možné s úspěchem využít kongruencí. Má-li totiž řešení diofantická rovnice L — P (kde L, P jsou výrazy obsahující neznámé, nabývající celočíselných hodnot pro libovolné celočíselné hodnoty neznámých), musí mít řešení i kongruence L = P (mod m) pro libovolné m G N, protože řešením této kongruence je například zmíněné řešení rovnice. Odtud plyne, že nalezneme-li nějaké přirozené číslo m tak, že kongruence L = P (mod m) nemá řešení, nemůže mít řešení ani původní diofantická rovnice L — P. Je nutno si však uvědomit, že obrácení předchozí úvahy obecně neplatí: má-li kongruence L = P (mod m) pro každé přirozené číslo m řešení, neznamená to ještě, že má řešení též diofantická rovnice L — P (ukážeme to v Příkladu na str. 163). příklad. Řešte diofantickou rovnici x\ + x\ + • • • + x\A = 15999. Řešeni. Ukážeme, že kongruence x\ + x\ + • • • + x\A = 15999 (mod 16) nemá řešení, odkud vyplyne, že řešení nemá ani daná diofantická rovnice. Je-li totiž celé číslo n sudé, je n — 2k pro k G Z a tedy rr — 16/c4 = 0 (mod 16). Jestliže je celé číslo n liché, platí rr — 1 — (n — l)(n + l)(n2 + 1) = 0 (mod 16), neboť čísla n — l,rz + larz2 + l jsou sudá a jedno z čísel n — 1, n + 1 musí být dokonce dělitelné čtyřmi. Znamená to tedy, že podle modulu 16 je rr kongruentní s 0 pro sudá n as 1 pro lichá čísla n. Je-li proto mezi čísly x±, x2,..., x^ právě r lichých, je x\ + x\ + • • • + x\A = r (mod 16). Platí 15999 — 16000 — 1 = 15 (mod 16) a protože 0 < r < 14, nemůže mít kongruence x\JrX2Jr---Jr x\A = 15 (mod 16) řešení, a nemá ho tedy ani daná rovnice. □ příklad. V oboru celých čísel řešte soustavu rovnic x2 + 2y2 = z2, 2x2 + y2 = u2. Řešeni. Snadno ověříme, že z x — y — 0 plyne také z — u — 0, což je řešení dané soustavy. Ukážeme, že další řešení soustava nemá. Předpokládejme, že x,y,z,u je řešení a že x ^ 0 nebo y ^ 0, a označme d — (x, y) > 0 největší společný dělitel čísel x,y. Z první rovnice plyne d \ z, ze druhé d \ u. Označíme-li %i — % Vi — f, 2i — 4, Ui — |, dostáváme, že (íCi, — 1, a po zkrácení obou rovnic číslem d2 dostaneme x21 + 2y21=z211 2x\ + y\ — u\. Odtud plyne sečtením 3x\ + 3yf — z\ + u\ a tedy 3 | z\ + u\. Podle Tvrzení 3.1 platí 3 | z\, 3 | u\ a tedy 9 | z2jru\. Pak ale 9 | 3(ir2 + ?/2), a tedy 3 | x\Jry2. Opět podle Tvrzení 3.1 platí 3 | x±, 3 | yi, což je spor s (xi,yi) — 1. Soustava má tedy jediné řešení x = y = z = u = 0. □ příklad. V oboru přirozených čísel řešte rovnici 1!+ 2!+ 3!+ ••• + £! = y2. Řešeni. Přímým výpočtem se přesvědčíme, že pro x < 5 vyhovují rovnici pouze x = y = larr — y = 3. Ukážeme, že pro x > 5 rovnice řešení nemá. Protože pro libovolné n > 5 je n\ dělitelné pěti, platí 1! + 2! + 3! + • • • + x\ = 1! + 2! + 3! + 4! - 33 = 3 (mod 5). Ovšem druhá mocnina přirozeného čísla je podle modulu 5 kongruentní s 0 nebo 1 nebo 4. Kongruence 1! + 2! + • • • + x\ = y2 (mod 5) pro x > 5 tedy nemá řešení, a proto nemá pro x > 5 řešení ani daná rovnice. □ příklad. V oboru přirozených čísel řešte rovnici ŘEŠENÍ. Ukážeme, že daná rovnice nemá řešení. Předpokládejme naopak, že pro vhodná x,y G Z platí x2 — y3 = 7. Kdyby y bylo sudé, platilo by x2 = 7 (mod 8), což není možné. Je tedy y liché, y = 2k + 1 pro k G Z. Pak platí x2 + 1 = y3 + 23 = (y + 2)(2/2 - 2y + 4) = (39) = (2/ + 2)((2/ - l)2 + 3) = (2k + 3)(4/c2 + 3). (40) Číslo Ak2 + 3 musí být dělitelné nějakým prvočíslem p = 3 (mod 4). V opačném případě vzhledem k tomu, že Ak2 + 3 je liché, by totiž v rozkladu čísla Ak2 + 3 na prvočísla vystupovala pouze prvočísla kongruentní s 1 podle modulu 4 a tedy by i jejich součin Ak2 + 3 musel být kongruentní s 1 podle modulu 4, což jistě není. Je tedy Ak2 + 3 dělitelné prvočíslem p = 3 (mod 4), a tedy platí x2 + 1 = 0 (mod p). Podle Tvrzení 3.1 odtud plyne x = 1 = 0 (mod p), a to je spor. □ Nyní uvedeme slibovaný příklad toho, že diofantická rovnice nemusí být řešitelná ani v případě, že je kongruence L = P (mod m) řešitelná pro libovolný modul m G N. příklad. Dokažte, že kongruence 6x2 + 5x + 1 = 0 (mod m) má řešení pro každé přirozené číslo m, a přitom diofantická rovnice 6x2 + 5x + 1 = 0 řešení nemá. ŘEŠENÍ. Platí 6x2 + 5rr + 1 = (3rr + l)(2x + 1), a tedy rovnice 6x2 + 5rr + 1 = 0 nemá celočíselné řešení. Nechť m je libovolné přirozené číslo a platí m — 2n • k1 kde n G N0 a je liché číslo. Protože (3,2n) — (2, k) — 1, mají obě kongruence soustavy 3x == — 1 (mod 2n) 2;i; = — 1 (mod k) podle Věty 21 řešení, a protože (2n, fc) = 1, má podle Věty 23 řešení i celá soustava. Pro libovolné x vyhovující této soustavě je pak 3x + 1 dělitelné číslem 2n a 2x + 1 číslem k a proto součin (3rr + l)(2rr + 1) je dělitelný číslem 2n • k — m. Je tedy rr řešením kongruence 6rr2 + hx + 1 = 0 (mod m). □ 6.2. Zmenšováni ad absurdum. Je to metoda důkazu neexistence řešení diofan-tické rovnice. Při důkazu touto metodou libovolné řešení dané diofantické rovnice charakterizujeme nějakým přirozeným číslem (například nej větším společným dělitelem hodnot některých neznámých nebo druhou mocninou hodnoty některé neznámé a podobně) a ukážeme, že existuje-li řešení charakterizované přirozeným číslem d1 musí existovat jiné řešení, charakterizované přirozeným číslem ď < d. Pak totiž žádné takové řešení existovat nemůže, o čemž se snadno můžeme přesvědčit sporem: kdyby existovalo, mohli bychom zvolit to řešení, které je ze všech řešení charakterizováno co nej menším přirozeným číslem d; pak by ovšem muselo existovat i jiné řešení, charakterizované přirozeným číslem ď < d1 což však by byl spor s volbou d. příklad. Řešte diofantickou rovnici x3 + 2y3 + Az3 — 6xyz — 0. Řešení. Rovnici jistě vyhovuje x — y — z — 0. Ukážeme, že jiné řešení rovnice nemá. Označme d — x2 + y2 + z2 a předpokládejme, že pro nějaké řešení x,y,z dané rovnice platí d > 0. Z původní rovnice plyne, že x3 je sudé číslo, a proto je x — 2xi pro vhodné x\ g Z. Dosazením do rovnice dostaneme 8rr? + 2y3 + Az3 - \2xxyz = 0, po vydělení dvěma Axl + y3 + 2z3 - 6xľyz = 0, a proto iy3 je sudé číslo, tedy y — 2y± pro vhodné ^eZ. Dosazením a vydělením dvěma dostaneme 2x1 + 4Ž/ľ + z3 - 6xľyľz = 0, odkud plyne, že z3 je také sudé číslo, a proto z — 2z\ pro vhodné z\ G Z. Dosazením a vydělením dvěma dostaneme #i + 2y\ + 4^ - GxiyiZi = 0, a tedy #1,2/1, 21 je řešení původní diofantické rovnice, přičemž platí 2 1 2 1 2 #2 , ž/2 , 22 ^7 Podle metody popsané v 6.4 daná diofantická rovnice nemá řešení s vlastností d > 0, a tedy # — 2/ — 2 — Oje jejím jediným řešením. □ příklad. V oboru přirozených čísel řešte rovnici #2 + y2 — 4Z. ŘEŠENÍ. Užijeme metodu 6.6.2 pro d = z. Předpokládejme nejprve, že x,y,z je řešením dané rovnice. Pak jistě platí z / 1, protože je-li x — y — 1, platí #2 + 2/2 — 2 < 4, a je-li alespoň jedno z čísel #, 2/ větší než jedna, je x2 + y2 > 4. Je tedy z > 1 a platí #2 + 2/2 — 4Z = 0 (mod 8). Protože druhá mocnina lichého čísla je kongruentní s 1 podle modulu 8 a druhá mocnina sudého čísla je kongruentní s 0 nebo 4 podle modulu 8, plyne z této kongruence, že x i y jsou sudá, a tedy x — 2rri, 2/ — 2yi pro vhodná #1,2/1 G N. Pak ovšem a tedy, označíme-li z\ — z — 1 £ N, čísla x±, 2/1,21 splňují danou rovnici, přičemž < z. Proto daná rovnice nemá řešení. příklad. Řešte diofantickou rovnici x4 + y4 + z4 — 9u4. Řešení. Je-li u — 0, musí být rovněž x = y = z = 0, což je řešení dané rovnice. Ukážeme, že jiné řešení rovnice nemá. Předpokládejme, že celá čísla vyhovují dané rovnici, přičemž « / 0, a označme cl — u4. Kdyby číslo u nebylo dělitelné pěti, bylo by u4 = 1 (mod 5) podle Fermatovy věty, a tedy by platilo x4 + y4 + z4 = 4 (mod 5), což však není možné, neboť podle Fermatovy věty každé z čísel x4,y4, z4 může být podle modulu 5 kongruentní pouze s 0 nebo 1. Je tedy u dělitelné pěti, u — 5u± pro vhodné «1 £ Z, a platí x4 + y4 + z4 = 0 (mod 5), odkud plyne, že čísla x,y,z jsou dělitelné pěti, tj. x — 5x±, y — 5í/i, 2 — 5z± pro vhodná 7/1, £1 g Z. Dosazením do rovnice a vydělením 54 dostaneme a tedy x\, 2/1, ^1, u± vyhovují dané rovnici. Přitom platí □ příklad. Řešte diofantickou rovnici x2 + y2 + z2 — 2xyz. Řešeni. Rovnice jistě splňuje x — y — z — 0. Ukážeme, že další řešení tato rovnice nemá. Dokážeme dokonce silnější tvrzení: žádná rovnice x2 + y2 + z2 = 2uxyZl (41) kde i,i/,2GZa«GN nemá jiné řešení než x = y = z = 0, u G N libovolné. Předpokládejme, že x, y, z G Z, u G N vyhovují rovnici (41) a že d — rr2 + t/2 + z2 > 0. Protože u > 1, je 2uxyz sudé číslo, a proto i rr2 + t/2 + z2 je sudé číslo. To ale znamená, že právě jedno z čísel x, y, z, nebo všechna tři jsou sudá. V prvním případě je však x2 + y2 + z2 = 1 + 1 + 0 - 2 (mod 4), kdežto 2uxyz = 0 (mod 4), neboť u > 1 a jedno z čísel rr, t/, z je sudé. Nastane tedy druhý případ a čísla %i — f, Vi — zi = f Jsou ce^- P°l°žme Ui — u + 1 a dosaďme do (41): 4rr2 + 4yl + 4z2 - 2M1_1 • 2Xl ■ 2yx ■ 2zu po vydělení čtyřmi x\ + y\ + z\ = 2U1 -xiyizu a tedy Xi,yi,zi,ui vyhovují rovnici (41). Přitom platí 0 < x\ + y\ + z\ — | < d, neboť d > 0. Podle 6.6.2 tedy rovnice (41) může mít jen řešení s vlastností d — 0, což jsou výše uvedená řešení x = y = z = 0, mgN libovolné. Speciálně, zadaná rovnice má jediné řešení x — y — z — 0. □ 6.3. Početnost množiny řešení. V mnoha případech, kdy neumíme najít všechna řešení diofantické rovnice, se nám může alespoň podařit rozhodnout, zda řešení je konečně či nekonečně mnoho. Konečnost je například zaručena zjištěním, že hodnoty neznámých jsou v absolutní hodnotě menší než nějaké číslo. Pokud toto číslo nalezneme a je „rozumně" malé, můžeme pak najít všechna řešení metodou popsanou v 6.4 To, že daná diofantická rovnice má řešení nekonečně mnoho, můžeme dokázat například tak, že nalezneme pro každou neznámou nějaký výraz s parametrem, a to takový, že po dosazení do rovnice dostaneme rovnost, přitom pro nekonečně mnoho hodnot parametru dostaneme navzájem různé hodnoty neznámých (jde tedy o jakousi zkoušku nekonečně mnoha řešení). Nebo můžeme nalézt jedno řešení rovnice a udat předpis, jak z libovolného řešení spočítat jiné. Máme-li zaručeno, že při další a další aplikaci tohoto předpisu dostáváme stále nová řešení (například jsou-li získávaná řešení stále větší a větší), opět tím dokážeme, že množina řešení je nekonečná. Je zřejmé, že při obou postupech mohou existovat ještě další nenalezená řešení. příklad. Dokažte, že diofantická rovnice 0 - l)2 + 0 + l)2 = y2 + 1 má nekonečně mnoho řešení. Řešení. Rovnici snadno upravíme do tvaru5 y2 -2x2 = 1. Zkusme najít nějaké řešení. Po chvíli pokusů asi každý objeví, že volba y — 3, x — 2 vyhovuje dané rovnici. Představme si nyní, že máme k dispozici libovolné řešení x,y £ Z a pokusme se získat další. Platí tedy (y + V2x) (y - V2x) = 1. Dosazením nalezených hodnot y — 3 a x — 2 získáme rovnost (3 + 2y/2)(3 — 2y/2) — 1, vynásobením dostaneme '(y + VŽx) (3 + 2^2)] • [(y - VŽx) (3 - 2^2)] = 1. Výrazy v obou hranatých závorkách upravíme. Platí (y + VŽx) (3 + 2y/2) = 3y + 3^ + 2^2/ + 4rr - (4rr + 3y) + (3rr + 2y)y/2, (y - V2x) (3 - 2V2) =3y- 3\Í2x - 2\Í2y + Ax = (4rr + 3y) - (3x + 2y)\Í2. 3Jde o speciální případ tzv. Pellovy rovnice Položme u — Ax + 3y, v — 3x + 2y. Platí tedy (u + V2v) (u - V2v) = 1, odkud u2 -2v2 = 1, a tedy u, v G Z je další řešení dané rovnice. Položíme-li x\ — 2, yi — 3 a ^n+i — 3rrn + 2í/n, yn+\ — 4rrn + 3í/n pro libovolné n G N, dostáváme pro každé n G N řešení xn,yn dané rovnice. A protože platí 0 < x\ < x2 < ..., 0 < y± < y2 < ■ ■ ■, dostáváme pro různé indexy n různá řešení xn,yn. Daná rovnice má tedy nekonečně mnoho řešení. □ příklad. Dokažte, že rovnice kJrx2jry2 = z2 má pro libovolné celé číslo k nekonečně mnoho řešení v oboru přirozených čísel. Řešení. Úpravou a rozkladem z2 — y2 dostaneme k + x2 — (z — y)(z + y). Není nutné hledat všechna řešení, proto můžeme předpokládat, že z-y = l, z + y = k + x . Libovolné řešení této soustavy bude také řešení dané rovnice (neplatí to však obráceně, zkuste sami pro nějaké pevně zvolené k nalézt příklad přirozených čísel x, y, z vyhovujících dané rovnici, avšak nevyhovujících uvedené soustavě rovnic). Rešíme-li soustavu vzhledem k neznámým z,y, dostáváme z = \(x2 + /C + 1), y = \(x2 + k-l). Zvolíme-li x = \k\ + 1 + 2t, kde t £ N, je x přirozené číslo. Platí x2 + k = k + l + 2t + k = l (mod 2) a tedy z = |((|/c| + 1 + 2t)2 + k + 1) > 0, y = |((|/c| + 1 + 2t)2 + k - 1) > 0 jsou také přirozená čísla. Protože pro různá t dostáváme různá x a tedy různá řešení, má rovnice nekonečně mnoho řešení. □ příklad. Dokažte, že diofantická rovnice 5rr2 - 8xy + 5y2 - 4k2 = 0 má pro libovolné přirozené číslo k pouze konečně mnoho řešení. ŘEŠENÍ. Danou rovnici upravíme do tvaru (2x — y)2 + (2y — x)2 — 4k2, odkud plyne (2x - y)2 < (2k)2 a (2y - x)2 < (2/c)2, a tedy -2k < 2x - y < 2k a —2k < 2y — x < 2k. Sečtením první a dvojnásobku druhé nerovnosti a vydělením třemi dostaneme — 2k < y < 2k a zcela analogicky — 2k < x < 2k. Protože x i y mohou pro pevné k nabývat pouze konečně mnoha hodnot, má daná rovnice pouze konečně mnoho řešení. □ Literatura [1] M. Davis. Hilbert's tenth problem is unsolvable. The American Mathematical Monthly, 80(3):233-269, March 1973. http://www.jstor.org/stable/2318447. [2] J. Herman, R. Kučera a J. Simša. Metody řešení matematických úloh I. MU Brno, druhé vydání, 2001. [3] K. Ireland a M. Rosen. A Classical Introduction to Modem Number Theory. Číslo 84 v Graduate Texts in Mathematics. Springer, druhé vydání, 1998. [4] J. Slovák, M. Panák a M. Bulant. Matematika drsně a svižně. Masarykova univerzita, 2013. [5] I. M. Vinogradov. Základy theorie čísel. Nakladatelství ČSAV, 1953.