Algebra 2 Teorie čísel. Michal Bulant

Home Page

Algebra 2 — Teorie čísel Title Page

Michal Bulant katedra matematiky, Přírodovědecká fakulta, Masarykova univerzita, Janáčkovo nám. 2a, 662 95 Brno E-mail address: [email protected]

Contents

JJ

II

J

I

Page 1 of 103

Go Back

Full Screen

Close

Quit

Home Page

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 nejzná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 + y n = z n ). Tento text výrazně čerpá z knih [2] a [3].

Title Page

Contents

JJ

II

J

I

Page 2 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Obsah 1. Základní pojmy 1.1. Dělitelnost 1.2. Největší společný dělitel a nejmenší společný násobek 1.3. Dělitelé a násobky mnoha čísel 1.4. Nesoudělnost 2. Prvočísla 3. Kongruence 3.1. Základní vlastnosti kongruencí 3.2. Aritmetické funkce 3.3. Eulerova funkce ϕ 3.4. Malá Fermatova věta, Eulerova věta 4. Kongruence o jedné neznámé 4.1. Lineární kongruence o jedné neznámé 4.2. Soustavy lineárních kongruencí o jedné neznámé 4.3. Kongruence vyšších stupňů 5. Diofantické rovnice 5.1. Lineární diofantické rovnice 5.2. Diofantické rovnice lineární vzhledem k některé neznámé 5.3. Rovnice jiného tvaru

Contents

5 5 8 11 12 14 23 24 30 34 36 41 42 45 53 61 61 67 71

JJ

II

J

I

Page 3 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

5.4. Řešení diofantických rovnic pomocí nerovností 5.4.1. Některé nerovnosti 5.5. Řešení diofantických rovnic metodou rozkladu 5.5.1. Pythagorova rovnice 5.6. Řešitelnost diofantických rovnic 5.6.1. Neexistence řešení 5.6.2. Zmenšování ad absurdum 5.6.3. Početnost množiny řešení Literatura

74 80 83 86 88 89 94 98 103

Contents

JJ

II

J

I

Page 4 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

1. Základní pojmy

Contents

1.1. Dělitelnost. Definice. Řekneme, že celé číslo a dělí celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a · c = b. Píšeme pak a | b. Přímo z definice plyne několik jednoduchých tvrzení, jejichž důkaz přenecháváme čtenáři jako cvičení s návodem v [2, §12]: Číslo nula je dělitelné každým celým číslem; jediné celé číslo, které je dělitelné nulou, je nula; pro libovolné číslo a platí a | a; pro libovolná čísla a, b, c platí tyto čtyři implikace: a | b ∧ b | c =⇒ a | c

(1)

a | b ∧ a | c =⇒ a | b + c ∧ a | b − c

(2)

c 6= 0 =⇒ (a | b ⇐⇒ ac | bc) a | b ∧ b > 0 =⇒ a ≤ b

(3)

JJ

II

J

I

Page 5 of 103

Go Back

Full Screen

(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 + 1)(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 +

Close

Quit

Home Page

Title Page

1) − (n2 − 1) = 2. Protože n ∈ N, platí n + 1 ≥ 2, a tedy z n + 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ělení celých čísel se zbytkem) Pro libovolně zvolená čísla a ∈ Z, m ∈ N existují jednoznačně určená čísla q ∈ Z, r ∈ {0, 1, . . . , m − 1} tak, ž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 ∈ Z. Nejprve budeme předpokládat, že a ∈ N0 a existenci čísel q, r dokážeme indukcí: Je-li 0 ≤ a < m, stačí volit q = 0, r = a a rovnost a = qm + r platí. Předpokládejme nyní, že a ≥ m a že jsme existenci čísel q, r dokázali pro všechna a0 ∈ {0, 1, 2, . . . , a − 1}. Speciálně pro a0 = a − m tedy existují q 0 , r0 tak, že a0 = q 0 m + r0 a přitom r0 ∈ {0, 1, . . . , m − 1}. Zvolíme-li q = q 0 + 1, r = r0 , platí a = a0 + m = (q 0 + 1)m + r0 = 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 0 ∈ Z, r0 ∈ {0, 1, . . . , m− 1} tak, že −a = q 0 m+r0 , tedy a = −q 0 m−r0 . Je-li r0 = 0, položíme r = 0, q = −q 0 ; je-li r > 0, položíme r = m − r0 , q = −q 0 − 1. V obou případech a = q · m + r, a tedy čísla q, r s požadovanými vlastnostmi existují pro každé a ∈ Z, m ∈ N. Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla q1 , q2 ∈ Z; r1 , r2 ∈ {0, 1, . . . , m − 1} platí a = q1 m + r1 = q2 m + r2 . Úpravou dostaneme r1 − r2 = (q2 − q1 )m, a tedy m | r1 − r2 . Ovšem z 0 ≤ r1 < m, 0 ≤ r2 < m plyne

Contents

JJ

II

J

I

Page 6 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

−m < r1 − r2 < m, odkud podle (4) platí r1 − r2 = 0. Pak ale i (q2 − q1 )m = 0, a proto q1 = q2 , r1 = r2 . Čísla q, r jsou tedy určena jednoznačně. Tím je důkaz ukončen.  Číslo q, resp. r z věty se nazývá (neúplný) podíl , resp. zbytek při dělení čísla a číslem m se zbytkem. Vhodnost obou názvů je zřejmá, přepíšeme-li rovnost a = mq + r do tvaru a r =q+ , m m

přitom 0 ≤

r < 1. m

Contents

JJ

II

J

I

Page 7 of 103

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. Go Back

Příklad. Dokažte, že jsou-li zbytky po dělení čísel a, b ∈ Z číslem m ∈ N jedna, je jedna i zbytek po dělení čísla ab číslem m. Full Screen

Řešení. Podle věty 1 existují s, t ∈ Z tak, že a = sm + 1, b = tm + 1. Vynásobením dostaneme vyjádření ab = (sm + 1)(tm + 1) = (stm + s + t)m + 1 = qm + r, kde q = stm + s + t, r = 1, které je podle věty 1 jednoznačné, a tedy zbytek po dělení čísla ab číslem m je jedna. 

Close

Quit

Home Page

Title Page

1.2. Největší společný dělitel a nejmenší společný násobek. Definice. Mějme celá čísla a1 , a2 . Libovolné celé číslo m takové, že m | a1 , m | a2 (resp. a1 | m, a2 | m) se nazývá společný dělitel (resp. společný násobek ) čísel a1 , a2 . Společný dělitel (resp. násobek) m ≥ 0 čísel a1 , a2 , který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel a1 , a2 , se nazývá největší společný dělitel (resp. nejmenší společný násobek ) čísel a1 , a2 a značí se (a1 , a2 ) (resp. [a1 , a2 ]). Poznámka. Přímo z definice plyne, že pro libovolné a, b ∈ Z platí (a, b) = (b, a), [a, b] = [b, a], (a, 1) = 1, [a, 1] = |a|, (a, 0) = |a|, [a, 0] = 0. Ještě však není jasné, zda pro každou dvojici a, b ∈ Z čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla m1 , m2 ∈ N0 totiž podle (4) platí, že pokud m1 | m2 a zároveň m2 | m1 , je nutně m1 = m2 . 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.

Contents

JJ

II

J

I

Page 8 of 103

Go Back

Full Screen

Věta 2. (Euklidův algoritmus) Nechť a1 , a2 jsou přirozená čísla. Pro každé n ≥ 3, pro které an−1 6= 0, označme an zbytek po dělení čísla an−2 číslem an−1 . Pak po konečném počtu kroků dostaneme ak = 0 a platí ak−1 = (a1 , a2 ).

Close

Důkaz. Podle věty 1 platí a2 > a3 > a4 > . . . . 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

Quit

Home Page

Title Page

konečném počtu kroků dostáváme ak = 0, přičemž ak−1 6= 0. Z definice čísel an plyne, že existují celá čísla q1 , q2 , . . . , qk−2 tak, že a1 = q1 · a2 + a3 , a2 = q2 · a3 + a4 , .. . ak−3 = qk−3 · ak−2 + ak−1 ak−2 = qk−2 · ak−1 .

(5)

Contents

JJ

II

J

I

Page 9 of 103

Z poslední rovnosti plyne, že ak−1 | ak−2 , z předposlední, že ak−1 | ak−3 , atd., až nakonec ze druhé ak−1 | a2 a z první dostaneme ak−1 | a1 . Je tedy ak−1 společný dělitel čísel a1 , a2 . Naopak jejich libovolný společný dělitel dělí i číslo a3 = a1 −q1 a2 , proto i a4 = a2 − q2 a3 , . . . , a proto i ak−1 = ak−3 − qk−3 ak−2 . Dokázali jsme, že ak−1 je největší dělitel čísel a1 , a2 . 

Full Screen

Poznámka. Z poznámky za definicí, z věty 2 a z toho, že pro libovolná a, b ∈ 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.

Close

Věta 3. (Bezoutova) Pro libovolná celá čísla a1 , a2 existuje jejich největší společný dělitel (a1 , a2 ), přitom existují celá čísla k1 , k2 tak, že (a1 , a2 ) = k1 a1 + k 2 a2 .

Go Back

Quit

Home Page

Title Page

Důkaz. Jistě stačí větu dokázat pro a1 , a2 ∈ N. Všimněme si, že jestliže je možné nějaká čísla r, s ∈ Z vyjádřit ve tvaru r = r1 a1 + r2 a2 , s = s1 a1 + s2 a2 , kde r1 , r2 , s1 , s2 ∈ Z, můžeme tak vyjádřit i r + s = (r1 + s1 )a1 + (r2 + s2 )a2 a také c · r = (c · r1 )a1 + (c · r2 )a2 pro libovolné c ∈ Z. Protože a1 = 1 · a1 + 0 · a2 , a2 = 0 · a1 + 1 · a2 , plyne z (5), že takto můžeme vyjádřit i a3 = a1 −q1 a2 , a4 = a2 −q2 a3 , . . . , ak−1 = ak−3 −qk−3 ak−2 , což je ovšem (a1 , a2 ).  Věta 4. Pro libovolná celá čísla a1 , a2 existuje jejich nejmenší společný násobek [a1 , a2 ] a platí (a1 , a2 ) · [a1 , a2 ] = |a1 · a2 |. Důkaz. Věta jistě platí, je-li některé z čísel a1 , 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 = a1 ·a2 /(a1 , a2 ) je nejmenší společný násobek čísel a1 , a2 . Protože (a1 , a2 ) je společný dělitel čísel a1 , a2 , jsou a1 /(a1 , a2 ) i a2 /(a1 , a2 ) celá čísla, a proto a1 a2 a1 a2 q= = · a2 = · a1 (a1 , a2 ) (a1 , a2 ) (a1 , a2 )

Contents

JJ

II

J

I

Page 10 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

je společný násobek čísel a1 , a2 . Podle věty 3 existují k1 , k2 ∈ Z tak, že (a1 , a2 ) = k1 a1 + k2 a2 . Předpokládejme, že n ∈ Z je libovolný společný násobek čísel a1 , a2 a ukážeme, že je dělitelný číslem q. Je tedy n/a1 , n/a2 ∈ Z, a proto je i celé číslo n n n(k1 a1 + k2 a2 ) n(a1 , a2 ) n · k1 + · k2 = = = . a2 a1 a1 a2 a1 a2 q To ovšem znamená, že q | n, což jsme chtěli dokázat.



Contents

JJ

II

J

I

1.3. Dělitelé a násobky mnoha čísel. Definice. Největší společný dělitel a nejmenší společný násobek n čísel a1 , a2 , . . . , an ∈ Z definujeme analogicky jako v 1.2. Libovolné m ∈ Z takové, že m | a1 , m | a2 , . . . , m | an (resp. a1 | 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 a1 , a2 , . . . , an , který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) těchto čísel, se nazývá největší společný dělitel (resp. nejmenší společný násobek ) čísel a1 , a2 , . . . , an a značí se (a1 , a2 , . . . , an ) (resp. [a1 , a2 , . . . , an ]).

Page 11 of 103

Go Back

Full Screen

Close

Snadno se přesvědčíme, že platí (a1 , . . . , an−1 , an ) = ((a1 , . . . , an−1 ), an ),

(6)

[a1 , . . . , an−1 , an ] = [[a1 , . . . , an−1 ], an ].

(7)

Quit

Home Page

Title Page

