4
1. Základní pojmy
1.1. Úvodní poznámky. V mnoha problémech je výhodné vyzkoušet chování algoritmů na reálných příkladech. K tomu lze využít SW nainstalovaný na počítačích Ústavu matematiky a statistiky. Doporučujeme zejména:
• PARI-GP : specializovaný SW na teorii čísel, při výpočtech s většími čísly obvykle výrazně efektivnější než obecně orientované balíky. Spouští se příkazem gp. Nej důležitější příkazy: \q - ukončení, ? - help, ?? - kompletní uživatelský manuál, ?? tutoriál - tutoriál pro úvodní seznámení. Viz také pari . math.u-bordeaux.fr.
• SAGE: obecně koncipovaný open-source systém, který mj. zahrnuje interface do Pari-GP a díky jeho prostředí je tak výrazně usnadněna práce. Protože jeho vývoj řídí William Stein, odborník na teorii čísel, je tato část balíku jednoznačně nejpro-pracovanější. Existuje rovněž mnoho výukových worksheetů. Spustit lze např. na http://sage.math.muni.cz
• Maple: vhodný zejména kvůli existenci mnoha výukových pracovních listů (worksheets, i pro teorii čísel), např. na www. mapleapps.com.
1.2. Dělitelnost.
Definice. Řekneme, že celé číslo a děli celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a ■ c = b. Píšeme pak a | b.
Přímo z definice plyne několik jednoduchých tvrzení, jejichž důkaz přenecháváme čtenáři jako cvičení s návodem v [2, §12]: Číslo nula je dělitelné každým celým číslem; jediné celé číslo, které je dělitelné nulou, je nula; pro libovolné číslo a platí a | a; pro libovolná čísla a, b, c platí tyto čtyři implikace:
a | b A b | c ==^ a \ c (1)
a | b A a \ c ==^ a\b + cAa\b — c (2)
c / 0 ==^ (a | b -<=^ ac | bc) (3)
a\b A b> 0 ^ a <b (4)
příklad. Zjistěte, pro která přirozená čísla n je číslo n2+l dělitelné číslem n + 1.
Řešení. Platí n2 — 1 = (n + \){n — 1), a tedy číslo n + 1 dělí číslo n2 — 1. Předpokládejme, že n + 1 dělí i číslo n2 + 1. Pak ovšem musí dělit i rozdíl (n2 + 1) — (n2 — 1) = 2. Protože n g N, platí n + 1 > 2, a tedy z n + 1 | 2 plyne n + 1 = 2, proto n = 1. Uvedenou vlastnost má tedy jediné přirozené číslo 1. □
5
VĚTA 1. (Věta o děleni celých čísel se zbytkem) Pro libovolně zvolená čísla a £ Z, m £ N existuji jednoznačně určená čísla q £ Z, r <E {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 G Z. Nejprve budeme předpokládat, že a G No a existenci čísel q, r dokážeme indukcí:
Je-li 0 < a < m, stačí volit q = 0, r = a a rovnost a = qm + r platí.
Předpokládejme nyní, že a > m a že jsme existenci čísel q, r dokázali pro všechna a' G {0,1, 2,..., a — 1}. Speciálně pro a' = a — m tedy existují q',r' tak, že a' = q'm + r' a přitom r' G {0,1,... ,m — 1}. Zvolíme-li q = q' + 1, r = r', platia = a' + m= (q'+ l)m + r' = qm + r, což jsme chtěli dokázat.
Existenci čísel q,r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < 0, pak ke kladnému číslu —a podle výše dokázaného existují q' G Z, r' G {0,1,...,m — 1} tak, že —a = q'm + r', tedy a = —q'm — r'. Je-li r' = 0, položíme r = 0, q = —q'; je-li r > 0, položíme r = m — r', q = —q' — 1. V obou případech a = q ■ m + r, a tedy čísla 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 qi,q2 £ Z; rl,r2 £ {0,1,..., m - 1} platí a = qxm + rl = q2m + r2. Úpravou dostaneme r\ — r2 = {q2 — qi)m, a tedy m | r\ — r2. Ovšem z 0 < ri < m, 0 < r2 < m plyne —m < r\ — r2 < m, odkud podle (4) platí ri — r2 = 0. Pak ale i (g2 — qi)m = 0, a proto qľ = q2, rľ = r2. Čísla q, r jsou tedy určena jednoznačně. Tím je důkaz ukončen. □
Číslo q, resp. r z věty se nazývá (neúplný) podíl, resp. zbytek při dělení čísla a číslem m se zbytkem. Vhodnost obou názvů je zřejmá, přepíšeme-li rovnost a = mq + r do tvaru
ar r
— = q H--,   přitom   0 < — < 1.
m m m
Je vhodné též si uvědomit, že z věty 1 plyne, že číslo m dělí číslo a, právě když zbytek r je roven nule.
PŘÍKLAD. Dokažte, že jsou-li zbytky po dělení čísel a, b £ Z číslem m G N jedna, je jedna i zbytek po dělení čísla ab číslem m.
ř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 + l)(tm + 1) = (stm + s + ť)m + 1 = qm + r,
kde q = stm + s +1, r = 1, které je podle věty 1 jednoznačné, a tedy zbytek po dělení čísla ab číslem m je jedna. □
SW UKÁZKA. Vydělením čísla 1234567890 číslem 321 se zbytkem dostáváme 3846005, zbytek 285 - jak vidíme v PARI:
6
? divrem(1234567890,321)
°/„2 = [3846005, 285] ~
nebo i jinak:
? 1234567890X321
°/„3 = 3846005
? 1234567890Z321
°/„4 = 285
1.3. 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 | di, m \ a2 (resp. aľ | m, a2 \ m) se nazývá společný dělitel (resp. společný násobek) čísel ai,a2. Společný dělitel (resp. násobek) m > 0 čísel di,a2, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel a±,a2, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel a±,a2 a značí se (01,02) (resp. [01,02])-
poznámka. Přímo z definice plyne, že pro libovolné a, b g Z platí (a, b) = (6, a), [a, 6] = [6, a], (a, 1) = 1, [a, 1] = |a|, (a, 0) = \a\, [a, 0] = 0. Ještě však není jasné, zda pro každou dvojici a, b g Z čísla (a,b) a [a, 6] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi,m2 g No totiž podle (4) platí, že pokud ni\ \ m2 a zároveň m2 \ mi, je nutně ni\ = 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.
věta 2. (Euklidův algoritmus) Nechť a1}a2 jsou přirozená čísla. Pro každé n > 3, pro které an_i ^ 0, označme an zbytek po dělení čísla an-2 číslem an_i. Pak po konečném počtu kroků dostaneme = 0 a platí Ofc_i = (01,02)-
důkaz. Podle věty 1 platí a2 > 03 > 04 > .... Protože jde o nezáporná celá čísla, je každé následující alespoň o 1 menší než předchozí, a proto po určitém konečném počtu kroků dostáváme = 0, přičemž a^i ^ 0. Z definice čísel an plyne, že existují celá čísla qi,Q2, ■ ■ -Ak-2 tak, že
Oi = qi ■ a2 + a3, a2 = q2 ■ a3 + a4,
i (5)
ak-3 = qk-3 ■ ak-2 + O-k-l ak-2 = qk-2 ■ ak-l-
Z poslední rovnosti plyne, že \ 0^-2? z předposlední, že a^i \ ak-3, atd., až nakonec ze druhé ak-i \ a2 a z první dostaneme ak-i \ a\. Je tedy ak-i společný dělitel čísel 01,02- Naopak jejich libovolný
7
společný dělitel dělí i číslo 03 = a\ — q±a2, proto i 04 = 02 — ^2^3,..., a proto i afc_i = afc_3 — qksdk-2- Dokázali jsme, že ak-i je největší dělitel čísel ai, 02- D
POZNÁMKA. Z poznámky za definicí, z věty 2 a z toho, že pro libovolná a, b G Z platí (a, 6) = (a,—6) = (—a, 6) = (—a,—6) plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Navíc dostáváme z Euklidova algoritmu i následující zajímavé a často využívané tvrzení.
VĚTA 3. (Bezoutova) Pro libovolná celá čísla a, b existuji celá čísla k, l tak, že (a, b) = ka + lb.
DŮKAZ. Jistě stačí větu dokázat pro a, b G N. Všimněme si, že jestliže je možné nějaká čísla r, s G Z vyjádřit ve tvaru r = rľa + r2b, s = s id + s2b, kde r1}r2, s1} s2 G Z, můžeme tak vyjádřit i
r + s = (ri + si)a + (r2 + s2)&
a také
c • r = (c • ?~i)a + (c • r2)& pro libovolné c G Z. Z Euklidova algoritmu (pro = b) plyne,
že takto můžeme vyjádřit i a3 = aľ — q±a2, a4 = a2 — q2a3,..., a tedy i číslo afc_i = afc_3 - qk_3ak-2, což je ovšem (ai, a2).
Zdůrazněme přitom, že hledaná čísla k, l zdaleka nejsou určena jednoznačně. □
SW UKÁZKA. Výpočet největšího společného dělitele pomocí Euklidova algoritmu je s využitím výpočetní techniky i pro relativně velká čísla poměrně rychlý. V našem příkladu to vyzkoušíme na 2 číslech A,B, z nichž každé je součinem dvou 101-ciferných prvočísel. Všimněme si, že výpočet největšího společného dělitele i takto velkých čísel trval zanedbatelný čas. Pozorovatelem zaznamenatelný čas zabere tento výpočet až ve druhé ukázce, v níž jsou vstupem dvě čísla mající více než milion cifer.
sage :  p=next_prime (5*10" 100) sage :  q=next_prime (3*10" 100) sage:   r=next _prime (10 " 100) sage: A=p*q;B=q*r; sage:   time G=gcd(A,B);   print G
Time: CPU 0.00  s,  Wall:   0.00 s 300000000000000000000000000000000000\ 000000000000000000000000000000000000\ 00000000000000000000000000223
time G=gcd(A"10000 + l,FT 10000 + 1); Time: CPU 2.47 s,  Wall:   2.48 s
8
POZNÁMKA. Euklidův algoritmus a Bezoutova věta jsou jedny z nej důležitějších výsledků elementární teorie čísel a tvoří jeden ze základních pilířů algoritmů algebry a teorie čísel.
To, že znalost těchto základů je občas důležitá i v praktickém životě, dokazuje Bruče Willis a Samuel Jackson ve filmu Smrtonosná past 3, kde mají za úkol zlikvidovat bombu pomocí 4 galonů vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonů. Zde stačí s využitím Euklidova algoritmu najít celá čísla k, l tak, že bude platit 3k + 5/ = 4.
Netroufám si tvrdit, že zmínění herci ovládají uvedené základy teorie čísel (tuto konkrétní úlohu jistě snadno vyřešíte experimentálně), nicméně předchozí věty dávají návod, jak vyřešit úlohu tohoto typu s libovolnými zadanými parametry, což podrobně rozebereme v části o diofantických rovnicích.
VĚTA 4. Pro libovolná celá čísla a1} a2 existuje jejích nejmenší společný násobek [01,02] a platí (a,i, a2) ■ [«1,02] = \ai ' a2\-
DŮKAZ. Věta jistě platí, je-li některé z čísel a±, a2 rovno nule. Můžeme navíc předpokládat, že obě nenulová čísla 01,02 Jsou kladná, neboť jejich znaménka se v dokazovaném vzorci neprojeví. Budeme hotovi, ukážeme-li, že q = aľ ■ a2/(ai,a2) je nejmenší společný násobek čísel 01,02- Protože (a1,a2) je společný dělitel čísel a1}a2, jsou ai/(ai,a2) i a2/(ai,a2) celá čísla, a proto
je společný násobek čísel a±, a2. Podle Bezoutovy věty 3 existují ki,k2 G Z tak, že (a1; a2) = k\d\ + k2a2. Předpokládejme, že n G Z je libovolný společný násobek čísel ukážeme, že je dělitelný číslem q. Je
tedy n/ai,n/a2 G Z, a proto je i celé číslo
a\a2
n
a±a2
a±a2
To ovšem znamená, že q \ n, což jsme chtěli dokázat.
□
1.4. Dělitelé a násobky mnoha čísel.
9
Definice. Největší společný dělitel a nejmenší společný násobek n čísel
a\,a2,... ,an G Z definujeme analogicky jako v 1.3. Libovolné m G Z takové, že m \ ai, m \ a,2, ..., m \ an (resp. cii | 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 cii, a2,..., an a značí se (cii, a2,..., cin) (resp. [a1,a2, ■ ■ ■ ,an]).
Snadno se přesvědčíme, že platí
(cii,..., cín-i, an) = ((ai,..., a„_i), an), (6) [ai,... ,cxn_i,cxn] = [[ai,... ,an_i],an]. (7)
Největší společný dělitel (cxi,..., an) totiž dělí všechna čísla Cli j • • • j C^n i a tedy je společným dělitelem čísel a1; ..., cin_i, a proto dělí i největšího společného dělitele (a1;..., cin_i), tj. (a1;..., an) | ((ai,..., cin_i), cin). Naopak největší společný dělitel čísel (a1;..., an_i), cin musí kromě čísla an dělit i všechna čísla a1}..., cin_i, protože dělí jejich největšího společného dělitele, a proto ((cii,..., cin_i), an) \ (a1;..., an). Dohromady dostáváme rovnost (6) a zcela analogicky se dokáže (7).
Pomocí (6) a (7) snadno dokážeme existenci největšího společného dělitele i nej menšího společného násobku libovolných n čísel indukcí vzhledem k n: pro n = 2 je jejich existence dána větami 2 a 4, jestliže pro některé n > 2 víme, že existuje největší společný dělitel i nejmenší společný násobek libovolných n — 1 čísel, podle (6) a (7) existuje i pro libovolných n čísel.
1.5. Nesoudělnost.
Definice. Čísla a1} a2,..., an G Z se nazývají nesoudělná, jestliže pro ně platí (a1; ci2) • • • > cin) = 1- čísla a1} a2,..., an G Z se nazývají po cfoon 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.
10
Řešení. Užijeme Euklidův algoritmus. Platí
291-l = 228(263 -l) + 228 -l, 263 -l = (235 + 27)(228 -l) + 27-l, 228 -l = (221 + 214 + 27 + l)(27-l). Hledaný největší společný dělitel je tedy 27 — 1 = 127. □
věta 5. Pro libovolná přirozená čísla a, b, c platí
(1) {ac, bc) = (a, b) ■ c,
(2) jestliže a \ bc a (a,b) = 1, pak a | c,
(3) d = (a, b) právě tehdy, když existují q\, q2 g N tak, že a = dq\, b = dq2 a (qi,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 g Z tak, že (a, b) = ka + lb. Protože (ac, bc) je společný dělitel čísel ac, 6c, dělí i číslo fcac + lbe = (a, b) ■ c. Dokázali jsme, že (a, b) ■ c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se podle (4) rovnají.
ad 2. Předpokládejme, že (a, b) = 1 a a | bc. Podle Bezoutovy věty (věta 3) existují k, l g Z tak, že ka + lb = 1, odkud plyne, že c = c(A;a + lb) = kca + lbe. Protože a | bc, plyne odsud, že i a | c.
ad 3. Nechť d = (a,6), pak existují q\,q2 g N tak, že a = dq\, b = dq2. Pak podle části (1) platí d = {a, b) = (dqi,dq2) = d ■ (q±,q2), a tedy (01,02) = 1- Naopak, je-li a = dqľ, b = dq2 a (01,02) = 1, pak (a, 6) = {dqi,dq2) = d(q1}q2) = d ■ 1 = d (opět užitím 1. části tohoto tvrzení). □