Literatura
[1] M. Davis. Hilbert's tenth problem is unsolvable. The American Mathematical Monthly, 80(3):233-269, March 1973. http: //links. j stor. org/sici?sici=0002-98907.281973037. 29807.3A37.3C2337.3AHTPIU7.3E2. 0. C07.3B2-E.
[2] J. Herman, R. Kučera a J. Simša. Metody řešeni 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] I. M. Vinogradov. Základy theorie čišel. Nakladatelství ČSAV, 1953.
Elementární teorie čísel
Michal Bulant
Ústav matematiky a statistiky, Přírodovědecká fakulta, Masarykova univerzita, Kotlářská 2, 611 37 Brno E-mail address: bulant@math.muni.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), Goldbachovu hypotézu (rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel), nebo klenot mezi problémy teorie čísel - velkou Fermatovu větu (rozhodnout, zda existují přirozená čísla n, x, y, z tak, že n > 2 a platí xn + yn — zn, P. de Fermat formuloval cca 1637, vyřešil A. Wiles 1995).
Tento text výrazně čerpá z knih [2] a [4], pro zájemce o bližší seznámení s některými tématy doporučujeme knihu [3], dostupnou v knihovně PřF MU.
Obsah
Literatura 1
1. Základní pojmy 7
1.1. Úvodní poznámky 7
1.2. Dělitelnost 7
1.3. Největší společný dělitel a nejmenší společný násobek 11
1.4. Dělitelé a násobky mnoha čísel 16
1.5. Nesoudělnost 17
2. Prvočísla 20
3. Kongruence 33
3.1. Základní vlastnosti kongruencí 34
3.2. Aritmetické funkce 40
3.3. Eulerova funkce ip 43
3.4. Malá Fermatova věta, Eulerova věta 46
4. Řešení kongruencí o jedné neznámé 54
4.1. Lineární kongruence o jedné neznámé 56
4.2. Soustavy lineárních kongruencí o jedné neznámé 60
4.3. Kongruence vyšších stupňů 68
4.4. Kongruence s prvočíselným modulem 76
4.5. Binomické kongruence a primitivní kořeny 77
Home Page
Title Page
4.6		Kvadratické kongruence a Legendreův symbol	91
4.7		Jacobiho symbol	101
4.8		Aplikace Legendreova a Jacobiho symbolu.	103
5.	Diofantické rovnice		108
5.1		Lineární diofantické rovnice	108
5.2		Diofantické rovnice lineární vzhledem k některé neznámé	114
5.3		Rovnice jiného tvaru	118
5.4		Řešení diofantických rovnic pomocí nerovností	121
5.4	1.	Některé nerovnosti	127
5.5		Řešení diofantických rovnic metodou rozkladu	130
5.5	1.	Pythagorova rovnice	133
5.6		Řešitelnost diofantických rovnic	135
5.6	1.	Neexistence řešení	136
5.6	2.	Zmenšování ad absurdum	141
5.6	3.	Početnost množiny řešení	145
Contents
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 sekce matematika. 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ě nejpropracovanější. Existuje rovněž mnoho výukových worksheetů. Spustit lze např. ma http://sage.math.muni.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ěli 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
a	b	A	a	c =	=>• a
(1)
- c A a | b - c (2) c ý 0 (a | &       clc | 6c) (3)
a|6 A & >0 ^ a<6 (4)
PŘÍKLAD. Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem n + 1.
Řešení. Platí n2 — 1 = (n + l)(n — 1), a tedy číslo n + 1 dělí číslo n2 — 1. Předpokládejme, že n + 1 dělí i číslo n2 + 1. Pak ovšem musí dělit i rozdíl (n2 + 1) — (n2 — 1) = 2. Protože n G N, platí n+ 1 > 2, a tedy zn + 1 | 2 plyne n +1 = 2, proto n = 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 q G Z; r G {0,1,..., m — 1} íaA;, že a = qm + 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 G Z. Nejprve budeme předpokládat, že a G No 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 q,r dokázali pro všechna a' G {0,1, 2,..., a — 1}. Speciálně pro a' = a — m tedy existují q', r' tak, že a1 = q'm + r' a přitom r' G {0,1,..., m — 1}. Zvolíme-li g = q1 + 1, r = r', platí a = a' + m = (q' + l)m + r' = qm + r, což jsme chtěli dokázat.
Existenci čísel q, 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' G Z, r' G {0,1,..., m— 1} tak, že —a = q'm + r', tedy a = —q'm — r1. Je-li r' = 0, položíme r = 0, q = —q'; 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 G Z, m G N.
Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla g1; g2 £ Z; ri)r2 £ {0,1,... ,m — 1} platí a = q^m + rx = q2m + r2. Úpravou dostaneme r\ — r2 = (g2 — Qi)m, a tedy m | rx — r2. Ovšem z 0 < ^ <m, 0 < r2 < m plyne —m < r\ — r2 < m, odkud podle (4) platí r\ — r2 = 0. Pak ale i (g2 — q\)m = 0, a proto qi = g2, ri = r2. Čísla g, 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ú, 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
ar r
— = q H--, přitom   0 < — < 1.
m m 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 a& číslem m.
Řešení. Podle věty 1 existují s, í g Z tak, že a = sm + 1, 6 = ŕm + 1. Vynásobením dostaneme vyjádření
ah = (sm + l)(tm + 1) = (stm + s + ŕ)m + 1 = gm + r,
kde g = stm + s + t, r = 1, které je podle věty 1 jednoznačné, a tedy zbytek po dělení čísla ah číslem m je jedna. □
Použití v Pari-GP. Vydělením čísla 1234567890 číslem 321 se zbytkem dostáváme 3846005, zbytek 285 - jak vidíme v PARI: ? divrem(1234567890,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 <2i,<22- Libovolné celé číslo m takové, že m | a±, m | <32 (resp. a\ \ m, cí2 \ m) se nazývá společný dělitel (resp. společný násobek) čísel <2i,<22- Společný dělitel (resp. násobek) m > 0 čísel ai,<22, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel a±, CL2, se nazývá nejvčtší společný dělitel (resp. nejmenší společný násobek) čísel značí se (a1}a2) (resp. [a^c^])-
poznámka. Přímo z definice plyne, že pro libovolné a, b g Z platí (a, 6) = (6, a), [a,b] = [b,a], (a, 1) = 1, [a, 1] = (a,0) = \a\, [a, 0] = 0. Ještě však není jasné, zda pro každou dvojici a, b g 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,rri2 g No totiž podle (4) platí, že pokud ni\ \ ni2 a zároveň ni2 \ nii, je nutně ni\ = ni2. Důkaz existence čísla (a, b) 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) Nechi a1}a2 jsou přirozená čísla. Pro každé n > 3, pro které an_i Ý 0; označme an zbytek po dělení čísla an_2 číslem an_i. Pak po konečném počtu kroků dostaneme aj- = 0 a platí       = (ai, 02)-
DŮKAZ. Podle věty 1 platí a2 > ^3 > 04 > .... 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ž dk-i 7^ 0. Z definice čísel an plyne, že existují celá čísla q1,q2,..., qu-2 tak, že
a>i = qi ■ a2 + a3, a2 = q2 ■ a3 + a4,
i (5)
ak-3 = qk-3 ' ak-2 + ak-l ak-2 = Qk-2 ■ ak-l-
Z poslední rovnosti plyne, že a^-i \ a.h-21 z předposlední, že a^-i | 0^-3? atd., až nakonec ze druhé a^-i \ a2 a z první dostaneme | aľ. Je tedy společný dělitel čísel a±, a2. Naopak jejich libovolný společný dělitel dělí i číslo 03 = a\ — q±a2, proto i 04 = a2 — q2a3,..., a proto i = ak-3 — qk-z&k-2- Dokázali jsme, že afc-i je největší dělitel čísel 01,02- D
POZNÁMKA. Z poznámky za definicí, z věty 2 a z toho, že pro libovolná a, 6 G Z platí (a, b) = (a, —b) = (—a, b) = (—a, —b) plyne, že existuje největší společný dělitel libovolných dvou celých čísel.
VĚTA 3. (Bezoutova) Pro libovolná celá čísla a±,a2 existuje jejich největší společný áčlitel (01,02); přitom existují celá čísla k±,k2 tak, že (01,02) = k±ai + k2a2.
DŮKAZ. Jistě stačí větu dokázat pro Oi,a2 G N. Všimněme si, že jestliže je možné nějaká čísla r, s G Z vyjádřit ve tvaru r = riOi + r2a2? s = siai + s2a2, kde ri) r2j si, s2 G Z, můžeme tak vyjádřit i
c ■ r = (c • ri)ai + (c • r2)a2
pro libovolné c G Z. Protože a\ = 1 • a\ + 0 • 02? a2 = 0 • ai + 1 • 02? plyne z (5), že takto můžeme vyjádřit i a3 = ai — qia2, 0,4 = a2 — q2a?>i ■ ■ ■, ak-i = ak-3~Qk-3ak-2,
POUŽITÍ V PARI-GP. Výpočet největšího společného dělitele pomocí Euklidova algoritmu je s využitím výpočetní techniky i pro relativně velká čísla poměrně rychlý. V našem příkladu to vyzkoušíme na 2 číslech A,B, z nichž každé je součinem dvou 101-ciferných prvočísel. Všimněme si, že výpočet největšího společného dělitele i takto velkých čísel trval zandbatelný čas. ? p=nextprime(5*lCT100) ; ? q=nextprime(3*lCT100);
r + s = (ri + si)ai + (r2 + s2)a2
a také
□
? r=nextprime(10"100); ? A=p*q; ? B=q*r; ? #
timer = 1 (on) ? gcd(A,B) time = 0 ms.
7.19 = 300000000000000000000000000000000000000000\
oooooooooooooooooooooooooooooooooooooooooooooooox
00000000223 ? bezout(A,B) time = 0 ms.
7.20 = [284455128205128205128205128205128205128205\ 1282051282051282051282051282051282051282051282051\ 282051358, -1422275641025641025641025641025641025\ 6410256410256410256410256410256410256410256410256\ 410256410256435, 30000000000000000000000000000000\
ooooooooooooooooooooooooooooooooooooooooooooooooox
00000000000000000223]
poznámka. Euklidův algoritmus a Bezoutova věta jsou jedny z nej důležitějších výsledků elementární teorie čísel a tvoří jeden ze základních pilířů algoritmů algebry a teorie čísel.
To, že znalost těchto základů je občas důležitá i v praktickém životě, dokazuje Bruče Willis a Samuel Jackson ve filmu Smrtonosná past 3, kde mají za úkol zlikvidovat bombu pomocí 4 galonů vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonů. Zde stačí s využitím Euklidova algoritmu najít celá čísla k, l tak, že bude platit 3k + 51 = 4. Netroufám si tvrdit, že zmínění herci ovládají uvedené základy teorie čísel (tuto konkrétní úlohu jistě snadno vyřešíte experimentálně), nicméně předchozí věty dávají návod, jak vyřešit úlohu tohoto typu s libovolnými zadanými parametry, což podrobně rozebereme v části o diofantických rovnicích.
věta 4. Pro libovolná celá čísla a1} a2 existuje jejich nejmenší společný násobek [a,i, a2] a platí (a1; a2) ' [ai, a2\ = \ai ' a2\■
důkaz. Věta jistě platí, je-li některé z čísel ai,a2 rovno nule. Můžeme navíc předpokládat, že obě nenulová čísla a1,a2 jsou kladná, neboť jejich znaménka se v dokazovaném vzorci neprojeví. Budeme hotovi, ukážeme-li, že q = a\-a2j(a1; a2) je nejmenší společný násobek čísel a1}a2. Protože (a1}a2) je společný dělitel čísel a1}a2, jsou a\j(a\^ a2) ia2/(ai>a2) celá čísla, a proto
Qj\Qj2 Qj\ CL2
q = t-r = t-r • a2 =--- • aľ
je společný násobek čísel a\, d2- Podle věty 3 existují k\, ^ G Z tak, že {a\, 02) = k\d\ + k^a^. Předpokládejme, že n G Z je libovolný společný násobek čísel 0,1,0,2 a ukážeme, že je dělitelný číslem q. Je tedy nja\,nj02 G Z, a proto je i celé číslo
n n n(kiOi + k2a2)     niaiia2) n
— • k\ H--• «2 =-= -= — •
<32 cti 0102 0102 Q
To ovšem znamená, že q \ n, což jsme chtěli dokázat. □ 1.4. Dělitelé a násobky mnoha čísel.
Definice. Nej větší společný dělitel a nejmenší společný násobek n čísel a1; a2,..., a Z definujeme analogicky jako v 1.3. Libovolné m G Z takové, že m | a1? m | 02? ..., m I an (resp. a\ \ m, a2 \ m, ..., an \ m) se nazývá společný dělitel (resp. společný násobek) čísel a1; a2,..., an. Společný dělitel (resp. násobek) m > 0 čísel ai, 0,2, ■ ■ ■ ,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ší společný násobek) čísel a\, 02,..., an a značí se {a\, 02,..., an) (resp. [a1,a2, ■ ■ -,an]).
Snadno se přesvědčíme, že platí
(ai,... ) = ((fli,...
j ^n—i); Q"n ), (6) [ai,..., an_i, an] = [[aľ,..., an-i], an]. (7)
Největší společný dělitel {a\, . . . , an) totiž dělí všechna čísla a\,..., an, a tedy je společným dělitelem čísel a\, ..., an_i, a proto dělí i největšího společného dělitele (<2i,..., an-i), tj. (ai,..., an) | ((<2i,..., an-i), an). Naopak největší společný dělitel čísel (a1;..., an_i), an musí kromě čísla an dělit i všechna čísla a1;..., an_i, protože dělí jejich největšího společného dělitele, a proto ((<2i,..., an_i), an) | (a1;...,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 n = 2 je jejich existence dána větami 2a-, jestliže pro některé n > 2 víme, že existuje největší společný dělitel i nejměnší společný násobek libovolných n — 1 čísel, podle (6) a (7) existuje i pro libovolných n čísel.
1.5. Nesoudělnost.
Definice. Čísla a1; a2,..., an g Z se nazývají nesoudělná, jestliže platí (a1; a2) • • 1. Čísla <2i, a,2,... ,an g Z se nazývají po dwon nesoudělná, jestliže pro každé i, j takové, že 1 < i < j < n, platí (aj, dj) = 1.
poznámka. V případě n = 2 oba pojmy splývají, pro n > 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 nejvě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 -l = (221 + 214 + 27 + l)(27-l).
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, b) právě tehdy, když existují q1}q2 g N tak, že a = dqľ, b = dq2 a
(Ql,Q2) = 1.
důkaz, ad 1. Protože (a, b) je společný dělitel čísel a, b, je (a, b) ■ c společný dělitel čísel ac, bc, proto (a, b) ■ c \ (ac,bc). Podle věty 3 existují fc,! g Z tak, že (a, b) = ka + lb. Protože (ac,bc) je společný dělitel čísel ac, bc, dělí i číslo kac + lbe = (a, b) ■ c. Dokázali jsme, že (a, b) ■ c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se podle (4) rovnají.
ad 2. Předpokládejme, že (a, b) = 1 a a | bc. Podle Bezoutovy věty (věta 3) existují k,l g Z tak, že ka + lb = 1, odkud plyne, že c = c(ka + lb) = kca + lbe. Protože a | bc, plyne odsud, že i a | c.
Home Page
ad 3. Nechť d = (a, b), pak existují q±,q2 G N tak, že a = dqi, b = dq2. Pak podle části (1) platí d = (a, b) = (dqi, dq2) = d-(qi, q2), a tedy (gi, q2) = 1. Naopak, je-li a = dqi, b = dq2 a (gi, q2) = 1, pak (a, b) = (dqi, dq2) = d(qi, q2) = d ■ 1 = d (opět užitím 1. části tohoto tvrzení). □
Page 19 of 149
Full Screen
Quit
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: 1 a n. 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, .... 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 (největší známé prvočíslo 243112609 — 1 má pouze 12 978189 cifer).
VĚTA 6. Přirozené číslo p > 2 je prvočíslo, právě káyž platí: pro kažáá 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 = ab, odkud 1 < a < p, 1 < b < p. Našli jsme tedy celá čísla a, b tak, že p | ab a přitom p nedělí ani a, ani b. □
příklad. Nalezněte všechna čísla k G No, pro která je mezi deseti po sobě jdoucími čísly k + l,k + 2,...,k + 10 nejvíce prvočísel.
řešení. Pro k = 1 je mezi našimi čísly pět prvočísel: 2, 3, 5, 7, 11. Pro k = 0 a k = 2 pouze čtyři prvočísla. Jestliže A; > 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+ 2, ..., 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é 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 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
'p\ =      p\       = p ■ (p - 1).....(p - k + 1)
Jt)     k\(p-k)\ 1-2.....k
a tedy k\ \ p ■ a, kde jsme označili a = (p — 1).....(p — k + 1). Protože k < p,
není žádné z čísel 1, 2,..., k dělitelné prvočíslem p, 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 = -| je celé číslo. Protože (f) = *f =     Je číslo (^) dělitelné číslem p. □
věta 7. Libovolné přirozené číslo n > 2 je možné vyjádřit jako součin prvočísel, přičemž je toto vyjádření jediné, nebereme-li v úvahu pořadí činitelů. (Je-li n prvočíslo, pak jde o "součin"jednoho prvočísla.)
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(^/—5) máme následující rozklady: 6 = 2-3 = (1 + \j—5) • (1 — \j—5); zkuste si rozmyslet, že všichni uvedení činitelé jsou skutečně v 7L(\j—5) ireducibilní).
DŮKAZ. Nejprve dokážeme indukcí, že každé n > 2 je možné vyjádřit jako součin prvočísel.
Je-li n = 2, je n součin jediného prvočísla 2.
Předpokládejme nyní, že n > 2 a že jsme již dokázali, že libovolné n', 2 < n! < n, je možné rozložit na součin prvočísel. Jestliže n je prvočíslo, je součinem jediného prvočísla. Jestliže n prvočíslo není, pak existuje jeho dělitel d, 1 < d < n. Označíme-li c = ^, platí také 1 < c < n. 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 = n.
Nyní dokážeme jednoznačnost. Předpokládejme, že platí rovnost součinů p\ ■
P2.....Pm = qi ■ Q2qs, kde p±,... ,pm, q±,..., qs jsou prvočísla a navíc platí
Pi < ř>2 < • • • < Pm, qi < ?2 < • • • < ?s a 1 < ^ < s. Indukcí vzhledem k m dokážeme, že m = s, p\ = q±,... ,pm = qm.
Je-li m = 1, je p\ = q±.....qs prvočíslo. Kdyby s > 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 s = 1 a platí Pi = q±.
Předpokládejme, že m > 2 a že tvrzení platí pro m— 1. Protože p\-p2.....pm =
q± ■ q2.....qs, dělí pm součin qľ.....qs, což je podle věty 6 možné jen tehdy,
jestliže pm dělí nějaké g« pro vhodné i E {1,2,..., s}. Protože g« je prvočíslo, plyne odtud pm = qi (neboť pm > 1). Zcela analogicky se dokáže, že qs = pj pro vhodné j g {1,2,..., m}. Odtud plyne
qs = Pj <Pm = qí< qa,
takže pm = qs. Vydělením dostaneme p± ■ p2.....pm-i = qi ■ <iiQs-i, a tedy
z indukčního předpokladu m — 1 = s — 1, p\ = q±,... ,pm-i = qm-i- Celkem tedy m = s a pi = qi,... ,pm-i = qm-i, Pm = qm- Jednoznačnost, a proto i celá věta 7 je dokázána. □
poznámka. Již jsme se zmínili, že je složité o velkých číslech s jistotou rozhodnout, jde-li o prvočíslo (na druhou stranu je o naprosté většině složených čísel snadné prokázat, že jsou skutečně složená). Přesto se v roce 2002 podařilo indickým matematikům (Agrawal, Saxena, Kayal: http://www.cse.iitk.ac.in/ users/manindra/algebra/primality_v6 .pdf) dokázat, že problém prvočíselnosti je možné rozhodnout algoritmem s časovou složitostí polynomiálně závislou na počtu cifer vstupního čísla. Nic podobného se zatím nepodařilo v otázce rozkladu čísla na prvočísla (třebaže se obecně nevěří, že je to možné, exaktní důkaz zatím nebyl podán).
Ze je problém rozkladu přirozeného čísla na prvočísla výpočetně složitý, o tom svědčí i výzva učiněná firmou RSA Security (viz http://www.rsasecurity.com/ rsalabs/node. asp?id=2093). Pokud se vám podaří rozložit čísla označená podle počtu cifer jako RSA-704, RSA-768, ..., RSA-2048, obdržíte 30 000, 50 000, resp. 200 000 dolarů (čísla RSA-576 a RSA-640 již byla rozložena v roce 2003, resp. 2005; byla-li vyplacena slíbená odměna, mi není známo).1.
Výzva byla ukončena v roce 2007
DŮSLEDEK.        (1) Jsou-li pi,... ,Pk navzájem různá prvočísla ani,
No, je kažáý klaáný áčlitel čísla a = p"1.....p^h tvaru p"11.....
mi,..., mk E N0 a nii < nlt m2 < n2, ■ ■ ■, mk < nk. Číslo a má teáy právě
r(á) = (m + l)(n2 + 1).....(nk + 1)
klaáných áělitelů, jejichž součet je
1
mu Pk
nk e , kde
pT+1
Pk
a (a)
K J      Pi-l Pk-l (2) Jsou-li pi,... ,pk navzájem různá prvočísla a n\, . . ., nk, ni\, . . ., mk No a označíme-li r,i = min{nj,mj}; ti = max{rij,mj} pro každé i 1,2,
rtu mi
pk ,Pi
nu mi
■pk ,Pi
pT) ■pT\
p'i
Á1
■Pk >
tu
Pk-
, k, platí (Pi1 ■ ■ [P? ■ ■
POZNÁMKA. S pojmem součet všech kladných dělitelů čísla a souvisí pojem tzv. dokonalého čísla a, které splňuje podmínku a(a) = 2a, resp. slovně: "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 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 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. Mersenneho prvočísly. Platí totiž: a je sudé dokonalé číslo, právě když je tvaru a = 2q~ľ-(2q — 1), kde 2q — 1 je prvočíslo. Mersenneho prvočísla jsou právě prvočísla tvaru 2k — 1. Bez zajímavosti není ani to, že právě Mersenneho prvočísla jsou mezi všemi prvočísly nejlépe "vidět"- obecně je pro velká čísla, u kterých se nedaří nalézt netriviálního dělitele, obtížné prokázat, že jsou prvočísla. Pro Mersenneho prvočísla existuje poměrně jednoduchý a rychlý postup. Proto není náhodou, že největší známá prvočísla jsou obvykle tvaru 2k — 1 (viz např. http://www.utm.edu/research/ primes/largest.html).
Na druhou stranu popsat lichá dokonalá čísla se dodnes nepodařilo, resp. dodnes se neví, jestli vůbec nějaké liché dokonalé číslo existuje
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\ — l (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 pi,P2, ■ ■ ■,pn- Položme N = p\ ■ p2 ■ ■ ■ pn + 1- Toto číslo je buď samo prvočíslem nebo je dělitelné nějakým prvočíslem různým od p±,... ,pn (čísla p±,... ,pn totiž dělí číslo N — 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 N = p\ ■ p2 • • -pn > 2. číslo N — 1 je podle věty 7 dělitelné některým prvočíslem pi, které dělí zároveň číslo N a tedy i iV— (N — 1) = 1. Spor.
(Fůrstenberg, 1955):
V této poznámce uvedeme elementární "topologický"důkaz existence nekonečně mnoha prvočísel. Zavedeme topologii prostoru celých čísel pomocí báze tvořené aritmetickými posloupnostmi (od — oo do +oo). 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 počtu 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 3k + 2, kde k E 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, ps = 11, ..., pn. Položme N =
3p2 -p3.....Pn + 2. Rozložíme-li N na součin prvočísel podle věty 7, musí v tomto
rozkladu vystupovat aspoň jedno prvočíslo p tvaru 3A;+2, neboť v opačném případě by bylo N součinem prvočísel tvaru 3A; + 1 (uvažte, že N není dělitelné třemi), a tedy podle příkladu na str. 10 by bylo i N tvaru 3fc + 1, což neplatí. Prvočíslo p ovšem nemůže být žádné z prvočísel p1}p2, ■ ■ ■ ,pn, jak plyne z tvaru čísla N,ato je spor. □
POZNÁMKA. Analogicky se dokáže i tvrzení o prvočíslech tvaru Ak + 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 Ak + 1.
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 9. (Č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 mezí čí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ý,
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":
VĚTA 10. (o hustotě prvočísel) Nechť tt(x) udává počet prvočísel menších nebo rovných číslu x G IR. Pak
tj. podíl funkcí 7r(x) a x/\nx se pro x —> oo limitně blíží k 1.
POZNÁMKA. To, jak jsou prvočísla hustě rozmístěna v množině přirozených čísel, rovněž udává Eulerův výsledek
proto zde není uveden.
□
Přitom např.
což znamená, že prvočísla jsou v N rozmístěna "hustěji"než druhé mocniny.
POUŽITÍ v Pari-GP. O tom, jak odpovídá asymptotický odhad tt(x) ~ x j 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]; ? for(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	7r(rr)	xj 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
Poslední příklad (o nekonečnosti počtu prvočísel tvaru 3fc+2) zobecňuje Dírích-letova věta o aritmetické posloupností:
věta 11. (Díríchletova) 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 • m + a, 2 • m + a, 3 • m + 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] □
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 n, nebo tím, že n = pvp(n) . m? kde m je celé čí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  =^ vp(a + b) > vp(a) (9)
vp(a) < Vp{b)  =^ vp(a + b) = vp(a) (10)
Vp(a)<Vp(b)  =^ 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, b, c platí
([a, 6], [a, c], [b, c]) = [(a, 6), (a, c), (6, c)]
ŘEŠENÍ. Podle věty 7 budeme hotovi, ukážeme-li, že i>p(L) = vp(P) pro libovolné prvočíslo p, 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(á), 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 kongruentní modulo m (též kongruentní podle modulu m), což zapisujeme takto:
a = b   (mod m).
V opačném případě řekneme, že a, b nejsou kongruentní 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;
(3) m\a-b.
důkaz. "(1)^(3)" Jestliže a = q\m + r, b =       + r, pak a — b = (qi — q2)m. " (3)=^(2)" Jestliže m \ a — b, pak existuje t g Z tak, že m ■ t = a — b, tj. a = b + mt.
" (2)^(1)" Jestliže a = b+mt, pak z vyjádření 6 = mq+r plyne a = m(q+t)+r, tedy a i b 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 £ 1* z a = b (mod m) plyne b = a (mod m)) a tranzitivní (tj. pro každé a, b, c G Z z a = b (mod m) a b = c (mod m) plyne a = c (mod m)) relace, jde tedy o ekvivalencí. Dokážeme nyní další vlastnosti:
VĚTA 12. (Základní vlastností 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 t1? ŕ2 £ Z tak, že aľ = bľ + mti, a2 = b2 + mt2. Pak ovšem a>i + 0-2 = bi + b2 + m(íi + t2) a opět podle lemmatu a\ + a2 = b\ + b2 (mod m). Sečteme-li kongruenci a+b = c (mod m) s kongruencí —6 = —b (mod m), která zřejmě platí, dostaneme a = c — b (mod m). Sečteme-li kongruenci a = b (mod m) s kongruencí mA; = 0 (mod m), jejíž platnost je zřejmá, dostaneme a + mk = 6 (mod m). □
^ Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence 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 g Z tak, že a\ = b\ + míi, 02 = &2 +        Pak ovšem
axa2 = (61 + míi) (62 + mt2) = hb2 + m{t^b2 + &it2 + mt^),
odkud podle dostáváme 0102 = b±b2 (mod m).
Je-li a = b (mod m), dokážeme indukcí vzhledem k přirozenému číslu n, že platí an = bn (mod m). Pro n = 1 není co dokazovat. Platí-li an = bn (mod m) pro nějaké pevně zvolené n, vynásobením této kongruence a kongruence a = b (mod m) dostáváme an ■ a = bn ■ b (mod m), tedy fln+i = ^n+i (moc[ m^ C02 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 = 6c (mod m). □
^ Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem.
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 = (aľ — bľ) ■ d dělitelný číslem 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 í tak, že a = b + mí, odkud pro c g N platí ac = 6c + mc ■ í, odkud opět podle lemmatu plyne ac = bc (mod mc). □
(5) Obě strany kongruence i její modul můžeme vydělit jejích společným kladným dělitelem.
DŮKAZ. Předpokládejme, že a = b (mod m), a = a\ ■ d, b = b\ ■ d, m = ni\ ■ d, kde d g N. Podle lemmatu existuje í g Z tak, že a = b + mí, tj. ai-d = bi-d + rriidt, odkud a\ = bi+rriit, což podle lemmatu znamená, že a\ = bi (mod rrii). □
(6) 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 1112),... ,a = b (mod nik), podle lemmatu je rozdíl a — b společný násobek čísel mi,rri2,... ,rrik a tedy je dělitelný jejich nejmenším společným násobkem [m1; m2,..., mj, odkud plyne a = b (mod [m1;..., m^]). □
(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). □
(8) 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 = ni\d. Pak podle lemmatu existuje t g Z tak, že a = b + mt = b\d + ni\dt = (pi + mit)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 10 lze přeformulovat do tvaru "jestliže a = 1 (mod m), 6 = 1 (mod m), pak také ab = 1 (mod m)", což je speciální případ tvrzení věty 12 (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 12 (2)
52o _ (_^io = x    (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 12 (2) a (1) platí
37n+2 + lgn+l + 2gn _ + +       = 2™(4+2+l) = T ■ 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 12
n = (25 + 6)18 - 1 = 3818 - 1 = 318 - 1 = 276 - 1 = (-1)6 - 1 = 0    (mod 7),
proto 7 | n. Podobně 835 = 3 (mod 16), a tedy
n = (35 + 6)18 - 1 = (3 • 81 + 6)18 - 1 = (3 • 1 + 6)18 - 1 =
= 918 - 1 = 819 - 1 = l9 - 1 = 0    (mod 16), proto 16 | n. Celkem tedy 112 | n, což jsme měli dokázat. □ PŘÍKLAD. Dokažte, že pro libovolné prvočíslo p a libovolná a, b g Z platí
ď + bp = (a + b)p   (mod p).
Řešení. Podle binomické věty platí
(a + bf = ď+ (Oď-'b + (l)ď-%2 + ■■■+ (^atř-1 + W.
Podle příkladu za větou 6 pro libovolné k E {1,... ,p— 1} platí (^) = 0 (mod p), odkud plyne tvrzení. □
Následující tvrzení je další užitečnou vlastností kongruencí:
Lemma. Dokažte, že pro libovolné přirozené číslo m a libovolná a, b E Z taková, že a = b (mod mn), kde nGN, platí, že am = bm (mod mn+1).
důkaz. Platí
am-bm = (a- b) (a171'1 + am~2& + • • • + a&m~2 + 6m_1) (12)
a protože m | mn, tak podle 12 (7) platí i a = b (mod m). Jsou tedy všechny sčítance ve druhé závorce v (12) kongruentní s am~ľ modulo m, a tedy
am-l + am-2h + . . . + fl&m-2 + _ m . flm-l _ Q      (mod m)?
proto je am~ľ + am~2 + • • • + abm~2 + &m_1 dělitelné m. Z a = b (mod mn) plyne, že mn dělí a — b, a tedy mn+1 dělí jejich součin, což vzhledem k (12) vede k závěru, že am = bm (mod mn+1). □
3.2. Aritmetické funkce. Aritmetickou funkcí zde rozumíme funkci, jejímž definičním oborem je množina přirozených čísel.
Definice. Rozložme přirozené číslo n na prvočísla: n = p"1 ■ ■ -p^k. Hodnotu Mobíovy funkce fi(n) definujeme rovnu 0, pokud pro některé i platí «j > 1 a rovnu (—l)k v opačném případě. Dále definujeme        = 1.
příklad. /x(4) = /x(22) = 0,/x(6) = fi(2 ■ 3) = (-l)2,/x(2) = /x(3) = -1.
Dokážeme nyní několik důležitých vlastností Môbiovy funkce, zejména tzv. Mobíovu inverzní formulí.
Lemma. Pro n e n \ {1} platí
5>(d) = o.
d\n
důkaz. Zapíšeme-li n ve tvaru n = p"1 ■ ■ -p^.k, pak všechny dělitele d čísla n jsou tvaru d = pf1 ■ ■ -pffe, kde 0 <     <     pro všechna i G {1,..., A;}. Proto
d\n (i81,...,i8fe)e(NU{0})fe 0<ft<«í
(h,...a)e{o,i}k = © + ©•(-!) + © "(-I)2 + -+(í)-("l)fc
= (i + (-i))fc = o.
□
S Môbiovou funkcí úzce souvisí pojem Díríchletův součin:
Definice. Buďte /, p aritmetické funkce. Jejich Díríchletův součin je definován předpisem
(fog)(n) = 52f(d)-g(*)=  ]T M)-^).
<i|n did,2=n
Lemma. Díríchletův součin je asociativní.
DŮKAZ.
((fog)oh){n)=    Y,    f{d1)-g{d2)-h{d,) = {fo(goh)){
d\d,2dz=n
n)
□
PŘÍKLAD. Definujme dvě pomocné funkce I a J předpisem 1(1) = 1, l(n) = 0 pro všechna n > 1, resp. I(n) = 1 pro všechna n G N. Pak pro každou aritmetickou funkci / platí:
/oI = Io/ = /
(Iof)(n) = (foI)(n) = Y,f(d).
d\n
Dále platí Jo/í = /íoJ = I) neboť
(W)(n) = X)/(d)M2) = X)7(5)Md) =
cí|n d\n
= = 0   pro všechna n > 1
<i|n
podle lemmatu za definicí Móbiovy funkce (pro n = 1 je tvrzení zřejmé).
VĚTA 13. (Môbíova inverzní formule) Nechť je aritmetická funkce F definovaná pomocí aritmetické funkce f předpisem F(n) = ^d|n f{d). Pak lze funkci f vyjádřit ve tvaru
/(n) = X>(3) • *W
d\n
DŮKAZ. Vztah F(n) = ^d|n f{d) lze jiným způsobem zapsat jako F = f o J. Proto F o ^ = (J o /) o p = / o (/ o /i) = / o I = /, což je tvrzení věty. □
Definice. Multiplikativní funkcí přirozených čísel rozumíme takovou aritmetickou funkci, která splňuje, že pro všechny dvojice nesoudělných čísel a, b g N platí
f(a-b) = f(a)-f(b).
PŘÍKLAD. Multiplikativními funkcemi jsou např. funkce f(n) = <j(n), f(n) = t(ji), či f(n) = fi(n) nebo, jak brzy dokážeme i tzv. Eulerova funkce f(n) = f(n).
3.3. Eulerova funkce ip.
Definice. Nechť n g N. Definujme Eulerovu funkci ip předpisem ip(n) = \{a g N I 0 < a < n, (a, n) = 1}\
PŘÍKLAD. </?(l) = 1, v?(5) = 4,99(6) = 2, je-li p prvočíslo, je zřejmě f{p) = p — 1.
Nyní dokážeme několik důležitých tvrzení o funkci ip: Lemma. Nechť n eN. Pak Y,d\n <-P{d) = n-důkaz. Uvažme n zlomků
1  2 3
n — 1 n
i   i   i ■ ■ ■ i i n n n n n
Zkrátíme-li zlomky na základní tvar a seskupíme podle jmenovatelů, snadno dostaneme právě uvedené tvrzení. □
věta 14. Nechť n eN, jehož rozklad je tvaru n = p"1 ■ ■ ■ p^. Pak
<p{n) = n
Pi
Pk
důkaz. S využitím předchozího lemmatu a Môbiovy inverzní formule dostáváme
d\n
n n
- = n--
d pl
^ + ... + (-1)' "
Pk P\---Pk
n ■ | 1--
Pi
1--
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. Nechi a, b G N, (a, b) = 1. Pak
ip(a • b) = p (a) • <p(b).
DŮKAZ. Zřejmý. □
POZNÁMKA. Rovněž toto tvrzení lze odvodit nezávisle na základě poznatku (n, ab) = 1 •<=>- (n, a) = lA(n,b) = 1. Spolu se snadno odvoditelným výsledkem
a-l
<p(pa)=Pa-pa-L = (p-l)-P
pak lze odvodit vztah (13) již třetím způsobem. PŘÍKLAD. Vypočtěte y?(72).
=* y>(72) = 72 • (1 - i) • (1
(14)
Řešení. 72 = 23 • 32 = y?(72) = v?(8) • y?(9) = 4 • 6 = 24.
příklad. Dokažte, že Vn g n : ip(4n + 2) = ip(2n + 1).
řešení. v?(4n + 2) = v?(2 • (2n + 1)) = ip{2) ■ <f{2n + 1) = v?(2n + 1).
24, alternativně □
□
3.4. Malá Fermatova věta, Eulerova věta. Tvrzení v tomto odstavci patří mezi nej důležitější výsledky teorie čísel.
VĚTA 15 (Fermatova, Malá Fermatova). Nechť a G Z, p prvočíslo, p\ a. Pak
ď'1 = 1   (modp). (15)
DŮKAZ. Tvrzení vyplyne jako snadný důsledek Eulerovy věty 16. □
důsledek. Nechť a e Z, p prvočíslo. Pak
ď = a   (mod p).
DŮKAZ. Pokud p | a, pak jsou obě strany kongruentní s 0 mod p, jinak tvrzení snadno plyne vynásobením obou stran kongruence (15) číslem a. □
Definice. Upíná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0,1,..., m — 1).
Redukovaná soustava zbytků modulo m je libovolná ^(m)-tice čísel nesoudělných s m a po dvou nekongruentních modulo m.
POZNÁMKA. Snadno lze vidět, že jsou-li a,b G Z, a = b (mod m), a (a,m) = 1, pak i (6, m) = 1.
Lemma. Nechť x±,x2,..., tvoři redukovanou soustavu zbytků modulo m.
Je-li a G Z, (a, m) = 1 pak i čísla tvoří redukovanou soustavu
zbytků modulo m.
DŮKAZ. Protože (a, m) = 1 a (xi,m) = 1, platí (a • Xi,m) = 1. Kdyby pro nějaká i, j platilo (mod m), po vydělení obou stran kongruence
číslem a nesoudělným s m dostaneme Xi = x j (mod m). □
VĚTA 16 (Eulerova). Nechť a G Z, m G N, (a, m) = 1. PaÄ:
a¥>(m) _ x    (mod my (16)
DŮKAZ. Buď rri,rE2,... ,xv(m) libovolná redukovaná soustava zbytků modulo m. Podle předchozího lemmatu je i a ■ x±,..., a ■ xv(m) redukovaná soustava zbytků modulo m. Platí tedy, že pro každé i existuje j (oba indexy jsou z množiny {1,2,..., íp(m)}) tak, že a ■ x,i = x j (mod m). Vynásobením čísel obou redukovaných soustav zbytků dostáváme
(a • xi) ■ (a • x2) • • • (a • xv^) = x\ ■ x2 • • • ^(m)   (mod m).
Po úpravě
av{m) .Xl.X2... x^m) =x1-x2--- x^m)   (mod m) a protože (x\ ■ x2 ■ ■ ■ xv^,m) = 1, můžeme obě strany kongruence vydělit číslem X\ ■ x2 ■ ■ ■ x^rn) a dostaneme a^(m) = 1 (mod m). □
poznámka. Eulerova věta je rovněž důsledkem Lagrangeovy věty uplatněným na grupu (Z*, •).
příklad. Nalezněte všechna prvočísla p, pro která 5p2 + 1 = 0 (mod p2).
řešení. Snadno se přesvědčíme, že p = 5 úloze nevyhovuje. Pro p ^ 5 platí (p, 5) = 1, a tedy podle Fermatovy věty 5P_1 = 1 (mod p). Umocněním na p + 1 dostaneme 5P _1 = 1 (mod p), odkud 5P = 5 (mod p). Z podmínky 5P +1 = 0 (mod p2) plyne 5P = — 1 (mod p), celkem tedy 5 = — 1 (mod p), a proto p | 6. Je tedy buď p = 2, nebo p = 3. Pro p = 2 však 54 + l = l4+ 1 = 2^0 (mod 4). Pro p = 3 dostáváme 59 + 1 = 56 • 53 + 1 = 53 + 1 = 126 = 0 (mod 9), kde jsme užili důsledek Eulerovy věty 56 = 1 (mod 9). Jediným prvočíslem, vyhovujícím úloze je tedy p = 3. □
příklad. Pro liché číslo m > 1 nalezněte zbytek po dělení čísla 2lr(m)~1 číslem
m.
řešení. Z Eulerovy věty plyne 2^™) = 1 = 1 + m = 2r (mod m)), kde r = je přirozené číslo, 0 < r < m. Podle 12 (3) platí 2'ŕ(m)~1 = r (mod m), a tedy hledaný zbytek po dělení je r = ^-r^L. □
tvrzení 3.1. Je-li p prvočíslo, p = 3 (mod 4), pak pro libovolná celá čísla a, b z kongruence a2 + b2 = 0 (mod p) plyne a = b = 0 (mod p).
DŮKAZ. Předpokládejme, že pro a, b G Z platí a2 + b2 = 0 (mod p). Jestliže p | a, platí a = 0 (mod p), proto 62 = 0 (mod p), tedy p | 62, odkud vzhledem k tomu, že p je prvočíslo, dostáváme p | b, a proto a = 6 = 0 (mod p), což jsme chtěli dokázat.
Zbývá prošetřit případ, kdy a není dělitelné prvočíslem p. Odtud dostáváme, že p nedělí ani 6 (kdyby p | 6, dostali bychom p | a2). Vynásobíme-li obě strany kongruence a2 = —b2 (mod p) číslem 6P_3, dostaneme podle Fermatovy věty
a2lf-3 = -F'1 = -1 (modp).
Protože p = 3 (mod 4), je p — 3 sudé číslo, a proto       G No- Označme
c = ab 2 .
Pak c není dělitelné p a platí c2 = a2^-3 = — 1 (mod p). Umocníme-li poslední kongruenci na      ^ dostaneme
ď-1 = (—l)2^ (modp).
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 (—1)(p-1)/2 = —1. Podle Fermatovy věty naopak platí cp_1 = 1 (mod p), odkud 1 = — 1 (mod p) a p | 2, spor. □
S Eulerovou funkcí a Eulerovou větou úzce souvisí důležitý pojem řá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ě </?(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
PŘÍKLAD. Určete řád čísla 2 modulo 7.
Ř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), paA: o6ě čísla a, b mají stejný řád modulo m.
důkaz. Umocněním kongruence a = b (mod m) na n-tou dostaneme an = bn (mod m), tedy an = 1 (mod m) <^=4> bn = 1 (mod m). □
Lemma. Nechť m g N, a g Z, (a, m) = 1. Je-Zž rad čzs/a a modulo m roven r ■ s, (kde r, s g N), pak řád čísla 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(s~1)r kongruentní s 1. Platí ale (ar)s = 1 (mod m), proto je řád ar modulo m roven s. □
POZNÁMKA. Opak obecně neplatí - z toho, že řád čísla ď 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. b = -4, 62 = 16    1 (mod 13), 63 = -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 17. Nechť m G N, a G Z, (a, m) = 1. Označme r řád čísla a modulo m. Pak pro libovolná t, s G N U {0} platí
a1 = 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 q, z E No, 0 < z < r. "<É=" Protože t = s (mod r), máme z = 0, a tedy a*~s = a?r = (ar)9 = l9 (mod m). Vynásobením obou stran kongruence číslem as dostaneme tvrzení. "=^" Z a* = as (mod m) plyne as • a9r+z = ď (mod m). Protože je ď = 1 (mod m), je rovněž a9r+z = az (mod m). Celkem po vydělení obou stran kongruence číslem ď (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 \ t — 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 G N, a G Z, (a,m) = 1. Označme r řád čísla a modulo
m.
(1) Pro libovolné ííGNU {0} platí
an = 1   (mod m) •<=>- r | n.
(2) r | </?(m) DŮKAZ.
(1) stačí v předchozí větě volit t = n, s = r.
(2) zřejmé z (1) díky Eulerově větě volbou n = íp(m).
□
Následující věta je zobecněním předchozího Lemmatu.
VĚTA 18. Nechť m,n G N, a G Z, (a, m) = 1. Je-Zž rad čYs/a a modulo m roven r G N, 7'e rad cYs/a an modulo m roven r^-r-
DŮKAZ. Protože       = [r, n], což je zřejmě násobek r, máme
(an)T^) = a[r'n] = 1 (modm)
(plyne z předchozího Důsledku, neboť r | [r,n]). Na druhou stranu, je-li k E N libovolné takové, že (an)k = an'k = 1 (mod m), dostáváme (r je řád a), že r | n ■ k a dále z Věty 5 plyne, že -r—r I • k a díky nesoudělnosti čísel -r—r a 7^ dostáváme 7J—r I k. Proto ie -r—r řádem čísla an modulo m. □
(n,r) 1 J (n,r)
Poslední z této řady tvrzení dává do souvislosti řády dvou čísel a řád jejich součinu:
Lemma. Nechť m g n, a, b g Z, (a, m) = (b, m) = 1. Jestliže a je řádu rab je řádu s modulo m, kde (r, s) = 1, pak číslo a - b je řádu r ■ s modulo m.
důkaz. Označme ô řád čísla a -b. Pak (ab)s = 1 (mod m) a umocněním obou stran kongruence dostaneme arSbrS = 1 (mod m). Protože je r řádem čísla a, je ar = 1 (mod m), tj. brS = 1 (mod m), a proto s | rč. Z nesoudělnosti ras plyne s I ô. Analogicky dostaneme i r | ô, a tedy (opět s využitím nesoudělnosti r, s) r ■ s I ô. Obráceně zřejmě platí (ab)rs = 1 (mod m), proto ô \ r s. Celkem tedy ô = rs. □
4. Řešení kongruencí o jedné neznámé
Definice. Nechť m e n, f(x),g(x) g Z[x\. Zápis
/(x) = g(x)   (mod m)
(17)
nazýváme kongruencí o jedné neznámé x a rozumíme jím úkol nalézt množinu řešení, tj. množinu všech takových čísel c G Z, pro která /(c) = g(c) (mod m).
Dvě kongruence o jedné neznámé nazveme ekvivalentní, mají-li stejnou množinu řešení.
Kongruence (17) je ekvivalentní s kongruencí f(x) — g{x) = 0 (mod m).
VĚTA 19. Nechť m G N, f (x) G Z[x]. Pro libovolná a,b G Z platí a = b   (mod m) ==^ f {a) = f {b)   (mod m).
DŮKAZ. Nechť je f {x) = cnxn + cn-ixn~ľ + • • - + CiX + cq, kde cq, c\, ..., cn G Z. Protože a = b (mod m), pro každé i = 1,2,... ,n platí podle Věty 12(2)
Ciď = CiU   (mod m),
a tedy sečtením těchto kongruencí pro i = 1,2,...,n a kongruence cq = cq (mod m) dostaneme
cnan + an_!an_1 + • • • + Ci<2 + c0 = cnbn + cn_!6n_1 + • • • + Ci& + c0   (mod m),
tj. f (a) = f (b) (mod m). □
DŮSLEDEK. Množina řešení libovolné kongruence modulo m je sjednocením některých zbytkových tříd modulo m.
Definice. Počtem řešení kongruence o jedné neznámé modulo m rozumíme počet zbytkových tříd modulo m obsahujících řešení této kongruence.
PŘÍKLAD.        (1) Kongruence 2x = 3 (mod 3) má jedno řešení (modulo 3).
(2) Kongruence lOx = 15 (mod 15) má pět řešení (modulo 15).
(3) Kongruence z příkladu (1) a (2) jsou ekvivalentní.
4.1. Lineární kongruence o jedné neznámé.
VĚTA 20. Nechť m G N, a, b G Z. Označme d = (a, m). Pak kongruence
ax = b   (mod m)
(o jedné neznámé x) má řešení pravé tehdy, když d \ b.
V případe, kdy d \ b, má tato kongruence pravé d řešení (modulo m).
DŮKAZ. Dokážeme nejprve, že uvedená podmínka je nutná. Je-li celé číslo c řešením této kongruence, pak nutně m \ a ■ c — b. Pokud přitom d = (a, m), pak protože d\mid\a-c — b & d \ a ■ c — {a ■ c — b) = b.
Obráceně dokážeme, že pokud d \ b, pak má daná kongruence právě d řešení modulo m. Označme a±, b\ G Z a ni\ G N tak, že a = d ■ a±, b = d ■ b\ a m = d ■ ni\. Řešená kongruence je tedy ekvivalentní s kongruencí
a\ ■ x = bi   (mod rrix),
kde (<2i,mi) = 1. Tuto kongruenci můžeme vynásobit číslem af^mi^ 1 a díky Eu-lerově větě obdržíme
x = bi ■ af^mi^ 1   (mod mi).
Tato kongruence má jediné řešení modulo ni\ a tedy d = m/mi řešení modulo m. □
Následující příklad ukáže, že postup uvedený v důkazu věty obvykle není tím nej efektivnějším - s výhodou lze použít jak Bezoutovu větu, tak ekvivalentní úpravy řešené kongruence.
PŘÍKLAD. Řešte 39x = 41 (mod 47)
řešení.        (1) Nejprve využijeme Eulerovu větu. Protože (39,47) = 1, platí
39^(47) = 3946 _ ľ   (mod 47);
tj-
3jT^_39^ = 394& • 41   (mod 47),
3946=1
z čehož už dostáváme
rr = 3945 - 41   (mod 47).
Úplné řešení vyžaduje ještě vypočtení zbytku po dělení čísla 3945 • 41 číslem 47, ale to již jistě laskavý čtenář zvládne sám a zjistí výsledek x = 36 (mod 47) (2) Další možností je využít Bezoutovu větu.
Euklidovým algoritmem pro vypočtení (39,47) dostáváme
47 = 1 • 39 + 8
39 = 4 • 8 + 7
8 = 1-7+1
Z čehož zpětným odvozením dostáváme
1 = 8- 7 = 8-(39 - 4-8) = 5- 8- 39 =
= 5 • (47 - 39) - 39 = 5 • 47 - 6 • 39.
Uvážíme-li tuto rovnost modulo 47, dostaneme
1 = -6 • 39   (mod 47)   / • 41
41 = 41 • (-6) -39   (mod 47)   / • 41
x = 41 • (-6)   (mod 47) x = -246   (mod 47) x = 36   (mod 47)
(3) Obvykle nejrychlejším, ale nejhůře algoritmizovatelným způsobem řešení je metoda takových úprav kongruence, které zachovávají množinu řešení.
39x = 41   (mod 47)
—8x = —6   (mod 47)
Ax = 3   (mod 47)
Ax = -AA   (mod 47)
x = —11   (mod 47)
x = 36   (mod 47)
□
Pomocí věty o řešitelnosti lineárních kongruencí lze dokázat mj. významnou Wilsonovu větu udávající nutnou (i postačující) podmínku prvočíselnosti. Takové podmínky jsou velmi významné ve výpočetní teorii čísel, kdy je třeba efektivně poznat, je-li dané velké číslo prvočíslem. Bohužel dosud není známo, jak rychle vypočítat modulární faktoriál velkého čísla, proto není v praxi Wilsonova věta k tomuto účelu používána.
VĚTA 21 (Wilsonova). Přirozené číslo n > 1 je prvočíslo, právě když
(n-l)! = -l   (mod n) (18)
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 = <i2, pak protože je n > 4, je i d > 2 a n | (d • 2d) | (n — 1)!. Pro n = 4 snadno dostáváme (4 — 1)! = 2^—1 (mod 4).
Nechť 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(p"3)/2 • (p-1) =-1 (modp).
□
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 20 rozhodnout o řešitelnosti 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 = q (mod rrii). Dostaneme tak soustavu kongruencí
x = c\   (mod ni\)
(19)
x
Ck   (mod nik)
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 22. Nechť c\, c2 jsou celá čísla, ni\, m2 přirozená. Označme d = (mi, m2). Soustava dvou kongruencí
x = ci (mod mi) x = c2   (mod rri2)
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 d). 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 x bude vyhovovat i druhé kongruenci soustavy (20), právě když bude platit c\ + tmi = c2 (mod m2), tj.
tmi = c2 — ci   (mod m2). Podle Věty 20 má tato kongruence (vzhledem k t) řešení, neboť d = (m1;m2) dělí c2 — Ci, a t G Z splňuje tuto kongruenci právě když
c2
ci /m1
tj. právě když
t
d
c2
mod — ,
a /
V d
Ci   ími^i—)-1 m2
d
V d )
d '
kde r G Z je libovolné. Dosazením
x
Ci + tmi = Ci
í m2 \
/miNW—)      mim2        ,      r , + (c2 - ci) •   — )        + r—-— = c + r • [mi, m2J
kde c = ci + (c2 — Ci) • [nii/d)^m2/d\ neboť m1m2 = d • [m1,m2]. Našli jsme tedy takové c G Z, že libovolné x G Z splňuje soustavu (20), právě když
x = 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 22 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 22 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). Nechi m1},... ,mk G N jsou po dvou nesoudělná, aí}... ,ak G Z. Pak platí: soustava
x = ai   (mod mi)
x = ak   (mod nik)
(21)
má jediné řešeni modulo ni\ ■     ■ ■ ■ nik-PŘÍKLAD. Řešte systém kongruencí
x = —3   (mod 49) x =   2   (mod 11).
ŘEŠENÍ. První kongruencí splňují právě všechna celá čísla x tvaru x -49£, kde t G Z. Dosazením do druhé kongruence dostáváme
-3 + 49í = 2 (modli),
odkud
5í = 5   (mod 11), tedy, vzhledem k (5,11) = 1, po vydělení pěti
t=l (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 x = 46 (mod 539).
PŘÍKLAD. Řešte systém kongruencí
x =   1   (mod 10)
x =   5   (mod 18)
x = —4   (mod 25).
539s, □
řešení. Z první kongruence dostáváme x = 1 + lOí pro í eZ. Dosazením do druhé kongruence získáme
1 + 10* = 5   (mod 18),
tedy lOí = 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 s G Z. Dosazením x = 1 + 10(4 + 9s) = 41 + 90s. 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)
18s = -9   (mod 5),
odkud — 2s = 1 (mod 5), tedy 2s = 4 (mod 5), s = 2 (mod 5), a proto s = 2 + 5r, kde r G 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) x = 25   (mod 73).
ŘEŠENÍ. Z první kongruence x = 18 + 25£, kde í G Z. Dosazením do druhé kongruence
18 + 25t = 21   (mod 45),
tedy
25í = 3   (mod 45).
Tato kongruence však podle Věty 20 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 22, neboť 18 ^ 21 (mod (25,45)). □
příklad. Řešte kongruenci 23 941x = 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 22 má kongruence řešení. Protože v?(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 12 (6) je x G Z řešením dané kongruence právě když je řešením soustavy
23941a; = 915   (mod 22)
23941a; = 915 (mod 34) (22) 23941a; = 915 (modli)
Vyřešíme nyní každou z kongruencí soustavy (22) zvlášť. První z nich je splněna, právě když
x = 3   (mod 4),
druhá, právě když
A6x = 24   (mod 81),
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 G Z je tedy řešením soustavy (22), právě když je řešením soustavy
x =   3   (mod 4)
x = -3 (mod 81) (23) x = —4   (mod 11)
Z druhé kongruence dostáváme, že x = —3 + 81í, kde £ G Z. Dosazením do třetí kongruence soustavy (23) dostaneme
-3 + 81í = -4 (modli),
tedy 81í = —1 (mod 11), tj. 4í = 32 (mod 11), odkud t = 8 (mod 11), a proto t = -3 + lls, kde s G Z. Dosazením x = -3 + 81(-3 + lis) = -3 - 3 • 81 + 11 • 81s do první kongruence soustavy (23) dostaneme
-3-3-81 +11-81s = 3   (mod 4),
tedy
1 + 1 • 1 + (-1) • ls = 3   (mod 4), tj. — s = 1 (mod 4) a proto s = — 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. Popíšeme si jednu sice pracnou, ale univerzální metodu řešení této kongruence, která je založena na následující větě.
TVRZENÍ 4.1. Pro libovolný mnohočlen F(x) s celočíselnými koeficienty, přirozené číslo m a celá čísla a, b taková, že a = b (mod m), platí F {a) = F(b) (mod m).
DŮKAZ. Nechť je F(x) = cnxn + cn-\xn~x + • • - + cix+cq, kde cq, Ci, ..., cn G Z. Protože a = b (mod m), pro každé i = 1,2,... ,n platí podle Věty 12(2)
a tedy sečtením těchto kongruencí pro i = 1,2,...,n a kongruence c0 = c0 (mod m) dostaneme
cnan + an_!an_1 + • • • + c^a + c0 = cnbn + cn_-\bn~x + • • • + c^b + c0   (mod m),
Při řešení kongruence (24) tedy 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"1 .. .p1^, kde p\, ..., pk jsou různá prvočísla, a je-li navíc k > 1, můžeme nahradit kongruenci (24) soustavou
□
kongruencí
F (x)
0   (mod p™1)
(25)
F (x)
0   (mod p%k),
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 x5 + 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) F(3) F(4)
33 = 0   (mod 11), 35 + 1 = 9 . 9 . 3 + 1
45 + 1 = 210 + 1 = 1
+
(-2)2 • 3 + 1 = 12 + 1 = 2 (modli) 1 = 2   (mod 11),
kde jsme využili Fermatovu větu 15, podle které 210 = 1 (mod 11). Podobně dále
F(5) =	55 +	1	= 165 + 1	= 410 + 1	= 1 + 1=2 (modli),
F(6) =	65 +	1	= (-5)5 +	1 = -165	+ 1 = -410 + 1 = 0 (modli
F{7) =	75 +	1	= (-4)5 +	1 = -210	+ 1 =-1 + 1 = 0 (modli),
F(8) =	85 +	1	_ 25 . 210 H	h 1 = 32 -f	-1=0 (modli),
F(9) =	95 +	1	= 310 + 1 E	= 1 + 1 =	2   (mod 11),
F(10) =	= 105	+	1 = (-1)5	+ 1=0	(mod 11),
a tedy řešením kongruence x5 + 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), x = 8 (mod 11), x = 10 (mod 11). □
příklad. Řešte kongruenci x3 — 3x + 5 = 0 (mod 105).
řešení. 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), F(l), ..., 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{1) = 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 iGZ splňující rr = 2 (mod 7) nebo x = —1 (mod 7). Zbývá tedy vyřešit dvě soustavy kongruencí:
x = 1   (mod 3), x =   1   (mod 3),
x = 0 (mod 5), a rr = 0 (mod 5), x = 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 = 5t pro í G Z, dosazením do první
5í = 1   (mod 3),
tedy — t = 1 (mod 3), odkud t = —1 + 3s pro s G Z, odkud rr = —5 + 15s. Dosaďme nejprve do třetí kongruence první soustavy:
-5 + 15s = 2   (mod 7),
odkud s = 0 (mod 7), tj. s = 7r pro r G Z a proto x = —5 + 105r. Dosadíme-li x = —5 + 15s do třetí kongruence druhé soustavy, dostaneme
—5 + 15s = —1   (mod 7),
odkud s = 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í modulo mocnina prvočísla udává důkaz následující
věty.
věta 23 (Henselovo lemma). Nechť p je prvočíslo, f(x) G Z[x], a G Z je takové, že p | f (a), p \ f (a). 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 x řešením (26) pro n, je řešením (26) i pro n — 1. Libovolné řešení (26) pro n je tedy tvaru
x = cn_i + k • pn_1,   kde A; G Z.
Je třeba zjistit, zda/(cn_!+A;-pn_1) =0 (mod pn). Víme, že pn_1 | /(cn_!+A;-pn_1) a užijme binomickou větu pro f(x) = amxm + • • • + aľx + a0, kde a0) • • •, am £ Z. Pak
(cn_! + fc • p^Y = én_x + i ■ é~\ ■ kpn-x   (mod pn).
Platí tedy
f(Cn^ + k ■ f1'1) = f(cn^) + k ■ p^V'ÍCn-l),
tj-
f{cn^ + k-pn-1) = 0   (mod p"
Q _ /(^_i) + k    /(cn_i}   (m }_
Protože cn_! = a (mod p), dostaneme /'(cn_i) = f'(a) ^ 0 (mod p), tedy (/'(cn_i),p) 1. Užitím Věty 20 o řešitelnosti lineárních kongruenci 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~ľ, je číslo cn_i + k ■ pn~ľ jediným řešením (26) modulo pn. □
příklad. Řešte kongruenci x4 + 7x + 4 = 0 (mod 27).
ŘEŠENÍ. Řešme nejprve tuto kongruenci modulo 3 (např. dosazením) - snadno zjistíme, že řešení je x = 1 (mod 3). Zapišme řešení ve tvaru x = 1 + 3t, kde í G Z
a řešme kongruenci modulo 9.
Zapsáním t
	x4 + 7x + 4 = 0   (mod 9)
(l + 3í)4 +	7(l + 3í)+4 = 0   (mod 9)
(l + 3í)4 +	7(l + 3t)+4 = 0   (mod 9)
1 + 4 • 3t +	7 + 7- 3í + 4 = 0   (mod 9)
	33t = -12   (mod 9)
	lit = -4   (mod 3)
	t = 1   (mod 3)
1 + 3s, kde s G Z dostaneme x = 4 + 9s a po dosazení	
(4 + 9s)4	■f 7(4 + 9s) + 4 = 0   (mod 27)
44 + 4 • 43 • 9s	+ 28 + 63s + 4 = 0   (mod 27)
256 • 9s + 63s = -288   (mod 27)	
	256s + 7s = -32   (mod 3)
	2s = 1   (mod 3)
	s = 2   (mod 3)
Celkem dostáváme řešení :r = 4 + 9s = 4 + 9(2 + 3r) = 22 + 27r, kde r G Z, neboli x = 22 (mod 27). □
Řešení obecných kongruenci vyššího stupně jsme tedy převedli na řešení kongruenci 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 4.1, 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 kongruenci 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 24. Buď p prvočíslo, f(x) G 7L\x\. Libovolná kongruence j(x) = 0 (mod p) je ekvivalentní s kongruenci stupně nejvýše p — 1.
věta 25. Buď p prvočíslo, f(x) G Z[rr]. Má-lí kongruence f(x) = 0 (mod p) více než st(/) řešení, pak jsou všechny koeficienty polynomu f násobkem p.
důsledek. (Jiný důkaz Wílsonovy 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) • • • (x - (p - 1)) - (x^-^ - 1) = 0   (mod p)
je podle Malé Fermatovy věty libovolné a g Z, které není násobkem p, tj. kon-gruence 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 kongruencí
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í kongruencí x\ = 2 (mod 7), která již splňuje omezení na nesoudělnost modulu a pravé strany kongruence. Podle Věty 25 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 x = 3 • x\ (mod 63), tj. x = ±9, ±12, ±30 (mod 63).
příklad. Řešte kongruenci
x3 = 3   (mod 18).
řešení. Protože je (3,18) = 3, nutně 3 | x. Užijeme-li, podobně jako výše, substituci dostáváme kongruenci
27x\ = 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)
ř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, O < xa < ip(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 < ip(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 < ip(m) je gx = gy (mod m). Podle Věty 17 pak x = y (mod ip(m)), tj. x = y. □
Později ukážeme, že primitivní kořeny existují "dostatečně často"na to, aby následující věta řešila všechny potřebné případy.
věta 26. Bud' m G N takové, že modulo m existují primitivní kořeny. Dále nechi a G Z, (a, m) = 1. Pak kongruence
kde d = (n, ip(m)).
Přitom, je-li tato kongruence řešitelná, má pravé d řešení.
důkaz. Nechť g je primitivní kořen modulo m. Pak podle předchozího Lemmatu existuje pro libovolné x nesoudělné s m jediné y G Z; 0 < y < ip(m) tak, že x = gy (mod m), podobně pro dané a existuje jediné b G Z; 0 < b < ip(m) tak, že a = gb (mod m). Řešená binomická kongruence je tedy po této substituci ekvivalentní s kongruenci
(gy)n = gb   (mod m)
a s využitím Věty 17 i s lineární kongruenci
n ■ y = b   (mod y?(m)).
Tato kongruence je řešitelná, právě když d = (n,íp(m)) \ b (a je-li řešitelná, pak má d řešení). Zbývá dokázat, že d \ 6, právě když a^m^d = 1 (mod m).
Kongruence 1 = a^m^d = gb^m)/d platí, právě když <p(m) \ bíp^; a to platí právě když d \ b. □
důsledek. Za předpokladů předchozí věty, je-li navíc (n, (p(m)) = 1, má kongruence xn = a (mod m) vždy řešení, a to jediné. Jinými slovy, umocňování na n-tou (kde n je nesoudělné s </?(m)) je bijekce na množině Z^ invertibilních zbytkových tříd modulo m.
důkaz. Zřejmý. □
Následující věty nám dávají obecnou informaci o počtu řešení kongruencí podle modulu, kterým je mocnina prvočísla. Jde o speciální případy Henselova lemmatu pro případ binomických kongruencí.
věta 27. Buď p prvočíslo, a g Z, n g N,p \ 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), kde f {x) = xn — a. Pak totiž f (x) = n-xn~ľ a pokud b g Z splňuje f (b) = 0 (mod p), pak jistě p \ 6, a proto p \ f (b).
□
věta 28. Buď n g H, o g Z, 2 { a. Označme dále l g No největší takové, že 2l | n. Je-li kongruence xn = a (mod 22í+1) řešitelná, je řešitelná i kongruence xn = a (mod 2a) pro libovolné a g N, a > 2/ + 1 a má stejný počet řešení 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 / = 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 kongru-encí 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 29. Buď m g 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 = A,
• 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ě </?(</?(m)). Je-li totiž g primitivní kořen a a E {1,2,..., íp(m)} libovolné, pak ga je podle Věty 18 řádu ^^(m))' co^ Je rovno ip(m) právě tehdy, je-li (a, y?(m)) = 1. Takových a je v množině {1,2,..., y?(m)} právě íp{íp{m)).
Důkaz Věty provedeme v několika krocích. Snadno je vidět, že primitivní kořen modulo 2 je 1 a modulo 4 je 3. Dále ukážeme, že primitivní kořeny existují modulo libovolné liché prvočíslo (pro ty, kdo si pamatují základy algebry, tak vlastně jiným způsobem dokážeme, že grupa (Z^, •) invertibilních zbytkových tříd modulo prvočíselné m je cyklická.
TVRZENÍ 4.2. Nechť p je liché prvočíslo. Pak existují primitivní kořeny modulo
p.
DŮKAZ. Označme r±,r2,..., rp_i řády čísel 1, 2,... ,p — 1 modulo p. Buď ô = [r1; r2,..., rp_i] nejmenší společný násobek těchto řádů. Ukážeme, že mezi čisly 1, 2,... ,p — 1 existuje číslo řádu ô a že ô = p — 1.
Nechť ô = g"1 • • • q^h je rozklad ô na prvočísla. Pro libovolné s G {1,... k} existuje c G — 1} tak, že g"s | rc (jinak by existoval menší společný
násobek čísel r±,r2,... ,tp-i než je ô), tj. ex. b G Z tak, že rc = b ■ qfs. Protože c má řád rc, má číslo gs := cb podle Věty 18 řád qfs.
Provedením předchozí úvahy pro libovolné s G {1,... k} dostaneme gi,... ,gk a můžeme položit g := g\ ■ ■ • g^. Podle Lemmatu za Větou 18 dostáváme, že řád g je roven součinu řádů čísel g1}..., g^, tj. číslu g"1 • • • q^k = ô.
Nyní dokážeme, že ô = p— 1. Protože řády čísel 1,2,... ,p— 1 dělí ô, dostáváme pro libovolné x G {1,2,... ,p — 1} vztah xs = 1 (mod p). Kongruence stupně 5 modulo p má podle Věty 25 nejvýše ô řešení (a podle předchozího máp — 1 řešení), proto nutně ô > p—1. Přitom ô \ p— 1 (jakožto řád čísla g), proto zejména ô < p—1, a celkem ô = 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í (1 + ap)pl~2 = 1 + apl~ľ   (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 / + 1. S využitím Lemmatu na str. 39 tak umocněním na p-tou tvrzení pro / (s navýšením modulu) dostaneme
(1 + apf'1 = (1 + ap1-1)1'   (mod pl+1). Z binomické věty přitom plyne
(1 + apř-y = 1 + p ■ a ■ p1'1 + ]T (A akp^k
k=2 ^ '
a vzhledem k tomu, že pro 1 < k < p platí p \ (^), stačí ukázat pl+1 \ p1+(l-1)k^ což je ekvivalentní s 1 < (k — 1)(/ — 1). Rovněž pro k = p dostáváme díky / > 3 vztah pl+1 | p(ř_1)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~ľ.
DŮKAZ. Podle předchozího Lemmatu je
(1 + apf1'1 = l + apl   (mod pl+1),
a uvážíme-li tuto kongruenci modulo pl, dostaneme (1 + ap)pl 1 = 1 (mod pl). 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.3. 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 gp~ľ ^ 1 (mod p2), je g dokonce primitivním kořenem modulo pl pro libovolné / G N. (Pokud by platilo gp~ľ = 1 (mod p2), pak {g + p)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 + p.)
Nechť tedy g splňuje gp~ľ ^ 1 (mod p2). Pak existuje a G Z, p \ a tak, že gP-i = \ -\- p . a% Ukážeme, že g je modulo pl řádu ip{pl) = (p — l)p'_1. Buď n G N nej menší číslo, splňující gn = 1 (mod př). Podle předchozího Lemmatu je gP-i _ i    p . a jádu pí_1 modulo pl. Pak ale
(pP-1)" = (gn)p-1 = 1   (mod př) =^ p'"1 | n.
Zároveň z gn = 1 (mod p) plyne p— 1 | n. Protože jsou čísla p— 1 a pí_1 nesoudělná, dostáváme (p — l)p'_1 | n. Proto n = ip{pl) a g je tedy primitivní kořen modulo př. □
tvrzení 4.4. 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 = 1 (mod pl), právě když cn = 1 (mod 2pl). Protože tp(2pl) = tp(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 52i~3 = 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.5. Nechi l G n. Primitivní kořeny existují modulo 2l pravé tehdy, když l < 2.
důkaz. Buď / > 3. Pak množina
S = {(-l)a ■ 56; a G {0,1}, 0 < b < 2ř~2; b G Z}
tvoří redukovanou soustavu zbytků modulo 2l (má totiž tp(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í 2ř~2, proto v této (a tedy ani v žádné jiné) redukované soustavě nemůže existovat
Posledním kamínkem do mozaiky tvrzení, která společně dokazují Větu 29 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.6. 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 No,Qíj G N, 2 \ pi a buď platí k > 2 nebo k > 1 a a > 2. Označíme-li ô = [p(2a), ^(p^1),(p(p° | pak se snadno vidí, že ô < tp(2a) • ^{Pi1) ''' VÍPí1) = f(,m) a ze Pro libovolné a G Z, (a,m) = 1 platí a5 = 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 30. Buď m takové, že modulo m existují primitivní kořeny. Zapišme ip(m) = g"1 • • • q^h. Pak pro libovolné g g Z, (g, m) = 1 platí, že g je primitivní kořen modulo m, právě když
g n   ^1   (mod m),..., g qk   ^ 1   (mod m).
důkaz. Pokud by platila některá z uvedených kongruenci, znamenalo by to, že řád g je menší než ip(m).
Obráceně, pokud g není primitivní kořen, pak existuje d g N, d \ </?(m), kde d < ip{m) a gd = 1 (mod m). Je-li u = ^^j— > 1, nutně existuje i g {1,..., k} tak, že q,i \ u. Pak ale
g ii   = g n = 1   (mod m).
□
příklad. Postupně určíme primitivní kořeny modulo 41,412 a 2 • 412.
Řešení. Protože y?(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 g8 =É 1   (mod 41).
9 = 2:
g = 3 g = A g = 5
9 = 6:
28 = 25 • 23 = -9 • 8 = 10   (mod 41)
220 = (25)4 _ (_g)4 = 812 _ (_-Q2 = (mod ^
38 = (34)2 = (-1)2 = 1   (mod 41) řád 4 = 22 vždy dělí řád 2
í 16
(2
8\2
10'
2
=20 - (52)10 = (-24)10 = 240 = (220)2 = 1   (mod 41
(mod 41)
58 = (52)4 = (-24)4 52o = (52)io _ (_24)xu = r
68 = 28 • 38 = 10 • 1 = 10   (mod 41)
620 = 220 . 32O _ 220 . (38)2 .^=l.l. = _X     (mod ^
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ě v?(40) = tp(23 ■ 5) = 16 a jsou jimi mezi tyto zbytky modulo 41: ±6, ±7, ±11, ±12, ±13, ±15, ±17, ±19.
Dokážeme-li nyní, že 640 ^ 1 (mod 412), budeme vědět, že 6 je i primitivním kořenem modulo libovolná mocnina 41 (pokud bychom "měli smůlu"a 640 = 1 (mod 412), pak by primitivním kořenem modulo 412 bylo číslo 47 = 6 ± 41).
Při ověření podmínky si vypomůžeme několika triky (tzv. modulární reprezentace čísel), abychom se obešli bez manipulace s velkými čísly.
Nejprve vypočtěme zbytek po dělení 68 číslem 412; k tomu se nám bude hodit vypočítat zbytek po dělení čísel 28 a 38:
28 = 256 = 6 • 41 + 10
38 = (34)2 = (2 • 41 - l)2 = -4 • 41 + 1   (mod 412) Pak 68 = 28 • 38 = (6 • 41 + 10)(-4 • 41 + 1) =
= -34-41 + 10 = 7-41 + 10 (mod412) a 640 = (68)5 = (7 • 41 + 10)5 = (105 + 5 • 7 • 41 • 104) = = 104(10 + 35 • 41) = (-2 • 41 - 4)(-6 • 41 + 10) = = (4-41 - 40) = 124    1 (mod412).
Přitom jsme využili toho, že 104 = 6-412-86, tj. 104 = -2-41-4 (mod 412).
Je tedy 6 primitivním kořenem modulo 412 a protože je to sudé číslo, je primitivním kořenem modulo 2 • 412 číslo 1687 = 6 + 412 (nejmenším kladným primitivním kořenem modulo 2 • 412 je přitom číslo 7).
4.6. Kvadratické kongruence a Legendreův symbol. Naším úkolem bude najít jednodušší podmínku, jak zjistit, jestli je řešitelná (a případně, kolik má řešení) kvadratická kongruence
Z obecné teorie, uvedené v předchozích odstavcích, je snadné vidět, že k rozhodnutí, je-li tato kongruence řešitelná, stačí určit, je-li řešitelná (binomická) kongruence
kde p je liché prvočíslo a a číslo s ním nesoudělné.
Pro určení řešitelnosti kongruence (27) můžeme samozřejmě využít Větu 26, její využití ale často naráží na výpočetní složitost, proto se v kvadratickém případě snažíme najít kritérium jednodušší na výpočet.
příklad. Určete počet řešení kongruence x2 = 219 (mod 383).
řešení. Protože 383 je prvočíslo a (2,^(383)) = 2, z Věty 26 plyne, že daná kongruence je řešitelná (a má 2 řešení), právě tehdy, když 219~ = 219191 = 1 (mod 383). Ověření platnosti není bez použití výpočetní techniky snadné (i když je to pořád ještě "na papíře"vyčíslitelné). Závěrem této části tuto podmínku ověříme s pomocí Legendreova symbolu daleko snadněji.
x2 = a   (mod p)
(27)
Definice. Nechť je p liché prvočíslo. Legendreův symbol definujeme předpisem
1     p \ a, a je kvadratický zbytek modulo p, 0     p | a,
— 1   p \ a, a je kvadratický nezbytek modulo p.
PŘÍKLAD. Protože je kongruence x2 = 1 (mod p) řešitelná pro libovolné liché prvočíslo p, je (1/p) = 1.
(—1/5) = 1, protože kongruence = —1 (mod 5) je ekvivalentní s kongruencí x2 = 4 (mod 5), jejímiž řešeními jsou x = ±2 (mod 5).
Lemma. Nechi p je liché prvočíslo, a, b g Z libovolná. Pak platí: 1. (-) =        (mod p).
důkaz, ad 1. Pro p | a je tvrzení zřejmé; pokud je a kvadratický zbytek modulo p, pak tvrzení plyne z Věty 26. Z téže věty plyne, že v případě kvadratického nezbytku je ^ 1 (mod p). Pak ale, protože p \ ď^1 — 1 = (a^- — l)^^ + 1) nutně p | a~ + 1, tj. a~ = — 1 (mod p).
3. a
b (mod p)
ad 2. Podle 1. dostáváme
g) -
a 2  . 5 2
( — ] ( - ] (mod p) \pj \pj
Protože jsou hodnoty Legendreova symbolu z množiny { — 1, 0,1}, plyne z kongru-ence (ab/p) = (a/p)(b/p) (mod p) přímo rovnost.
důsledek. 1. V libovolné redukované soustavě zbytků modulo p je stejný počet kvadratických zbytků a nezbytků.
2. Součin dvou kvadratických zbytků je zbytek, součin dvou nezbytků je zbytek, součin zbytku a nezbytků je nezbytek.
3. (—1/p) = (—1)^, tj. kongruence x2 = —1 (mod p) je řešitelná právě tehdy, když p = 1 (mod 4).
důkaz, ad 1. Kvadratické zbytky získáme tak, že všechny prvky redukované soustavy zbytků umocníme na druhou. Těchto prvků je p — 1, přitom druhé mocniny 2 prvků jsou spolu kongruentní právě tehdy, když je součet těchto prvků násobkem p. Máme tedy právě kvadratických zbytků, a tedy rovněž p — 1 — P-^- = ^2^- kvadratických nezbytků modulo p. Předpoklad, že p je prvočíslo, je podstatný - pro složená čísla je kvadratických nezbytků více než zbytků (viz dále část o Jacobiho symbolu).
ad 2. Tvrzení je zřejmé z předchozího lemmatu.
ad 3. Zřejmé z definice.
□
ad 3. Zřejmé. □
Již s využitím těchto základních tvrzení o hodnotách Legendreova symbolu jsme schopni dokázat větu o nekonečnosti počtu prvočísel tvaru Ak + 1.
tvrzení 4.7. Prvočísel tvaru Ak + 1 je nekonečně mnoho.
důkaz. Sporem. Předpokládejme, že p1} p2,..., p\ jsou všechna prvočísla tvaru Ak + 1 & uvažme číslo N = (2pi • • • pi)2 + 1. Toto číslo je opět tvaru Ak + 1. Pokud je N prvočíslo, jsme hotovi (protože je jistě větší než kterékoli z p±, p2,..., pi), pokud je složené, musí existovat prvočíslo p, dělící N. Zřejmě přitom žádné z prvočísel 2,pi,p2, ■ ■ ■ ,Pi není dělitelem N, proto stačí dokázat, že p je rovněž tvaru Ak + 1. Protože ale (2pi ■ ■ - pí)2 = — 1 (mod p), dostáváme, že (—1/p) = 1, a to platí právě tehdy, je-li p = 1 (mod 4). □
Nyní odvodíme další pravidla pro výpočet Legendreova symbolu.
Uvažujme množinu S nej menších zbytků (v absolutní hodnotě) modulo p. Je-li p prvočíslo, a G Z, p \ a, pak označíme up(a) počet záporných nejmenších zbytků (v absolutní hodnotě) čísel
p — 1
1 • a, 2 • a,..., —-— • a,
tj. pro každé z těchto čísel určíme, se kterým číslem z množiny S je kongruentní a spočítáme počet záporných z nich.
poznámka. Obvykle budou p a, a zafixované, potom budeme místo fip(a) psát jen ii.
příklad. Vypočtěte hodnotu fi pro p = 11, a = 3.
řešení. S = {-5,-4,-3,-2,-1,1,2,3,4,5}. Protože 1 • 3 = 3, 2 • 3 = -5,3 • 3 = —2,4-3 = 1,5-3 = 4 (mod 11), dostáváme fi = 2.
Lemma (Gaussovo). Je-li p prvočíslo, a G Z, p \ a, pak
důkaz. Pro každé i G {1,2,... určíme m, G {1,2,... ,2^} tak, že
i ■ a = ±m,i (mod p). Snadno se vidí, že pokud k, l G {1,2,..., jsou různá, jsou různé i hodnoty nik, mi (nik = mi =^ k ■ a = ±1 ■ a (mod p) ==^ k = ±/ (mod p), což nelze jinak, než že k = /).
Proto splývají množiny {1,2,...,        a {mi,rri2,..., rrip^i}. Vynásobením
kongruencí
1 • a = itííi   (mod p)
2 ■ a = ±m2   (mod p)
p — 1
a = ±mp^i    (mod p)
dostáváme
P_1'   -^-(-l)^.^Í! (modp)
-! • a 2
2 v    7 2
(mezi pravými stranami je jich právě fi záporných). Po vydělení obou stran číslem ((p — l)/2)! dostáváme vzhledem k tomu, že
a'°2     (mod p)
tvrzení.
□
S využitím Gaussova lemmatu dokážeme hlavní větu této části, tzv. zákon kvadratické reciprocity.
věta 31. Necht p, q jsou lichá prvočísla. Pak
(f) = (-D2*1 *1) = (?) ■ (-D*^
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 (ajp) 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 E Z, p \ a, k E N a nechť [x] (resp. (x)) značí celou (resp. necelou) část reálného čísla x. Pak
~2ak~			ak	„ / ak\		ak		„ / ak\
	=	2		+ 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 ne-jmenší 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
Q =(-ir = (-i)^S^i.
Je-li navíc a liché, je a + p číslo sudé a dostáváme
/2a\ = /2a + 2p\ = /^JA = /2\2 =
\P/        V      ř*      /        V   P   /        W \P/
= (_!)££[^1 = (_i)ESľ[f 1 . (_i)£2r*. Celkem tak dostáváme (pro liché a)
©■(^(-1)eS*-(-D^. P8)
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)£&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\
^2^- •      a ukážeme, že rovněž
(_l)ľr| = (_i)ESlf 1 . (_!)ESlf ];
(29)
čímž budeme vzhledem k předchozímu hotovi.
Protože pro žádná 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 H {[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 -y <
qv qv — q
2    ^ 2 ' J
ty dvojice [qx,py], pro které 1 < x < [|?/], a tedy |T]
< ^2^"- Pro pevné y tedy v T\ leží právě Eti1)/2[^]- Analogicky
Eti1)/2^]-
Proto (2) dokázán.
(—l)'Tl' a (-)  = (—1)'T2' a zákon kvadratické reciprocity je
□
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).
Home Page
3. Je-li p = 1 (mod 4) nebo q = 1 (mod 4), je (p/q) = (q/p), jinak (tj. p q = 3 (mod 4)) je (p/q) = —{q/p)-
příklad. Určete (j§^).
Řešení.
/79
-
Vioi
101
"79"
22
79
11
79/   V 79
11 79
(-1)
(-1)
11
neboi 101 dává po dělení 4 zbytek 1
neboí 79 dává pod dělení 8 zbytek -1 neboi 11 i 79 dávají pod dělení 4 zbytek 3 neboi 11 dává pod dělení 8 zbytek 3
Page 100 of 149
Full Screen
Quit
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 e Z, b e N, 2 \ b. Nechť b = p\P2---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).
(D-O-<-'>■<-'>-'
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)).
Tvrzení 4.8. Nechť b, b' G N jsou lichá, G Z libovolná. Pak platí:
1. ai = a2 (mod 6) =^ (f) = (f).
(^) = (f)(f)-5- (&) = (!)(*)■
LEMMA. Buďte a, b G N /zc/za. PaÄ; p/aü'
ab-l _ 2 -
a262-l
q-1   i b-1 2 2 . a2-l   , b2-l
^ +       (mod 2).
(mod 2).
8      —    8     1 8
Důsledek. Pro G N /zc/za p/aŕí"
1- Eľ=i ^ = nľ^2fflfc'1 (mod 2).
2. Eľ^^11^ (mod2)-
VĚTA 32. Nechť a, b G N json /zc/za. PaÄ: 1- (Ť) = (-1)^ (I) = (-1)^
*(!)® = (-i)"
DŮKAZ. Snadný.
□
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.
219
383
383 219 164 219 41 219 219
ir
41)
41) V41 7_ 41 41
T
(Jacobí) 383 i 219 dávají po dělení 4 zbytek 3
164 = 22 • 41
(Jacobí) 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 neboť 7 dává po dělení 4 zbytek 3.
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 33. 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 = ±b2 (mod Aq), 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) = (—^^(p/q). Nechť nejprve p = +b2 (mod Aq), kde b je liché. Pak p = b2 = 1 (mod 4) a p = b2 (mod q). Tedy (—l)^ = 1 a (p/q) = 1, odkud (q/p) = 1. Je-li nyní p = —b2 (mod Aq), pak obdobně p = —b2 = 3 (mod 4) a p = —b2 (mod q). Tedy (—1)^ = — 1 a (p/q) = —1, odkud opět (q/p) = 1.
Obráceně, mějme (q/p) = 1. Máme dvě možnosti - buď = 1 a (p/q) =
1, nebo (—l)" = — 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 Aq). V druhém případě je p = 3 (mod 4) a existuje b liché tak, že p = —b2 (mod q). Tedy —b2 = 3=p (mod 4) a celkem p = —b2 (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.9. Nechi p = 3 (mod 4), a G Z splňuji (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]).
5. 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 sed-militrové nádoby odměřit do třetí nádoby osm litrů vody, která vede na rovnici 5x + 7y = 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 lOpuM MaTHAceBira (Yuri Matiasevič) v roce 1970 (viz elementárně psaný text [1]).
Přesto však uvedeme několik nejobvyklejších metod, které v řadě konkrétních případů povedou k výsledku.
5.1. Lineární diofantické rovnice.
a\x\ + a2x2 + • • • + CLnxn = b, (30)
kde xi,..., xn jsou neznámé, a1;..., an, b daná celá čísla. Budeme předpokládat, že <2j ý 0 Pro každé i = 1,... ,n (je-li a,i = 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 d = (ai,..., an), nemůže mít (30) žádné řešení, protože pro libovolná celá čísla xi,...,xn je levá strana (30) dělitelná číslem d. Jestliže naopak d \ b, můžeme celou rovnici (30) vydělit číslem d. Dostaneme tak ekvivalentní rovnici
a[xi + a'2x2 + • • • + a'nxn = b',
kde a\ = a^jd pro i = 1,..., n a b' = b/d. Přitom platí
d ■ (a'ľ,..., a'n) = (da'ľ,..., da'n) = (a±,..., an) = d,
a tedy (a[,... ,a'n) = 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 a1; a2,..., a,
VĚTA 35. Nechť n > 2. Rovníce
d\x\ + 02^2 + ' ' • + o,nxn = b, (31)
kde ai, a2,..., an, b jsou celá čísla taková, že (a1;..., an) = 1, má vždy celočíselné řešení. Všechna celočíselná řešení této rovníce je možné popsat pomocí n — 1 celočíselných parametrů.
DŮKAZ. Provedeme indukcí vzhledem k počtu n neznámých x i v rovnici (31).
Je výhodné formálně začít s případem n = 1, kdy podmínka (ai) = 1 znamená, že a\ = ±1. Tehdy rovnice (31) má tvar buď x\ = 6, nebo —x\ = 6, a tedy jediné řešení, které zřejmě nezávisí na žádném parametru, což odpovídá tomu, že n - 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 = (a1;... ,an_i). Pak libovolné řešení x1}... ,xn rovnice (31) triviálně splňuje kongruenci
diXi + 02^2 + • • • + CLnxn = 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 20 tato kongruence řešení
xn = c   (mod d),
kde c je vhodné celé číslo, neboli xn = c + d ■ t, kde í G Z je libovolné. Dosazením do (31) a úpravou dostaneme
CLlXi ~\~ ' ' ' ~\~ Q"n—l*En—l ~ b — 0/nC — dridt.
Protože anc = b (mod d), je číslo (6 — anc)/d celé a poslední rovnici můžeme vydělit číslem d. Dostaneme pak rovnici
a[x1 H-----h a^_i^n-i = b',
kde a'i = a^jd pro i = 1,... ,n — 1 a 6' = ((& — anc)/d) — ant. Protože
K, • • •, an-i) = (daí, • • • > dť4-i) • \ =      • • •' a™-!) ' 5 = X' podle indukčního předpokladu má tato rovnice pro libovolné t G Z řešení pop-satelné pomocí n—2 celočíselných parametrů. Přidáme-li k tomuto řešení podmínku %n = 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 35 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 xi, x2, x3,....
příklad. 5x + 7y = 8.
řešení. Libovolné řešení této rovnice musí splňovat kongruenci
5x + 7y = 8   (mod 5),
tedy 2y = —2 (mod 5)), odkud y = — 1 (mod 5)), tj. y = —1 + 5í pro t G Z. Dosazením do dané rovnice dostaneme
5x + 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 t je libovolné celé číslo. □ příklad. 91a: - 28y = 35.
řešení. Protože (91,28) = 7 a 7 | 35, má rovnice celočíselné řešení. Vydělme ji sedmi:
13a; — Ay = 5.
Libovolné řešení této rovnice musí splňovat kongruenci
13a; — Ay = 5   (mod 13),
tj. —Ay = —8 (mod 13), odkud y = 2 (mod 13) a y = 2+13Í pro í eZ. Dosazením
13a; - 4(2 + 13í) = 5,
odkud vypočteme x = 1 + At. Řešením je tedy x = 1 + 4í, y = 2 + 13t, kde t 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. 18a; + 20y + 152 = 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 největší společný dělitel čísel 18, 20)
18x + 20y + 152 = 1   (mod 2), tedy z = 1 (mod 2), odkud z = 1 + 2s, kde s G Z. Dosazením
18x + 20í/+ 15(1 + 2s) = 1 odkud po vydělení dvěma a úpravě dostaneme rovnici,
9x + 10y = -7- 15s kterou budeme řešit pro libovolné s G Z. Je-li tato rovnice splněna, musí platit
9x + 10y = -7 - 15s   (mod 9), odkud y = 2 + 3s (mod 9), a proto y = 2 + 3s + 9t, kde t G Z. Dosazením
9x + 10(2 + 3s + 9í) = -7 - 15s, odkud po úpravě x = —3 — 5s — lOt. Řešení dané rovnice jsou tedy trojice
x = —3 — 5s — 10í y = 2 + 3s + 9t z = l + 2s
kde s, t jsou libovolná celá čísla. □
PŘÍKLAD. 15x - 12y + A8z - biu = 1.
ŘEŠENÍ. Protože (15,12,48, 51) = 3 není dělitel čísla 1, nemá rovnice celočíselné
5.2. Diofantické rovnice lineární vzhledem k některé neznámé. Jde o rovnice, které můžeme upravit do tvaru
kde m je přirozené číslo a F(x1}..., rrn_i) mnohočlen s celočíselnými koeficienty. Je zřejmé, že má-li být x1} x2,... ,xn celočíselným řešením rovnice (32), musí platit
Naopak, je-li x1}..., xn_\ řešení kongruence (33), pak pro xn = F(x1}..., xn_i)/m dostaneme celočíselné řešení x±,..., xn-i,xn rovnice (32). Proto pro řešení rovnice (32) postačí vyřešit kongruenci (33). V případě n = 2, tj. v případě, kdy je mnohočlen F(xi) 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 36. Pro libovolný mnohočlen F(x1}..., xs) s celočíselnými koeficienty, přirozené číslo m a celá čísla a±,..., as, bi,..., bs taková, že a\ = b\ (mod m), . . ., as = bs (mod m), platí F(ai,..., as) = F(pi,..., bs) (mod m).
resem.
□
(32)
(33)
důkaz. Snadný.
□
Pro nalezení všech řešení kongruence (33) tedy postačí dosazovat do mnohočlenu F(xi,..., xn-i) zaxi,..., 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 a1,...,an_1 je splněna podmínka F(a1}..., an_i) =   (mod m), dostáváme řešení kongruence (33) ve tvaru
kde ti,... ,tn_i mohou nabývat libovolných celočíselných hodnot. Tak dostaneme i řešení rovnice (32):
xi = ai + mti
xn-i = an-i + mt
n— 11
•En—l      ^n—1 + mín_ i, 1
xn = —F(ai + míi, • • •
an_i + mín_i).
m
příklad. Řešte diofantickou rovnici 7x2
+ 5y + 13 = 0.
Řešení. Rovnici upravíme na tvar 5y = —7x2 — 1
-7x2 - 13 = 0   (mod 5)
13 a budeme řešit kongruenci
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 kde t G Z. Dosazením dostaneme v prvním případě
5í,
5y = -7(1 + 5t)s
13
-7 - 70í - 175í2
13
a tedy
-4 - Ut - 35ť
ve druhém případě % =
a proto
-7(4 + 5ťT
13
-112 - 280í - 175ť - 13,
y = -25 - 56í - 35í2. Řešením dané rovnice jsou tedy právě všechny dvojice čísel x,y tvaru
x = l + 5t,y = -4- 14Í-35Í2 nebo x = 4 + 5í,y = -25 - 56í kde í je libovolné celé číslo.
příklad. Řešte diofantickou rovnici x(x + 3) = Ay — 1.
35ť,
□
řešení. Rovnici upravíme na tvar Ay = x2 + 3x+ 1 a budeme řešit kongruenci
x2 + 3x + 1 = 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 = -x2 -6x-Az2-8z + l
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 = x + 3, b = 2z + 2 dostaneme, že z kongruence (34) plyne
x + 3 = 2^ + 2 = 0   (mod 7),
a tedy všechna řešení kongruence (34) jsou tvaru
x = — 3 + 7t,      z = — 1 + 7s, kde t, s jsou celá čísla. Dosazením do rovnice dostaneme
7y
-(x + 3)2 - (2z + 2)2 + 14
-49r - 196s2 + 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 -kde s,t jsou libovolná celá čísla.
-7ť - 28s2
7s,
□
5.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 xn, dostaneme
F{x\^ • • • , l)
xtl
m
což je celé číslo, právě když m \ F(x\,..., rrn_i), tj. právě když je splněna kongruence (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 3X = 4y + 5.
řešení. Vyjádřeme z této rovnice neznámou y:
y = \(Sx-5).
Je-li x < 0, je 0 < 3X < 1, a tedy \(3X - 5) i Z. Pro x > 0 platí
3x-5 = (-l)x-l   (mod 4);
číslo (—l)x — 1 je kongruentní s nulou podle modulu 4 právě tehdy, když x je sudé, tj. x = 2k, kde k G No- Řešením této diofantické rovnice jsou tedy právě všechny dvojice
9k - 5
y =
x — 2 k.
4
kde k G No je libovolné.
příklad. Řešte v Z rovnici x(y + l)2 = 243y. Řešení. Vyjádřeme neznámou x:
2A3y
□
x
12 •
Aby x G Z, musí (y + 1)2 být dělitelem čísla 243y. Protože y a jsou nesoudělná čísla pro libovolné y G Z, musí být (y + 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, y + 1 = ±3 nebo y + 1 = ±9. Dostáváme tedy šest řešení dané rovnice:
y = 0, x = 0,
y = -2, x = -2 • 243 = -486,
y = 2, x = 2 ■ 27 = 54,
y = -4, x =-4-27 =-108,
y = 8, x = 8 • 3 = 24,
y = -10, x =-10 • 3 =-30.
Jiná řešení daná diofantická rovnice nemá. □ příklad. Řešte v N rovnici ^fx + ^fy = ^1988 .
řešení. Odečteme-li od obou stran rovnice ^fy a umocníme-li na druhou, dostaneme
x = 1988 - Ay/7- 71 -y + y.
Jsou-li x, y celá čísla, je i 4^/7 • 71y celé číslo, a tedy ^/7 • 71y je racionálni číslo. Pak je ^/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 ■ 71t pro vhodné í G No tedy
y
7-71
497í2.
Zcela analogicky je možné odvodit, že existuje s G N0 tak, že
x = 497s2.
Dosazením do původní rovnice dostáváme
VÄ97s + VÄ97t = V1988,
odkud po vydělení plyne s + í = 2. Jsou tedy tři možnosti: s = 0, í = 2 nebo s = í = 1 nebo s = 2, í = 0, takže daná diofantická rovnice má tři řešení:
x = 0,   y = 1988   nebo   x = y = 497   nebo   x = 1988,   y = 0.
□
5.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 + 5y2 = 74.
řešení. Protože pro libovolné y g Z platí 5y2 > 0, musí libovolné řešení x,y dané rovnice splňovat
74 = 6x2 + hy2 > 6x2,
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, 5y2 = 68, 5y2 = 50, 5í/2 = 20. První tři případy jsou ve sporu s y g Z, z posledního dostáváme y2 = A, t], y = ±2. Rovnice má tedy čtyři řešení: x = 3, y = 2; x = 3, y = —2; x = —3, y = 2; x = -3, y = -2. □
příklad. Řešte v Z rovnici x2 + rry + 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 < y2 + y2 + y2 = 3y2.
Platí tedy y = 0 nebo x2 < 3. Dosazením do rovnice dostáváme v prvním případě x = 0, ve druhém pro x = 0 opět y = 0, pro x = 1 je ?/ = -1 a pro x = — 1 je y = 1. Rovnice má tedy tři řešení:
x = 0,    y = 0;       x = 1,    y = —1;       x = —1,    y = 1.
□
PŘÍKLAD. Řešte v Z rovnici 2X = 1 + 3y.
Řešení. Je-li y < 0, platí 1 < 1 + 3^ < 2, odkud 0 < x < 1, což je spor. Je tedy y > 0 a proto 2X = 1 + 3^ > 2, odkud rr > 1. Ukážeme, že také platí x < 2. Kdyby totiž bylo x > 3, platilo by
l + 3*/ = 2a: = 0   (mod 8),
odkud bychom dostali
3y = -l   (mod 8),
což však není možné, neboť pro sudá čísla y je 3y = 1 (mod 8) a pro lichá čísla y platí 3^ = 3 (mod 8). Zbývá tedy vyřešit případ 1 < x < 2. Pro x = 1 dostáváme
3y = 21 - 1 = 1,
a tedy i/ = 0. Zi = 2 plyne
3^ = 22 - 1 = 3,
takže y = 1. Rovnice má tedy dvě řešení: x=l,y = 0ax = 2,y = l. □
PŘÍKLAD. Řešte rovnici x + y + z = xyz 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 xy < 3. Je tedy xy = 1, nebo xy = 2, nebo xy = 3.
Je-li xy = 1, platí x = 1, y = 1, odkud dostaneme dosazením do rovnice 2 + 2 = 2, což není možné.
Je-li xy = 2, platí x = 1, y = 2 (předpokládáme x < y), odkud 3 + 2 = 22, a tedy 2 = 3.
Je-li xy = 3, platí x = 1, y = 3, odkud 4 + z = 3z, tedy 2 = 2, což je ve sporu s předpokladem y < z.
Rovnice má tedy jediné řešení x = 1, y = 2, 2 = 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 < ď1 < (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 + 8x)(x2 + 8x + 7). Označíme-li x2 + 8x = z, je naše rovnice tvaru
y2 = z2 + 7 z.
Ukážeme, že z < 9. Předpokládejme naopak z > 9. Pak platí
(z + 3)2 = z2 + 6^ + 9 < z2 + 7z = y2 < z2 + 8^ + 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| < |y| < |z + 4|.
Je tedy 2 < 9, tj. x2 + 8x < 9, odkud
(x + 4)2 =     + 8x + 16 < 25,
a proto —5 < x + 4 < 5, neboli —9 < x < 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 = 8X3 + 2Ax2 + 32x + 16 = 8(x3 + 3x2 + Ax + 2),
odkud plyne, že y je sudé. Položme y = 2z, z G Z. Platí tedy
z3 = x3 + 3a:2 + Ax + 2.
Je-li x > 0, platí
(z + l)3 = x3 + 3x2 + 3x+ 1 < x3 + 3x2 + Ax+ 2 =
= z3 < x3 + 6a:2 + 12a: + 8 = (x + 2)3,
odkud a; + l<2<a; + 2, což není možné. Daná rovnice tedy nemá řešení x, y G Z takové, že x > 0. Předpokládejme, že má nějaké řešení Xi,yi G Z takové, že X\ < —2. Pak platí
(xi + 2)4 - x\ = y3 a dosadíme-li x2 = —x\ — 2, y2 = —yi, dostaneme
x$-(x2 + 2)4 = -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. x = — 1. Pro x = —1 vychází z původní rovnice y = 0; dvojice rr = —1, y = 0 je jediným řešením úlohy. □
i. 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 37 (AG-nerovnost). Pro libovolná čísla a1}a2,... ,an G Mq platí nerovnost a\ + a2 + • • • + a„
n
> ^axa2 ...an,
(35)
přitom rovnost v (35) nastane, jen když a\ = a2 = ■ ■ ■ = an.
DŮKAZ. Prozatím neuveden. □
VĚTA 38 (Bernoulliova nerovnost). \/x G IR,x > — 1, Vn G N platí:
(1 + x)n > 1 + n-x.
DŮKAZ. Pro n = 1 nebo x = 0 je tvrzení zřejmé. Pro reálná A > B > 0 a přirozené číslo n > 2 platí:
n(A - B)Bn-1 <An-Bn< n(A - B)An~1   (A > B > 0, n > 2),
z čehož po dosazení A = l+ x& B = l (pro x > 0), resp. A = l, B=l + x (pro — 1 < x < 0) dostaneme požadované tvrzení. □
PŘÍKLAD. V oboru přirozených čísel řešte rovnici
x    y z
- + - + -
y    z x
3.
ř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 37). Geometrický průměr těchto tří čísel je 1, a proto pro jejich aritmetický průměr platí
> 1,
1.
1 / x    y z
ô   - + " +
3 \y    2 x
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 = z, 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 x, n, kde n > 2, je daná rovnice splněna, a označme y = x + 1 > 2. Pak platí
(y
(36)
odkud dostáváme
0 = {y + 1)™ - Vn - (y - l)n = 1 - ("l)n   (mod y). Připusťme, že n je liché, pak 0 = 2 (mod y), tedy y = 2 a
0 = 3n — 2n — 1,
což platí pouze pro n = 1. Je tedy n sudé a podle binomické věty platí
(y + ir = Qy2+(r^y + l (mody3), (y-l)-=(^-(-)y + l (mody3),
odkud plyne
0 = (ž/+l)"-ž/"-(ž/-l)" = 2nž/ (mody3), tedy 0 = 2n (mod y2), a proto 2n > y2. Vydělíme-li (36) číslem yn, dostaneme
< 2.
Naopak podle Bernoulliovy nerovnosti (viz Věta 38) platí
l\n n 2n y2 y
1 + -     >1 + - = 1 + —>1 + —= l + ->2. y J y 2y~       2y 2 "
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.
5.5. Řešení diofantických rovnic metodou rozkladu. Tato metoda spočívá v úpravě dané rovnice do tvaru
Ai-A2.....An = B, (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 B 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ů Vyšetříme-li pak pro každý z těchto
rozkladů soustavu rovnic
A\ = di,   A2 = 0,2,    • • •,   An = an,
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
y + xy + x = [y-\—) H—x > 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 y = x + 1 z první do druhé rovnice dostaneme x2 + x — 30 = 0, odkud x = 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 x2 + 7x + 12 = 0, tedy x = -3 a y = 4 nebo x = —4 aj/ = 3.
(3) y — x = 13, í/2 + rry + x2 = 7. Nyní x2 + 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ě x2 + 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) e {(5; 6), (-6; -5), (-3; 4), (-4; 3)}.
□
PŘÍKLAD. Řešte diofantickou rovnici x4 + 2x7y — x14 — y2 = 7. ŘEŠENÍ. Upravme nejprve levou stranu rovnice:
x4 + 2x7y — x14 — y2 = x4 — (x7 — y)2 = (x2 — x7 + y) (x2 + x7 — 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 x2 = 4, odkud x = 2 a y = 125, nebo x = —2 a y = —131.
(2) x2 — x7 + y = 7,    x2 + x7 — y = 1. Nyní x2 = 4, a tedy x = 2, y = 131 nebo x = —2, y = —125.
(3) x2 — x7 + y = — 1,    x2 + x7 — y = — 7. Sečtením x2 = —4, což je spor.
(4) x2 — x7 + y = — 7,    x2 + x7 — y = — 1. Opět spor x2 = —4.
Rovnice má tedy čtyři řešení:
(x; y) e {(-2; -131), (-2; -125), (2; 125), (2; 131)}.
□
PŘÍKLAD. Řešte diofantickou rovnici
1     1 _ 1
x    y p'
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) • (—1)-Budeme proto řešit šest systémů rovnic:
(1)	X	-p =	1, y -p = p2	a tedy x = p -	M, y = p2	+ p;
(2)	X	-p =	p,y-p = p,	a tedy x = 2p,	y = 2p;	
(3)	X	-p =	p2,y-p = i	a tedy x = p2	+ p,y = p	+ i;
(4)	X	-p =	-i, y-p = -	-p2, a tedy x =	= p-l,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,y	= p — 1.
Daná rovnice má tedy pět řešení, popsaných v případech (l)-(4) a (6). □
.5.1. Pythagorova rovníce. 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 2
x + y = z .
Řešení. Označme t = (x, y, z), x\ = j, y± = |, z\ = |. Pak platí
t2x\ + ŕy\ = t2 z2,
odkud po vydělení číslem í2 7^ 0 vychází
x\ + yl = zl (38)
a navíc (xi,yi,Zi) = 1. Ukážeme nyní, že čísla Xi,yi,Zi jsou dokonce po dvou nesoudělná: kdyby nějaké prvočíslo p dělilo dvě z čísel Xi,yi,Zi, vyšlo by z (38), že dělí i třetí, což vzhledem k (xi,yi,Zi) = 1 není možné. Z čísel xľ, yľ 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 xl7 yi právě jedno sudé. Protože v rovnici (38) vystupují X\ a yľ symetricky, můžeme pro určitost předpokládat, že sudé je X\ = 2r, r G N. Z (38) pak plyne
A   2 2 2
Ar =z1- y1
a tedy
2 _ Z! + í/i zx-yx
Označme u = \(z\ + yi), v = \(z\ — yi). Pak z\ = u + v, y\ = u — v. Protože jsou y±,zi nesoudělná čísla, jsou i u, v nesoudělná čísla. Z rovnice
r2 = u ■ v
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 = txi = 2tr = 2tab,
y = ty1= t (u -v) = t(a2 - b2),
z = tz1= t{u + v) = t(a2 + b2),
což skutečně pro libovolné í G N a 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ě x\ je sudé):
x = t(a2 - b2),   y = 2tab,    z = t(a2 + b2),
kde opět t, a, b G N jsou libovolná taková, že a > b, (a, b) = 1. □
5.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 kongru-ence 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. 140).
příklad. Řešte diofantickou rovnici
15999.
Řešení. Ukážeme, že kongruence
x\ + x\ + • • • + x414 = 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 A; G Z a tedy n4 = 16k4 = 0 (mod 16). Jestliže je celé číslo n liché, platí n4 — 1 = (n — l)(n + l)(n2 + 1) = 0 (mod 16), neboť čísla n — l,n+lan2 + 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 n4 kongruentní s 0 pro sudá n a s 1 pro lichá čísla n. Je-li proto mezi čísly x1} x2,..., iy právě r lichých, je
xi + xt + ''' + xi4 = r   (mod 16). Platí 15999 = 16000 — 1 = 15 (mod 16) a protože 0 < r < 14, nemůže mít kongruence
x\ + x\ + • • • + x44 = 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ŠENÍ. 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 i / 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
x\ = |, íji = 2, zi = 2i ui =     dostáváme, že = 1, a po zkrácení obou
rovnic číslem d2 dostaneme
x\ + 2y2 = zi, 2x\ + y 2 = u\.
Odtud plyne sečtením 3xf + 3yf = z\ + uf a tedy 3 | ^2 + w2. Podle Tvrzení 3.1 platí 3 | Zi, 3 | Ui a tedy 9 | z2 + m2. Pak ale 9 | 3{x\ + yf), a tedy 3 | x\ + y\. Opět podle Tvrzení 3.1 platí 3 | xl7 3 \ y±, 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! + ••• + x\ = y2.
ŘEŠENÍ. Přímým výpočtem se přesvědčíme, že pro x < 5 vyhovují rovnici pouze x = y= lax = 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
x2 - y3 = 7.
Ř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 E Z. Pak platí
x2 + 1 = y3 + 23 = (y + 2) (y2 - 2y + 4) = (39) = (y + 2)((y - l)2 + 3) = (2fc + 3)(4A;2 + 3). (40)
Číslo 4A;2 + 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 4A;2 + 3 je liché, by totiž v rozkladu čísla 4A;2 + 3 na prvočísla vystupovala pouze prvočísla kongruentní s 1 podle modulu 4 a tedy by i jejich součin 4A;2 + 3 musel být kongruentní s 1 podle modulu 4, což jistě není. Je tedy 4A;2 + 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
6a:2 + 5a: + 1 = 0   (mod m) má řešení pro každé přirozené číslo m, a přitom diofantická rovnice
6x2 + 5a: + 1 = 0
řešení nemá.
Řešení. Platí 6x2 + 5a: +1 = (3a: + l)(2x + 1), a tedy rovnice 6x2 + 5x + 1 = 0 nemá celočíselné řešení. Nechť m je libovolné přirozené číslo a platí m = 2n ■ k, kde n G N0 a A; je liché číslo. Protože (3,2n) = (2,k) = 1, mají obě kongruence soustavy
3a: = -1   (mod 2n) 2a: = —1   (mod k)
podle Věty 20 řešení, a protože (2n, k) = 1, má podle Věty 22 řešení i celá soustava. Pro libovolné x vyhovující této soustavě je pak 3a: + 1 dělitelné číslem 2n a 2a: + 1 číslem k a proto součin (3a: + l)(2a: + 1) je dělitelný číslem 2n ■ k = m. Je tedy x řešením kongruence
6a:2 + 5a: + 1 = 0   (mod m).
□
6.2. Zmenšováni ad absurdum. Je to metoda důkazu neexistence řešení diofantická rovnice. Při důkazu touto metodou libovolné řešení dané diofantická rovnice charakterizujeme nějakým přirozeným číslem (například nejvě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 d, 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 nejmenším přirozeným číslem d; pak by ovšem muselo existovat i jiné řešení, charakterizované přirozeným číslem ď < d, 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
8x3 + 2y3 + Az3 - \2xxyz = 0,
po vydělení dvěma
Ax\ + y3 + 2z3 - 6xľyz = 0,
a proto i y3 je sudé číslo, tedy y = 2y\ pro vhodné y\ G Z. Dosazením a vydělením dvěma dostaneme
2xf + %i + -23 - 6xií/i2 = 0,
odkud plyne, že z3 je také sudé číslo, a proto z = 2z\ pro vhodné z\ Dosazením a vydělením dvěma dostaneme
x\ + 2í/3 + Az\ - šxxyxzx = 0,
a tedy x1}y1} Z\ je řešení původní diofantické rovnice, přičemž platí
G Z.
2 , 2 , 2 ^1 + Ž/l + Zl
< d.
x2    y2    z2 d —+—+—= 4      4      4 4
Podle metody popsané v 6.4 daná diofantická rovnice nemá řešení s vlastností d > 0, a tedy x = y = z = 0]e jejím jediným řešením. □
PŘÍKLAD. V oboru přirozených čísel řešte rovnici x2
ŘEŠENÍ. Užijeme metodu 5.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í x2 + y2 = 2 < 4, a je-li alespoň jedno z čísel x, y větší než jedna, je x2 + y2 > A. Je tedy z > 1 a platí + í/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
2xi, y = 2yi pro vhodná x±,yi G N. Pak ovšem
a tedy, označíme-li z\ = z — 1 G N, čísla x±,yi,zi splňují danou rovnici, přičemž Zi < 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 x, y, z, u vyhovují dané rovnici, přičemž u ^ 0, a označme d = 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 = A   (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é u\ G 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 = 5y±, z = 5zľ pro vhodná Xi,yi,Zi G Z. Dosazením do rovnice a vydělením 54 dostaneme
9<
A + ví + zi
a tedy xi,yi,xi,ui vyhovují dané rovnici. Přitom platí
_ u4
a a 7
Ut = — < u = a.
54
□
PŘÍKLAD. Řešte diofantickou rovnici x2
y2 + z2
2xyz.
ŘEŠENÍ. 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 = 2uxyz, (41)
kde x,y, z E Z a u E N nemá jiné řešení než x = y = z = 0, u E N libovolné.
Předpokládejme, že x, y, z E Z, u E N vyhovují rovnici (41) a že d
x
■r
-z2 >
0. Protože u > 1, je 2uxyz sudé číslo, a proto i x
z 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
Txyz = 0   (mod 4), neboť u > 1 a jedno z čísel x,y,z je sudé. Nastane tedy druhý případ a čísla x\ = |, í/i = |, £i = | jsou celá. Položme Mi = « + 1 a dosaďme do (41):
Ax\ + 4í/2 + Az\ = Tx~x ■ 2xl ■ 2yl ■ 2zu
po vydělení čtyřmi
xl + yl + z2 = 2Ul ■ xiyizu
a tedy Xi,yi,Zi,Ui vyhovují rovnici (41). Přitom platí 0 < x\ + y\ + z\ = | < d, neboť d > 0. Podle 5.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, u E N libovolné. Speciálně, zadaná rovnice má jediné řešení x = y = z = 0. □
6.3. Početnost množiny řešeni. 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 5.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
(x - l)2 + (x + l)2 = y2 + 1
má nekonečně mnoho řešení.
ŘEŠENÍ. Rovnici snadno upravíme do tvaru2
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 G 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 + V2x) (3 + 2^2)]- [(y - V2x) (3 -2^2)]= 1. 2Jde o speciální případ tzv. Pellovy rovnice
Výrazy v obou hranatých závorkách upravíme. Platí
(y + y/2x) (3 + 2y/2) = 3y + 3y/2x + 2y/2y + Ax = (Ax + 3y) + (3a: + 2y)y/2, (y - x/2x) (3 - 2V2) =3y- 3y/2x - 2\/2y + Ax = (Ax + 3y) - (3x + 2y)y/2. Položme u = Ax + 3y, v = 3x + 2y. Platí tedy
(u + v^w) (m - y/2v) = 1,
odkud
m2 - 2w2 = 1,
a tedy -u, -u G Z je další řešení dané rovnice. Položíme-li a?i = 2, y\ = 3 a
a^n+i = 3a;n + 2yn,       Vn+i = 4a;n + 3yn
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 < í/i < 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
k + x2 + y2 = 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 = 1,
z + y = k + x2.
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). Řešíme-li soustavu vzhledem k neznámým z, y, dostáváme
z= \{x2 + k + l), y= \{x2 + k- 1).
Zvolíme-li x = \k\ + 1 + 2t, kde t G N, je x přirozené číslo. Platí
x2 + k = k + l + 2t + k = l   (mod 2)
a tedy z = i((|fc| + 1 + 2t)2 + k + 1) > 0, y = i((|fc| + 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
5x2 - 8xy + 5y2 - Ak2 = 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 = Ak2, odkud plyne (2x - y)2 < (2k)2 a (2y - x)2 < (2k)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í. □