Největší společný dělitel (a1 , . . . , an ) totiž dělí všechna čísla a1 , . . . , an , a tedy je společným dělitelem čísel a1 , . . . , an−1 , a proto dělí i největšího společného dělitele (a1 , . . . , an−1 ), tj. (a1 , . . . , an ) | ((a1 , . . . , an−1 ), an ). Naopak největší společný dělitel čísel (a1 , . . . , an−1 ), an musí kromě čísla an dělit i všechna čísla a1 , . . . , an−1 , protože dělí jejich největšího společného dělitele, a proto ((a1 , . . . , an−1 ), 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 nejmenšího společného násobku libovolných n čísel indukcí vzhledem k n: pro n = 2 je jejich existence dána větami 2 a 4, 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.4. Nesoudělnost. Definice. Čísla a1 , a2 , . . . , an ∈ Z se nazývají nesoudělná, jestliže platí (a1 , a2 , . . . , an ) = 1. Čísla a1 , a2 , . . . , an ∈ Z se nazývají po dvou nesoudělná, jestliže pro každé i, j takové, že 1 ≤ i < j ≤ n, platí (ai , aj ) = 1. Poznámka. V případě n = 2 oba pojmy splývají, pro n > 2 plyne z nesoudě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.

Contents

JJ

II

J

I

Page 12 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Řešení. Užijeme Euklidův algoritmus. Platí

Contents

291 − 1 = 228 (263 − 1) + 228 − 1, 263 − 1 = (235 + 27 )(228 − 1) + 27 − 1,

JJ

II

J

I

228 − 1 = (221 + 214 + 27 + 1)(27 − 1). Hledaný největší společný dělitel je tedy 27 − 1 = 127.



Věta 5. Pro libovolná přirozená čísla a, b, c platí (1) (ac, bc) = (a, b) · c, (2) jestliže (a, b) = 1 a a | bc, pak a | c, (3) d = (a, b) právě tehdy, když existují q1 , q2 ∈ N tak, že a = dq1 , b = dq2 a (q1 , 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í k, l ∈ Z tak, že (a, b) = ka + lb. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo kac + lbc = (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 ∈ Z tak, že ka + lb = 1, odkud plyne, že c = c(ka + lb) = kca + lbc. Protože a | bc, plyne odsud, že i a | c.

Page 13 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

ad 3. Nechť d = (a, b), pak existují q1 , q2 ∈ N tak, že a = dq1 , b = dq2 . Pak podle části (1) platí d = (a, b) = (dq1 , dq2 ) = d·(q1 , q2 ), a tedy (q1 , q2 ) = 1. Naopak, je-li a = dq1 , b = dq2 a (q1 , q2 ) = 1, pak (a, b) = (dq1 , dq2 ) = d(q1 , q2 ) = d · 1 = d (opět užitím 1. části tohoto tvrzení). 

Contents

JJ

II

J

I

2. Prvočísla Prvočíslo je jeden z nejdů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.

Page 14 of 103

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.

Go Back

V dalším textu budeme zpravidla prvočíslo značit písmenem p. Nejmenší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, . . . .

Full Screen

Věta 6. Přirozené číslo p ≥ 2 je prvočíslo, právě když platí: pro každá celá čísla a, b z p | ab plyne p | a nebo p | b. Důkaz. „⇒ÿ Předpokládejme, že p je prvočíslo a p | ab, kde a, b ∈ 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.

Close

Quit

Home Page

Title Page

„⇐ÿ 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 = ap ∈ 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 ∈ N0 , pro která je mezi deseti po sobě jdoucími čísly k + 1, 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 k ≥ 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 ∈ {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 ∈ N, k < p, je
kombinační číslo kp dělitelné p.

Contents

JJ

II

J

I

Page 15 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Řešení. Podle definice kombinačního čísla   p p! p · (p − 1) · · · · · (p − k + 1) = = ∈ N, k 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 a k! dělitelné prvočíslem p, (k!, p) = 1. Podle
odkud
věty 5 platí k! | a, a tedy b = k! p p pa je celé číslo. Protože k = k! = pb, je číslo k 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.) 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é n0 , 2 ≤ 0 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 = nd , 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.

Contents

JJ

II

J

I

Page 16 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Nyní dokážeme jednoznačnost. Předpokládejme, že platí rovnost součinů p1 · p2 · · · · · pm = q1 · q2 · · · · · qs , kde p1 , . . . , pm , q1 , . . . , qs jsou prvočísla a navíc platí p1 ≤ p2 ≤ · · · ≤ pm , q1 ≤ q2 ≤ · · · ≤ qs a 1 ≤ m ≤ s. Indukcí vzhledem k m dokážeme, že m = s, p1 = q1 , . . . , pm = qm . Je-li m = 1, je p1 = q1 · · · · · qs prvočíslo. Kdyby s > 1, mělo by číslo p1 dělitele q1 takového, že 1 < q1 < p1 (neboť q2 q3 . . . qs > 1), což není možné. Je tedy s = 1 a platí p1 = q1 . Předpokládejme, že m ≥ 2 a že tvrzení platí pro m−1. Protože p1 ·p2 ·· · ··pm = q1 · q2 · · · · · qs , dělí pm součin q1 · · · · · qs , což je podle věty 6 možné jen tehdy, jestliže pm dělí nějaké qi pro vhodné i ∈ {1, 2, . . . , s}. Protože qi je prvočíslo, plyne odtud pm = qi (neboť pm > 1). Zcela analogicky se dokáže, že qs = pj pro vhodné j ∈ {1, 2, . . . , m}. Odtud plyne

Contents

JJ

II

J

I

Page 17 of 103

Go Back

qs = p j ≤ p m = qi ≤ qs , takže pm = qs . Vydělením dostaneme p1 · p2 · · · · · pm−1 = q1 · q2 · · · · · qs−1 , a tedy z indukčního předpokladu m − 1 = s − 1, p1 = q1 , . . . , pm−1 = qm−1 . Celkem tedy m = s a p1 = q1 , . . . , pm−1 = qm−1 , pm = qm . Jednoznačnost, a proto i celá věta 7 je dokázána.  Důsledek. (1) Jsou-li p1 , . . . , pk navzájem různá prvočísla a n1 , . . . , nk ∈ mk 1 N0 , je každý kladný dělitel čísla a = pn1 1 · · · · · pnk k tvaru pm 1 · · · · · pk , kde m 1 , . . . , m k ∈ N0 a m 1 ≤ n 1 , m 2 ≤ n 2 , . . . , m k ≤ n k .

Full Screen

Close

Quit

Home Page

Title Page

Číslo a má tedy právě

Contents

τ (a) = (n1 + 1)(n2 + 1) · · · · · (nk + 1) kladných dělitelů, jejichž součet je pn1 1 +1

−1 −1 ... . p1 − 1 pk − 1 (2) Jsou-li p1 , . . . , pk navzájem různá prvočísla a n1 , . . . , nk , m1 , . . . , mk ∈ N0 a označíme-li ri = min{ni , mi }, ti = max{ni , mi } pro každé i = 1, 2, . . . , k, platí σ(a) =

(pn1 1 [pn1 1

1 · · · · · pnk k , pm 1 1 · · · · · pnk k , pm 1

JJ

II

J

I

pnk k +1

k · · · · · pm k ) k · · · · · pm k ]

= =

pr11 · · · · · prkk , pt11 · · · · · ptkk .

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) = 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−1 ·(2q −1), kde 2q −1 je prvočíslo. Mersenneho prvočísla jsou právě prvočísla tvaru 2k −1. Bez

Page 18 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

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!−1 (takové existuje podle věty 7, protože n! − 1 > 1). Kdyby p ≤ n, muselo by p dělit číslo n! a nedělilo by n! − 1. Je tedy n < p. Protože p | (n! − 1), platí p ≤ n! − 1, tedy p < n!. Prvočíslo p splňuje podmínky úlohy.  Nyní uvedeme několik důkaz toho, že existuje nekonečně mnoho prvočísel (i když tvrzení v podstatě vyplývá už z předchozího příkladu). Věta 8. Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Důkaz. (Eukleides) Předpokládejme, že prvočísel je konečně mnoho a označme je p1 , p2 , . . . , pn . Položme N = p1 · p2 , . . . , pn + 1. Toto číslo je buď samo prvočíslem nebo je dělitelné nějakým prvočíslem různým od p1 , . . . , pn , což je spor.

Contents

JJ

II

J

I

Page 19 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

(Kummer, 1878): Předpokládejme, že prvočísel je konečně mnoho a označme je p1 < p2 < · · · < pn . Položme N = p1 · 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 N −(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 −∞ do +∞). 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 = ∪Ap , 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 −1 a 1 a 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.

Contents

JJ

II

J

I

Page 20 of 103

Go Back

Full Screen

Close



Quit

Home Page

Title Page

Příklad. Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3k + 2, kde k ∈ N0 . Řešení. Předpokládejme naopak, že existuje pouze konečně mnoho prvočísel tohoto tvaru a označme je p1 = 2, p2 = 5, p3 = 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 3k+2, neboť v opačném případě by bylo N součinem prvočísel tvaru 3k + 1 (uvažte, že N není dělitelné třemi), a tedy podle příkladu na str. 7 by bylo i N tvaru 3k + 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 , a to je spor. 

Contents

JJ

II

J

I

Page 21 of 103

Go Back

Poznámka. Předchozí příklady je možné značně zobecnit. Platí totiž tvrzení: „Pro libovolné přirozené číslo n > 5 existují mezi čísly n a 2n alespoň dvě prvočíslaÿ, které zobecňuje Čebyševovu větu: „Pro každé číslo n > 3 existuje mezi čísly n a 2n − 2 alespoň jedno prvočísloÿ. Důkaz lze provést elementárními prostředky, je však poměrně dlouhý. Předchozí příklad zobecňuje Dirichletova věta o aritmetické posloupnosti: „Jsouli a, m nesoudělná přirozená čísla, existuje nekonečně mnoho přirozených čísel k tak, že mk + a je prvočísloÿ. 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.

Full Screen

Close

Quit

Home Page

Title Page

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 + b 6= 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) ∧ vp ([a, b]) = vp (b)

(11)

Contents

JJ

II

J

I

Page 22 of 103

Go Back

Full Screen

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í

Close

([a, b], [a, c], [b, c]) = [(a, b), (a, c), (b, c)] Řešení. Podle věty 7 budeme hotovi, ukážeme-li, že vp (L) = vp (P ) pro libovolné prvočíslo p, kde L, resp. P značí výraz na levé, resp. pravé straně. Nechť

Quit

Home Page

Title Page

je tedy p libovolné prvočíslo. Vzhledem k symetrii obou výrazů můžeme bez újmy na obecnosti předpokládat, že vp (a) ≤ vp (b) ≤ vp (c). Podle (11) platí vp ([a, b]) = vp (b), vp ([a, c]) = vp ([b, c]) = vp (c); vp ((a, b)) = vp ((a, c)) = vp (a), vp ((b, c)) = vp (b), odkud vp (L) = vp (b) = vp (P ), což jsme měli dokázat. 

Contents

JJ

II

J

I

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).

Page 23 of 103

Go Back

Full Screen

V opačném případě řekneme, že a, b nejsou kongruentní modulo m, a píšeme a 6≡ b

(mod m).

Lemma. Pro libovolná a, b ∈ Z, m ∈ N jsou následující podmínky ekvivalentní: (1) a ≡ b (mod m), (2) a = b + mt pro vhodné t ∈ Z,

Close

Quit

Home Page

Title Page

(3) m | a − b. Důkaz. „(1)⇒(3)ÿ Jestliže a = q1 m + r, b = q2 m + r, pak a − b = (q1 − q2 )m. „(3)⇒(2)ÿ Jestliže m | a − b, pak existuje t ∈ Z tak, že m · t = a − b, tj. a = b + mt. „(2)⇒(1)ÿ Jestliže a = b+mt, pak z vyjádření b = 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 ∈ Z), symetrická (tj. pro každé a, b ∈ Z z a ≡ b (mod m) plyne b ≡ a (mod m)) a tranzitivní (tj. pro každé a, b, c ∈ Z z a ≡ b (mod m) a b ≡ c (mod m) plyne a ≡ c (mod m)) relace, jde tedy o ekvivalenci. Dokážeme nyní další vlastnosti: Věta 9. (Základní vlastnosti kongruencí) (1) Kongruence podle téhož modulu můžeme sčítat. Libovolný sčítanec můžeme přenést s opačným znaménkem z jedné strany kongruence na druhou. Na libovolnou stranu kongruence můžeme přičíst jakýkoliv násobek modulu. Důkaz. Je-li a1 ≡ b1 (mod m) a a2 ≡ b2 (mod m), existují podle lemmatu t1 , t2 ∈ Z tak, že a1 = b1 + mt1 , a2 = b2 + mt2 . Pak ovšem a1 + a2 = b1 + b2 + m(t1 + t2 ) a opět podle lemmatu a1 + a2 ≡ b1 + b2

Contents

JJ

II

J

I

Page 24 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

(mod m). Sečteme-li kongruenci a+b ≡ c (mod m) s kongruencí −b ≡ −b (mod m), která zřejmě platí, dostaneme a ≡ c − b (mod m). Sečteme-li kongruenci a ≡ b (mod m) s kongruencí mk ≡ 0 (mod m), jejíž platnost je zřejmá, dostaneme a + mk ≡ b (mod m).  (2) 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 a1 ≡ b1 (mod m) a a2 ≡ b2 (mod m), existují podle t1 , t2 ∈ Z tak, že a1 = b1 + mt1 , a2 = b2 + mt2 . Pak ovšem a1 a2 = (b1 + mt1 )(b2 + mt2 ) = b1 b2 + m(t1 b2 + b1 t2 + mt1 t2 ), odkud podle dostáváme a1 a2 ≡ b1 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 an+1 ≡ bn+1 (mod m), což je tvrzení pro n + 1. Důkaz indukcí je hotov. Jestliže vynásobíme kongruenci a ≡ b (mod m) a kongruenci c ≡ c (mod m), dostaneme ac ≡ bc (mod m). 

Contents

JJ

II

J

I

Page 25 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

(3) 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 = a1 · d, b = b1 · d a (m, d) = 1. Podle lemmatu je rozdíl a − b = (a1 − b1 ) · d dělitelný číslem m. Protože (m, d) = 1, je podle věty 5 číslo a1 − b1 také dělitelné číslem m, odtud podle lemmatu plyne a1 ≡ b1 (mod m).  (4) Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. Důkaz. Je-li a ≡ b (mod m), existuje podle lemmatu celé číslo t tak, že a = b + mt, odkud pro c ∈ N platí ac = bc + mc · t, odkud opět podle lemmatu plyne ac ≡ bc (mod mc).  (5) Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. Důkaz. Předpokládejme, že a ≡ b (mod m), a = a1 · d, b = b1 · d, m = m1 · d, kde d ∈ N. Podle lemmatu existuje t ∈ Z tak, že a = b + mt, tj. a1 ·d = b1 ·d+m1 dt, odkud a1 = b1 +m1 t, což podle lemmatu znamená, že a1 ≡ b1 (mod m1 ). 

Contents

JJ

II

J

I

Page 26 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

(6) Jestliže kongruence a ≡ b platí podle různých modulů m1 , . . . , mk , platí i podle modulu, kterým je nejmenší společný násobek [m1 , . . . , mk ] těchto čísel. Důkaz. Jestliže a ≡ b (mod m1 ), a ≡ b (mod m2 ), . . . , a ≡ b (mod mk ), podle lemmatu je rozdíl a − b společný násobek čísel m1 , m2 , . . . , mk a tedy je dělitelný jejich nejmenším společným násobkem [m1 , m2 , . . . , mk ], odkud plyne a ≡ b (mod [m1 , . . . , mk ]).  (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). 

Contents

JJ

II

J

I

Page 27 of 103

Go Back

(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. Full Screen

Důkaz. Předpokládejme, že a ≡ b (mod m), b = b1 d, m = m1 d. Pak podle lemmatu existuje t ∈ Z tak, že a = b + mt = b1 d + m1 dt = (b1 + m1 t)d, a tedy d | a.  Poznámka. Poznamenejme, že některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli – například větu 7 lze přeformulovat do tvaru „jestliže a ≡ 1 (mod m), b ≡ 1 (mod m), pak také ab ≡ 1 (mod m)ÿ, což je

Close

Quit

Home Page

Title Page

speciální případ tvrzení věty 9 (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 9 (2) 20

5

10

≡ (−1)

=1

Contents

JJ

II

J

I

Page 28 of 103

(mod 26),

a tedy zbytek po dělení čísla 520 číslem 26 je jedna.



Příklad. Dokažte, že pro libovolné n ∈ N je 37n+2 + 16n+1 + 23n dělitelné sedmi.

Go Back

Full Screen

Řešení. Platí 37 ≡ 16 ≡ 23 ≡ 2 (mod 7), a tedy podle 9 (2) a (1) platí 37n+2 + 16n+1 + 23n ≡ 2n+2 + 2n+1 + 2n = 2n (4+2+1) = 2n · 7 ≡ 0

(mod 7),

což jsme chtěli dokázat. Příklad. Dokažte, že číslo n = (8355 + 6)18 − 1 je dělitelné číslem 112.

Close

 Quit

Home Page

Title Page

Ř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 9 n ≡ (25 + 6)18 − 1 = 3818 − 1 ≡ 318 − 1 = 276 − 1 ≡ (−1)6 − 1 = 0

(mod 7),

Contents

JJ

II

J

I

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 = 18

9

9

= 9 − 1 = 81 − 1 ≡ 1 − 1 = 0

(mod 16),

proto 16 | n. Celkem tedy 112 | n, což jsme měli dokázat.



Page 29 of 103

Příklad. Dokažte, že pro libovolné prvočíslo p a libovolná a, b ∈ Z platí ap + bp ≡ (a + b)p

(mod p).

Řešení. Podle binomické věty platí

(a + b)p = ap + p1 ap−1 b + p2 ap−2 b2 + · · · +

Go Back

p p−1

abp−1 + bp .
Podle příkladu za větou 6 pro libovolné k ∈ {1, . . . , p − 1} platí kp ≡ 0 (mod p), odkud plyne tvrzení. 


Full Screen

Close

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 ∈ Z taková, že a ≡ b (mod mn ), kde n ∈ N, platí, že am = bm (mod mn+1 ).

Quit

Home Page

Title Page

Důkaz. Platí

Contents

am − bm = (a − b)(am−1 + am−2 b + · · · + abm−2 + bm−1 )

(12)

a protože m | mn , tak podle 9 (7) platí i a ≡ b (mod m). Jsou tedy všechny sčítance ve druhé závorce v (12) kongruentní s am−1 modulo m, a tedy am−1 + am−2 b + · · · + abm−2 + bm−1 ≡ m · am−1 ≡ 0

(mod m),

proto je am−1 + am−2 + · · · + abm−2 + bm−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 1 · · · pαk k . Hodnotu Möbiovy funkce µ(n) definujeme rovnu 0, pokud pro některé i platí αi > 1 a rovnu (−1)k v opačném případě. Dále definujeme µ(1) = 1.

JJ

II

J

I

Page 30 of 103

Go Back

Full Screen

Close

Příklad. µ(4) = µ(22 ) = 0, µ(6) = µ(2 · 3) = (−1)2 , µ(2) = µ(3) = −1. Dokážeme nyní několik důležitých vlastností Möbiovy funkce, zejména tzv. Möbiovu inverzní formuli.

Quit

Home Page

Title Page

Lemma. Pro n ∈ N \ {1} platí

Contents

X

µ(d) = 0.

d|n

Důkaz. Zapíšeme-li n ve tvaru n = pα1 1 · · · pαk k , pak všechny dělitele d čísla n jsou tvaru d = pβ1 1 · · · pβkk , kde 0 ≤ βi ≤ αi pro všechna i ∈ {1, . . . , k}. Proto X

X

µ(d) =

µ(pβ1 1 · · · pβkk ) =

JJ

II

J

I

Page 31 of 103

(β1 ,...,βk )∈(N∪{0})k 0≤βi ≤αi

d|n

X

=

Go Back

µ(pβ1 1 · · · pβkk )

(β1 ,...,βk )∈{0,1}k k 0




k 1




· (−1) +
k = 1 + (−1) = 0.

=

+

k 2




· (−1)2 + · · · +

k k




· (−1)k

Full Screen

Close

 S Möbiovou funkcí úzce souvisí pojem Dirichletův součin:

Quit

Home Page

Title Page

Definice. Buďte f, g aritmetické funkce. Jejich Dirichletův součin je definován předpisem X X
(f ◦ g)(n) = f (d) · g nd = f (d1 ) · g(d2 ).

Contents

JJ

II

J

I

d1 d2 =n

d|n

Lemma. Dirichletův součin je asociativní. Důkaz. ((f ◦ g) ◦ h)(n) =

X

Page 32 of 103

f (d1 ) · g(d2 ) · h(d3 ) = (f ◦ (g ◦ h))(n)

d1 d2 d3 =n

 Příklad. Definujme dvě pomocné funkce I a I předpisem I(1) = 1, I(n) = 0 pro všechna n > 1, resp. I(n) = 1 pro všechna n ∈ N. Pak pro každou aritmetickou funkci f platí: f ◦I=I◦f =f

Go Back

Full Screen

Close

a (I ◦ f )(n) = (f ◦ I)(n) =

X d|n

f (d).

Quit

Home Page

Title Page

Dále platí I ◦ µ = µ ◦ I = I, neboť X X (I ◦ µ)(n) = I(d)µ( nd ) = I( nd )µ(d) = d|n

=

X

d|n

Contents

JJ

II

J

I

µ(d) = 0 pro všechna n > 1

d|n

podle lemmatu za definicí Möbiovy funkce (pro n = 1 je tvrzení zřejmé). Věta 10. (Möbiova inverzní formule) Nechť je aritmetická funkce F definoP vaná pomocí aritmetické funkce f předpisem F (n) = d|n f (d). Pak lze funkci f vyjádřit ve tvaru X f (n) = µ( nd ) · F (d).

Page 33 of 103

Go Back

d|n

P

Důkaz. Vztah F (n) = d|n f (d) lze jiným způsobem zapsat jako F = f ◦ I. Proto F ◦ µ = (f ◦ I) ◦ µ = f ◦ (I ◦ µ) = f ◦ I = f , což je tvrzení věty. 

Full Screen

Definice. Multiplikativní funkcí přirozených čísel rozumíme takovou aritmetickou funkci, která splňuje, že pro všechny dvojice nesoudělných čísel a, b ∈ N platí f (a · b) = f (a) · f (b).

Close

Quit

Home Page

Title Page

Příklad. Multiplikativními funkcemi jsou např. funkce f (n) = σ(n), f (n) = τ (n), či f (n) = µ(n) nebo, jak brzy dokážeme i tzv. Eulerova funkce f (n) = ϕ(n). 3.3. Eulerova funkce ϕ.

Contents

JJ

II

J

I

Definice. Nechť n ∈ N. Definujme Eulerovu funkci ϕ předpisem ϕ(n) = |{a ∈ N | 0 < a ≤ n, (a, n) = 1}| Příklad. ϕ(1) = 1, ϕ(5) = 4, ϕ(6) = 2, je-li p prvočíslo, je zřejmě ϕ(p) = p − 1. Page 34 of 103

Nyní dokážeme několik důležitých tvrzení o funkci ϕ: P Lemma. Nechť n ∈ N. Pak d|n ϕ(d) = n. Důkaz. Uvažme n zlomků n−1 n 1 2 3 , , ,..., , . 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 11. Nechť n ∈ N, jehož rozklad je tvaru n = pα1 1 · · · pαk k . Pak     1 1 ϕ(n) = n · 1 − ··· 1 − . p1 pk

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Důkaz. S využitím předchozího lemmatu a Möbiovy inverzní formule dostáváme X n n n n ϕ(n) = µ(d) = n − − ··· − + · · · + (−1)k = d p1 pk p1 · · · pk d|n (13)     1 1 =n· 1− ··· 1 − . p1 pk  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í poučtu čísel soudělných s n.

Contents

JJ

II

J

I

Page 35 of 103

Go Back

Důsledek. Nechť a, b ∈ N, (a, b) = 1. Pak ϕ(a · b) = ϕ(a) · ϕ(b). Důkaz. Zřejmý.



Poznámka. Rovněž toto tvrzení lze odvodit nezávisle na základě poznatku (n, ab) = 1 ⇐⇒ (n, a) = 1 ∧ (n, b) = 1. Spolu se snadno odvoditelným výsledkem ϕ(pα ) = pα − pα−1 = (p − 1) · pα−1 pak lze odvodit vztah (13) již třetím způsobem.

Full Screen

Close

(14) Quit

Home Page

Title Page

Příklad. Vypočtěte ϕ(72).

Contents

Řešení. 72 = 23 · 32 =⇒ ϕ(72) = 72 · (1 − 12 ) · (1 − 13 ) = 24, alternativně ϕ(72) = ϕ(8) · ϕ(9) = 4 · 6 = 24. 

JJ

II

J

I

Příklad. Dokažte, že ∀n ∈ N : ϕ(4n + 2) = ϕ(2n + 1). Řešení. ϕ(4n + 2) = ϕ(2 · (2n + 1)) = ϕ(2) · ϕ(2n + 1) = ϕ(2n + 1).



3.4. Malá Fermatova věta, Eulerova věta. Tvrzení v tomto odstavci patří mezi nejdůležitější výsledky teorie čísel.

Page 36 of 103

Věta 12 (Fermatova, Malá Fermatova). Nechť a ∈ Z, p prvočíslo, p - a. Pak ap−1 ≡ 1

(mod p).

Důkaz. Tvrzení vyplyne jako snadný důsledek Eulerovy věty 13.

(15) 

Důsledek. Nechť a ∈ Z, p prvočíslo. Pak p

a ≡a

Go Back

Full Screen

(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. Úplná soustava zbytků modulo m je libovolná m-tice čísel po dvou nekongruentních modulo m (nejčastěji 0, 1, . . . , m − 1).

Close

Quit

Home Page

Title Page

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 ∈ Z, a ≡ b (mod m), a (a, m) = 1, pak i (b, m) = 1. Lemma. Nechť x1 , x2 , . . . , xϕ(m) tvoří redukovanou soustavu zbytků modulo m. Je-li a ∈ Z, (a, m) = 1 pak i čísla a · x1 , . . . , a · xϕ(m) 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 a · xi ≡ a · xj (mod m), po vydělení obou stran kongruence číslem a nesoudělným s m dostaneme xi ≡ xj (mod m). 

Contents

JJ

II

J

I

Page 37 of 103

Go Back

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

(mod m).

(16)

Důkaz. Buď x1 , x2 , . . . , xϕ(m) libovolná redukovaná soustava zbytků modulo m. Podle předchozího lemmatu je i a · x1 , . . . , a · xϕ(m) redukovaná soustava zbytků modulo m. Platí tedy, že pro každé i existuje j (oba indexy jsou z množiny {1, 2, . . . , ϕ(m)}) tak, že a · xi ≡ xj (mod m). Vynásobením čísel obou redukovaných soustav zbytků dostáváme (a · x1 ) · (a · x2 ) · · · (a · xϕ(m) ) ≡ x1 · x2 · · · xϕ(m)

(mod m).

Full Screen

Close

Quit

Home Page

Title Page

Po úpravě

Contents

aϕ(m) · x1 · x2 · · · xϕ(m) ≡ x1 · x2 · · · xϕ(m)

(mod m)

a protože (x1 · x2 · · · xϕ(m) , m) = 1, můžeme obě strany kongruence vydělit číslem x1 · x2 · · · xϕ(m) a dostaneme aϕ(m) ≡ 1 (mod m). 

JJ

II

Poznámka. Eulerova věta je rovněž důsledkem Lagrangeovy věty uplatněným na grupu (Zm , ·)× .

J

I

2

Příklad. Nalezněte všechna prvočísla p, pro která 5p + 1 ≡ 0 (mod p2 ). Řešení. Snadno se přesvědčíme, že p = 5 úloze nevyhovuje. Pro p 6= 5 platí (p, 5) = 1, a tedy podle Fermatovy věty 5p−1 ≡ 1 (mod p). Umocněním na p + 1 2 2 2 dostaneme 5p −1 ≡ 1 (mod p), odkud 5p ≡ 5 (mod p). Z podmínky 5p + 1 ≡ 0 2 (mod p)2 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 + 1 ≡ 14 + 1 = 2 6≡ 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 2ϕ(m)−1 číslem m.

Page 38 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Řešení. Z Eulerovy věty plyne 2ϕ(m) ≡ 1 ≡ 1 + m = 2r (mod m)), kde r = 1+m je přirozené číslo, 0 < r < m. Podle 9 (3) platí 2ϕ(m)−1 ≡ r (mod m), a 2 tedy hledaný zbytek po dělení je r = 1+m .  2 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 ∈ Z platí a2 + b2 ≡ 0 (mod p). Jestliže p | a, platí a ≡ 0 (mod p), proto b2 ≡ 0 (mod p), tedy p | b2 , odkud vzhledem k tomu, že p je prvočíslo, dostáváme p | b, a proto a ≡ b ≡ 0 (mod p), což jsme chtěli dokázat. Zbývá prošetřit případ, kdy a není dělitelné prvočíslem p. Odtud dostáváme, že p nedělí ani b (kdyby p | b, dostali bychom p | a2 ). Vynásobíme-li obě strany kongruence a2 ≡ −b2 (mod p) číslem bp−3 , dostaneme podle Fermatovy věty a2 bp−3 ≡ −bp−1 ≡ −1 p−3 2

JJ

II

J

I

Page 39 of 103

Go Back

(mod p).

Protože p ≡ 3 (mod 4), je p − 3 sudé číslo, a proto c = ab

Contents

p−3 2

∈ N0 . Označme

Full Screen

. Close

Pak c není dělitelné p a platí c2 = a2 bp−3 ≡ −1 (mod p). Umocníme-li poslední kongruenci na p−1 ∈ N, dostaneme 2 cp−1 ≡ (−1)

p−1 2

(mod p).

Quit

Home Page

Title Page

= Protože p ≡ 3 (mod 4), existuje celé číslo t tak, že p = 3 + 4t. Pak ovšem p−1 2 (p−1)/2 1 + 2t, což je číslo liché a proto (−1) = −1. Podle Fermatovy věty naopak p−1 platí c ≡ 1 (mod p), odkud 1 ≡ −1 (mod p) a p | 2, spor.  S Eulerovou funkcí a Eulerovou větou úzce souvisí pojem řád čísla modulo m: Definice. Nechť a ∈ Z, m ∈ N (a, m) = 1. Řádem čísla a modulo m rozumíme nejmenší přirozené číslo n splňující an ≡ 1

Contents

JJ

II

J

I

(mod m).

Příklad. Pro libovolné m ∈ N má číslo 1 modulo m řád 1. Číslo −1 má řád • 1 pro m = 1 nebo m = 2 • 2 pro m > 2

Page 40 of 103

Go Back

Příklad. Určete řád čísla 2 modulo 7. Řešení.

Full Screen

21 = 2 6≡ 1

(mod 7)

22 = 4 6≡ 1

(mod 7)

23 = 8 ≡ 1

(mod 7)

Řád čísla 2 modulo 7 je tedy roven 3.

Close



Quit

Home Page

Title Page

Lemma. Nechť m ∈ N, a, b ∈ Z, (a, m) = (b, m) = 1. Jestliže a ≡ b (mod m), pak obě čí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) ⇐⇒ bn ≡ 1 (mod m).  Lemma. Nechť m ∈ N, a ∈ Z, (a, m) = 1. Je-li řád čísla a modulo m roven r · s, (kde r, s ∈ N), pak řád čísla ar modulo m je roven s. Důkaz. později

Contents

JJ

II

J

I



Poznámka. Opak obecně neplatí – Př: později

Page 41 of 103

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

(mod m) ⇐⇒ t ≡ s

Go Back

(mod r).

Důkaz. později



Full Screen

4. Kongruence o jedné neznámé Definice. Nechť m ∈ N, f (x), g(x) ∈ Z[x]. Zápis f (x) ≡ g(x) (mod m)

Close

(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 ∈ Z, pro která f (c) ≡ g(c) (mod m).

Quit

Home Page

Title Page

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). | {z } ∈Z[x]

Contents

JJ

II

J

I

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

(mod m) =⇒ f (a) ≡ f (b)

(mod m).

Důkaz. snadný, později



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 10x ≡ 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é.

Page 42 of 103

Go Back

Full Screen

Close

Věta 16. Nechť m ∈ N, a, b ∈ Z. Označme d = (a, m). Pak kongruence ax ≡ b

(mod m)

Quit

Home Page

Title Page

(o jedné neznámé x) má řešení právě tehdy, když d | b. V případě, kdy d | b, má tato kongruence právě d řešení (modulo m). Důkaz. později

Contents



JJ

II

J

I

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 ≡ 1

(mod 47),

tj.

Page 43 of 103

Go Back

45

45

39 | {z· 39} x ≡ 39 · 41 (mod 47), 3946 ≡1

z čehož už dostáváme x ≡ 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)

Full Screen

Close

Quit

Home Page

Title Page

(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

Contents

JJ

II

J

I

Z čehož zpětným odvozením dostáváme Page 44 of 103

1 = 8 − 7 = 8 − (39 − 4 · 8) = 5 · 8 − 39 = = 5 · (47 − 39) − 39 = 5 · 47 − 6 · 39. Go Back

Uvážíme-li tuto rovnost modulo 47, dostaneme 1 ≡ −6 · 39 (mod 47) / · 41 41 ≡ 41 · (−6) ·39 (mod 47) / · 41 | {z } x ≡ 41 · (−6) (mod 47) x ≡ −246

Full Screen

Close

(mod 47)

x ≡ 36 (mod 47)

Quit

Home Page

Title Page

(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 4x ≡ 3

Contents

JJ

II

J

I

(mod 47) (mod 47)

4x ≡ −44 (mod 47) x ≡ −11 (mod 47)

Page 45 of 103

x ≡ 36 (mod 47) 

Go Back

Věta 17 (Wilsonova). Nechť p je prvočíslo, pak Full Screen

(p − 1)! ≡ −1 Důkaz. později

(mod p)

(18) 

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 16 rozhodnout o řešitelnosti každé z nich. V případě, kdy aspoň jedna z kongruencí nemá řešení, nemá

Close

Quit

Home Page

Title Page

řešení ani celá soustava. Naopak, jestliže každá z kongruencí řešení má, upravíme ji do tvaru x ≡ ci (mod mi ). Dostaneme tak soustavu kongruencí x ≡ c1 .. .

(mod m1 )

x ≡ ck

(mod mk )

Contents

JJ

II

J

I

(19)

Zkoumejme nejprve případ k = 2, který – jak uvidíme později – má stěžejní význam pro řešení soustavy (19) s k > 2. Věta 18. Nechť c1 , c2 jsou celá čísla, m1 , m2 přirozená. Označme d = (m1 , m2 ). Soustava dvou kongruencí x ≡ c1 (mod m1 ) (20) x ≡ c2 (mod m2 ) v případě c1 6≡ c2 (mod d) nemá řešení. Jestliže naopak c1 ≡ c2 (mod d), pak existuje celé číslo c tak, že x ∈ Z splňuje soustavu (19), právě když vyhovuje kongruenci x ≡ c (mod [m1 , m2 ]). Důkaz. Má-li soustava (20) nějaké řešení x ∈ Z, platí nutně x ≡ c1 (mod d), x ≡ c2 (mod d), a tedy i c1 ≡ c2 (mod d). Odtud plyne, že v případě c1 6≡ c2 (mod d) soustava (20) nemůže mít řešení.

Page 46 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Předpokládejme dále c1 ≡ c2 (mod d). První kongruenci soustavy (20) vyhovují všechna celá čísla x tvaru x = c1 + tm1 , kde t ∈ Z je libovolné. Toto x bude vyhovovat i druhé kongruenci soustavy (20), právě když bude platit c1 + tm1 ≡ c2 (mod m2 ), tj. tm1 ≡ c2 − c1 (mod m2 ). Podle Věty 16 má tato kongruence (vzhledem k t) řešení, neboť d = (m1 , m2 ) dělí c2 − c1 , a t ∈ Z splňuje tuto kongruenci právě když m c2 − c1  m1 ϕ( d2 )−1  m2  mod , t≡ · d d d tj. právě když m c2 − c1  m1 ϕ( d2 )−1 m2 t= · , +r· d d d kde r ∈ Z je libovolné. Dosazením  m ϕ( md2 ) m1 m2 1 x = c1 + tm1 = c1 + (c2 − c1 ) · +r = c + r · [m1 , m2 ], d d kde c = c1 + (c2 − c1 ) · (m1 /d)ϕ(m2 /d) , neboť m1 m2 = d · [m1 , m2 ]. Našli jsme tedy takové c ∈ Z, že libovolné x ∈ Z splňuje soustavu (20), právě když x≡c což jsme chtěli dokázat.

Contents

JJ

II

J

I

Page 47 of 103

Go Back

Full Screen

Close

(mod [m1 , m2 ]), 

Quit

Home Page

Title Page

Všimněme si, že důkaz této věty je konstruktivní, tj. udává vzorec, jak číslo c najít. Věta 18 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 kongruencí 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 18 není nutné určovat pomocí uvedeného vzorce. Můžeme vzít libovolné t ∈ Z vyhovující kongruenci c2 − c1  m2  m1 t· ≡ mod d d d a položit c = c1 + tm1 .

Contents

JJ

II

J

I

Page 48 of 103

Go Back

Full Screen

Důsledek (Čínská zbytková věta). Nechť m1 , , . . . , mk ∈ N jsou po dvou nesoudělná, a1 , . . . , ak ∈ Z. Pak platí: soustava x ≡ a1 .. .

(mod m1 )

x ≡ ak

(mod mk )

Close

(21) Quit

Home Page

Title Page

má jediné řešení modulo m1 · m2 · · · mk .

Contents

Příklad. Řešte systém kongruencí x ≡ −3

(mod 49)

x≡

(mod 11).

2

Řešení. První kongruenci splňují právě všechna celá čísla x tvaru x = −3 + 49t, kde t ∈ Z. Dosazením do druhé kongruence dostáváme −3 + 49t ≡ 2

JJ

II

J

I

(mod 11), Page 49 of 103

odkud 5t ≡ 5 (mod 11), tedy, vzhledem k (5, 11) = 1, po vydělení pěti t≡1

Go Back

(mod 11),

neboli t = 1 + 11s pro libovolné s ∈ Z. Proto x = −3 + 49(1 + 11s) = 46 + 539s, kde s ∈ Z, což můžeme také zapsat jako x ≡ 46 (mod 539). 

Full Screen

Příklad. Řešte systém kongruencí x≡

1

(mod 10)

x≡

5

(mod 18)

x ≡ −4

(mod 25).

Close

Quit

Home Page

Title Page

Řešení. Z první kongruence dostáváme x = 1 + 10t pro t ∈ Z. Dosazením do druhé kongruence získáme 1 + 10t ≡ 5

(mod 18),

tedy 10t ≡ 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 ∈ Z. Dosazením x = 1 + 10(4 + 9s) = 41 + 90s. Z třetí kongruence pak vychází 41 + 90s ≡ −4

(mod 25),

Contents

JJ

II

J

I

Page 50 of 103

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 ∈ Z. Dosazením x = 41 + 90(2 + 5r) = 221 + 450r, tedy x ≡ 221 (mod 450). 

Go Back

Full Screen

Příklad. Řešte systém kongruencí x ≡ 18 (mod 25)

Close

x ≡ 21 (mod 45) x ≡ 25 (mod 73).

Quit

Home Page

Title Page

Řešení. Z první kongruence x = 18 + 25t, kde t ∈ Z. Dosazením do druhé kongruence 18 + 25t ≡ 21 (mod 45), tedy 25t ≡ 3

Contents

JJ

II

J

I

(mod 45).

Tato kongruence však podle Věty 16 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 18, neboť 18 6≡ 21 (mod (25, 45)). 

Page 51 of 103

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 18 má kongruence řešení. Protože ϕ(3564) = 2 · (33 · 2) · 10 = 1080, je řešení tvaru x ≡ 915 · 23 9411079 (mod 3564). Úprava čísla stojícího na pravé straně by však vyžádala značné úsilí. Proto budeme kongruenci řešit poněkud jinak. Podle Věty 9 (6) je x ∈ Z řešením dané kongruence právě když je řešením soustavy 23941x ≡ 915

(mod 22 )

23941x ≡ 915

(mod 34 )

23941x ≡ 915

(mod 11)

Go Back

Full Screen

Close

(22) Quit

Home Page

Title Page

Vyřešíme nyní každou z kongruencí soustavy (22) zvlášť. První z nich je splněna, právě když x ≡ 3 (mod 4),

Contents

JJ

II

J

I

druhá, právě když 46x ≡ 24 (mod 81), odkud vynásobením dvěma 92x ≡ 48 (mod 81), tj. 11x ≡ −33 (mod 81) a po vydělení jedenácti x ≡ −3 (mod 81).

Page 52 of 103

Třetí kongruence je splněna, právě když 5x ≡ 2

(mod 11),

Go Back

odkud vynásobením číslem −2 dostaneme −10x ≡ −4 (mod 11), tedy x ≡ −4

Full Screen

(mod 11).

Libovolné x ∈ Z je tedy řešením soustavy (22), právě když je řešením soustavy Close

x≡

3

(mod 4)

x ≡ −3

(mod 81)

x ≡ −4

(mod 11)

(23) Quit

Home Page

Title Page

Z druhé kongruence dostáváme, že x = −3 + 81t, kde t ∈ Z. Dosazením do třetí kongruence soustavy (23) dostaneme −3 + 81t ≡ −4

(mod 11),

tedy 81t ≡ −1 (mod 11), tj. 4t ≡ 32 (mod 11), odkud t ≡ 8 (mod 11), a proto t = −3 + 11s, kde s ∈ Z. Dosazením x = −3 + 81(−3 + 11s) = −3 − 3 · 81 + 11 · 81s do první kongruence soustavy (23) dostaneme −3 − 3 · 81 + 11 · 81s ≡ 3

Contents

JJ

II

J

I

(mod 4), Page 53 of 103

tedy 1 + 1 · 1 + (−1) · 1s ≡ 3

(mod 4), Go Back

tj. −s ≡ 1 (mod 4) a proto s = −1 + 4r, kde r ∈ Z. Je tedy x = −3 − 3 · 81 + 11 · 81(−1 + 4r) = −3 − 14 · 81 + 4 · 11 · 81r = −1137 + 3564r,

Full Screen

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)

Close

Quit

Home Page

Title Page

kde F (x) je mnohočlen s celočíselnými koeficienty a m ∈ 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) = cn xn +cn−1 xn−1 +· · ·+c1 x+c0 , kde c0 , c1 , . . . , cn ∈ Z. Protože a ≡ b (mod m), pro každé i = 1, 2, . . . , n platí podle Věty 9(2) c i ai ≡ c i b i

JJ

II

J

I

Page 54 of 103

(mod m),

a tedy sečtením těchto kongruencí pro i = 1, 2, . . . , n a kongruence c0 ≡ c0 (mod m) dostaneme cn an + an−1 an−1 + · · · + c1 a + c0 ≡ cn bn + cn−1 bn−1 + · · · + c1 b + c0 tj. F (a) ≡ F (b) (mod m).

Contents

(mod m),

Go Back

Full Screen



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 = pn1 1 . . . pnk k , kde p1 , . . . , pk jsou různá prvočísla, a je-li navíc k > 1, můžeme nahradit kongruenci (24) soustavou

Close

Quit

Home Page

Title Page

kongruencí

Contents

F (x) ≡ 0 .. .

(mod pn1 1 )

F (x) ≡ 0

(mod pnk k ),

JJ

II

J

I

(25)

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).

Page 55 of 103

Go Back

Příklad. Řešte kongruenci x5 + 1 ≡ 0 (mod 11). Řešení. Označme F (x) = x5 + 1. Pak platí F (0) = 1, F (1) = 2 a dále platí F (2) = 33 ≡ 0

Close

(mod 11),

F (3) = 35 + 1 = 9 · 9 · 3 + 1 ≡ (−2)2 · 3 + 1 = 12 + 1 ≡ 2 F (4) = 45 + 1 = 210 + 1 ≡ 1 + 1 = 2

Full Screen

(mod 11),

(mod 11), Quit

Home Page

Title Page

kde jsme využili Fermatovu větu 12, podle které 210 ≡ 1 (mod 11). Podobně dále F (5) = 55 + 1 ≡ 165 + 1 = 410 + 1 ≡ 1 + 1 = 2 5

5

5

5

5

10

(mod 11),

10

F (6) = 6 + 1 ≡ (−5) + 1 ≡ −16 + 1 ≡ −4 + 1 ≡ 0 F (7) = 7 + 1 ≡ (−4) + 1 = −2 + 1 ≡ −1 + 1 = 0 5

5

5

10

10

F (8) = 8 + 1 ≡ 2 · 2 + 1 ≡ 32 + 1 ≡ 0 F (9) = 9 + 1 = 3 + 1 ≡ 1 + 1 = 2

Contents

(mod 11),

JJ

II

J

I

(mod 11),

(mod 11),

(mod 11),

F (10) = 105 + 1 ≡ (−1)5 + 1 = 0 (mod 11),

Page 56 of 103

5

a tedy řešením kongruence x + 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). 

Go Back

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 (1), . . . , F (104). Proto raději rozložíme 105 = 3·5·7 a budeme řešit kongruence F (x) ≡ 0 postupně pro moduly 3, 5, 7. Platí F (0) = 5, F (1) = 3, F (2) = 7, F (3) = 23, F (−1) = 7, F (−2) = 3, F (−3) = −13 (pro snadnější výpočty jsme počítali například F (−1) místo F (6) – využijeme toho, že F (6) ≡ F (−1) (mod 7) podle předchozího Tvrzení a podobně). Kongruence F (x) ≡ 0 (mod 3) má tedy řešení x ≡ 1 (mod 3);

Full Screen

Close

Quit

Home Page

Title Page

kongruence F (x) ≡ 0 (mod 5) má řešení x ≡ 0 (mod 5); řešením kongruence F (x) ≡ 0 (mod 7) jsou x ∈ Z splňující x ≡ 2 (mod 7) nebo x ≡ −1 (mod 7). Zbývá tedy vyřešit dvě soustavy kongruencí: x≡1

(mod 3),

x≡0

(mod 5),

x≡2

(mod 7)

a

x≡

1

(mod 3),

x≡

0

(mod 5),

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 t ∈ Z, dosazením do první 5t ≡ 1

(mod 3),

tedy −t ≡ 1 (mod 3), odkud t = −1 + 3s pro s ∈ Z, odkud x = −5 + 15s. Dosaďme nejprve do třetí kongruence první soustavy: −5 + 15s ≡ 2

JJ

II

J

I

Page 57 of 103

Go Back

Full Screen

(mod 7),

odkud s ≡ 0 (mod 7), tj. s = 7r pro r ∈ Z a proto x = −5 + 105r. Dosadíme-li x = −5 + 15s do třetí kongruence druhé soustavy, dostaneme −5 + 15s ≡ −1

Contents

(mod 7),

Close

Quit

Home Page

Title Page

odkud s ≡ 4 (mod 7), tj. s = 4 + 7r pro r ∈ 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 19. Nechť p je prvočíslo, f (x) ∈ Z[x], a ∈ Z je takové, že p | f (a), p 0 f (a). Pak platí: pro každé n ∈ N má soustava x≡a

(mod p)

f (x) ≡ 0

n

(mod p )

(26)

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

Contents

JJ

II

J

I

Page 58 of 103

Go Back

Full Screen

x = cn−1 + k · pn−1 , kde k ∈ Z. Je třeba zjistit, zda f (cn−1 +k·pn−1 ) ≡ 0 (mod pn ). Víme, že pn−1 | f (cn−1 +k·pn−1 ) a užijme binomickou větu pro f (x) = am xm + · · · + a1 x + a0 , kde a0 , . . . , am ∈ Z. Pak n−1 (mod pn ). (cn−1 + k · pn−1 )i ≡ cin−1 + i · ci−1 n−1 · kp

Close

Quit

Home Page

Title Page

Platí tedy

Contents

f (cn−1 + k · pn−1 ) ≡ f (cn−1 ) + k · pn−1 f 0 (cn−1 ), JJ

II

J

I

tj. f (cn−1 + k · p

n−1

)≡0

n

(mod p ) ⇐⇒ ⇐⇒ 0 ≡

f (cn−1 ) + k · f 0 (cn−1 ) n−1 p

(mod p).

Protože cn−1 ≡ a (mod p), dostaneme f 0 (cn−1 ) ≡ f 0 (a) 6≡ 0 (mod p), tedy (f 0 (cn−1 ), p) = 1. Užitím Věty 16 o řešitelnosti lineárních kongruencí dostáváme, že existuje právě jedno řešení k (modulo p) této kongruence a protože cn−1 bylo podle indukčního předpokladu jediné řešení modulo pn−1 , je číslo cn−1 + k · pn−1 jediným řešením (26) modulo pn .  Příklad. Řešte kongruenci x4 + 7x + 4 ≡ 0 (mod 27). Příklad. Ř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 t ∈ Z

Page 59 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

a řešme kongruenci modulo 9.

Contents

x4 + 7x + 4 ≡ 0

(mod 9)

(1 + 3t) + 7(1 + 3t) + 4 ≡ 0

(mod 9)

(1 + 3t)4 + 7(1 + 3t) + 4 ≡ 0

(mod 9)

1 + 4 · 3t + 7 + 7 · 3t + 4 ≡ 0

(mod 9)

4

JJ

II

J

I

33t ≡ −12 (mod 9) 11t ≡ −4

(mod 3)

t≡1

(mod 3)

Zapsáním t = 1 + 3s, kde s ∈ Z dostaneme x = 4 + 9s a po dosazení (4 + 9s)4 + 7(4 + 9s) + 4 ≡ 0

(mod 27)

44 + 4 · 43 · 9s + 28 + 63s + 4 ≡ 0

(mod 27)

256 · 9s + 63s ≡ −288

(mod 27)

Page 60 of 103

Go Back

Full Screen

256s + 7s ≡ −32 (mod 3) 2s ≡ 1

(mod 3)

s≡2

(mod 3)

Close

Quit

Home Page

Title Page

Celkem dostáváme řešení x = 4 + 9s = 4 + 9(2 + 3r) = 22 + 27r, kde r ∈ Z, neboli x ≡ 22 (mod 27).  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 sedmilitrové 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 ri$i Matiseviq (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.

Contents

JJ

II

J

I

Page 61 of 103

Go Back

Full Screen

Close

5.1. Lineární diofantické rovnice. a1 x1 + a2 x2 + · · · + an xn = b,

(27)

Quit

Home Page

Title Page

kde x1 , . . . , xn jsou neznámé, a1 , . . . , an , b daná celá čísla. Budeme předpokládat, že ai 6= 0 pro každé i = 1, . . . , n (je-li ai = 0, pak neznámá xi z rovnice „zmizíÿ). K řešení těchto rovnic je možné užít kongruencí. Nejprve si všimněme, kdy má rovnice (27) řešení. Jestliže číslo b není dělitelné číslem d = (a1 , . . . , an ), nemůže mít (27) žádné řešení, protože pro libovolná celá čísla x1 , . . . , xn je levá strana (27) dělitelná číslem d. Jestliže naopak d | b, můžeme celou rovnici (27) vydělit číslem d. Dostaneme tak ekvivalentní rovnici

Contents

JJ

II

J

I

a01 x1 + a02 x2 + · · · + a0n xn = b0 , Page 62 of 103

kde a0i = ai /d pro i = 1, . . . , n a b0 = b/n. Přitom platí d · (a01 , . . . , a0n ) = (da01 , . . . , da0n ) = (a1 , . . . , an ) = d, a tedy (a01 , . . . , a0n ) = 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 (27) má celočíselné řešení, právě když číslo b je dělitelné největším společným dělitelem čísel a1 , a2 , . . . , an .

Go Back

Full Screen

Věta 20. Nechť n ≥ 2. Rovnice a1 x1 + a2 x2 + · · · + an xn = b,

(28)

kde a1 , 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 rovnice je možné popsat pomocí n − 1 celočíselných parametrů.

Close

Quit

Home Page

Title Page

Důkaz. Provedeme indukcí vzhledem k počtu n neznámých xi v rovnici (28). Je výhodné formálně začít s případem n = 1, kdy podmínka (a1 ) = 1 znamená, že a1 = ±1. Tehdy rovnice (28) má tvar buď x1 = b, nebo −x1 = b, 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 (28) o n neznámých. Označme d = (a1 , . . . , an−1 ). Pak libovolné řešení x1 , . . . , xn rovnice (28) triviálně splňuje kongruenci a1 x 1 + a2 x 2 + · · · + an x n ≡ b

(mod d).

Vzhledem k tomu, že d je společný dělitel čísel a1 , . . . , an−1 , je tato kongruence tvaru an x n ≡ b

JJ

II

J

I

Page 63 of 103

Go Back

(mod d).

Protože platí, že (d, an ) = (a1 , . . . , an−1 , an ) = 1, má podle věty 16 tato kongruence řešení xn ≡ c

Contents

Full Screen

(mod d), Close

kde c je vhodné celé číslo, neboli xn = c + d · t, kde t ∈ Z je libovolné. Dosazením do (28) a úpravou dostaneme a1 x1 + · · · + an−1 xn−1 = b − an c − an dt.

Quit

Home Page

Title Page

Protože an c ≡ b (mod d), je číslo (b − an c)/d celé a poslední rovnici můžeme vydělit číslem d. Dostaneme pak rovnici a01 x1 + · · · + a0n−1 xn−1 = b0 , kde a0i = ai /d pro i = 1, . . . , n − 1 a b0 = ((b − an c)/d) − an t. Protože (a01 , . . . , a0n−1 ) = (da01 , . . . , da0n−1 ) ·

1 d

= (a1 , . . . , an−1 ) ·

1 d

Contents

JJ

II

J

I

= 1,

podle indukčního předpokladu má tato rovnice pro libovolné t ∈ Z řešení popsatelné pomocí n − 2 celočíselných parametrů. Přidáme-li k tomuto řešení podmínku xn = c + dt, dostaneme řešení rovnice (28) popsané pomocí n − 2 původních parametrů a nového parametru t. Důkaz indukcí je hotov.  Metodu z důkazu věty 20 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 x 1 , x 2 , x3 , . . . . Příklad. 5x + 7y = 8.

Page 64 of 103

Go Back

Full Screen

Řešení. Libovolné řešení této rovnice musí splňovat kongruenci 5x + 7y ≡ 8

(mod 5),

Close

tedy 2y ≡ −2 (mod 5)), odkud y ≡ −1 (mod 5)), tj. y = −1 + 5t pro t ∈ Z. Dosazením do dané rovnice dostaneme 5x + 7(−1 + 5t) = 8,

Quit

Home Page

Title Page

odkud vypočítáme x = 3 − 7t. Řešením naší rovnice je tedy x = 3 − 7t,

Contents

y = −1 + 5t,

kde t je libovolné celé číslo.



JJ

II

Řešení. Protože (91, 28) = 7 a 7 | 35, má rovnice celočíselné řešení. Vydělme ji sedmi: 13x − 4y = 5. Libovolné řešení této rovnice musí splňovat kongruenci

J

I

Příklad. 91x − 28y = 35.

13x − 4y ≡ 5

Page 65 of 103

(mod 13),

tj. −4y ≡ −8 (mod 13), odkud y ≡ 2 (mod 13) a y = 2+13t pro t ∈ Z. Dosazením

Go Back

13x − 4(2 + 13t) = 5, odkud vypočteme x = 1 + 4t. Řešením je tedy x = 1 + 4t, 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. 18x + 20y + 15z = 1.

Full Screen

Close

Quit

Home Page

Title Page

Ř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 + 15z ≡ 1 (mod 2), tedy z ≡ 1 (mod 2), odkud z = 1 + 2s, kde s ∈ Z. Dosazením 18x + 20y + 15(1 + 2s) = 1

Contents

JJ

II

J

I

odkud po vydělení dvěma a úpravě dostaneme rovnici, 9x + 10y = −7 − 15s

Page 66 of 103

kterou budeme řešit pro libovolné s ∈ Z. Je-li tato rovnice splněna, musí platit 9x + 10y ≡ −7 − 15s

(mod 9),

Go Back

odkud y ≡ 2 + 3s (mod 9), a proto y = 2 + 3s + 9t, kde t ∈ Z. Dosazením 9x + 10(2 + 3s + 9t) = −7 − 15s,

Full Screen

odkud po úpravě x = −3 − 5s − 10t. Řešení dané rovnice jsou tedy trojice x = −3 − 5s − 10t y = 2 + 3s + 9t z = 1 + 2s kde s, t jsou libovolná celá čísla.

Close



Quit

Home Page

Title Page

Příklad. 15x − 12y + 48z − 51u = 1.

Contents

Řešení. Protože (15, 12, 48, 51) = 3 není dělitel čísla 1, nemá rovnice celočíselné řešení. 

JJ

II

J

I

5.2. Diofantické rovnice lineární vzhledem k některé neznámé. Jde o rovnice, které můžeme upravit do tvaru mxn = F (x1 , . . . , xn−1 ),

(29)

kde m je přirozené číslo a F (x1 , . . . , xn−1 ) 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 (29), musí platit F (x1 , . . . , xn−1 ) ≡ 0 (mod m). (30) Naopak, je-li x1 , . . . , xn−1 řešení kongruence (30), pak pro xn = F (x1 , . . . , xn−1 )/m dostaneme celočíselné řešení x1 , . . . , xn−1 , xn rovnice (29). Proto pro řešení rovnice (29) postačí vyřešit kongruenci (30). V případě n = 2, tj. v případě, kdy je mnohočlen F (x1 ) 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 21. Pro libovolný mnohočlen F (x1 , . . . , xs ) s celočíselnými koeficienty, přirozené číslo m a celá čísla a1 , . . . , as , b1 , . . . , bs taková, že a1 ≡ b1 (mod m), . . . , as ≡ bs (mod m), platí F (a1 , . . . , as ) ≡ F (b1 , . . . , bs ) (mod m).

Page 67 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Důkaz. Snadný.



Pro nalezení všech řešení kongruence (30) tedy postačí dosazovat do mnohočlenu F (x1 , . . . , xn−1 ) za x1 , . . . , xn−1 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−1 ) ≡ (mod m), dostáváme řešení kongruence (30) ve tvaru x1 = a1 + mt1 , . . . , xn−1 = an−1 + mtn−1 , kde t1 , . . . , tn−1 mohou nabývat libovolných celočíselných hodnot. Tak dostaneme i řešení rovnice (29): x1 = a1 + mt1 , .. . xn−1 = an−1 + mtn−1 , 1 xn = F (a1 + mt1 , . . . , an−1 + mtn−1 ). m Příklad. Řešte diofantickou rovnici 7x2 + 5y + 13 = 0.

Contents

JJ

II

J

I

Page 68 of 103

Go Back

Full Screen

Close

Řešení. Rovnici upravíme na tvar 5y = −7x2 − 13 a budeme řešit kongruenci −7x2 − 13 ≡ 0

(mod 5),

Quit

Home Page

Title Page

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 + 5t

nebo

x = 4 + 5t,

kde t ∈ Z. Dosazením dostaneme v prvním případě 5y = −7(1 + 5t)2 − 13 = −7 − 70t − 175t2 − 13

Contents

JJ

II

J

I

a tedy y = −4 − 14t − 35t2 ,

Page 69 of 103

5y = −7(4 + 5t)2 − 13 = −112 − 280t − 175t2 − 13,

Go Back

y = −25 − 56t − 35t2 .

Full Screen

ve druhém případě

a proto Řešením dané rovnice jsou tedy právě všechny dvojice čísel x, y tvaru x = 1 + 5t, y = −4 − 14t − 35t2

nebo x = 4 + 5t, y = −25 − 56t − 35t2 ,

kde t je libovolné celé číslo. Příklad. Řešte diofantickou rovnici x(x + 3) = 4y − 1.

Close

 Quit

Home Page

Title Page

Řešení. Rovnici upravíme na tvar 4y = x2 + 3x + 1 a budeme řešit kongruenci x2 + 3x + 1 ≡ 0

Contents

(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 + 4z 2 + 6x + 7y + 8z = 1.

JJ

II

J

I

Řešení. Rovnici upravíme na tvar 7y = −x2 − 6x − 4z 2 − 8z + 1

Page 70 of 103

a doplníme na čtverce 7y = −(x + 3)2 − (2z + 2)2 + 14.

Go Back

Proto budeme řešit kongruenci (x + 3)2 + (2z + 2)2 ≡ 0

(mod 7)

(31)

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 (31). Výhodnější ale bude využít tvaru kongruence (31) a odvolat se na tvrzení tvr:nonresidue-3mod-4, odkud pro p = 7, a = x + 3, b = 2z + 2 dostaneme, že z kongruence (31) plyne x + 3 ≡ 2z + 2 ≡ 0

(mod 7),

Full Screen

Close

Quit

Home Page

Title Page

a tedy všechna řešení kongruence (31) jsou tvaru x = −3 + 7t,

Contents

z = −1 + 7s,

kde t, s jsou celá čísla. Dosazením do rovnice dostaneme

JJ

II

J

I

7y = −(x + 3)2 − (2z + 2)2 + 14 = −49t2 − 196s2 + 14, odkud 2

2

2

2

y = −7t − 28s + 2. Řešením dané rovnice jsou tedy právě všechny trojice čísel x, y, z tvaru x = −3 + 7t,

y = −7t − 28s + 2,

kde s, t jsou libovolná celá čísla.

Page 71 of 103

z = −1 + 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 (29) neznámou xn , dostaneme F (x1 , . . . , xn−1 ) xn = , m což je celé číslo, právě když m | F (x1 , . . . , xn−1 ), tj. právě když je splněna kongruence (30). Ukážeme si na příkladech, že tento postup je použitelný i na rovnice, které nejsou tvaru (29). V příkladech uvedeme i případ, kdy je vhodné vyjádřit

Go Back

Full Screen

Close

Quit

Home Page

Title Page

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: 1 y = (3x − 5). 4 1 x x Je-li x < 0, je 0 < 3 < 1, a tedy 4 (3 − 5) ∈ / Z. Pro x ≥ 0 platí 3x − 5 ≡ (−1)x − 1

(mod 4);

číslo (−1)x − 1 je kongruentní s nulou podle modulu 4 právě tehdy, když x je sudé, tj. x = 2k, kde k ∈ N0 . Řešením této diofantické rovnice jsou tedy právě všechny dvojice 9k − 5 x = 2k, y= , 4 kde k ∈ N0 je libovolné.  Příklad. Řešte v Z rovnici x(y + 1)2 = 243y .

Contents

JJ

II

J

I

Page 72 of 103

Go Back

Full Screen

Close

Řešení. Vyjádřeme neznámou x: x=

243y . (y + 1)2

Quit

Home Page

Title Page

Aby x ∈ Z, musí (y+1)2 být dělitelem čísla 243y. Protože y a y+1 jsou nesoudělná čísla pro libovolné y ∈ Z, musí být (y + 1)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 y y y y y

= 0, = −2, = 2, = −4, = 8, = −10,

x = 0, x = −2 · 243 = −486, x = 2 · 27 = 54, x = −4 · 27 = −108, x = 8 · 3 = 24, x = −10 · 3 = −30.

Jiná řešení daná diofantická rovnice nemá.  √ √ √ Příklad. Řešte v N rovnici x + y = 1988 . √ Řešení. Odečteme-li od obou stran rovnice y a umocníme-li na druhou, dostaneme p x = 1988 − 4 7 · 71 · y + y. √ √ Jsou-li √ x, y celá čísla, je i 4 7 · 71y celé číslo, a tedy 7 · 71y je racionální číslo. Pak je 7 · 71y = k nezáporné celé číslo. Platí tedy 7 · 71y = k 2 , odkud plyne, že

Contents

JJ

II

J

I

Page 73 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

k 2 a tedy i k je dělitelné prvočísly 7, 71. Je tedy k = 7 · 71t pro vhodné t ∈ N0 a tedy k2 y= = 497t2 . 7 · 71 Zcela analogicky je možné odvodit, že existuje s ∈ N0 tak, že x = 497s2 . Dosazením do původní rovnice dostáváme √ √ √ 497s + 497t = 1988,

Contents

JJ

II

J

I

Page 74 of 103

odkud po vydělení plyne s + t = 2. Jsou tedy tři možnosti: s = 0, t = 2 nebo s = t = 1 nebo s = 2, t = 0, takže daná diofantická rovnice má tři řešení: x = 0,

y = 1988 nebo x = y = 497 nebo x = 1988,

Go Back

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, b, 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.

Full Screen

Close

Quit

Home Page

Title Page

Příklad. Řešte diofantickou rovnici 6x2 + 5y 2 = 74.

Contents

Řešení. Protože pro libovolné y ∈ Z platí 5y 2 ≥ 0, musí libovolné řešení x, y dané rovnice splňovat 74 = 6x2 + 5y 2 ≥ 6x2 , odkud x2 < 37 , tedy −3 ≤ x ≤ 3, proto x2 je některé z čísel 0, 1, 4, 9. Dosazením 3 do rovnice postupně dostáváme 5y 2 = 74, 5y 2 = 68, 5y 2 = 50, 5y 2 = 20. První tři případy jsou ve sporu s y ∈ Z, z posledního dostáváme y 2 = 4, tj. 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. 

JJ

II

J

I

Page 75 of 103

Příklad. Řešte v Z rovnici x2 + xy + y 2 = x2 y 2 . Řešení. Protože jsou v dané rovnici neznámé x, y zastoupeny symetricky, můžeme předpokládat, že x2 ≤ y 2 , odkud plyne xy ≤ y 2 , a tedy x2 y 2 = x2 + xy + y 2 ≤ y 2 + y 2 + y 2 = 3y 2 .

Full Screen

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 y = −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,

Go Back

Close

y = 1. 

Quit

Home Page

Title Page

Příklad. Řešte v Z 2x = 1 + 3y .

Contents

Řešení. Je-li y < 0, platí 1 < 1 + 3y < 2, odkud 0 < x < 1, což je spor. Je tedy y ≥ 0 a proto 2x = 1 + 3y ≥ 2, odkud x ≥ 1. Ukážeme, že také platí x ≤ 2. Kdyby totiž bylo x ≥ 3, platilo by 1 + 3y = 2x ≡ 0

JJ

II

J

I

(mod 8),

odkud bychom dostali 3y ≡ −1 (mod 8), což však není možné, neboť pro sudá čísla y je 3y ≡ 1 (mod 8) a pro lichá čísla y platí 3y ≡ 3 (mod 8). Zbývá tedy vyřešit případ 1 ≤ x ≤ 2. Pro x = 1 dostáváme 3y = 21 − 1 = 1,

Page 76 of 103

Go Back

a tedy y = 0. Z x = 2 plyne 3y = 22 − 1 = 3, takže y = 1. Rovnice má tedy dvě řešení: x = 1, y = 0 a x = 2, y = 1.

Full Screen



Příklad. Řešte rovnici x + y + z = xyz v oboru přirozených čísel. Close

Ř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,

Quit

Home Page

Title Page

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 + z = z, což není možné. Je-li xy = 2, platí x = 1, y = 2 (předpokládáme x ≤ y), odkud 3 + z = 2z, a tedy z = 3. Je-li xy = 3, platí x = 1, y = 3, odkud 4 + z = 3z, tedy z = 2, což je ve sporu s předpokladem y ≤ z. Rovnice má tedy jediné řešení x = 1, y = 2, z = 3 splňující x ≤ y ≤ z. Všechna řešení v oboru přirozených čísel dostaneme všemi záměnami pořadí čísel 1, 2, 3:

Contents

JJ

II

J

I

Page 77 of 103

(x; y; z) ∈ {(1; 2; 3), (1; 3; 2), (2; 1; 3), (2; 3; 1), (3; 1; 2), (3; 2; 1)}. 

Go Back

Č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í

Full Screen

cn < dn < (c + 1)n ,

Close

kde c, d jsou celá a n přirozené číslo. Příklad. Řešte diofantickou rovnici x(x + 1)(x + 7)(x + 8) = y 2 .

Quit

Home Page

Title Page

Řešení. Úpravou

Contents

2

2

2

y = (x + 8x)(x + 8x + 7). 2

Označíme-li x + 8x = z, je naše rovnice tvaru 2

JJ

II

J

I

2

y = z + 7z. Ukážeme, že z ≤ 9. Předpokládejme naopak z > 9. Pak platí 2

2

2

2

2

2

(z + 3) = z + 6z + 9 < z + 7z = y < z + 8z + 16 = (z + 4) , což je spor, neboť z + 3, y, z + 4 jsou celá čísla a z těchto nerovností by plynulo

Page 78 of 103

|z + 3| < |y| < |z + 4|. Je tedy z ≤ 9, tj. x2 + 8x ≤ 9, odkud 2

Go Back

2

(x + 4) = x + 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) ∈ {(−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 = y 3 .

Full Screen

Close

Řešení. Úpravou získáme y 3 = 8x3 + 24x2 + 32x + 16 = 8(x3 + 3x2 + 4x + 2),

Quit

Home Page

Title Page

odkud plyne, že y je sudé. Položme y = 2z, z ∈ Z. Platí tedy

Contents

z 3 = x3 + 3x2 + 4x + 2. Je-li x ≥ 0, platí (x + 1)3 = x3 + 3x2 + 3x + 1 < x3 + 3x2 + 4x + 2 = 3

3

2

JJ

II

J

I

3

= z < x + 6x + 12x + 8 = (x + 2) , odkud x + 1 < z < x + 2, což není možné. Daná rovnice tedy nemá řešení x, y ∈ Z takové, že x ≥ 0. Předpokládejme, že má nějaké řešení x1 , y1 ∈ Z takové, že x1 ≤ −2. Pak platí (x1 + 2)4 − x41 = y13 a dosadíme-li x2 = −x1 − 2, y2 = −y1 , dostaneme

Page 79 of 103

Go Back

Full Screen

x42 − (x2 + 2)4 = −y23 , a proto x2 , y2 je také řešení dané rovnice. Ovšem x2 = −x1 − 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 x = −1, y = 0 je jediným řešením úlohy. 

Close

Quit

Home Page

Title Page

5.4.1. Některé nerovnosti. Při řešení diofantických rovnic jsou někdy užitečné i některé složitější postupy a nerovnosti. Uveďme si některé z nejčastěji používaných. Věta 22 (AG-nerovnost). Pro libovolná čísla a1 , a2 , . . . , an ∈ R+ 0 platí nerovnost √ a1 + a2 + · · · + an ≥ n a1 a2 . . . an , (32) n přitom rovnost v (32) nastane, jen když a1 = a2 = · · · = an . Důkaz. Prozatím neuveden.



Contents

JJ

II

J

I

Page 80 of 103

Věta 23 (Bernoulliova nerovnost). ∀x ∈ R, x ≥ −1, ∀n ∈ N platí: (1 + x)n ≥ 1 + n · x.

Go Back

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)B n−1 < An − B n < n(A − B)An−1

Full Screen

(A > B ≥ 0, n ≥ 2),

z čehož po dosazení A = 1 + x a B = 1 (pro x > 0), resp. A = 1, B = 1 + x (pro −1 ≤ x < 0) dostaneme požadované tvrzení. 

Close

Quit

Home Page

Title Page

Příklad. V oboru přirozených čísel řešte rovnici x y z + + = 3. y z x Řešení. Podíl přirozených čísel je číslo kladné, a proto můžeme pro čísla xy , yz a xz použít nerovnost mezi aritmetickým a geometrickým průměrem (viz Věta 22). Geometrický průměr těchto tří čísel je 1, a proto pro jejich aritmetický průměr platí   1 x y z + + ≥ 1, 3 y z x kde rovnost nastane právě tehdy, když x y z = = = 1. 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

Contents

JJ

II

J

I

Page 81 of 103

Go Back

Full Screen

Close

xn + (x + 1)n = (x + 2)n nemá řešení v oboru přirozených čísel.

Quit

Home Page

Title Page

Ř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 − 1)n + y n = (y + 1)n ,

(33)

Contents

JJ

II

J

I

odkud dostáváme 0 = (y + 1)n − y n − (y − 1)n ≡ 1 − (−1)n

(mod y).

Připusťme, že n je liché, pak 0 ≡ 2 (mod y), tedy y = 2 a 0 = 3n − 2n − 1,

Page 82 of 103

což platí pouze pro n = 1. Je tedy n sudé a podle binomické věty platí

(y + 1)n ≡ n2 y 2 + n1 y + 1 (mod y 3 ),

(y − 1)n ≡ n2 y 2 − n1 y + 1 (mod y 3 ),

Go Back

Full Screen

odkud plyne 0 = (y + 1)n − y n − (y − 1)n ≡ 2ny

(mod y 3 ), Close

tedy 0 ≡ 2n (mod y 2 ), a proto 2n ≥ y 2 . Vydělíme-li (33) číslem y n , dostaneme  n  n 1 1 1+ =1+ 1− < 2. y y

Quit

Home Page

Title Page

Naopak podle Bernoulliovy nerovnosti (viz Věta 23) platí  n 1 n 2n y2 y >1+ =1+ 1+ ≥1+ = 1 + ≥ 2. y 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 A1 · A2 · · · · · An = B,

(34)

kde A1 , . . . , 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ů a1 , . . . , an . Vyšetříme-li pak pro každý z těchto rozkladů soustavu rovnic A1 = a 1 ,

A2 = a2 ,

...,

Contents

JJ

II

J

I

Page 83 of 103

Go Back

Full Screen

An = an ,

získáme všechna řešení rovnice (34). Ukažme si to na příkladech. Příklad. Řešte diofantickou rovnici y 3 − x3 = 91.

Close

Řešení. Rozložme levou stranu rovnice: (y − x)(y 2 + xy + x2 ) = 91.

Quit

Home Page

Title Page

Protože

Contents

x 2 3 2 y 2 + xy + x2 = y + + x ≥ 0, 2 4 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, y 2 + 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, y 2 + xy + x2 = 13. Pak x2 + 7x + 12 = 0, tedy x = −3 a y = 4 nebo x = −4 a y = 3. (3) y − x = 13, y 2 + xy + x2 = 7. Nyní x2 + 13x + 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, y 2 + xy + x2 = 1. V tomto případě x2 + 91x + 2760 = 0. Ani tato rovnice nemá řešení v oboru reálných čísel. Daná rovnice má tedy čtyři řešení: 

(x; y) ∈ {(5; 6), (−6; −5), (−3; 4), (−4; 3)}.

JJ

II

J

I

Page 84 of 103

Go Back

Full Screen

Close

 Příklad. Řešte diofantickou rovnici x4 + 2x7 y − x14 − y 2 = 7.

Quit

Home Page

Title Page

Řešení. Upravme nejprve levou stranu rovnice:

Contents

x4 + 2x7 y − x14 − y 2 = 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) ∈ {(−2; −131), (−2; −125), (2; 125), (2; 131)}.

JJ

II

J

I

Page 85 of 103

Go Back

Full Screen

 Příklad. Řešte diofantickou rovnici 1 1 1 + = , x y p kde p je libovolné prvočíslo.

Close

Quit

Home Page

Title Page

Řešení. Vynásobením číslem xyp a další úpravou dostaneme

Contents

xy − px − py = 0. Úprava do tvaru (34) 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) (2) (3) (4) (5) (6)

x − p = 1, y − p = p2 , a tedy x = p + 1, y = p2 + p; x − p = p, y − p = p, a tedy x = 2p, y = 2p; x − p = p2 , y − p = 1, a tedy x = p2 + p, y = p + 1; x − p = −1, y − p = −p2 , a tedy x = p − 1, y = p − p2 ; x − p = −p, y − p = −p, a tedy x = y = 0, což nevyhovuje; x − p = −p2 , y − p = −1, a tedy x = p − p2 , y = p − 1.

JJ

II

J

I

Page 86 of 103

Go Back

Full Screen

Close

Daná rovnice má tedy pět řešení, popsaných v případech (1)-(4) a (6).



5.5.1. Pythagorova rovnice. Pythagorova rovnice se zabývá otázkou hledání všech pravoúhlých trojúhelníků s celočíselnými délkami stran.

Quit

Home Page

Title Page

Příklad. V oboru přirozených čísel řešte rovnici

Contents

x2 + y 2 = z 2 . Řešení. Označme t = (x, y, z), x1 = xt , y1 = yt , z1 = zt . Pak platí

JJ

II

J

I

t2 x21 + t2 y12 = t2 z12 , odkud po vydělení číslem t2 6= 0 vychází x21 + y12 = z12

(35)

a navíc (x1 , y1 , z1 ) = 1. Ukážeme nyní, že čísla x1 , y1 , z1 jsou dokonce po dvou nesoudělná: kdyby nějaké prvočíslo p dělilo dvě z čísel x1 , y1 , z1 , vyšlo by z (35), že dělí i třetí, což vzhledem k (x1 , y1 , z1 ) = 1 není možné. Z čísel x1 , y1 je tedy nejvýše jedno sudé. Připusťme, že jsou obě lichá. Pak z kongruence

Page 87 of 103

Go Back

z12 ≡ x21 + y12 ≡ 1 + 1 (mod 8) plyne, že z12 je sudé číslo, které není dělitelné 4, což není možné. Je tedy z čísel x1 , y1 právě jedno sudé. Protože v rovnici (35) vystupují x1 a y1 symetricky, můžeme pro určitost předpokládat, že sudé je x1 = 2r, r ∈ N. Z (35) pak plyne 4r2 = z12 − y12 a tedy r2 =

z1 + y1 z1 − y1 · . 2 2

Full Screen

Close

Quit

Home Page

Title Page

Označme u = 12 (z1 + y1 ), v = 12 (z1 − y1 ). Pak z1 = u + v, y1 = u − v. Protože jsou y1 , z1 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 = tx1 = 2tr = 2tab,

Contents

JJ

II

J

I

y = ty1 = t(u − v) = t(a2 − b2 ), z = tz1 = t(u + v) = t(a2 + b2 ),

Page 88 of 103

což skutečně pro libovolné t ∈ N a libovolná nesoudělná a, b ∈ 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ě x1 je sudé):

Go Back

x = t(a2 − b2 ),

y = 2tab,

z = t(a2 + b2 ), Full Screen

kde opět t, a, b ∈ 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

Close

Quit

Home Page

Title Page

ř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á. 5.6.1. Neexistence řešení. Při důkazu, že nějaká diofantická rovnice nemá žádné řešení, je často možné s úspěchem využít kongruencí. Má-li totiž řešení diofantická rovnice L = P (kde L, P jsou výrazy obsahující neznámé, nabývající celočíselných hodnot pro libovolné celočíselné hodnoty neznámých), musí mít řešení i kongruence L ≡ P (mod m) pro libovolné m ∈ 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. 92). Příklad. Řešte diofantickou rovnici

Contents

JJ

II

J

I

Page 89 of 103

Go Back

Full Screen

x41 + x42 + · · · + x414 = 15999. Řešení. Ukážeme, že kongruence x41

+

x42

+ ··· +

x414

Close

≡ 15999

(mod 16)

nemá řešení, odkud vyplyne, že řešení nemá ani daná diofantická rovnice. Je-li totiž celé číslo n sudé, je n = 2k pro k ∈ Z a tedy n4 = 16k 4 ≡ 0 (mod 16).

Quit

Home Page

Title Page

Jestliže je celé číslo n liché, platí n4 − 1 = (n − 1)(n + 1)(n2 + 1) ≡ 0 (mod 16), neboť čísla n − 1, n + 1 a n2 + 1 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 , . . . , x14 právě r lichých, je x41 + x42 + · · · + x414 ≡ r (mod 16). Platí 15999 = 16000 − 1 ≡ 15 (mod 16) a protože 0 ≤ r ≤ 14, nemůže mít kongruence x41 + x42 + · · · + x414 ≡ 15 (mod 16) řešení, a nemá ho tedy ani daná rovnice.

Contents

JJ

II

J

I

Page 90 of 103



Příklad. V oboru celých čísel řešte soustavu rovnic

Go Back

x2 + 2y 2 = z 2 , 2x2 + y 2 = 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 x 6= 0 nebo y 6= 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 x1 = xd , y1 = yd , z1 = dz , u1 = ud , dostáváme, že (x1 , y1 ) = 1, a po zkrácení obou

Full Screen

Close

Quit

Home Page

Title Page

rovnic číslem d2 dostaneme

Contents

x21 + 2y12 = z12 , 2x21 + y12 = u21 .

JJ

II

Odtud plyne sečtením 3x21 + 3y12 = z12 + u21 a tedy 3 | z12 + u21 . Podle Tvrzení 3.1 platí 3 | z1 , 3 | u1 a tedy 9 | z12 + u21 . Pak ale 9 | 3(x21 + y12 ), a tedy 3 | x21 + y12 . Opět podle Tvrzení 3.1 platí 3 | x1 , 3 | y1 , což je spor s (x1 , y1 ) = 1. Soustava má tedy jediné řešení x = y = z = u = 0. 

J

I

Příklad. V oboru přirozených čísel řešte rovnici

Page 91 of 103

2

1! + 2! + 3! + · · · + x! = y . Řešení. Přímým výpočtem se přesvědčíme, že pro x < 5 vyhovují rovnici pouze x = y = 1 a x = 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! ≡ y 2 (mod 5) pro x ≥ 5 tedy nemá řešení, a proto nemá pro x ≥ 5 řešení ani daná rovnice. 

Go Back

Full Screen

Close

Příklad. V oboru přirozených čísel řešte rovnici x2 − y 3 = 7.

Quit

Home Page

Title Page

Řešení. Ukážeme, že daná rovnice nemá řešení. Předpokládejme naopak, že pro vhodná x, y ∈ Z platí x2 − y 3 = 7. Kdyby y bylo sudé, platilo by x2 ≡ 7 (mod 8), což není možné. Je tedy y liché, y = 2k + 1 pro k ∈ Z. Pak platí x2 + 1 = y 3 + 23 = (y + 2)(y 2 − 2y + 4) = = (y + 2)((y − 1)2 + 3) = (2k + 3)(4k 2 + 3).

(36)

JJ

II

J

I

(37)

Číslo 4k 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 4k 2 + 3 je liché, by totiž v rozkladu čísla 4k 2 + 3 na prvočísla vystupovala pouze prvočísla kongruentní s 1 podle modulu 4 a tedy by i jejich součin 4k 2 + 3 musel být kongruentní s 1 podle modulu 4, což jistě není. Je tedy 4k 2 + 3 dělitelné prvočíslem p ≡ 3 (mod 4), a tedy platí x2 + 1 ≡ 0

Contents

Page 92 of 103

Go Back

(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 ∈ N.

Full Screen

Close

Příklad. Dokažte, že kongruence 6x2 + 5x + 1 ≡ 0

(mod m)

Quit

Home Page

Title Page

má řešení pro každé přirozené číslo m, a přitom diofantická rovnice

Contents

6x2 + 5x + 1 = 0 JJ

II

J

I

řešení nemá. Řešení. Platí 6x2 + 5x + 1 = (3x + 1)(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 ∈ N0 a k je liché číslo. Protože (3, 2n ) = (2, k) = 1, mají obě kongruence soustavy 3x ≡ −1

(mod 2n )

2x ≡ −1

(mod k)

Page 93 of 103

Go Back

podle Věty 16 řešení, a protože (2n , k) = 1, má podle Věty 18 řešení i celá soustava. Pro libovolné x vyhovující této soustavě je pak 3x + 1 dělitelné číslem 2n a 2x + 1 číslem k a proto součin (3x + 1)(2x + 1) je dělitelný číslem 2n · k = m. Je tedy x řešením kongruence 6x2 + 5x + 1 ≡ 0

Full Screen

Close

(mod m). 

Quit

Home Page

Title Page

5.6.2. Zmenšování 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 d0 < 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 d0 < d, což však by byl spor s volbou d. Příklad. Řešte diofantickou rovnici x3 + 2y 3 + 4z 3 − 6xyz = 0. Řešení. Rovnici jistě vyhovuje x = y = z = 0. Ukážeme, že jiné řešení rovnice nemá. Označme d = x2 + y 2 + z 2 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 = 2x1 pro vhodné x1 ∈ Z. Dosazením do rovnice dostaneme 8x31 + 2y 3 + 4z 3 − 12x1 yz = 0,

Contents

JJ

II

J

I

Page 94 of 103

Go Back

Full Screen

Close

po vydělení dvěma 4x31 + y 3 + 2z 3 − 6x1 yz = 0,

Quit

Home Page

Title Page

a proto i y 3 je sudé číslo, tedy y = 2y1 pro vhodné y1 ∈ Z. Dosazením a vydělením dvěma dostaneme 2x31 + 4y13 + z 3 − 6x1 y1 z = 0, odkud plyne, že z 3 je také sudé číslo, a proto z = 2z1 pro vhodné z1 ∈ Z. Dosazením a vydělením dvěma dostaneme x31 + 2y13 + 4z13 − 6x1 y1 z1 = 0,

Contents

JJ

II

J

I

a tedy x1 , y1 , z1 je řešení původní diofantické rovnice, přičemž platí x2 y 2 z 2 d + + = + + = < 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 je jejím jediným řešením.  x21

y12

Page 95 of 103

z12

Příklad. V oboru přirozených čísel řešte rovnici x2 + y 2 = 4z . Ř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 6= 1, protože je-li x = y = 1, platí x2 + y 2 = 2 < 4, a je-li alespoň jedno z čísel x, y větší než jedna, je x2 + y 2 > 4. Je tedy z > 1 a platí x2 + y 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

Go Back

Full Screen

Close

Quit

Home Page

Title Page

x = 2x1 , y = 2y1 pro vhodná x1 , y1 ∈ N. Pak ovšem x2 y 2 + = 4z−1 , 4 4 a tedy, označíme-li z1 = z − 1 ∈ N, čísla x1 , y1 , z1 splňují danou rovnici, přičemž z1 < z. Proto daná rovnice nemá řešení.

Contents

x21 + y12 =

Příklad. Řešte diofantickou rovnici x4 + y 4 + z 4 = 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 6= 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 + y 4 + z 4 ≡ 4

(mod 5),

což však není možné, neboť podle Fermatovy věty každé z čísel x4 , y 4 , z 4 může být podle modulu 5 kongruentní pouze s 0 nebo 1. Je tedy u dělitelné pěti, u = 5u1 pro vhodné u1 ∈ Z, a platí x4 + y 4 + z 4 ≡ 0

(mod 5),

JJ

II

J

I

Page 96 of 103

Go Back

Full Screen

Close

odkud plyne, že čísla x, y, z jsou dělitelné pěti, tj. x = 5x1 , y = 5y1 , z = 5z1 pro vhodná x1 , y1 , z1 ∈ Z. Dosazením do rovnice a vydělením 54 dostaneme x41 + y14 + z14 = 9u41 ,

Quit

Home Page

Title Page

a tedy x1 , y1 , x1 , u1 vyhovují dané rovnici. Přitom platí u4 4 u1 = 4 < u4 = d. 5

Contents



JJ

II

J

I

Příklad. Řešte diofantickou rovnici x2 + y 2 + z 2 = 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 + y 2 + z 2 = 2u xyz,

(38)

kde x, y, z ∈ Z a u ∈ N nemá jiné řešení než x = y = z = 0, u ∈ N libovolné. Předpokládejme, že x, y, z ∈ Z, u ∈ N vyhovují rovnici (38) a že d = x2 +y 2 +z 2 > 0. Protože u ≥ 1, je 2u xyz sudé číslo, a proto i x2 + y 2 + z 2 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 + y 2 + z 2 ≡ 1 + 1 + 0 = 2 (mod 4), kdežto 2u xyz ≡ 0 (mod 4), neboť u ≥ 1 a jedno z čísel x, y, z je sudé. Nastane tedy druhý případ a čísla x1 = x2 , y1 = y2 , z1 = z2 jsou celá. Položme u1 = u + 1 a dosaďme do (38): 4x21 + 4y12 + 4z12 = 2u1 −1 · 2x1 · 2y1 · 2z1 ,

Page 97 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

po vydělení čtyřmi

Contents

x21 + y12 + z12 = 2u1 · x1 y1 z1 , a tedy x1 , y1 , z1 , u1 vyhovují rovnici (38). Přitom platí 0 < x21 + y12 + z12 = d4 < d, neboť d > 0. Podle 5.6.2 tedy rovnice (38) může mít jen řešení s vlastností d = 0, což jsou výše uvedená řešení x = y = z = 0, u ∈ N libovolné. Speciálně, zadaná rovnice má jediné řešení x = y = z = 0.  5.6.3. Početnost množiny řešení. V mnoha případech, kdy neumíme najít všechna řešení diofantické rovnice, se nám může alespoň podařit rozhodnout, zda řešení je konečně či nekonečně mnoho. Konečnost je například zaručena zjištěním, že hodnoty neznámých jsou v absolutní hodnotě menší než nějaké číslo. Pokud toto číslo nalezneme a je „rozumněÿ malé, můžeme pak najít všechna řešení metodou popsanou v 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

JJ

II

J

I

Page 98 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

ř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 2

2

Contents

JJ

II

J

I

2

(x − 1) + (x + 1) = y + 1 má nekonečně mnoho řešení. Řešení. Rovnici snadno upravíme do tvaru1 y 2 − 2x2 = 1. Zkusme najít nějaké řešení. Po chvíli pokusů asi každý objeví, že volba y = 3, x = 2 vyhovuje dané rovnici. Představme si nyní, že máme k dispozici libovolné řešení x, y ∈ Z a pokusme se získat další. Platí tedy √
√
y + 2x y − 2x = 1. √
Dosazením nalezených hodnot y = 3 a x = 2 získáme rovnost 3 + 2 2 3 − √
2 2 = 1, vynásobením dostaneme √
√
  √
√
  y + 2x 3 + 2 2 · y − 2x 3 − 2 2 = 1. 1Jde

Page 99 of 103

Go Back

Full Screen

Close

Quit

o speciální případ tzv. Pellovy rovnice

Home Page

Title Page

Výrazy v obou hranatých závorkách upravíme. Platí √
√
√ √ √ y + 2x 3 + 2 2 = 3y + 3 2x + 2 2y + 4x = (4x + 3y) + (3x + 2y) 2, √
√
√ √ √ y − 2x 3 − 2 2 = 3y − 3 2x − 2 2y + 4x = (4x + 3y) − (3x + 2y) 2. Položme u = 4x + 3y, v = 3x + 2y. Platí tedy √
√
u + 2v u − 2v = 1,

Contents

JJ

II

J

I

odkud u2 − 2v 2 = 1,

Page 100 of 103

a tedy u, v ∈ Z je další řešení dané rovnice. Položíme-li x1 = 2, y1 = 3 a xn+1 = 3xn + 2yn ,

yn+1 = 4xn + 3yn

pro libovolné n ∈ N, dostáváme pro každé n ∈ N řešení xn , yn dané rovnice. A protože platí 0 < x1 < x2 < . . . , 0 < y1 < 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

Go Back

Full Screen

Close

k + x2 + y 2 = z 2 má pro libovolné celé číslo k nekonečně mnoho řešení v oboru přirozených čísel.

Quit

Home Page

Title Page

Řešení. Úpravou a rozkladem z 2 − y 2 dostaneme

Contents

k + x2 = (z − y)(z + y). Není nutné hledat všechna řešení, proto můžeme předpokládat, že

JJ

II

J

I

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

Page 101 of 103

Go Back

z= y=

1 (x2 2 1 (x2 2

+ k + 1), + k − 1).

Full Screen

Zvolíme-li x = |k| + 1 + 2t, kde t ∈ N, je x přirozené číslo. Platí x2 + k ≡ k + 1 + 2t + k ≡ 1

(mod 2)

a tedy z = 12 ((|k| + 1 + 2t)2 + k + 1) > 0, y = 12 ((|k| + 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í. 

Close

Quit

Home Page

Title Page

Příklad. Dokažte, že diofantická rovnice

Contents

5x2 − 8xy + 5y 2 − 4k 2 = 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 = 4k 2 , 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í. 

JJ

II

J

I

Page 102 of 103

Go Back

Full Screen

Close

Quit

Home Page

Title Page

Literatura [1] M. Davis. Hilbert’s tenth problem is unsolvable. The American Mathematical Monthly, 80(3):233–269, March 1973. http://links.jstor.org/sici?sici=0002-9890%28197303% 2980%3A3%3C233%3AHTPIU%3E2.0.CO%3B2-E. [2] J. Herman, R. Kučera a J. Šimša. Metody řešení matematických úloh I. MU Brno, druhé vydání, 2001. [3] I. M. Vinogradov. Základy theorie čísel. Nakladatelství ČSAV, 1953.

Contents

JJ

II

J

I

Page 103 of 103

Go Back

Full Screen

Close

Quit