1
Základy elementární teorie čísel Karel Lepká
Úvodní slovo autora
Významný německý matematik Karl Friedrich Gauss napsal, že matematika je královnou věd a teorie čísel je královnou matematiky. Jeho neméně slavný kolega Kronecker pak tvrdil, že přirozená čísla jsou od Boha a vše ostatní je dílem lidským. Je skutečností, že bez čísel by matematika nebyla matematikou. Samozřejmě že již nepovažujeme čísla za základ světa jako Pythagoras a jeho škola, aleje pravdou, že čísla mají v matematice hlubší význam než je počítání. V tomto textu se zaměříme především na množinu přirozených a celých čísel, přičemž se pro začátek nebudeme pouštět do složitých teorií, jak tyto číselné množiny definovat. Množinu přirozených čísel, kterou v textu budeme označovat symbolem N, budeme definovat intuitivně jako počet prvků konečné množiny. Množinu čísel celých budeme v textu uvádět symbolem Z a budeme jí rozumět původní množinu N, kterou doplníme o čísla záporná a o nulu. Záporná čísla budeme opět interpretovat intuitivně, například jako dluh či teploty, při nichž se voda mění za normálních podmínek v led. Opravdovou matematickou teorii číselných množin si naznačíme až v závěru tohoto textu.
V následujících kapitolách si ukážeme některé vlastnosti množiny čísel přirozených a celých. Jelikož je tento text primárně určen studentům pedagogické fakulty, budeme se snažit, aby text byl čtivý, ačkoliv se nebudeme příliš odchylovat od letitých zvyklostí, podle nichž se podobné texty píší, tedy ono eukleidovské definice, věta, důkaz. Text je doplněn i ilustračními či motivačními příklady a také praktickými aplikacemi. Možná bude čtenář překvapen, jak blízko má tato teorie blízko každodenním životu. Čtenář zde samozřejmě najde i řešené příklady a také řadu úloh, aby si mohl teorii procvičit. Nezapomeneme ani na historické odkazy, jelikož kdo nezná historii nějakého oboru, může mu těžko porozumět. V závěrečné kapitole jsou uvedeny i některé věci, které s teorií čísel přímo nesouvisejí, ale při výuce matematiky na základních školách mo-
2
hou být učitelům užitečné, neb podle mínění autora je nutnou podmínou dobré výuky matematiky této vědě vdechnout poezii a humor. Autor nepředpokládá, že se tento spisek dostane do rukou ortodoxním matematikům. Pokud se tak přesto stane, tak se jim velice omlouvá. Ponořme se tedy do tajemného světa čísel a začněme hledat zajímavé vlastnosti a překvapující souvislost.
Než tak učiníme, sluší se na tomto místě poděkovat všem, kdo mi byli nápomocni při sestavování tohoto textu. Jmenovitě uvádím prof. RNDr. Ladislava Skulu, DrSc. a RNDr. Helenu Durnovou, PhD, kteří pozorně text přečetli a svými připomínkami notně přispěli k jeho zlepšení.
V Brně na svátek Tří králů 2021 Karel Lepká
Kapitola 1 Teorie dělitelnosti
Tuto kapitolu začneme letitou žertovnou hádankou. Babička má pět vnoučat a dvanáct jablíček. Jak to má udělat, aby všechna vnoučata byla spravedlivě podělena? Správná odpověď je, že jim udělá štrůdl. Ve výše uvedeném případě babička jinou možnost nemá, pokud by však přikoupila další tři jablíčka, tak by každému vnoučkovi dala tři jablíčka a mohla by si ušetřit práci se štrůdlem. Babička ovšem může dvě jablíčka dětem zatajit, ta zbudou a opět vnuky spravedlivě podělí, tentokrát ovšem každého jen dvěma jablíčky. Jak vyplývá z uvedeného příkladu, někdy se nám podaří množinu prvků rozdělit na několik disjunktních podmnožin, z nichž každá obsahuje stejný, předem daný počet prvků, někdy však takové rozdělení možné není.
Pojem dělitelnost bude hlavním tématem této kapitoly. Seznámíme se i s dalšími důležitými pojmy jako prvočíslo a číslo složené, nej-menší společný násobek a největší společný dělitel. Dále se seznámíme s kritérii dělitelnosti a poznáme i Eukleidův algoritmus.
1.1    Základní pojmy a věty
Jak již bylo řečeno v úvodním slově, budeme přirozené číslo chápat jako počet prvků jisté konečné množiny. Pojem dělitelnosti lze vztáhnout i na čísla záporná, neboť i velký dluh můžeme rozdělit na několik menších.1 Dosti však již příkladů, začněme s vlastním tex-
1V matematice je nutné i přirozené číslo přesně definovat. Jednu možnost ukázal italský matematik Giuseppe Peano (1858-1932), viz např. [12], str. 168.
3
4
KAPITOLA 1. TEORIE DĚLITELNOSTI
tem. Start však bude netradiční, nezahájíme ani axiomy ani definicí, nýbrž rovnou větou.
Věta 1.1 Nechť a, b £ Z, přičemž b > 0. Pak existuji celá čísla q, r s vlastností
a = bq + r,       0 < r < b. (1-1) Čísla q, r s uvedenými vlastnostmi jsou určena jednoznačně.
Důkaz: Důkaz provedeme ve dvou krocích. Nejdříve dokážeme existenci čísel q r, pro něž platí vztah (1. 1). Označme symbolem M množinu všech celých čísel m tvaru
m = a — bt,
kde t je celé číslo s vlastností a — bt > 0. Zřejmě je množina M podmnožinou množiny celých nezáporných čísel. Snadno se přesvědčíme, že je neprázdná. Je-li a > 0, položíme t = 0 a máme m = a — 6.0 = a > 0. Pro a < 0 stačí položit t = a. Pak je m = a — b.a = a(l — b) > 0. Množina celých nezáporných čísel je dobře uspořádaná, proto množina M má nejmenší prvek, označme ho r, je r > 0 a existuje celé číslo q = t tak, že platí
0 < r = a — b ■ q       a = b ■ q + r.
Pokud by bylo r > b, pak bychom měli
0<r-b = a-b-(q-l)eM.
Avšak je r — b < r, což je spor s tím, že r je nejmenší prvek (číslo) množiny M.
Důkaz jednoznačnosti provedeme opět sporem. Předpokládejme, že platí a = bq± + r\ a současně a = bq2 + r2- Odečteme-li od druhé rovnice první, obdržíme 0 = 6(g2 — Qi) + ^2 — fi, tedy r2 — r\ je násobkem b. Jelikož však je \r<i — r\\ < b, musí platit r\ = T2 a tedy i qi = Q2-
Úloze, ve které se má k dané dvojici celých čísel a, b najít dvojici čísel g, r splňující vztah (1. 1), se říká dělení, číslo a nazýváme
Jiný způsob lze najít například v publikaci [10]. Jak zavést čísla celá se lze dočíst nij. v článku [4].
1.1. ZÁKLADNÍ POJMY A VĚTY
5
dělenec, číslo b dělitel. Zaměřme nyní svou pozornost na číslo r. Pro r > 0 mluvíme o děleni se zbytkem. V tomto případě je q částečný podíl a r je zbytek. Je-li r = 0, mluvíme o dělení beze zbytku; číslo q se nazývá podíl. Říkáme též, že číslo a je dělitelné číslem b, což budeme značit b\a a číst b dělí a. Stejný smysl má i formulace a je násobkem b.
Poznámka 1.1 Pozor! Zbytek je vždy číslo nezáporné, tedy —41 = 11.(-4) + 3, nikoliv -41 = (-3).11 - 8.
Poznámka 1.2 Předpoklad b > 0 není pro dělitelnost celých čísel nezbytný. Pokud bychom však předpokládali pouze b ^ 0, pak musíme vyžadovat platnost nerovnosti 0 < r < |6|
Platí následující věty:
Věta 1.2 Je-li a násobkem m a je-li současně m násobkem b, pak a je násobkem b.
Věta 1.3 Jsou-li v rovnosti typu a1 + a2 +.. - + an = b1 + b2 + ■ ■ - + bs
všechny členy s výjimkou jednoho násobkem čísla k, pak i tento člen je násobkem tohoto čísla k.
Poznámka 1.3 Této věty se někdy využívá při řešení úlohy typu dokažte, že jistý výraz je dělitelný číslem k. Je-li V = V\ + V2 + • • • + Vm a všechny sčítance na prvé straně jsou dělitelné číslem k, je i výraz V dělitelný číslem k.
Věta 1.4 Nechť a\b a a\c. Pak a\(bx + cy) pro libovolná celá čísla x a y.
Důslekem této věty je skutečnost, že pokud číslo a dělí čísla b a c, pak dělí i jejich součet a rozdíl.
Věta 1.5 Nechť a\b. Pak a\bc, kde c je libovolné celé číslo. Věta 1.6 Nechť a\b a současně b\c. Pak a\c.
6
KAPITOLA 1. TEORIE DĚLITELNOSTI
Této vlastnosti se říká tranzítívíta. Důkazy těchto tvrzení jsou snadné a doporučujeme, aby si je čtenář udělal jako cvičení.
Naskýtá se otázka, jak poznat je-li číslo a dělitelné číslem b. Ve věku počítačů a kalkulaček se zdá být nej jednodušší tato čísla prostě vydělit. Autor má sice velký obdiv k moderní výpočetní technice, přesto však ani tato si neumí s mnoha otázkami teorie čísel poradit. V některých případech by bylo nasazení této techniky zbytečné, asi jako jít s kanónem na vrabce, neboť dělitelnost můžeme poznat mnohem snadněji. Uvedeme si proto několik kritérií pro dělitelnost čísel, zejména pro případy, kdy je dělitel malé číslo.
Věta 1.7 Přirozené číslo n je dělitelné:
a) dvěma, je-li poslední cifra sudá,
b) třemi, je-li jeho ciferný součet dělitelný třemi,
c) čtyřmi, je-li jeho poslední dvojčíslí dělitelné čtyřmi,
d) pěti, je-li jeho poslední cifra 0 nebo 5,
e) šesti, je-li sudé a dělitelné 3,
f) sedmi, je-li dvojnásobek počtu stovek zvětšený o poslední dvojčíslí dělitelný 7,
g) osmi, je-li poslední trojčíslí dělitelné 8,
h) devíti, je-li jeho ciferný součet dělitelný 9,
i) desíti, je-li jeho poslední cifra 0.
Důkaz: Každé přirozené číslo n lze v dekadické číselné soustavě vyjádřit následujícím způsobem:
n = ck10k + ■■■ + c2102 + cilO + c0,
kde Ci G {0,1, 2,..., 9} a ck Ý 0. Z tohoto vyjádření okamžitě plynou tvrzení a), c), d), g) a i). Nechť
s = ck-\-----h C2 + Ci + c0
je ciferný součet čísla n. Pak je
n - s = (10fc - l)cjfe + • • • + 99c2 + 9ci.
Jelikož každý sčítanec na pravé straně je dělitelný devíti a stejně tak je dělitelné devíti číslo s, musí být dělitelné devíti i číslo n. Tím je dokázáno h) a součsně i b).
1.1. ZÁKLADNÍ POJMY A VĚTY
7
Zbývá dokázat kritérium pro dělitelnost sedmi. Dvojnásobek stovek čísla n zvětšený o poslední dvojčíslí je roven
m = 2ck10k~2 H-----h 2c2 + 10ci + c0.
Rozdíl
n-m = 98cfc10fc~2 + • • • + 98c2
je dělitelný sedmi, protože 7|98. Jestliže platí 7\m, je i číslo n dělitelné sedmi.
Kritérium dělitelnosti sedmi je oproti zbývajícím poměrně komplikované a pro praxi nepříliš vhodné. Uvedeme jednoduchý příklad. Chceme-li zjistit, zda je číslo 7056 dělitelné sedmi, musíme postupovat následujícím způsobem. 70.2+56=196. 196:7=28. Číslo m je dělitelné sedmi, je tedy i 7056 dělitelné sedmi. Existují i jiná kritéria pro dělitelnost sedmi, leč problematiku složitosti neřeší. Kritéria pro dělitelnost dvojcifernými prvočísly menšími než dvacet může čtenář najít např. v [2] na str. 31 resp. 164.
Nyní si uvedeme několik úloh na dělitelnost čísel.
Příklad 1.1 Určete, jaký den bude za 39 dní, je-li dnes středa. Řešení: 39=7.5+4. Za 39 dní bude neděle.
Příklad 1.2 Dokažte, že výraz a (a + l)(2a + 1) je dělitelný 6 pro libovolné celé číslo a.
Řešení: a(a + l)(2a + 1) = a(a + l)(a + 2 + a - 1) = a(a + l)(a + 2) + a(a + l)(a — 1). Oba sčítance jsou součinem tří po sobě jdoucích čísel, jedno z nich musí být dělitelné 3 a nejméně jedno musí být dělitelné 2.
Příklad 1.3 Dokažte, že pro každé n E N platí 169|33n+3 — 26n — 27.
Řešení: Upravme nejdříve první člen daného výrazu.
33n+3 = 27n+l = +
8
KAPITOLA 1. TEORIE DĚLITELNOSTI
. Použitím binomické věty pak obdržíme
(26 + 1)
n+l _
n + 1 0
+
n + 1
n + 1 n + 1
)
26n + ...+
)
26'
'0
n + 1 n — 1
)
262+
Je zřejmé, že všechny členy tohoto rozvoje s výjimkou posledních jsou dělitelné 169, neboť obsahují minimálně druhou mocninu čísla 26 = 2.13. Poslední dva členy pak dávají 26n + 27 a tudíž se vyruší s posledními dvěma členy daného výrazu.
1.2   Nej větší společný dělitel, nejmenší společný násobek
V této části budeme řešit dva problémy. Budeme hledat největší číslo, které současně dělí několik různých čísel a naopak nejmenší číslo, které je současně dělitelné několika různými čísly.
Def. 1.1 Každé celé číslo, délící současné celá čísla a,b,...,l se nazývá jejích společným dělitelem. Je-li aspoň jedno z uvedených čísel různé od nuly, pak je počet jejich společných dělitelů konečný, a tedy jeden z nich je největší. Ten se nazývá největším společným dělitelem čísel a,b,... ,1 a budeme ho značit (a, b,...,/). Tato čísla a,b,... ,1 se nazývají nesoudělná, je-li (a, b,..., /) = 1. Je-li každé z čísel a,b,... ,1 nesoudělné s každým druhých z nich, pak čísla a,b,... ,1 se nazývají po dvou nesoudělná. Zřejmě čísla po dvou nesoudělná jsou vždy nesoudělná; v případě dvou čísel se pojmy nesoudělná a po dvou nesoudělná shodují.
Příklad 1.4 a) (15,18,63) = 3 &J(15,21,28) = 1 cj(ll, 18,25) = 1 V případě b) jsou uvedená čísla nesoudělná, avšak ne po dvou nesoudělná. Je totiž (15,21) = 3; (21,35) = 7 a (15,35) = 5. Naproti tomu v případě c) jsou i po dvou nesoudělná, neboť je (11,18) = (11,25) = (18,25) = 1.
1.2. NEJVĚTŠÍ SPOLEČNÝ DĚLITEL, NEJMENŠÍ SPOLEČNÝ NÁS0BEK9
V dalších úvahách se budeme zabývat jen největším společným dělitelem dvou čísel, pro jednoduchost a z úsporných důvodů budeme používat zkratky NSD. Pokud tato čísla nejsou příliš velká, pak obyčejně nalezení NSD nebývá příliš složité, neboť se nám podaří rozložit obě čísla na součin prvočinitelů (viz důsledek věty 1. 8) a pak vybereme vybereme ty, které jsou pro obě čísla společné. NSD je pak jejich součin.
Příklad 1.5 Určete NSD čišel 153 a 258. Platila = 32.17 a 258 = 2.3.43. Je tedy (153,258) = 3.
Ne vždy se nám podaří najít NSD tak jednoduše, zejména pro velká čísla je mnohdy obtížné najít byť jednoho dělitele, natož provést jeho rozklad na prvočinitele, příkladem budiž čísla Ferma-tova, o nichž se více dozvíte v oddíle 5. 2. Ptejme se tedy, zda pro nalezení NSD neexistuje nějaký jiný postup; ideální by bylo, pokud by se jednalo o algoritmus. Odpověď zní, že takový algoritmus existuje a je pojmenován po řeckém matematikovi Eukleidovi.2
Mějme tedy přirozená čísla a a b, bez újmy na obecnosti můžeme předpokládat, že a > b. Podle věty (1. 1) platí a = bq + r. Společný dělitel čísel a a b musí dělit také zbytek r = a — qb a tedy každý společný dělitel čísel b a r je rovněž dělitelem čísla a. Platí
(a, b) = (b,q).
Zavedeme-li označení a = n0, b = rii a r = n2, má tato rovnice tvar
(n0,ni) = (ni,n2).
Nyní mohou nastat dva případy: Je-li n2 = 0, je n\ hledaný největší společný dělitel čísel n0 = a ani = b. Je-li n2 Ý 0, musíme dělit číslo ni číslem n2 a celý proces zopakovat. Obdržíme systém rovností
2Eukleides z Alexandrie žil ve 3. století př. Kr. Působil v alexandrijském Múseionu (domu Múz). Je autorem díla Základy, v němž shrnul veškeré tehdejší matematické vědomosti.
(n0,ni) (ni,n2) (n2,n3)
(ni,n2) (n2,n3) (n3,n4)
(nk-i,nk)
(nk,nk+i)
10
KAPITOLA 1. TEORIE DĚLITELNOSTI
Jelikož je rii+i je zbytek po dělení n^i číslem rii pro (i = 1,2,... ,k) a množina N je dobře uspořádaná, musí platit
rii > n2 ■ ■ ■ > 0.
Musí být rik+i = 0 a (nk-i,nk) = nk. Podle předchozích úvah obdržíme
(n0,ni) = (ni,n2) = ... = (nk-i,nk) = nk,
odkud
(n0,ni) = (a, b) = nk. NSD je tedy největší nenulový zbytek v Eukleidově algoritmu.
Příklad 1.6 Určete největší společný dělitel čísel 1512 a 110.
Řešení: Použijeme Eukleidův algoritmus postupného dělení, čímž obdržíme 1512 = 13 x 110 + 82; 110 = 1 x 82+ 28; 82 = 2x28 + 26; 28 = 1 x 26 + 2; 26 = 2 x 13. (1512,110) = 2.
Příklad 1.7 Určete největší společný dělitel čísel 988 a 35.
Řešení: Podobně jako v předchozím příkladě využijeme Eukleidův algoritmus. 988 = 28 x 35 + 8; 35 = 4 x 8 + 3; 8 = 2 x 3 + 2; 3 = 1x2 + 1; 2 = 1x1 + 1; 1 = 1x1 + 0. (988,35) = 1, tato čísla jsou nesoudělná.
Příklad 1.8 Dokažte, že dvě po sobě jdoucí čísla jsou nesoudělná. Řešení: (a, a + l) = (a, a + 1 — a) = (a, 1) = 1.
1.3   Prvočísla a čísla složená
V této části se seznámíme s pojmem prvočíslo a číslo složené. Dále uvedeme základní větu aritmetiky a některé aplikace.
Def. 1.2 Uvažujme přirozená čísla větší než jedna. Každé má alespoň dva dělitele, totiž jedničku a sebe sama. Nenajdeme-li již žádného dalšího dělitele, pak se toto číslo nazývá prvočíslo. V opačném případě mluvíme o číslech složených.
1.3. PRVOČÍSLA A ČÍSLA SLOŽENÁ
11
Jedničku nezařazujeme ani do jedné skupiny, přesně v souladu s pythagorejskou školou. Ačkoliv se zdá, že se jedná jen o matematickou hříčku, byť velmi krásnou, není tomu tak. Umění rozeznat prvočíslo a číslo složené má v praxi velký význam, jak o tom bude pojednáno v dalším textu. Použití slova umění není od věci, neboť zejména má-li číslo velký počet cifer, je jeho rozklad na součin prvočinitelů (faktorizace) mnohdy velmi obtížný.
Pro malá čísla můžeme využít Eratosthenova súa3. Dejme tomu, že máme nalézt všechna prvočísla menší než 100. Všechna čísla seřadíme podle velikosti a nejprve ponecháme dvojku a vyškrtáme všechny její násobky. Po této operaci je prvním nevyškrtnutým číslem trojka, vyškrtáme tedy všechny její násobky (pokud nejsou již vyškrtnuty při předchozí operaci). Tímto způsobem postupujeme tak dlouho, až narazíme na nevyškrtnuté číslo větší než deset, to již škrtání končí a všechna nevyškrtnutá čísla jsou prvočísla. Možná se ptáte, proč neškrtáme násobky čísla jedenáct. Inu je to proto, že máme jistotu, že jsou již škrtnuty. Obecně lze říci, že hledáme-li prvočísla tímto způsobem, tak eliminace končí při nalezení prvočísla většího než je y/n, kde n je největší číslo na seznamu.
Věta 1.8 (První věta Eukleidova). Nechť a, b G N, p je prvočíslo a p\ab. Pak p\a nebo p\b.
Důkaz: Jestliže p\a, jsme s důkazem hotovi. Pokud p nedělí a, je (a,p) = 1. Pak existují celá čísla x a, y tak, že platí ax + py = 1. Vynásobíme-li obě strany této rovnice číslem b, obdržíme abx + pby = b. Jelikož oba sčítance na levé straně jsou dělitelné p, musí být dělitelné číslem p i číslo b.
Důsledkem je skutečnost, že každé přirozené číslo n > 1 lze jednoznačně rozložit na součin přirozených mocnin prvočísel p\ < P2 < ■ ■ ■ < pr- Platí tedy
r
i=i
3Eratosthenes z Kyrény, mezi 272 a 276-194 př. Kr., řecký matematik, astronom, geograf, ale též básník a správce alexandrijské knihovny. Hledání prvočísel prováděl na voskových tabulkách, čísla nevyškrtával, ale vymazával, takže tabulka pak skutečně připomínala síto. Změřil též zemský poloměr.
12
KAPITOLA 1. TEORIE DĚLITELNOSTI
Prvočíslo pi se nazývá prvočínítel. Následuje věta o jednoznačnosti rozkladu čísla na prvočinitele.
Věta 1.9 Jestliže
VlV2   ■■■Vr    = <R $2   •••<fs ,
kde pi < P2 < ••• < pr,Qi < Q2 < ••• < Qs Jsou prvočísla a r, s, ai,/3i G N, pak r = s, pi = qi, on = fy pro každé i = 1,... ,r.
Důkaz: Nechť m = p^p^2 • • 'Prri n = Qi1(l22 ''' Qs3 a nechť m = n. Jestliže nějaké prvočíslo p dělí m, pak podle První Eukleidovy věty prvočíslo p musí dělit pk pro nějaké k G {1,..., r}. Z definice prvočísla však plyne, že p = p^. Protože m = n, musí p dělit také nějaké qi pro / G {l,...,s} a stejným způsobem dostaneme, že p = qi. Odtud plyne, že pk = qi- Jelikož prvočísla pi a qj jsou seřazena podle velikosti, musí platit p\ = q±,... ,pr = qr ar = s.
Předpokládejme dále, že aľ > fy pro nějaké i G {l,...,r}. Vydělíme-li rovnost m = n číslem př\ obdržíme
nai . . . nOLi^^i . . . nar — rP1 . . . n° . . . rPr
Pl p,i pr    — Pi p,i        pr ,
což je spor, neboť levá strana rovnice je dělitelná pi, zatímco pravá strana tímto číslem dělitelná není. Analogicky postupujeme v případě, že on < fy. Je tedy     = fy pro všechna i G {1,..., r}.
Věta o jednoznačnosti rozkladu přirozeného čísla na prvočinitele se nám zdá samozřejmá, existují však algebraické struktury, v nichž neplatí. Například v tělese Q(iy/E) tato věta neplatí, neboť 21 = 3-7 a (1 + 2i\/5)(l — 2iv/5)• Základní věta aritmetiky je také jedním z důvodů, proč nepovažujeme jedničku za prvočíslo. Pokud by tomu tak bylo, tak by v rozkladu nebyla jednoznačnost exponentů.
Položíme-li si otázku, kolik je prvočísel, odpověď nalezneme v Eukleidových základech, kniha 9, tvrzení 20. Toto tvrzení uvedeme nejdříve v moderním znění.
Věta 1.10 (Druhá Eukleidova věta.) Prvočísel je nekonečně mnoho.
Důkaz: Důkaz provedeme sporem. Budeme předpokládat, že prvočísel je konečně mnoho. V tom případě je můžeme vyjmenovat, budou to čísla pi,P2, ■ ■ ■ ,pn- Vynásobme je mezi sebou a připočtěme
1.3. PRVOČÍSLA A ČÍSLA SLOŽENÁ
13
jedničku. Takto vzniklé číslo m = p\P2---pn + 1 není ani jedno z uvedených prvočísel, ani není některým z těchto prvočísel dělitelné. Dělíme-li totiž číslo m kterýmkoliv z uvedených prvočísel pi, obdržíme vždy zbytek jedna. Je zde spor a proto je prvočísel nekonečně mnoho.
Poznamenejme, že zkonstruované číslo m je někdy prvočíslo (2.3.5.7+1=211), jindy je to zase číslo složené (2.3.5.7.11.13+1 = 30 031=59.509). Podíváme-li se do Základů, zjistíme, že Eukleides tuto větu uvedl v poněkud jiném tvaru. Jelikož řečtí matematikové pojem nekonečna ve smyslu jak ho chápeme dnes nepoužívali, museli věty formulovat opisem. Tvrzení tedy zní: Prvočísel je víc, než dané množství prvočísel. Důkaz pak je stejný, jak je uvedeno výše, jen počet známých prvočísel je mnohem nižší, Eukleides si vystačil se třemi.
1.3.1   Pythagorejské trojice
Pythagorovu větu ovládá každý, kdo se jen trochu potkal s geometrií. Každý zedník si umí udělat vingl (pravý úhel) tak, že tři latě s délkami v poměru 3:4:5 spojí v trojúhelník a ví, že hledaný pravý úhel je oproti nejdelší lati. Pythagorova věta se obvykle uvádí slovně, říkáme že obsah čtverce nad přeponou se rovná součtu obsahů čtverců nad oběma odvěsnami. Takto formulované tvrzení má ovšem tvar implikace a Pythagorova věta nás ke konstrukci pravého úhlu výše uvedeným způsobem neopravňuje. Dá se však dokázat, že i obrácená implikace je správná, platí tedy následující věta:
Věta 1.11 Trojúhelník s délkami stran a, b, c je pravoúhlý s přeponou délky c právě tehdy, když platí c2 = a2 + b2.
Def. 1.3 Nechi pro uspořádanou trojici čísel [a, b, c] platí a2 + b2 = c2. Tuto trojici nazýváme pythagorejská trojice a trojúhelník s těmito délkami stran pythagorejský trojúhelník. Jestliže navíc tato čísla nemají společného dělitele d > 1, mluvíme o primitivní pythagorejské trojici.
14
KAPITOLA 1. TEORIE DĚLITELNOSTI
Odpověď na otázku jak sestavit libovolnou pythagorejskou trojici nalezneme již u Diofanta.4.
Věta 1.12 Uspořádaná trojíce přirozených čísel [a,b,c] je primitivní pythagorejskou trojicí tehdy a jen tehdy, existují-li nesoudělná přirozená čísla m > n opačné parity tak, že buď
a = m2 — n2,       b = 2mn,       c = m2 + n2
nebo
a = 2mn,       b = m2 — n2,       c = m2 + n2. Čísla man jsou určena jednoznačně.
Důkaz není obtížný, avšak pro jeho délku odkazujeme čtenáře např. na publikaci [2]. Ani Diofantos nebyl první, kdo se zabýval těmito trojicemi, jejich tabulky byly používány již ve staré Ba-bylónii. S pythagorejskými trojicemi se v teorii čísel setkáváme poměrně často. Závěrem uvedeme jednu jejich aplikaci, kterou poprvé uvedl (a zřejmě i dokázal) P. Fermat.
Věta 1.13 Žádné číslo tvaru Ak — 1 pro k E N není součtem dvou čtverců celých čísel.
Důkaz: Důkaz je snadný, pokud si uvědomíme, že sudé číslo je tvaru 21 a liché 2m + 1. Jejich čtverce jsou pak AI2, resp. Am2 + Am + 1 = An + 1. Součet dvou čtverců může být tvaru Ak, Ak + 1 či Ak + 2, nikdy nemůže být tvaru Ak + 3 = A{k + 1) — 1. Z výše uvedeného vyplývá, že číslo tvaru Ak — 1 není ani čtvercem celého čísla.
1.4   Vlastnosti prvočísel
Úvodem rozšíříme definici dělitelnosti.
Def. 1.4 Pro přirozená čísla j, man řekneme, že m? přesně dělí n, a budeme psát mJ'||n, jestliže ny>\n, ale mi+1 )(n. Pro j = 0 bude symbol m°||n znamenat, že m)fn.
4Diofantos z Alexandrie žil ve 3. století. Z jeho hlavního díla Aritmetika se zachovala jen část.
1.5. ÚLOHY K PROCVIČENÍ
15
Dokážeme větu, která uvádí vztah mezi prvočísly a binomickými koeficienty (kombinačními čísly).
Věta 1.14 Přirozené číslo n je prvočíslem právě tehdy, když n nedělí (™) pro každé k G {1,... ,n — 1}.
Důkaz: Nechť n je prvočíslo. Pro k E {1,... ,n — 1} je n — k mezi čísly 1 a n — 1. Číslo n nedělí ani k\ ani (n — k)\, ale dělí n\. Jelikož (fc) = fc!(n-fc)!' Je čísl° dělitelné n. Předpokládejme naopak, že n je složené a nechť p je nejmenší prvočíslo, které dělí n. Tedy je 1 < p < n a
n{n-l)---{n-p+l)
p(p- l)---2- 1      ' 1 ' J
Dále předpokládejme, že pro nějaké přirozené číslo j. Mezi
p postupně jdoucími čísly n, n — 1,..., n — p + 1 je právě jedno dělitelné p. Protože p | n, platí p/f (n — l)(n — 2) • • • (n — p + 1). Platí tedy p3 \\n(n — 1) • • • (n — p + 1) a zřejmě i p||p(p — 1) • • • 2 • 1. Podle (1. 2) dostaneme, že p^H (n). Ale n)( (n), protože p5
1.5   Úlohy k procvičení
1.1. Druhou mocninu každého přirozeného čísla je možné napsat buď ve tvaru 4A; nebo 4A; + 1. Dokažte.
1.2. Jestliže současně platí a\b a 6|a, pak je \a\ = \b\. Dokažte.
1.3. Otec se synem jeli na dovolenou z Brna do Chorvatska autem. Jelikož cesta je dlouhá, rozhodli se, že se budou každých 80 km v řízení střídat. Kdo řídil auto při příjezdu do Splitu, je-li vzdálenost Brno - Split 888 km?
1.4. Nechť a — b je násobkem čísla c. Pak i an — bn je násobkem c.
1.5. Dokažte, že pro libovolné přirozené číslo n platí 9|4n + 15n — 1.
1.6. Dokažte, že rozdíl čtverců dvou po sobě jdoucích lichých čísel je dělitelný osmi.
16 KAPITOLA 1. TEORIE DĚLITELNOSTI
1.7. Součet tří po sobě jdoucích třetích mocnin přirozených čísel je násobkem čísla 9. Dokažte.
1.8. Součet čtverců dvou po sobě jdoucích čísel zmenšený o jednu je dělitelný čtyřmi. Dokažte.
1.9. Číslo n3 + lln je dělitelné šesti pro libovolné n. Dokažte.
1.10. Číslo 22n+1 + 1 je dělitelné třemi. Dokažte.
1.11. 25/1 Výraz n(n4 + 35n2 + 24) je dělitelný 60 pro každé celé n. Dokažte.
1.12. Dokažte, že výraz 22n+3.7n + 3n.5n+1 je dělitelný 13.
1.13. Dokažte, že výraz V = n2(n2 — 4)(n2 — 16) je pro sudé n dělitelné 11520.
1.14. Dokažte, že žádné prvočíslo větší než 5 nelze uvést na tvar N = nŕ + 4n4.
1.15. Dokažte, že čísla tvaru 34n+4 — 43^+3 jgou dělitelná 17.
1.16. Dokažte, že číslo n +(>+2) je pro cej^ n vždy celé a složené.
1.17. Dokažte, že výraz V = 24n+1 — 22n — 1 je dělitelný devíti pro všechna n G N.
1.18. Dokažte, že žádné číslo An = 4n + 5 není současně dělitelné 7 a 9.
Výsledky
1.1. Stačí si uvědomit, že přirozená čísla jsou buď sudá tvaru 2k nebo lichá tvaru 2k — 1, k G N.
1.2. a\b =^ b = ka, b\a =^ a = Ib. Je tedy b = k(lb). Čísla a a b jsou tedy buď stejná nebo opačná.
1.3. 888=11x80+8. Při příjezdu do Splitu řídil ten, kdo neřídil při odjezdu z Brna.
1.5. ÚLOHY K PROCVIČENÍ
17
1.4. an - bn = (a - 6)(a™-1 + an-2b + ■■■ + b"1-1).
1.5. Důkaz provedeme indukcí. Pro n = 1 tvrzení platí. Volba n = k+1 dává po úpravě Ak + 15k— l+3.4fc+15. První tři členy jsou podle předpkoladu dělitelné devíti, další dva upravíme následovně. 3(4fc - 1 + 6) = 3(4 - l)(4fc-1 + 4fc~2 + • • • + 1)
1.6. (2k + l)2 - (2k- l)2 = 8k
1.7. (n— l)3 + n3 + (n +1)3 = 3n(n2 + 2). Je-li 3\n, jsme s důkazem hotovi. V opačném případě je n = 3k + 1, resp. n = 3k + 2 a snadno se dokáže, že výraz v závorce je dělitelný třemi.
1.8. (n + l)2 + n2 - 1 = 2n(n + 1)
1.9. n3 + lln = n(n2 - 1 + 12) = (n - l)n(n + 1) + 12n. Lze použít i matematickou indukci. První krok je zřejmý, volba n = k + 1 dává po úpravě k3 + 3A;2 + 3A; + 1 + llk + 11. Výraz 3(A;2 + A; + 4) je dělitelný šesti, neboť druhá mocnina zachovává paritu a součet dvou lichých čísel stejně jako součet dvou sudých čísel je číslo sudé.
1.10. 22n+1 + l = 2(2n-l)(2n + l) + 3. Čísla v závorkách se liší o dvě a jsou lichá. S využitím známých vzorců pro rozklad součtu druhých mocnin zjistíme, že právě jedno z nich je dělitelné třemi. Pro n sudé je to to menší, pro n liché to větší.
1.11. Výrazy A = n(n + l)(n + 2)(n + 3)(n + 4) a B = n(n-l)(n-2)(n — 3)(n — 4) jsou dělitelné 120, neboť představují součin pěti po sobě jdoucích celých čísel. Jejich aritmetický průměr je roven zadanému výrazu a ten je tudíž dělitelný 60.
1.12. Výraz upravíme 8.4n.7n+5.3n.5n=13.28n-5.28n+5.13n=13.28n-5(28n — 15n). Oba sčítance jsou dělitelné 13.
1.13. n = 2k. V = 64fc2(jfc2 - 1)(A;2 - 4) = 64A;2(A; - l)(jfc - 2)(jfc + 1)(A; +2).Součin pěti po sobě jdoucích čísel je dělitelný 3, 4, 5. Navíc trojka je v něm obsažena dvakrát. Buď je k = 31 nebo jsou trojkou dělitelné současně výrazy k — 2&k + lčik — 2a k + 1. Výraz V je tedy dělitelný číslem 64x9x4x5 = 11520.
18
KAPITOLA 1. TEORIE DĚLITELNOSTI
1.14. Číslo N = (m2 + 2n2)2 — Am2n2, což lze psát jako N = [(m + n)2 + n2] [(m — n)2 + n2]. Jelikož N je prvočíslo, musí být buď první nebo druhá závorka rovna 1. To je možné jen pro n = 0 a m = 1 nebo m = n = 1. První možnost dává iV = 1, druhá pak N = 5.
1.15. 34«+4_43n+3= 81n+1-64n+1 = (81-64)(81n + 81n-1x64 + ...).
1.16. Použijeme-li známý vzorec pro rozklad součtu třetích mocnin, obdržíme "3+(^+2)3 = (n + i)(y + 2n + 4).
1.17. V = 2.24n-2.22n+22n-l=(22n-l)(22n+1 + l). Opět využijeme vzorce pro rozklad součtu či rozdílu mocnin. Navíc pro n = 3k a n = 3k + 1 je dělitelný 27.
1.18. Je-li číslo současně dělitelné 7 a 9, je dělitelné 63 = 43 — 1. Platí 4n+5 = 43(4n-3+5)-5(43-l),tedy An = 64An_3-5.63. An tedy bude dělitelno 63 když i An^ bude dělitelno 63. Ale ani jedno z čísel Aq = 6, A\ = 9 a A2 = 21 není dělitelno 63.
Kapitola 2
Některé funkce používané v teorii čísel
V této kapitole se zmíníme o některých funkcích, které se zhusta používají v teorii čísel. I my se v tomto textu budeme s těmito funkcemi setkávat, je proto nutné, abychom poznali jejich definici a základní vlastnosti.
2.1   Funkce [x], {x}
První funkcí, s níž se seznámíme, je celá část, kterou označujeme která je definována následujícím způsobem:
Def. 2.1 Celá část reálného čísla x jako nejvčtší celé číslo, které není vetší než x.
Tak například [10] = 10, [16,12] = 16 a [7r]=3. Uvedeme i příklady pro čísla záporná. [-4] =-4, [-5,2] =-6. Všimněme si, že pro čísla kladná je celá část v absolutní hodnotě vždy menší nebo rovna absolutní hodnotě daného čísla, kdežto u čísel záporných je tomu naopak. Je to obdobné jako v případě dělitelnosti čísel. Dělíme-li dvě kladná čísla, je součin dělitele a (neúplného) podílu vždy menší nebo roven dělenci. Dělíme-li naproti tomu záporné číslo kladným, je absolutní hodnota součinu dělitele a (neúplného) podílu vždy větší nebo rovna absolutní hodnotě dělitele.
19
20KAPITOLA 2. NĚKTERÉ FUNKCE POUŽÍVANÉ V TEORII ČÍSEL
Aby se desetinná část reálného čísla necítila odstrčená, definujeme i lomenou část čísla x.
Def. 2.2 Lomená část reálného čísla x je rozdíl x — [x]. Lomenou část značíme {x}.
Jako příklady uvedeme čísla {4} = 0, {1,6} = 0,6 a {—6,26} = 0,74.Z definice celé a lomené části plyne, že lomená část je vždy nezáporné číslo (podobně jako zbytek), zde navíc platí 0 < {x} < 1. Jako příklad využití této funkce uvedeme následující větu.
Věta 2.1 Mocnitel, s kterým je dané prvočíslo p obsaženo v součinu n\, je roven
n
p
p-
mezi nimi je násobků čísla p3 atd.
Důkaz: Počet součinitelů součinu n\ je
násobků čísla p2, mezi těmito pak zase
Součet uvedených čísel tedy dá uvedeného mocnitele, neboť každý činitel součinu n\, který je násobkem čísla pm, avšak ne čísla pm+1, počítá se uvedeným způsobem m—krát jako násobek prvočísel p, p2,
„m 1 . . . , jj .
Příklad 2.1 V čísle 5! je prvočíslo 2 s exponentem 3, neboi [|] + [|] =2 + 1 = 3. Snadno se vidí, že 5! = 600 = 23.3.52. V čísle 57! je pětka s exponentem [y] + [||] = 11 + 2 = 13. Jelikož třináctka je považována za číslo nešťastné, ověření přes kanonický rozklad dělat nebudeme, čtenáři v tom však nebránime.
2.2   Součty vztahující se na dělitele čísla
Velmi důležitou úlohu v teorii čísel hrají multiplikativní funkce. Tyto funkce můžeme definovat následujícím způsobem:
Def. 2.3 Funkce ů(a) se nazývá multiplikativní, je-li definována pro všechna přirozená čísla, přičemž alespoň pro jednu hodnotu a je nenulová. Současně musí platit ■í?(a1a2) = ^(01)^(02); Je~^ (a1;a2) = 1.
1V publikaci [11] jsou exponenty mylně uvedeny jako koeficienty.
2.2. SOUČTY VZTAHUJÍCÍ SE NA DĚLITELE ČÍSLA
21
Příkladem multiplikativní funkce je mocnina přirozeného čísla, neboť platí afa^ = («102)5• S dalšími multiplikativními funkcemi seznámíme čtenáře v další části kapitoly, než však k tomu dojde, uvedeme ještě některé další vlastnosti multiplikativní funkce.
Věta 2.2 Nechť ů(a) je multiplikativní funkce. Pak platí$(1) = 1.
Důkaz: Podle definice musí existovat alespoň jedno přirozené číslo, pro něž je funkce nenulová, nechť je to oq- Pak máme ů(clq) = ů(l.a0)=ů(l)ů(ao).
Věta 2.3 Nechiů^a) aů2(a) jsou multiplikativní funkce. Pak také funkce ůo(a) = $1 (a)$2 (o) Je funkce multiplikativní.
Důkaz: 1) ů0(l) = #i(l)tf2(l) = 1
2) Předpokládejme, že je (01,02) = 1- pak je
A)(oi02) = ^1(0102)^2(0102) = ^1(01)^1(02)^2(01)^2(02) =
= ^1(01)^2(01)^1(02)^2(02) = $0(01)^0(02)-
Věta 2.4 Nechť ů(a) je multiplikativní funkce a a = Piľp22 .. .pkh je kanonický rozklad čísla a. Pak platí
J2$(d) = (l + ^(pi)+^(p2) + ... + ^(Pife))...
d\a
(l+^+tf(p2) + ...+tf(pf)). (2.1) Je-li a = 1, pak i pravá strana je rovna jedné.
Důkaz: Roznásobíme-li výraz na pravé straně, dostaneme součet sčítanců tvaru
. .. ů(pl*) = ů(j£pfc . . . (p^);
0 <(31<a1,      0< (32<a2,...,      0 < (3k < ak,
přičemž ani jeden takový sčítanec nebude vynechán a ani se nebude opakovat, takže součty na levé i na pravé straně budou stejné.
22KAPITOLA 2. NĚKTERÉ FUNKCE POUŽÍVANÉ V TEORII ČÍSEL
Je-li ů(a) = as, má předchozí rovnost tvar
= (i+pi+pis+...+Pan...a+rf+pis+■■+pan (2.2)
d\a
Položíme-li s = 1, je levá strana rovnice (2.1) rovna součtu všech dělitelů čísla a, který označíme a (a). Pravou stranu lze zjednodušit, takže obdržíme vztah pro součet všech dělitelů čísla a:
«1 + 1 _  1       „«2+1 _  1 r)ak + 1 _ 1
a(a) = *--± ■ ^--± ■ ■ - *--1. (2.3)
Pl - 1 P2 - 1 Pfc - 1
Položíme-li s = 0, je levá strana rovnice (2.1) rovna počtu dělitelů čísla a, který označíme r (a). Počet všech dělitelů tedy určíme podle vzorce
r(a) = (a1 + l)(a2 + l)...(afc + l) (2.4)
Příklad 2.2 Nechť a = 36. PaA; je/zo kanonický rozklad je 36 = 2232 a jeho dělitelé jsou čísla 1,2, 3,4, 6, 9,12,18, 36. Sečteme-li tato čísla, obdržíme 91. Nu a toto číslo dostaneme i použijeme-li pravou stranu předchozího vzorce ^^^f-~r- Sečteme-li všechny dělitele jako kusy, dostaneme se k číslu 9. Ale také je (2 + 1)(2 + 1) = 9.
S funkcemi a(a) a r(a) se budeme setkávat v dalším textu.
2.3   Möbiova funkce
2
Po přečtení definice Möbiovy3 funkce může se zdát, že je pro teorii čísel zbytečnou. Následující text ukáže, že tomu tak není.
Def. 2.4 Nechť a je celé kladné číslo. Möbiova funkce //(a) je definována následujícími rovnostmi: //(a) = 0 je-li a dělitelné druhou mocminou přirozeného čísla n > 1 a //(a) = (—l)k v opačném případě. Číslo k udává počet prvočinitelů čísla a.
2August Ferdinand Möbius (1790-1868), německý matematik a astronom. Nejznámější je po něm pojmenovaná páska, která má jen jednu stranu. Je vzdáleným potomkem Martina Luthera
3 Möbius
2.4. EULEROVA FUNKCE
23
Příklad 2.3 Môbiova funkce má pro všechna prvočísla hodnotu —1, např. /x(2) = — 1. Pro libovolnou mocninu prvočísla je tato funkce rovna nule, ke stejnému výsledku se dobereme i v případě, že kanonický rozklad čísla a obsahuje alespoň jednu mocninu prvočísla. Je tedy /x(9) = 0, /x(343) = 0, /x(245) = 0. V ostatních případech už musíme počítat prvočinitele, je tedy /x(39) = 1, /x(110) = —1 aíd. Jelikož číslo jedna na součin prvočísel být rozloženo nemůže,
Věta 2.5 Nechť ů(a) je multiplikativní funkce a a = p^p^2 ■ ■ - Vk je kanonický rozklad čísla a. Pak platí
5>(d)0(d) = (1 - 0(pi))(l - ů(pl))... (1 - í?(pfc)). (2.5)
Je-li a = 1, pak i pravá strana je rovna jedné.
Důkaz: Funkce //(a) je zřejmě multiplikativní, proto je multiplikativní i funkce $i(a) = ii(a)ů(a). Využijeme-li na tuto funkci identitu (2.1) a uvážíme-li, že $i(p) = —$(p) a $i(ps) = 0 pro s > 1, jsme s důkazem hotovi.
Důsledek 2.1 Volíme-li ů(a) = 1, obdržíme
je /i(l)=0.
íí|a
a > 1 a = 1
(2.6)
Důsledek 2.2
a > 1
(2.7)
2.4   Eulerova funkce
Tato funkce se bude v tomto textu vyskytovat velmi často, je tedy nejvyšší čas, abychom ji definovali a uvedli některé její vlastnosti.
24KAPITOLA 2. NĚKTERÉ FUNKCE POUŽÍVANÉ V TEORII ČÍSEL
Def. 2.5 Eulerova funkce tp(a) je definována pro všechna přirozená čísla a jako počet těch čísel posloupnosti O,1,..., a — 1 která jsou nesoudělná s a.
Příklad 2.4        = 1, <p(2) = 1, y?(6) = 2, y?(7) = 6, y?(9) = 7, V?(13) = 12.
Ve výše uvedených příkladech jsme hodnotu Eulerovy funkce stanovili přímo z definice. V případě velkých čísel by tento postup nebyl vhodný, je tedy na místě otázka, zda nelze hodnotu této funkce stanovit jiným způsobem. Tento problém řeší následující věta.
Věta 2.6 Nechť a = p^p^2 ■ ■ - P^ je kanonický rozklad čísla a. Pak platí
Důsledek 2.3 Je-li p prvočíslo, pak je ip(p) = p — 1 a tp(pa) =
_
Příklad 2.5 y?(14) = 14(1 - ±)(1 - ±) = 6 V?(512) = 83 - 82 = 448 V?(ll) = 11 - 1 = 10
Důsledek 2.4 Eulerova funkce je multiplikativní.
2.5   Příklady k procvičení
2.1. Vypočtěte mocnitele, s nímž je číslo 3 obsaženo v kanonickém rozkladu 1024!
2.2. Nalezněte kanonický rozklad čísla 18!
2.3. Vypočtěte tr(51450) a r(51450)
2.4. Vypočtěte y?(41) a ^(1786050)
2.5. PŘÍKLADY K PROCVIČENÍ
25
2.5. Kanonický rozklad čísla je tvaru 2a.7b, součet dělitelů pak 6000. Určete ono číslo.
2.6. Stanovte nejmenší kladné číslo n = 2e.p1.p2 ..., tak aby součet jejich dělitelů byl 2n, 3n, 5n. pi jsou lichá prvočísla. 18/34. Návod k řešení: Pro součet dělitelů platí
Vzhledem k tomu, že číslo n je dělitelné 2e, je zřejmé, že prvočísel pi musí být právě g. Prověříme jednotlivé možnosti.
Výsledky
2.1. 508
2.2. 216.38.5.7.11.13.17
2.3. o-(51450) = 148800, r(514500) = 48
2.4. 40, 408240
2.5. 6000 = Po úpravě máme 25.32.52 = (2a+1)(7b+1). První závorka musí být liché číslo a navíc o jednu menší než libovolná mocnina 2. Tomuto vyhovuje číslo 15 a a = 4. Zbývají 4000, což je zase číslo o jedničku menší než čtvrtá mocnina sedmi, tedy 6 = 3.
S(n)
2-1 px-ť^-l
po uprave
1)(P1 + 1).(P2 + 1)....
26KAPITOLA 2. NĚKTERÉ FUNKCE POUŽÍVANÉ V TEORII ČÍSEL
Kapitola 3 Diofantické rovnice
V nej starší česky psané matematické učebnici, jejímž autorem je Ondřej Klatovský a která vyšla v roce 1530, nalezneme tuto úlohu: Dvacet šest osob na jednom kvasu propilo 88 penízků bílých. Při tom kvase byli muži, ženy a panny. Z mužů jedna osoba dáli měla šest penízků, z žen čtyři penízky a z pannen dva. Kolik jest při tom cechu aneb kvasu mužů bylo, kolik žen a kolik pannen. Potlačme rozhořčení, že se tohoto kvasu zúčastnily i nevinné panny a pusťme se chutě do řešení. Tak jak je dnes zvykem, označme počet mužů x, počet žen y a konečně počet pannen z. Tímto získáme první rovnici x + y + z = 26. Spočítáme-li této povedené společnosti útratu, dojdeme k druhé rovnici 6x + Ay + 2z = 88. Vyjádříme-li z první rovnice z a dosadíme-li do rovnice druhé, obdržíme po úpravě rovnici 2x + y = 18. Vidíme, že ač máme jednu rovnici, neznámé jsou dvě. Takovým rovnicím, v nichž se vyskytuje více neznámých, budeme říkat rovnice neurčité. Daleko častěji se však užívá název rovnice diofantické, a to na počest řeckého matematika Diofanta z Alexandrie, který se jimi zabýval.
3.1   Lineární diofantické rovnice
Abychom dovedli problém staročeské hostiny ke zdárnému konci, budeme se v této části zabývat rovnicemi tvaru
ax + by = c,
27
28
KAPITOLA 3. DIOFANTICKÉ ROVNICE
kde a, b, c jsou celá čísla, a, b ^ 0. Označme dále (a, b) = d největší společný dělitel čísel a a b.
Nejdříve se budeme zabývat nej jednodušším případem, kdy c = 0. Položme A = 2, B = 2- Rovnici (3.1) převedeme na tvar
x       b B y       a A'
přičemž poslední zlomek jev základním tvaru.
Věta 3.1 Všechna celočíselná řešení rovníce ax + by = 0 jsou dvojíce čísel tvaru x = Bt, y = —At, kde t je libovolné celé číslo.
Důkaz tvrzení přenecháváme čtenářům jako cvičení. Příklad 3.1 Řešte rovnici 10rr — 6y = 0.
Jelikož (10,6) = 2, jsou řešením všechny dvojice čísel x = —|ŕ = —3t, y = — y ŕ = — 5t, kde t je libovolné celé číslo.
Nyní obrátíme svou pozornost k případu c ^ 0. Nejprve se podíváme, kdy má rovnice řešení.
Věta 3.2 Rovnice ax + by = c má řešení právě tehdy, když (a, b)\c.
Důkaz: Předpokládejme nejdříve, že daná rovnice má řešení, které označíme xq a í/o, platí tedy axo + byo = c. Z vlastností čísla d = (a, b) plyne, že dělí levou stranu rovnice, musí tedy dělit i pravou.
Předpokládejme nyní, že d\c. V tom případě musí existovat celá čísla Xq a í/o taková, že platí ax0 + by0 = d. Dále platí c = de, kde e je nějaké číslo. Položme X\ = ex0 a yľ = ey0. Zřejmě platí
ax\ + byi = e(axo + byo) = ed = c.
Čísla X\ a yi jsou řešením rovnice (3.1), čímž je důkaz ukončen.
Hledejme nyní způsob, jak rovnici (3.1) vyřešit. Jednou z možností je využití Eukleidova algoritmu a postup ukážeme na konkrétním příkladě. Nejprve si ukážeme, jak vypadá řešení, je-li c = (a, b).
3.1. LINEÁRNÍ DIOFANTICKÉ ROVNICE
29
Příklad 3.2 Řešte rovnicí 21x + 15y = 3.
Jelikož (21,15) = 3; má tato rovnice řešeni. Největší společný dělitel čísel 21 a 15 nalezneme Eukleidovým algoritmem.
21 = 15.1 + 6
15 = 6.2 + 3 6 = 3.2 + 0
Z předposlední rovnice vyjádříme 3, tedy největšího společného dělitele čísel 21 a 15. Máme
3 = 15.1+ 6.(-2) (3.2)
Nyní vyjádříme z první rovnice 6 a dosadíme do (3.2), čímž obdržíme
3 = 15.1 + [21.1 + 15(-l)].(-2) = 21.(-2) + 15.3. Jedním z řešení dané rovnice je tedy x = —2 a y = 3.
Množina řešení diofantické rovnice se nezmění, vydělíme-li všechny jejich koeficienty jejich společným dělitelem. Pokud na pravé straně je jiné číslo než d a je-li rovnice řešitelná, musí být c = ed. Najdeme tedy nejprve řešení rovnice kdy pravá strana je d a nalezené řešení pak vynásobíme číslem e.
Příklad 3.3 Řešte rovnici 21x + 15y = —6.
V předchozím příkladu jsme nalezli řešení rovnice, kdy pravá strana je rovna 3. Máme —6 = 3(—2), je e = —2 a řešení naší rovnice je x = (-2)(-2) = 4 a y = 3(-2) = 6.
Příklad 3.4 Uveďte alespoň jeden způsob, kterým lze vyplatit částku 37 Kč pouze dvoukorunovými a pětikorunovými mincemi. Máme řešit diofantickou rovnici 2x + 5y = 37. Protože čísla a a b jsou nesoudělná, tak má rovnice vždy řešení. Dáme-li na pravou stranu jedničku, je 5 = 2.2 + 1, tedy 1 = 5.1 + 2(—2) a x = —2, y = 1. Vynásobíme-li toto řešení číslem 37, získáme x = — 74 a y = 37. Řešení jsme tedy našli, jenže je pro danou úlohu nepoužitelné. Je nad slunce jasné, že se nemůžeme spokojit s tím, že umíme nalézt
30
KAPITOLA 3. DIOFANTICKÉ ROVNICE
jedno řešeni diofantické rovnice a musíme se pokusit nalézt způsob, jak najít všechna její řešení.
Jedno řešení rovnice (3.1) nalézt umíme, řekněme, že je to uspořádaná dvojice (x0; íjq). Nechi i uspořádaná dvojice (r; s) je řešením rovnice (3.1). V tom případě platí
ar + bs = c = ax0 + by q , což můžeme uvést na tvar
a(r - x0) = -b(s - y0) a po vydělení číslem d = (a, b) máme
^(r - x0) =-^(s - y0). (3.3)
Protože (|,^) = 1, je zlomek | dělitelem čísla s — yo a tedy je s — yo = it|. Podobnou úvahou zjistíme, že platí r — xq = t^, přičemž u a t jsou celá čísla. Po dosazení do (3.3) máme
a(b\=_b,au d \d )       d \d
tedy t = —u. Řešením rovnice (3.1) jsou tedy čísla
b a r = x0 + -t,       s = y0- -t,       t E Z. (3.4)
Nechi naopak ras jsou dvě libovolná čísla tvaru (3.4)■ Dosadíme-li je do rovnice (3.1), máme
(       b \     (       a \ ab ab
a\Xo + ďt}\yo~dt) = (a:Co+řW + -^-r--^-r = axo+byo = c.
Poněkud jsme přehodili obvyklý matematický postup, neboť výše uvedené úvahy jsou důkazem následující věty:
Věta 3.3 Nechi Xq\y q je řešením rovnice (3.1). Pak dvojice čísel (r, s) je jejím řešením tehdy a jen tehdy, má-li tvar (3.4)-
3.2. DIOFANTICKÉ ROVNICE VYŠŠÍHO STUPNĚ
31
Poznámka 3.1 Jsou-li oba koeficienty rovnice (3.1) záporné, je třeba ji vynásobit číslem (—1). Je-li záporný jen jeden, dejme tomu a, zavedeme substituci x = —z, čímž dostaneme rovnici s kladnými koeficienty. Po jejím vyřešení se pak vrátíme k původní neznámé.
Takto jsouce vyzbrojeni teorií, můžeme se pustit do vyřešení obou předchozích úloh. Začněme úlohou peněžní. Podle věty (3.3) budou všechna řešení ve tvaru
x = -7A + 5t,      y = 37-2t,
kde t je libovolné celé číslo. Jelikož řešením úlohy mohou být pouze čísla přirozená, snadno se přesvědčíme, že taková řešení dostaneme pouze pro t = 15,16,17,18. Úkolem bylo nalézt jakékoliv řešení, my jako správní číselní teoretici si vybereme jediné prvočíslo z nabízených možností. V tomto případě můžeme 37 Kč vyplatit pomocí jedenácti dvoukorun a tří pětikorun.
Nyní již máme peníze, a tak se můžeme vydat na kvas. I zde připadají jako řešení úlohy pouze přirozená čísla. Jelikož snadno zjistíme, že jedno z řešení rovnice je x = 0, y = 18, můžeme obecné řešení psát ve tvaru x = t, y = 18 — 2t. Snadno zjistíme, že úloze vyhovují pouze čísla t = 1,..., 8. Řešení uvedeme ve formě tabulky. ^12345678 y   16   14   12   10    8    6    4 2 z    9   10   11   12   13   14   15 16
Je zajímavé, že Klatovský uvádí pouze dvě řešení, a to případy se šesti a osmi muži. Zarážející je ovšem skutečnost, kolik pan-nen se onoho kvasu zúčastnilo, vždyť ve více než polovině případů panny kvasu kralovaly a vůbec: Podle našeho mínění bylo mnohem výstižnější mluvit ne o kvasu, nýbrž o dámské jízdě.
3.2   Diofantické rovnice vyššího stupně
V předchozí části jsme se naučili řešit diofantické rovnice lineární. Můžeme s klidným svědomím prohlásit, že dovedeme vyřešit každou lineární diofantickou rovnici o dvou neznámých, pokud ovšem řešení
32
KAPITOLA 3. DIOFANTICKÉ ROVNICE
má. Ale i o řešitelnosti těchto rovnic umíme rozhodnout jednoznačně. S řešením rovnic vyššího stupně je to ovšem mnohem obtížnější, mnohdy se spokojíme s tím, že umíme alespoň rozhodnout je-li rovnice vůbec řešitelná a jásáme, nalezneme-li alespoň nějaké řešení. Z tohoto důvodu uvedeme jen dva typy rovnic, ovšem kvantitu nahradíme kvalitou a uvedeme úplné řešení těchto typů. Některé rovnice lze převést na tvar
Předtím než ukážeme způsob řešení této rovnice, zavedeme následující pojem:
Def. 3.1 Celá čísla u a v se nazývají sdružení dělitelé čísla w, platí-li u.v = w.
Příkladem budiž čísla 2 a 5, která jsou sdruženými děliteli čísla 10, neboť 10=5.2. Nebo čísla -7 a 4 jsou sdruženými děliteli čísla -28, jelikož -28=(-7).4.
Jsou-li čísla x a y celočíselným řešením rovnice (3.5), tak čísla ax + by a cx + dy jsou celá a navíc jsou to sdružení dělitelé čísla k. Proto řešení rovnice (3.5) najdeme následujícím způsobem. Určíme nějakého dělitele čísla k, dejme tomu že to bude k\. Nalezneme sdruženého dělitele k2 a položíme
To je ovšem soustava dvou lineárních rovnic o dvou neznámých. Jeli tato soustava řešitelná, pak jsou čísla x a, y určena jednoznačně a jsou to současně řešení rovnice (3.5).
Z uvedené metody vyplývá, že rovnice typu (3.5) mohou mít nejvýš konečný počet řešení. Počet dvojic sdružených dělitelů čísla k je konečný a ke každé dvojici sdružených dělitelů přísluší buď jedno, nebo žádné řešení.
Podívejme se na rovnici
{ax + by) {cx + dy) = k
(3.5)
ax + by = k\
cx + dy = &2
y2 = k
(3.6)
Snadno se přesvědčíme, že tato rovnice není řešitelná v případě k = At + 2. Každá mocnina celého čísla je totiž buď tvaru As nebo
3.2. DIOFANTICKÉ ROVNICE VYŠŠÍHO STUPNĚ
33
4s +1. Pokud jsou obě mocniny stejného tvaru, je jejich rozdíl tvaru 41 Je-li x2 = As + 1 a y = Av, je jejich rozdíl At + 1. Je-li naopak x2 = As a y = Av + 1, je jejich rozdíl At — 1= Aw + 3. Naopak není-li A; = At + 2, je rovnice vždy řešitelná. Pro sudé A; = 4rje:r=| + la y = | — 1. Pro liché A; = 2s + 1 jsou řešením čísla i = s + la?/ = s. Podívejme se ještě na rovnici
anxn + ... + a\x + clq = ky, (3-7)
kde Oj a A; jsou celá čísla. Skutečnost, že jedna neznámá se vyskytuje pouze v první mocnině, bude pro další úvahy důležitá.
Ne každá taková rovnice má řešení, jak si ukážeme v následujícím příkladu. Zkusme vyřešit rovnici
x2 + 2 = Ay.
Již bylo zmíněno, že druhá mocnina celého čísla je buď tvaru At či At + 1. Přičteme-li k oběma tvarům dvojku, nikdy nedostaneme číslo dělitelné čtyřmi.
Nyní dokážeme jednu větu, kterou budeme potřebovat pro řešení rovnice (3.7).
Věta 3.4 Nechť x = a + kt, kde a,k, t jsou celá čísla. Je-li m G N, je xm tvaru kT + am, kde T je celé číslo.
Důkaz: Důkaz provedeme matematickou indukcí. Je-li m = 1, tak tvrzení evidentně platí. Budeme tedy předpokládat, že tvrzení platí pro m = n a dokážeme, že za tohoto předpokladu platí i pro m = n + 1.
xn+1 = (a + kt)n+1 = (a + kt)n(a + kt).
Podle indukčního předpokladu je (a + kt)n rovno kL + an, můžeme tedy pokračovat v úpravách.
(kL + an)(a + kt) = kLa + k2Lt + ktan + an+1.
Vytkneme-li z prvních tří členů k a označíme-li T = La + kLt + tan, je důkaz hotov.
Věta 3.5 Nechť (xo,yo) je řešením rovnice (3.7) a t je celé číslo. Pak ke každému číslu tvaru x = xq + kt existuje takové y, že (x, y) je řešením rovnice (3.7).
34
KAPITOLA 3. DIOFANTICKÉ ROVNICE
Důkaz: Při důkazu využijeme předchozí věty. Je-li (xo,yo) řešením rovnice (3.7), má mocnina tvar = (xQ + kt)i tvar kTj + x^. Máme tedy
an(xo + kt)n + ... + a,i(xo + kť) + a0 =
an(kTn + x%) + ... + cli{xq + kť) + a0 =
k(anTn + .. . + a1t) + (anx0l + .. , + aiXQ + ao) = kT + ky0 = k(T + y0).
Dvojice xq + H, T+yo je řešením rovnice (3.7), čímž je důkaz hotov.
Tato věta nám říká, že známe-li jedno řešení, umíme najít nekonečně mnoho řešení, které tvoří třídu. To je sice hezké, ale umíme nějakým způsobem najít alespoň jedno řešení rovnice (3.7)? Věta (3.5) má jeden pro nás důležitý důsledek. Je-li rovnice (3.7) řešitelná, pak existuje takové řešení, že | X \<\ k |. Skutečně, k daným nezáporným celým číslům xq a k existují nezáporná čísla s a r taková, že platí
Xq = \k\s + r,       0 < r < |A;|,
tedy
0 < xq — \k\s = r < \k\.
Je-li k > 0, položíme t = — s, pro k < 0 dáme t = s a obdržíme číslo X = Xq + kt < \k\. Nu a podle věty (3.5) existuje k tomuto číslu i Y takové, že dvojice (X,Y) je řešením rovnice (3.7).
Díky tomuto důsledku můžeme odehnat chmury z čela. Stačí zjistit, zda některé z čísel 0,1,..., |A;| — 1 je řešením rovnice (3.7). Pokud se nám to podaří, má rovnice (3.7) nekonečně mnoho řešení, pokud ne, řešení tato rovnice nemá.
Příklad 3.5 Řešte rovnicí x2 + 3x + 1 = Ay.
Do levé strany dosadíme postupně čísla 0,1,2,3. Výsledkem jsou čísla 1, 5,11,19 z nichž ani jedno není dělitelné čtyřmi, tato rovnice řešení nemá.
Příklad 3.6 Řešte rovnicí x2 + 2x + 4 = Ay.
Zde budeme mít již více štěstí. Dosadíme-li do levé strany postupně čísla 0,1, 2,3, obdržíme 4, 7,12,19; první a třetí čísla v této řadě jsou násobky čtyř, máme tedy dvě třídy řešení At, At + 2.
3.3. ÚLOHY K PROCVIČENÍ
35
3.3   Úlohy k procvičení
i
3.1. Z uvedených rovnic vyberte ty, které jsou řešitelné:
a)7x + 3y = 2 b) 18a: + 40y = 3 c) QAx - 72y = 44 d) 15a: + 35y = 100
3.2. Řešte rovnici 15a; - 20y = 100 Z3/40
3.3. Pro která x je výraz 17^~2 celé číslo?
3.4. Jistý stařešina vedl stočlenný rod. Po sklizni se jim rozhodl dát 100 měřic obilí, přičemž muži měli dostat 3 měřice, ženy dvě a každé dítě půl měřice. Ať řekne, kdo se domnívá, že ví, kolik bylo mužů, kolik žen a kolik dětí.
3.5. Nějaký muž chtěl za sto zlatých koupit sto zvířat. Nařídil svému sluhovi, ať je velbloud koupen za pět zlatých, osel za jeden zlatý a dvacet ovcí za jeden zlatý. Řekni kdo chceš, kolik bylo za sto zlatých koupeno velbloudů, kolik oslů a kolik ovcí.
3.6. Ani mezi kleriky nepanovala rovnost, jak se můžeme přesvědčit v této úloze: Nějaký biskup kázal rozdělit klerikům 12 chlebů. Nařídil, aby každý kněz dostal dva chleby, každý jáhen polovinu chleba a každý lektor čtvrtinu chleba, přičemž kleriků bylo stejně jako chlebů. Řekni, kdo jsi s to, kolik muselo být kněží, kolik jáhnů a kolik lektorů.
3.7. Najděte všechny dvojice navzájem různých sdružených dělitelů čísla 36.
3.8. Řešte rovnici 6x2 — 5xy + y2 = 21
3.9. Řešte rovnici 2x2 + 3xy + y2 = 35
3.10. Najděte všechna celočíselná řešení rovnice x2 — 4 = lly.
1 Úlohy 3. 4. až 3. 6. nalezl jsem v publikaci [5]. Tuto půvabnou knížečku doporučuji vaší pozornosti nejen kvůli diofantickým rovnicím.
36
KAPITOLA 3. DIOFANTICKÉ ROVNICE
3.11. Pro jaká x je výraz x3 + 2x + 2 násobkem čísla 125?
3.12. Pro jaké n je 6n + 2 třetí mocninou celého čísla?
3.13. Cvičenci nastoupili do obdélníku, přičemž na jedné straně je o pět cvičenců víc než na druhé. Po skončení cvičení nastoupili do čtyřstupu a odpochodovali z plochy. V poslední řadě však jeden cvičenec chyběl. Kolik cvičenců vystoupilo?
Výsledky
3.1. Řešitelné jsou rovnice a) a d). Ve zbývajících případech (a, b) /
c
3.2. x = -20 + At,y = -20 + 3t, t G Z
3.3. x = 1 + 15í, í G Z
3.4. m = -100 + 3t, z = 200 - 5t, t = 34,..., 39. Litera z značí ženy, tech na písmena s háčkem nadává, caparty si laskavě dopočtěte sami.
3.5. Úloha vede na řešení rovnice 99x+19í/ = 1900, kde x představuje velbloudy a y ovce. Řešení má tedy tvar x = x0 + 19í, y = í/o — 99í. Snadno uhodneme, že x0 = 0 a y0 = 100. Úloha má jediné řešení pro t = 1, tedy 19 velbloudů, osel a 80 ovcí. Zejména v poušti řešení rozumné.
3.6. Řešíme rovnici 7k + j = 36. k = 5 +1, j = 1 — 7í. Pro ŕ = 0 je řešením 5 kněží, jeden jáhen a šest lektorů. Formálně by mohlo být i řešení pro t = — 1, ale že by pan biskup chtěl krmit neexistující lektory?
3.7. -36, -1; -18, -2; -12, -3; -9, -4; 9, 4; 12, 3; 18, 2; 36, 1.
3.8. [20, 61], [4,15], [4, 5], [20, 39] a dvojice čísel s opačnými znaménky.
3.9. [—34, 69]; [34, —33]; [—2,9]; [2, 3] a dvojice čísel s opačnými znaménky.
3.10. x = 2 + lit,y = 4ŕ+ lit2 a x = 9 + llŕ,y = 7 + 18* + llí2, t G Z
3.3.
ÚLOHY K PROCVIČENÍ
37
3.11. x = 125í + 113, í G Z. Těm, kteří prověřili všech 24 možností, skládám poklonu pro pracovitost. Jinak je zřejmé, že x musí být liché. Vyjádříme-li x pomocí dekadického rozvoje a spoč-teme-li výraz na levé straně, zjistíme, že nekončí-li pětkou, nemá cenu takové číslo zkoušet. Navíc musíme vyřadit všechna x, která končí jedničkou, protože předposlední cifra je 0 nebo 5 a levá strana tudíž není dělitelná 125. Zbývá prověřit jen lichá čísla končící 3. Lenost je k nezaplacení.
3.12
n = 36ŕ3 + 36ŕ2 + 12í + 1, t G Z
3.13
Úloha nemá řešení.
KAPITOLA 3. DIOFANTICKÉ ROVNICE
Kapitola 4 Kongruence
V této kapitole se budeme zabývat kongruencemi. Tento pojem zavedl do teorie čísel Gauss1 a umožňuje nám zkráceně zapsat důležité vztahy mezi čísly.
Def. 4.1 Nechí a, b, m G Z, přičemž m > 1. Řekneme, že číslo a je kongruentní s číslem b podle modulu m, jestliže m\(a — b), neboli čísla a a b dávají po dělení číslem m týž zbytek. Píšeme a = b (mod m).
Platí tedy, že 14 = 39 (mod 5), neboť 5|(39 — 14). Naproti tomu 5/(27- 14), píšeme tedy 27 ^ 14 (mod 5).
4.1   Vlastnosti kongruencí podobné vlastnostem rovnic
Z definice plyne, že kongruence jsou tranzitivní, tedy platí věta
Věta 4.1 Nechť platí a = b (mod m) a současně b = c (mod m). Pak je a = c (mod m).
Věta 4.2 Kongruence podle téhož modulu je možné člen po členu sčítat.
1Johann Carl Friedrich Gauss (1777-1855) byl německý matematik, fyzik a astronom. Jeho dílo Disquisitiones arithmeticae, publikované v roce 1801, patří ke stěžejním dílům ele mentární teorie čísel-
39
40
KAPITOLA 4. KONGRUENCE
Důkaz: Nechť a\ = b\ (mod m) a a2 = b2 (mod m). V tomto případě je a\ = bi+mti aa2 = b2+mt2 a,a\+a2 = bi+b2+m(ti+t2), tedy a\ + a2 = b\ + b2 (mod m). Důsledkem je, že podobně jako u rovnic lze v kongruenci převádět z jedné strany na druhou. Jinými slovy ke každé straně kongruence lze přičíst totéž číslo.
Věta 4.3 Kongruence podle téhož modulu lze navzájem násobit.
Důkaz: Vyjádříme opět a\ a a2 stejným způsobem jako v předchozím případě, pak platí a±a2 = b\b2 + mN, kde N je celé číslo. Je tedy a±a2 = b\b2 (mod m). Důsledkem je, že obě strany kongruence můžeme umocnit týmž exponentem. Dalším důsledkem je, že obě strany kongruence můžeme vynásobit týmž číslem, násobíme totiž evidentně správnou kongruenci k = k (mod m). Na rozdíl od rovnic může být k = 0, i když o smysluplnosti této operace lze s úspěchem pochybovat.
Věta 4.4 Obě strany kongruence je možno vydělit jejich společným dělitelem, je-li nesoudělný s modulem.
Důkaz: Z podmínek a = b (mod m), a = aľd,b = bľd, (d, m) = 1 plyne,že rozdíl a — b, rovný (aľ — bľ)d, je dělitelný číslem m. Proto je a\ — b\ je dělitelné číslem m, tedy a\ = b\ (mod p).
4.2   Další vlastnosti kongruenci
Věta 4.5 Obě strany kongruence i modul je možno vynásobit týmž celým číslem.
Důkaz: Z a = b (mod p) plyne a = b + mt, ak = bk + mkt a tedy je ak = bk (mod bk).
Věta 4.6 Obě strany kongruence i modul je možno vydělit jejich libovolným společným dělitelem.
Důkaz: Nechť a = b (mod p), a = a±d, b = b±d, m = ni\d. Máme a = b + mt, a\d = b\d + rriidt, a\ = b\ + rriit, z čehož plyne a\ = b\ (mod mi).
4.3. ÚPLNÁ SOUSTAVA ZBYTKŮ
41
Věta 4.7 Platí-li kongruence a = b podle několika modulů, pak platí i podle modulu, který je roven nejmenšímu společnému násobku těchto modulů.
Důkaz je zřejmý, rozdíl a — b je dělitelný všemi moduly, je tedy dělitelný i jejich nejmenším společným násobkem.
Věta 4.8 Platí-li kongruence podle modulu m, pak platí i podle modulu d, kde d je libovolný dělitel čísla m.
Důkaz je zřejmý neboť je-li rozdíl a — b dělitelný číslem m, je dělitelný i jeho libovolným dělitelem.
Věta 4.9 Jsou-li jedna strana kongruence a modul dělitelné kte-rýmkoliv číslem, pak je i druhá strana kongruence dělitelná tímto číslem.
Důkaz: Platí a = b + mt. Je-li m a, a dělitelné d, musí být tímto číslem dělitelné i b.
Věta 4.10 Je-li a = b (mod m), pak (a,m) = (b,m).
Důkaz: Důkaz plyne z faktu, že je-li a = b (mod m), pak máme a = b + mt. Každé číslo, které dělí současně a a, m musí dělit i b. Naopak každé číslo, které dělí b a, m musí dělit a. Jelikož to platí pro libovolné číslo, platí to i pro největšího společného dělitele.
4.3   Upíná soustava zbytků
Čísla kongruentní podle modulu m vytvářejí třídu čísel podle modulu m. Z této definice plyne, že všem číslům třídy odpovídá jeden a týž zbytek r a že všechna čísla třídy dostaneme, když ve výrazu mq + r bude q probíhat všechna celá čísla. V souhlasu s tím, že r může nabývat m různých hodnot, máme m tříd podle modulu m.
Libovolné číslo třídy se nazývá zbytkem podle modulu m. Zbytek získaný pro q = 0, který je roven samotnému zbytku r se nazývá nejmenší nezáporný zbytek. Zbytek g s nejmenší absolutní hodnotou se nazývá absolutně nejmenší zbytek. Pro r < y je zřejmě g = r;
42
KAPITOLA 4. KONGRUENCE
pro r > y je g = r — m; konečně je-li m sudé a r = y je za £ možné vzít kterékoliv ze dvou čísel y a —y.
Vezmeme-li z každé třídy po jednom zbytku, dostaneme úplnou soustavu zbytků podle modulu m. Nejčastěji se používají jako úplná soustavu zbytků nej menší nezáporné zbytky, případně absolutně nej menší zbytky. Příklad: Úplnou soustavu zbytků podle modulu 5 můžeme vyjádřit buď jako 0,1, 2, 3,4 nebo —2, —1,0,1, 2.
Věta 4.11 Libovolných m čísel po dvou nekongruentních podle modulu m vytváří úplnou soustavu zbytků podle modulu m.
Věta 4.12 Nechť (a,m) = 1 a x probíhá úplnou soustavu zbytků podle modulu m, pak ax + b, kde b je libovolné celé číslo, probíhá také úplnou soustavu zbytků podle modulu m.
Důkazy obou tvrzení jsou snadné a ponecháváme je na čtenáři jako cvičení.
4.4   Redukovaná soustava zbytků
Čísla jedné a téže zbytkové třídy podle modulu m mají s modulem jednoho a téhož největšího společného dělitele. Třídy obsahující zbytky nesoudělné s modulem tvoří redukovanou soustavu zbytků. Redukovanou soustavu zbytků tedy můžeme sestavit z čísel úplné soustavy, které jsou nesoudělné s modulem. Redukovanou soustavu obvykle vytváříme ze soustavy nej menších nezáporných zbytků. Poněvadž mezi čísly úplné soustavy je jich právě </?(m) nesoudělných s modulem m, je počet čísel redukované soustavy stejně jako počet tříd obsahující čísla nesoudělná s modulem ip(m). Příklad: Redukovaná soustava zbytků podle modulu 16 je 1, 3, 5, 7, 9, 11, 13, 15, jelikož je modul mocninou dvojky, musíme vynechat všechny sudé zbytky. Je-li modul prvočíselný, pak je redukovaná soustava zbytků totožná s úplnou soustavou zbytků.
Věta 4.13 Libovolných </?(m) čísel, po dvou nekongruentních podle modulu m a nesoudělných s modulem, tvoří redukovanou soustavu zbytků podle modulu m.
4.5. KONGRUENCE O JEDNÉ NEZNÁMÉ
43
Věta 4.14 Je-li (a, m) = 1 a x probíhá redukovanou soustavu zbytků podle modulu m, pak ax rovněž probíhá redukovanou soustavu zbytků podle modulu m.
Důkazy obou vět jsou analogické důkazům vět 4. 11 a 4. 12 a rovněž je přenecháváme čtenáři jako cvičení.
4.5   Kongruence o jedné neznámé
V této kapitole budeme studovat kongruence obecného tvaru
f{x) = 0   (mod m);    f{x) = anxn + an_ixn_1 + ... + oq. (4.1)
Není-li an dělitelné číslem m, pak se n nazývá stupeň kongruence. Řešit kongruenci znamená najít všechny hodnoty x, které jí vyhovují. Dvě kongruence, kterým vyhovují stejné hodnoty x, se nazývají ekvivalentní.
Poznámka 4.1 V případě polynomu musí být koeficient u nejvyšší mocniny různý od nuly. Zkuste si rozmyslet, co by se stalo, kdyby m\an.
Vyhovuje-li kongruenci (4.1) jistá hodnota x0, pak jí vyhovují i všechna čísla x splňující kongruenci x = xq (mod m). Celá tato třída se považuje za jedno řešení. Za této úmluvy bude mít kongruence (4.1) tolik řešení, kolik zbytků úplné soustavy jí vyhovuje.
Příklad 4.1 Kongruenci x3 + 3x2 + 3 = 0 (mod 5) vyhovuje x = 4. Kongruence má jediné řešení x = 4 (mod 5).
4.5.1   Lineární kongruence
Budeme nyní studovat lineární kongruenci, tedy kongruenci tvaru
Předpokládejme, že je (a,m) = 1. Tato kongruence má právě tolik řešení, kolik zbytků úplné soustavy jí vyhovuje. Probíhá-li x úplnou
(4.2)
44
KAPITOLA 4. KONGRUENCE
soustavu zbytků podle modulu m, pak i ax probíhá úplnou soustavu zbytků podle modulu m. Z tohoto důvodu bude ax kongruentní s b právě pro jednu hodnotou x z úplné soustavy zbytků, jinými slovy kongruence (4.2) má právě jedno řešení.
Nechť nyní je (a, m) = d > 1. Aby kongruence (4.2) měla řešení, je nutné, aby b bylo dělitelné číslem d, jinak kongruence (4.2) nemůže pltit pro žádné celé číslo x. Budeme proto předpokládat, že b je násobkem d a položíme a = a±d, m = ni\d a b = b\d. V tomto případě můžeme kongruenci zkrátit číslem d a nově vzniklá kongruence aľx = bľ (mod nii) bude mít jedno řešení podle modulu m1? neboť je (a1;mi) = 1. Nechť X\ je nejmenší nezáporný zbytek tohoto řešení podle modulu mi, pak všechna čísla x, tvořící toto řešení, jsou tvaru
x = X\   (mod mi). (4-3)
Podle modulu m však čísla (4.3) netvoří jedno řešení, ale právě tolik řešení, kolik se najde v řadě 0,1,2,..., m — 1 nejmenších nezáporných zbytků podle modulu m. Sem patří všechna tato čísla (4.3):
Xi, x\ + m, x\ + 2m,..., x\ + (d — l)m, (4-4)
tedy celkem d čísel (4.3), a tudíž kongruence (4.2) má d řešení. Výše uvedené úvahy dokazují tuto větu:
Věta 4.15 Nechť (a,m) = d. Kongruence ax = b (mod m) nemá řešení, není-li pravá strana dělitelná d. V případě, že je b násobkem d, má kongruence d řešení.
Nyní si ukážeme některé metody řešení kongruenci.
Příklad 4.2 Řešte kongruenci Ax = 1 (mod 6).
Tato kongruence nemá řešení, neboť (4,6) = 2 a 2/1.
Pokud není modul příliš velký, lze kongruenci řešit tak, že zjistíme, která čísla jí vyhovují, obvykle ze soustavy nejmenších nezáporných zbytků.
4.5. KONGRUENCE O JEDNÉ NEZNÁMÉ
45
Příklad 4.3 Řešte kongruenci 3x = 2 (mod 5). Jelikož (3,5) = 1, má kongruence právě jedno řešení. Soustava nejmenších nezáporných zbytků má tvarO, 1, 2,3,4. Snadno se přesvědčíme, že této kongruenci vyhovuje právě číslo 4- Řešením kongruence jsou tedy všechna čísla x = 4 (mod 5).
Příklad 4.4 Řešte kongruenci 6x = 9 (mod 15).
Jelikož (6,15) = 3 fl 3 | 9, bude mít kongruence 3 řešení. Vydělíme-li obě strany kongruence 3, obdržíme novou kongruenci 2x = 3 (mod 5). Vzhledem k tomu, že modul je poměrně malé číslo, lze řešení určit postupným dosazováním čísel ze soustavy nejmenších nezáporných zbytků. Snadno zjistíme, že jejím řešením je číslo x\ = 4. Dalším řešením jsou čísla x2 = x\ + 5 a x3 = x\ + 2.5. Řešení původní kongruence lze uvést ve tvaru x = 4; 9; 14 (mod 15).
Při řešení kongruenci, kde (a,m) = 1, lze využít Eulerovu větu2 (4. 27). Skutečně, je-li a^m) = 1 (mod m), je i a^b = b (mod m). Odsud máme ax = a^^b, a proto je x = aíp(-m^1b. Stačí tedy vypočítat číslo aíp(-m^1b. Toto číslo sice nebude patřit mezi nejmenší nezáporné zbytky, není však problém nejmenší nezáporný zbytek najít.
Příklad 4.5 Řešte kongruenci 6x = 2 (mod 7).
Jelikož íp{7) = Q, je x = 65 • 2 = 2221 x 7 + 5 a kvůli eleganci a jednoduchosti ho zapíšeme ve tvaru x = 5 (mod 7).
4.5.2   Soustava lineárních kongruenci
Jelikož některé vlastnosti kongruenci jsou stejné či analogické vlastnostem rovnic, je namístě si položit otázku, zda lze řešit i soustavu lineárních kongruenci. Omezíme se na soustavu kongruenci o jedné neznámé s různými, po dvou nesoudělnými moduly, tedy na soustavu tvaru
x = b\   (mod mi), ..., x = bk   (mod nik). (4-5)
Řešit soustavu (4.5) je možno podle následující věty.
2Leonhard Euler (1707==1783), švýcarský matematik a fyzik, působil v Petrohradě a v Berlíně. Významně zasáhl do mnoha odvětví matematiky.
46
KAPITOLA 4. KONGRUENCE
Věta 4.16 Necht čísla Ms a Ms jsou definována podmínkami 17111712 . . . nik = Msms,    Msms = 1   (mod ms)   s = 1, 2,..., k
a nechť
x0 = M1M'1b1 + M2M'2b2 + ... + MkM'kbk.
Pak souhrn hodnot x vyhovujících soustavě (4-5) je určen kongru-encí
X = Xq    (mod 171x1712 ■ ■ ■ mk)- (4-6)
Důkaz: Vskutku, vzhledem k dělitelnosti všech čísel Mj, různých od Ms, číslem ms při libovolném s = 1,2,..., A; je
xQ = MsMsbs = bs   (mod ms),
a tedy soustavě (4.5) vyhovuje x = xq. Odtud přímo plyne, že soustava (4.5) je ekvivalentní se soustavou
x = Xq   (mod mi), ...,x = x0   (mod m^), (4-7)
tedy soustavám (4.5) a (4.7) vyhovují tytéž hodnoty x. Soustavě (4.7) pak vyhovují jen ty hodnoty x, které vyhovují kongruenci (4.6).
Věta 4.17 Nechť bi, 62, • • •, bk probíhají nezávisle jedno na druhém úplné soustavy zbytků podle modulů mi, 7712,..., mk, pak x0 probíhá úplnou soustavu zbytků podle modulů mi, 7712, • • •, nik-
Důkaz: Vskutku, xq probíhá mi, 1712,..., nik hodnot, vzhledem k (4.6) nekongruentních podle modulu m1; m2,..., m\..
Příklad 4.6 Řešte soustavu kongruenci
x = bi   (mod 4),       x = b2   (mod 5),       x = 63   (mod 7) Platí4.5.7 = 4.35 = 5.28 = 7.20, přičemž
35.3 = 1   (mod 4),       28.2 = 1   (mod 5),       20.6 = 1   (mod 7).
4.6. KONGRUENCE LIBOVOLNÉHO STUPNĚ PODLE PRVOČÍSELNÉHO MODULU47
Proto je
Xo = 35.36i + 28.262 + 20.663 = 105&i + 5662 + 12063,
a tedy souhrn hodnot x vyhovujících soustavě může být vyjádřen ve tvaru
x = 1056i + 5662 + 12063   (mod 140). tak např. souhrn hodnot x, vyhovujících soustavě
x = 1   (mod 4),    x = 3   (mod 5),    x = 2   (mod 7),
je
x = 105.1 + 56.3 + 120.2 = 93   (mod 140). a souhrn hodnot x, vyhovujících soustavě
x = 3   (mod 4),    x = 2   (mod 5),    x = 6   (mod 7),
je
x = 105.3 + 56.2 + 120.6 = 27   (mod 140).
4.6   Kongruence libovolného stupně podle prvočíselného modulu
Budeme se zabývat kongruencí tvaru
anxn + aix^1 + ... + a0 =    (mod p), (4.8) kde p je prvočíslo.
Věta 4.18 Kongruence tvaru (4-8) je ekvivalentní s kongruencí stupně nejvýš p — 1.
Důkaz: Toto tvrzení plyne ze skutečnosti, že f(x) lze psát jako
f[x) = (xp - x)Q(x) + R(x),
kde R{x) je zbytek po dělení f(x) polynomem xp — x, jehož stupeň nemůže převýšit p—1. Podle Malé Fermatovy věty (viz 4. 26) zase máme xp — x = 0 (mod p), je tedy f(x) = R{x) (mod p).
48
KAPITOLA 4. KONGRUENCE
Věta 4.19 Nechť kongruence (4-8) má více než n řešení. Pak platí, že všechny koeficienty clí jsou násobky p.
Důkaz:
Označme zbytky všech řešení kongruence (4.8) písmeny Xi,x2, ■ ■ ■ xn, xn+1. Polynom f {x) můžeme vyjádřit jako f (x)   =a(x — Xi)(x — x 2).. .{x — xn_i(x — xn) + b{x — Xi)(x — x 2) .. .{x — xn_i + + ...+ +l(x — Xi) +m.
Sčítance na pravé straně přeměníme v mnohočleny a zvolíme b tak, aby součet koeficientů dvou prvých mnohočlenů u xn~ľ byl di, známe-li b, zvolíme c tak, aby součet koeficientů prvých tří mnohočlenů u xx~ byl 02 atd. Klademe-li postupně x2, ■ ■ ■, x = xn, x = xn+i, přesvědčíme se, že všechna čísla m, l,k,..., c, b, a jsou násobky p. Protože a,i jsou součty čísel dělitelných p, jsou také dělitelná p.
4.7   Kongruence druhého stupně
V tomto oddíle budeme vyšetřovat kongruence tvaru
x2 = a   (mod p);       (a,p) = 1, (4-9)
kde p je liché prvočíslo. Pokud má tato kongruence řešení, nazýváme číslo a kvadratickým zbytkem, v opačném případě kvadratickým ne-zbytkem podle modulu p.
Poznámka 4.2 Kvadratický zbytek i nezbytek můžeme definovat pro libovolný modul. Případ složeného modulu je naznačen v pojednání o Jacobiho symbolu. Prvočíselný modul m = 2 je případ triviální. Čtverec sudého čísla je opět číslo sudé a lichého liché. Každá dvě čísla, které mají stejnou paritu (obě jsou sudá či lichá), jsou kongruentní podle modulu 2.
Příklad 4.7 Číslo čtyři je kvadratický zbytek podle modulu pět, neboť kongruence x2 = 4 (mod 5) má řešeníx\ = 2+5k a x2 = 3+5A;.
4.7. KONGRUENCE DRUHÉHO STUPNĚ
49
Naproti tomu číslo dva je kvadratický nezbytek podle modulu pět, neboť kongruuence x2 = 2 (mod 5) nemá řešení.
Věta 4.20 Nechť a je kvadratický zbytek podle modulu p. Pak kon-gruence (4-9) má právě dvě řešení.
Důkaz: Jelikož a je kvadratický zbytek, musí mít kongruence (4.9) alespoň jedno řešení, řekněme, že je to X\. Protože je (—xľ)2 = xf, má tato kongruence i druhé řešení x = —x\ (mod p). Dále nemůže platit x\ = —x\ (mod p), neboť pak by bylo 2x± = 0 (mod p). Toto však není možné, protože (2,p) = (xi,p) = 1. Další řešení již tato kongruence nemůže mít, jak bylo dokázáno ve větě 4. 19.
Věta 4.21 Redukovaná soustava zbytků podle modulu p se skládá z       kvadratických zbytků, které jsou kongruentní s čísly 12,22,...,
í2^")2 a       kvadratických nezbytků.
Důkaz: Mezi zbytky redukované soustavy podle modulu p jsou kvadratickými zbytky ty a jenom ty, které jsou kongruentní s čtverci čísel
p — 1 p — 1 .
-^-,...,-2,-1,1,2,...,^- (4.10)
podle modulu p. Přitom čtverce čísel (4.10) nejsou kongruentní podle modulu p, neboť z podmínek k2 = l2 (mod p), 0 < k < l < by plynulo, že kongruenci x2 = l2 (mod p) z čísel (4.10) vyhovují čtyři: x = —l, —k, l, k, což je spor.
Věta 4.22 Nechť a je kvadratický zbytek podle modulu p. Pak platí
0^ = 1   (mod p); (4.11) Je-li a kvadratický nezbytek podle modulu p, platí
a2^- = -1   (mod p). (4.12)
Důkaz: Malá Fermatova věta nám říká, že ap_1 = 1 (mod p). Tuto kongruenci lze psát také ve tvaru
{^ŕ^ — ŕj (^a^ + 1 j = 0   (mod p).
50
KAPITOLA 4. KONGRUENCE
Jelikož rozdíl obou závorek je roven dvěma, tak platí pouze jedna z kongruencí (4.11), (4.12). Každý kvadratický zbytek a vyhovuje při některém x kongruenci
a = x2   (mod p), (4-13)
a proto vyhovuje i kongruenci (4.11), kterou obdržíme, umocníme-li obě strany kongruence na       Kvadratickými zbytky jsou vyčerpána všechna řešení kongruence (4.11). Kvadratické nezbytky musí tedy vyhovovat kongruenci (4.12).
4.8   Legendreův symbol
Legendreův symbol y^j je roven 1 je-li a kvadratický zbytek a je
roven -1, je-li a kvadratický nezbytek podle modulu p, přičemž je (a,p) = 1. Číslo a se nazývá čitatel a číslo p jmenovatel Legendreova symbolu. Čteme a vzhledem k p. Zřejmě platí
- ) = (mod p).
V)
Jelikož čísla jedné a téže třídy jsou současně kvadratické zbytky nebo nezbytky, platí dále následující tvrzení.
Věta 4.23 Nechť a = ax (mod p). Pak platí (jf) = (^f
Důkaz: Jelikož 1 = l2, je jednička kvadratický zbytek pro každý modul a tedy platí:
1.
V,'
Lichá prvočísla můžeme vyjádřit buď ve tvaru 4A; + 1 nebo Ak + 3. V prvním případě je ale výraz vždy číslo sudé, ve druhém pak liché. Číslo —1 je proto kvadratickým zbytkem prvočísel tvaru 4A;+1 a kvadratickým nezbytkem prvočísel tvaru 4A; + 3. Platí tedy
P )
4.8. LEGENDREŮV SYMBOL
51
Věta 4.24 Pro Legendreův symbol platí:
íab...l\ _ ía\ íb
)
\   P   J     \pj \P
P
Důkaz Vskutku máme
- (mod p) P J
(a)V(&V...(/)%
Důsledek 4.1 V čitateli Legendreova symbolu můžeme vypustit každý kvadratický činitel, tedy platí
Tato věta je v teorii čísel známa jako Gaussův zákon kvadratické reciprocity. Jako první ho dokázal Gauss, který ho nazval theorema aurea (zlatá věta). Tento zákon nám umožňuje ve spojení s výše uvedenými vlastnostmi značně zjednodušit výpočet Legendreova symbolu jak ukážeme níže. Důkaz zákona kvadratické reciprocity neuvádíme pro jeho délku, čtenář ho může najít např. v [11]
Příklad 4.8 Vypočtěte Legendreův symbol L = ■
Nejpre si všimneme, že 111 je číslo složené a že platí 111 = 3.37. Platí tedy
Nyní využijeme zákon kvadratické reciprocity, čímž v čitateli Legendreova symbolu obdržíme větší číslo než ve jmenovateli. Máme tedy
Věta 4.25 Nechť p a q jsou lichá prvočísla. Pak platí
52
KAPITOLA 4. KONGRUENCE
Pokud dělíme číslo 1999 třemi či třiceti sedmi, dostaneme v obou případech zbytek jedna. Jinými slovy 1999 je kongruentní s jedničkou jak podle modulu 37, tak i podle modulu 3. Můžeme tedy výpočet ukončit.
Naskýtá se otázka, zda by nešlo zavést podobný symbol i v případě, že ve jmenovateli není prvočíslo. Tímto problémem se zabýval německý matematik CG. Jacobi, který Legendreův symbol rozšířil následujícím způsobem.
Def. 4.2 Nechť a je celé číslo a nechť n > 3 je liché. Nechť dále n = pip2...pr, kde pri jsou lichá prvočísla, nikoliv nutné různá. Jacobiho symbol je definován vztahem
Vlastnosti Jacobiho symbolu jsou analogické vlastnostem symbolu Legendreova včetně zákona kvadratické reciprocity, jeden významný rozdíl však přece najdeme. Je-li Legendreův symbol roven jedné, je vždy a kvadratický zbytek modulo p, to plyne z jeho definice. V případě Jacobiho symbolu to však platit nemusí, jak se můžeme přesvědčit z následujícího příkladu.
= (-!)(-!) = 1,
dvojka však není kvadratický zbytek modulo 15.
4.9   Některé důležité věty z teorie čísel
Závěrem této kapitoly uvedeme několik vět z teoreie čísel.
Věta 4.26 Malá Fermatova věta. Nechť p je prvočíslo a platí (a, p) = 1. Pak je
(4.14)
,p-i =
1   (mod p).
(4.15)
4.9. NĚKTERÉ DŮLEŽITÉ VĚTY Z TEORIE ČÍSEL
53
Dnes je známo několik důkazů této věty, autor si dovolí přihřát svou polívčičku a odkázat čtenáře na publikaci [3]. Aby čtenáři nebyli zcela ošizeni, uvedeme elegantní důkaz pro speciální případ kdy a = 2. Jednou z nej důležitějších vět turbodidaktiky je věta Tesákova, která praví, že 1 + 1 = 2. Využijeme-li tuto větu, máme
^+HoMi)+'"+c-i)+e>
Jelikož p je prvočíslo, jsou všechny binomické koeficienty (p) dělitelné p s výjimkou k = 0 a k = p. Můžeme tedy od rovnosti přejít ke kongruenci, čímž obdržíme
2P = 2   (mod p) =>■ 2P_1 = 1 (modp).
Poslední úprava plyne ze skutečnosti, že podle předpokladu Malé Fermatovy věty je (2,p) = 1.
Důsledkem Malé Fermatovy věty je skutečnost, že podíl
= -p-
je celé číslo. Podíl q(a) se nazývá Fermatův kvocient. Malou Fermatovu větu později zobecnil Euler.
Věta 4.27 (Euler). Nechť a a n jsou přirozená čísla a (a,n) = 1. Pak platí
kde íp(ri) je Eulerova funkce, kterou jsme definovali v kapitole druhé.
Připomeneme, že výraz n\ = n.(n — 1)... 2.1 nazýváme n fak-toriál. Dá se dokázat věta
Věta 4.28 (Wilson) Nechť p je prvočíslo, pak platí
(p-l)! = -l   (modp). (4.17)
Jelikož byla uvedena Malá Fermatova věta, sluší se též uvést i Velkou Fermatovu větu, i když tato přímo do tematiky tohoto textu nezapadá.
54
KAPITOLA 4. KONGRUENCE
Věta 4.29 Díofantícká rovnice
xn+yn = zn
nemá pro n > 2 řešeni v oboru celých čísel.
Jak již bylo řečeno, tato věta se přímo netýká probírané problematiky, avšak jedná se o velmi známý problém, takže pokud by se s ním chtěl někdo blíže seznámit, doporučujeme knihu [8].
4.10   Příklady k procvičení
4.1. Zjistěte, které z následujících kongruencí jsou řešitelné
a) 6x = 1 (mod 9) b) 9x = 3 (mod 6) c) lAx = 21 (mod 70)
4.2. Řešte kongruence
a) 20x = 4 (mod 30) b) 20x = 30 (mod 4) c) 353x = 254 (mod 400)
4.3. Najděte nejmenší přirozené číslo větší než 1, které vyhovuje kongruencím x = 1 (mod 3), x = 1 (mod 5), x = 1 (mod 7).
4.4. Řešte soustavu kongruencí x = 2 (mod 3), x = 3 (mod 5), x = 5 (mod 2).
4.5. Řešte soustavu kongruencí x = 1 (mod 4), x = 0 (mod 3), x = 5 (mod 7).
4.6. Najděte všechna celá čísla, která při dělení čísly 3, 4 a 5 dávají zbytky 1, 2 a 3.
Výsledky
4.1. Řešitelná je pouze kongruence b).
4.2. c) x = —88 (mod 400). Ostatní dvě nemají řešení.
4.3. x = 106
4.4. x = 23 + 10Í, t G Z
4.5. x = 33 (mod 8)4
4.6. n = 60t - 2, t G Z
Kapitola 5
Speciální typy přirozených čísel
V této kapitole uvedeme některé speciální typy čísel, a to jak prvočísel, tak čísel složených. Tato kapitola nebude mít charakter učebního textu jako předchozí, čtenář se v ní seznámí s některými speciálními typy čísel a pozná různé zajímavosti, které pak bude moci uplatnit ve výuce. Čísla jsou totiž velmi zajímavá a můžeme říci že i tajuplná. Jednotlivé podkapitoly budeme řadit podle abecedy.
5.1   Dokonalá čísla
Jak již bylo řečeno, má každé přirozené číslo n > 1 přinejmenším dva dělitele, a sice lan. Označme <j(n) součet všech dělitelů čísla n. Zřejmě platí <j(n) > 1, porovnejme však součet dělitelů s dvojnásobkem čísla n. Zvolíme-li tuto hranici, tak se množina přirozených čísel n > 1 rozloží na tři navzájem disjunkntní podmnožiny. Do první zařadíme ta čísla, pro něž <j(n) < 2n a budeme je nazývat deficientní (numeri deficientes). Tato množina je nekonečná, neboť sem patří mj. všechna prvočísla. Čísla pro něž <y(n) > 2n nazveme abundatní (numeri abundantes). I tato množina je nekonečná, můžeme sem zařadit čísla tvaru n = 2k ■ 3, k > 1. Důkaz je snadný pro toho, kdo ovládá vzorec pro součet prvních
55
56   KAPITOLA 5. SPECIÁLNÍ TYPY PŘIROZENÝCH ČÍSEL
n členů geometrické posloupnosti. Platí
a(n) = = (2fc+1 - 1) • 4 > 2 • (2k • 3) = 2n.
Třetí množinu pak tvoří čísla n > 1, pro něž je <j(n) = 2n. Tato čísla nazýváme čísla dokonalá (numeri perfecti), někdy též používáme název dokonalá čísla prvního druhu. Někdy se dokonalé číslo (prvního druhu) také definuje tak, že je rovno součtu všech svých pravých dělitelů, tedy dělitelů menších než je číslo samo. Nejmenší dokonalé číslo je 6=1+2+3. Ve starověku byla známa ještě tři další dokonalá čísla, a to 28, 496 a 8128. Je zajímavé, že již v Euk-leidových Základech je uvedena postačující podmínka pro to, aby sudé číslo bylo dokonalé, ověřování však bylo zřejmě nad síly tehdejších počtářů. Jak si jistě čtenáři všimli, tak uvedená dokonalá čísla jsou sudá. Uvedeme proto nutnou a postačující podmínku pro to, aby sudé číslo bylo dokonalé.
Věta 5.1 Sudé číslo n > 1 je dokonalé právě tehdy, když je tvaru
n = 2S-1(2S - 1), (5.1) kde s > 1 je přirozené číslo a Ms = 2S — 1 je prvočíslo.
Čísla Ms se nazývají Mersennova čísla1. V následujícím důkazu je však pro zjednodušení zápisu budeme označovat písmenem p. Důkaz: Důkaz postačující podmínky je snazší, proto jím začneme. Nechť nějaké číslo je tvaru (5.1); tento tvar představuje zároveň jeho kanonický rozklad. Proto je
2S - 1   p2 - 1
Odtud jednoduchou úpravou zjistíme, že <j(n) = 2sp = 2(2s~1p), tedy n je dokonalé.
Dokážeme dále podmínku nutnou. Nechť n je sudé dokonalé číslo. Snadno nahlédneme, že jeho kanonický rozklad musí obsahovat přinejmenším jedno liché prvočíslo, neboť pak by bylo tvaru
1P. Marin Mersenne ((1588-1648), francouzský kněz, matematik, fyzik, teolog, filozof a organizátor vědeckého života. Po něm pojmenovaných prvočísel bylo zatím objeveno 51, neví se, zda je jich konečný počet či nekonečně mnoho.
5.1. DOKONALÁ ČÍSLA
57
2k, k > la <j(n) = 2k+1 — 1 a číslo n by tedy nebylo dokonalé. Kanonický rozklad čísla n nechť je n = 2OLpc^1 • p%2 ■ ■ -p^ ■ Položme / = p"1 ■ P22 ■ ■ -p^.k a a = s — 1. Jelikož n je dokonalé, musí být
os — 1    r>ai+1 — 1      nak+1 — 1
a(n) =--- • ^-- • • • ^-- = (2S - IV(/) = 2sl,
K 1     2-1     Pl - 1 pi - 1       v        ; w
protože
Rovnost
ai+l _ 1 _
a(l) = Pl-t...Pl-
W       Pi ~ 1 P* - 1
(2S - l).o-(Z) = 2S./ (5.2)
ukazuje, že 2S dělí součin (2S — l).a(l). Číslo 2S je však dělitelné pouze čísly ±l,±2r, kde 1 < r < s. Jelikož 2S — 1 je liché, pak je zřejmé, že čísla 2S a 2S — 1 jsou nesoudělná, tedy 2S | u{l). Musí tedy existovat číslo q > 1 takové, že čt(Z) = 2s.g. Dosadíme-li do předchozí rovnosti (5.2.), obdržíme po zkrácení 2S
(2s-l).q = l (5.3)
neboli
2s.q = a(l) = l + q. (5.4)
Číslo / > 1 je dělitelné / a podle (5.3) i q. Z rovnosti (5.4) vyplývá, že / ý li rovnost (5.3) pak říká, že číslo / nemůže mít jiné dělitele než / a q. Pokud by totiž existovalo číslo d > 1 a současně by d bylo různé od čísel / a g, byl by součet dělitelů čísla / roven přinejmenším / + q + d, což je v rozporu s (5.2). Proto / má pouze dva dělitele, a to sebe sama a q = 1, je to tedy prvočíslo. Podle (5.3.) je / = 2S — 1, dokonalé číslo n je pak tvaru 2S~1.(2S — 1), s > 1 a 2S — 1 je prvočíslo.
Dokonalé číslo druhého druhu je takové číslo, které je rovno součinu všech svých pravých dělitelů. Příkladem je číslo 6 (6=1.2.3), které je dokonalé i prvního druhu. I pro dokonalá čísla druhého druhu existuje jednoduchý vzorec pro jejich určení, navíc z něho vyplývá, že je jich nekonečně mnoho.
Věta 5.2 Číslo n > 1 je dokonalé číslo druhého druhu právě tehdy, když je bud' třetí mocninou prvočísla, nebo je součinem dvou prvočísel.
58   KAPITOLA 5. SPECIÁLNÍ TYPY PŘIROZENÝCH ČÍSEL
Je-li n = p3, jsou jeho dělitelé 1, p a p2 a jejich součin je roven n. Je-li n = p±.p2, pak jsou tato prvočísla spolu s jedničkou jediní dělitelé a jejich součin je roven číslu n.
Nechť naopak je n > 1 dokonalé číslo druhého druhu. Předpokládejme, že jeho kanonický rozklad je n = p^p^2 ■ ■ -Pkk- Všechny dělitele čísla n seřadíme podle velikosti, je tedy 1 = dľ < d2 ... < ds = n. Položme t (n) = s. Je tedy n = d\Ä2 ... ds=\. Vynásobíme-li tuto rovnost číslem n
ds, obdržíme
n
d\.d2 ... ds.
(5.5)
Je-li d dělitelem čísla n, je jeho dělitelem i ^. Proto můžeme psát
n
d'
n
n di
n
n2
(5.6)
Vynásobíme-li předchozí dvě rovnosti, máme n4 = ns, z čehož plyne s = 4. Jelikož je r(n) = («i + 1) ... («& + 1), jsou všechny závorky větší nebo rovny dvěma, proto je k < 2. Jsou tedy možné pouze dva kanonické rozklady čísla n. Buď je n = pf1, nebo je n = p^.p^2-V prvním případě je «i = 3, ve druhém «i = «2 = 1.
5.2   Fermatova čísla
V této části se opět setkáváme se jménem Fermat. Tento pán studoval také čísla tvaru
Fm = 22m + 1,      m = 0,1,2,....
Fermat byl přesvědčen o tom, že jsou to prvočísla, přes veškeré úsilí se mu to však nepodařilo ani dokázat, ani vyvrátit, ačkoliv nástroje k tomu měl. Prvních pět těchto čísel jsou skutečně prvočísla, usly-šíme-li pojem Fermatovo prvočíslo, pak se bude jednat právě o tato čísla.
Zdálo by se, že zápis těchto čísel je zbytečně komplikovaný, následující tvrzení však ukáže, že Fermat dobře věděl, proč zvolil tento tvar.
Věta 5.3 Nechť n je přirozené číslo. Je-li k = 2n + 1 prvočíslo, pak n = 2m pro nějaké m G {0,1, 2,...}.
5.2. FERMATOVA ČÍSLA
59
Nechť k a / jsou přirozená čísla, přičemž / je liché a současně je / > 3. V tomto případě platí formule
2kl + 1 = (2k + l)(2fc(z_1) - 2fc(ř~2) +----2k + 1).
Číslo tvaru 2n + 1 je vždy složené, je-li exponent dělitelný lichým přirozeným číslem větším než jedna. Formule pro Fermatova čísla tedy zabezpečuje splnění nutné podmínky pro to, aby tato čísla byla prvočísla.
Nyní si od čísel odpočineme a podíváme se do geometrie či chcete-li do planimetrie. Eukleidovské konstrukce kružítkem a pravítkem patří mezi krásné partie matematiky. Na jedné straně máme v hlavě absolutně přesné úvahy, tyto však nelze nikdy v praxi realizovat. Je to vlastně pěkný příklad platónské filozofie, kdy na papír dáváme jen stíny či odlesky ideální geometrie. Takové ořezávátko ještě vynalezeno nebylo a v budoucnu ani nebude, aby jím ostrouhaná tužka narýsovala přímku, tedy délku bez šířky či jiné ideální geometrické útvary. Z velkého množství geometrických konstrukcí si vybereme sestrojení pravidelného n-úhelníka. Narýsovat rovnostranný trojúhelník, čtverec či pravidelný šestiúhelník je procházka růžovým sadem, s menšími problémy zvládneme i pravidelný pětiúhelník. Ačkoliv sedmička je považována za šťastné číslo, v případě pravidelného sedmiúhelníka to neplatí. Generace geometrů se o takovou konstrukci pokoušely, leč marně. Teprve Gaussovi se podařilo tento oříšek rozlousknout, když dokázal následující větu:
Věta 5.4 Pravidelný n-úhelník lze sestrojit pravítkem a kružítkem právě tehdy když, n = 2%FmiFm2 ■ ■ ■ Fmj, kde n > 3, i > 0, j > 0 a Fmi,... Fm. jsou navzájem různá Fermatova prvočísla.
Důkaz této věty přesahuje rámec tohoto textu, sdělíme jen, že problém geometrický je převeden na algebraický. Například pro středový úhel pravidelného pětiúhelníka platí cos ^ = . Nu a kosinus je roven délce přilehlé odvěsny pravoúhlého trojúhelníka s přeponou jedna a tuto úsečku dovedeme sestrojit kružítkem a pravítkem. Jelikož jediná dosud známá Fermatova prvočísla jsou 3, 5, 17, 257 a 65537, je zřejmé, že eukleidovská konstrukce pravidelného sedmiúhelníka (a samozřejmě mnoha dalších s lichým počtem stran)
60   KAPITOLA 5. SPECIÁLNÍ TYPY PŘIROZENÝCH ČÍSEL
z principu není možná. Existují i další souvislosti mezi Ferma-tovými prvočísly a geometrií, jelikož přesahují rozsah obvykle probírané látky na základních či středních školách, tak je neuvádíme a zájemce odkazujeme např. na publikaci [2].
Po návratu z geometrického výletu uzavřeme část věnovanou Fermatovým číslům. Je tak trochu záhada, proč Fermat nezjistil, že F5 = 641.6700417, to se podařilo až Eulerovi. Na druhou stranu dnes chápeme, že tento geniální Francouz nenašel v tomto směru žádný důkaz. Ten se totiž nenašel dodnes, přestože je těmto číslům věnována současnými matematiky velká pozornost. Tato čísla jsou totiž velká, či přesněji jejich dekadický zápis obsahuje mnoho cifer (např. F18 jich má téměř 80 000). Byly zapojeny i počítače a vyvinuty metody na faktorizaci velkých čísel, zatím máme jedinou jistotu, a sice že pro 5 > m > 32 se jedná o čísla složená, přestože pro F20 a F24 neznáme žádného netriviálního dělitele. Nepodařilo se zatím ani najít nějakou zákonitost, která by v tomto směru něco napověděla. Teorie čísel tedy před nás staví další výzvu.
5.3   Spřátelená čísla
Def. 5.1 Dvě různá přirozená čísla a a b nazýváme spřátelená, jestliže součet pravých dělitelů čísla a je roven b a současně je součet pravých dělitelů čísla b roven a.
Příkladem budiž dvojice 220 a 284, kterou znali již pythagorejci. Skutečně, praví dělitelé prvního z nich jsou čísla 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 a 110; součet těchto čísel je 284. Číslo 284 nemá tolik pravých dělitelů jsou jen čísla 1, 2, 4, 71 a 142 a jejich součet je 220. Do publikace [9], která byla určena především řešitelům matematické olympiády, se vloudila malá chybička, kdy místo 71 je uvedeno 7.
Věta 5.5 Čísla a a b jsou spřátelená právě tehdy, když a(a) = a(b) = a + b.
Důkaz: Je zřejmé, že počet pravých dělitelů čísla m je <j(m) — m. Jsou-li a a b spřátelená je současně a(a) — a = b a a(b) — b = a. Vypočítáme-li z druhé rovnice b a dosadíme do první, máme
5.4. ZÁVĚR KAPITOLY
61
o~(a) = <j(b). Je-li naopak o~(a) = a(b) = a + b, snadno nahlédneme, že o~(a) — a = b a současně a(b) — b = a a že tedy čísla a a 6 jsou spřátelená.
I v případě spřátelených čísel nebylo zatím vše objasněno. Nevíme například, zda je jich konečně či nekonečně mnoho. Zatím všechny dvojice spřátelených čísel mají největší společný dělitel větší než jedna. Známe však dvojici lichých spřátelených čísel a = 33.5.7.11 a 6 = 3.5.7.139.
Hledat spřátelená čísla můžeme podle návodu, který udal v 9. stol. arabský matematik Ben Korrah a který je uveden v následující větě.
Věta 5.6 Nechť existuji pro n > 1 prvočísla tvaru p = 3.2n_1 — 1, q = 3.2n — 1 a r = 9.22n_1 — 1. Pak čísla k = 2npq a l = 2n.r jsou spřátelená.
Důkaz: Jako první krok dokážeme, že součet všech dělitelů čísla k je roven součtu dělitelů čísla /. Pro součet dělitelů o~(k) platí
a(2n.p.q) = (2n+1 - l).(p + l).(g + 1) = (2n+1 - l).9.22n-\
Pro součet dělitelů a (V) zase platí
a(2n.r) = (2n+1 - l)(r + 1) = (2n+1 - l)9.22n-\
Jako druhý krok musíme dokázat, že tento součet je roven k + /.
k + l = 2npq + 2nr = 2n(pq + r) = 9.22n"1(2n+1 - 1) = a(k) = a)l).
5.4   Závěr kapitoly
V závěrem této kapitoly uvedeme stručně některá další speciální prvočísla. Připomeňme si nejdříve Eukleidův důkaz o nekonečném počtu prvočísel, v němž stěžejní úlohu hrál výraz n = pľp2 .. .pk + l-Číslo n může, ale také nemusí být prvočíslo. Je-li prvočíslo, pak je budeme nazývat Eukleidovo prvočíslo. Eukleidův důkaz můžeme lehce pozměnit tak, že místo čísla n sestavíme číslo m = p\ + 1, kde p je největší prvočíslo, jichž předpokládáme konečný počet. Ani v
62   KAPITOLA 5. SPECIÁLNÍ TYPY PŘIROZENÝCH ČÍSEL
tomto případě není číslo m dělitelné žádným prvočíslem, neboť pro každé q < p je zbytek po dělení čísla m číslem q vždy roven jedné. To jsme ale zkonstruovali prvočíslo větší než p, nebo jem dělitelné prvočíslem větší než p, v každém případě jsme se dostali do sporu s předpokladem. Prvočísla tvaru k\ + l nazýváme faktoriální. Týmž názvem se označují i prvočísla tvaru k\ — 1. V obou případech nevyžadujeme, aby k bylo prvočíslo.
Kapitola 6 Aplikace teorie čísel
Pokud se čtenář v tomto textu propracoval až k této kapitole, tak si mohl myslet následující. Teorie čísel je velmi hezkou součástí matematiky, obsahuje řadu zajímavých tvrzení, některé důkazy jsou velmi elegantní, řada poznatků se dá využít pro zpestření výuky, zajímavá jsou i některá dosud nedokázaná ani nevyvrácená tvrzení, ale jaký to má význam pro praxi? Nejedná se zde jen o sice krásnou, ale jinak neužitečnou vědu? V této kapitole se pokusíme dokázat, že tomu tak není, že teorie čísel je pro praxi velice významná a její důležitost poslední dobou neustále roste. A začneme tím, s čím je spojen každý občan našeho státu od kolébky až po rakev. Ano, začneme rodným číslem.
6.1   Rodná čísla
Každý občan České republiky má již od narození přidělené rodné číslo, které se sestaví tak, že prvních šest čísel je dáno datem narození. První dvojčíslí udává rok, druhé měsíc a třetí den narození. Kvůli rozlišení pohlaví se k druhému dvojčíslí u dívek přičítá padesátka. Rodné číslo hochů, kteří se narodili například 10. prosince 1996 začíná šestičíslím 961210, u děvčat je to 966210. Protože se denně rodí více dětí, přidávají se za tuto šestici ještě další čísla. U nás se od roku 1986 přidávají čtyři čísla, rodná čísla jsou tedy deseticiferná. Poslední čtyřčíslí se však nevolí náhodně, nýbrž tak, aby celé rodné číslo bylo dělitelné jedenácti. Jaký jek tomu důvod,
63
64
KAPITOLA 6. APLIKACE TEORIE ČÍSEL
nestačilo by například seřadit děti narozené v jednom dni například podle času, kdy přišly na svět a pak jim přiřadit čísla odpovídající pořadí?
Abychom mohli zodpovědět tuto otázku, dokážeme nejdříve kritérium pro dělitelnost jedenácti.
Věta 6.1 Nechť kE {0,1,2,...} a m = cn10n přičemž je
cn G {0,1,2,...,9}, Ck Ý 0, tedy Ck, ■ ■ ■ ,cq jsou cifry přirozeného čísla m v desítkové soustavě. Pak
Důkaz: Podle vzorce pro rozdíl dvou n-tých mocnin platí
ion-(-i)n = (io+i)[ion-1+ion-2(-i)+---+io(-i)n-2+(-i)n-1],
kde hranatá závorka obsahuje právě n sčítanců. Rozdíl 10n — (—l)n je tedy dělitelný 11. Použijeme-li nyní vzorec (6.2) na každý sčítanec v (6.1) kromě posledního, pak dostaneme
Podobně zjistíme, že když platí (6.3), je splněn i vztah (6.1).
Vraťme se nyní k našemu chlapci, jehož rodné číslo může být 9612107032. Dejme tomu, že se při jeho zadávání spleteme v jedné cifře. Pak rozdíl mezi správným a špatně zadaným číslem bude ±c • 10n, kde c G {1,2,... ,9}. Tento rozdíl není nikdy dělitelný číslem 11, ale může být dělitelný složenými čísly 12, 14, 15 atd. Napíšeme-li v našem rodném čísle místo sedmičky jedničku, je rozdíl mezi správným a špatným rodným číslem 6 000. Nalezení všech jeho dvojciferných dělitelů pak přenecháváme čtenáři. Protože číslo 11 nám umožňuje odhalit chybu, hovoříme o jedenáctkovém samode-tekujícím kódu.
Při použití jednociferných prvočísel se obecně nedá odhalit chyba při vložení jedné nesprávné cifry. Použití větších dvojciferných prvočísel nám zase snižuje počet použitelných rodných čísel. Jedenáctka je tedy pro potřeby rodného čísla optimální. Závěrem přidáme ještě jednu zajímavost. Česká dvoukoruna je pravidelný jedenáctiúhelník.
(6.2)
11 | ((-l)kck + (-l)k-lck^ + • • • + Cl + c0).
(6.3)
6.2. ŠIFROVÁNÍ ZPRÁ V POMOCÍ PRVOČÍSEL
65
Položíme minci do základní polohy a pak ji střídavě otáčíme po a proti směru hodinových ručiček o tolik vrcholů, kolik je příslušná cifra. Po posledním pootočení se mince musí vrátit do původní polohy.
Na podobném principu fungují rovněž kódy ISBN a ISSN pro knihy či časopisy, identifikační čísla organizací (ICO), bankovní účty a pod. Více se lze dočíst například v [14]. Samodetekující kódy dovedou chybu najít, nikoliv opravit. Z tohoto důvodu byly vyvinuty kódy samoopravné. Ty nám umožňují pomocí redundantní (nadbytečné) informace obsažené v kódových slovech stanovit, ve kterém znaku došlo k chybě, a opravit ji. Velká budoucnost je vkládána do tzv. dvourozměrných kódů s vysokou informační kapacitou a schopností detekce a opravy chyb. Tyto kódy se používají mj. v amerických řidičských průkazech či různých identifikačních kartách. Také u nás jsou tyto kódy postupně zaváděny, viděl jsem je na jízdenkách, vstupenkách a je jisté, že se jejich použití bude rozšiřovat. Mají tu výhodu, že se tisknou a přenášejí na papíru a že zde není nutnost vkládat data z klávesnice.
6.2   Šifrování zpráv pomocí prvočísel
Potřeba utajit písemná sdělení je patrně tak stará, jako písmo samo. V průběhu tisíciletí lidé vynalezli řadu způsobů, jak zabránit nepovolané osobě, které se dostala do rukou tajná zpráva, aby ji přečetla. Jako příklad můžeme uvést šifrování pomocí mřížky, které používal Matyáš Sandorf a jeho přátelé. Stačilo však, aby se padouch Šarkany dostal k mřížce a přečtení zpráv již pro něj nepředstavovalo žádný problém. Jindy k rozluštění stačilo logické uvažování. Geniální detektiv Sherlock Holmes takové šifry luštil běžně. Šifru spočívající v tom, že každé písmeno bylo nahrazeno tančící figurkou, rozluštil pomocí frekvence výskytu jednotlivých písmen. Zatímco v české abecedě je to písmeno a, v angličtině to je litera e. Stejný postup volí i luštitelé tzv. číselných křížovek. Jiná metoda spočívá v tom, že se slovo nahradí číslem, určujícím pořadí slova na jisté stránce knihy, kterou mají obě strany k dispozici. V tomto případě se nedoporučuje, aby klíčem byly kniha o více dílech. Dobrý voják Švejk
66
KAPITOLA 6. APLIKACE TEORIE ČÍSEL
logicky nafasoval pro pány oficíry první díl knihy Hříchy otců, jenže klíčem byl díl druhý a jedenáctá marškumpanie nemohla tuto šifru používat.
Uvedené případy jsou staršího data, kdy si luštitel šifry musel vystačit jen se svým intelektem. V době počítačů se zdá, že není v lidských silách vymyslet takovou šifru, která by před řešiteli obstálo, neboť co jeden člověk vymyslí, druhý rozluští, jak pravil Sherlock Holmes. Avšak matematika není nadarmo považována za královnu věd. Pánové Rivest, Shamir a Adelman objevili v roce 1978 metodu, která se podle počátečních písmen jejich příjmení nazývá RSA. Oč je metoda jednodušší, o to je účinnější, dokonce není nutné tajit šifrovací klíč, šifrovat může každý. Zatím však bez znalosti dešifrovacího klíče není a vypadá to, že ani v budoucnu nebude možné tyto šifry rozluštit. Jádrem pudla je totiž skutečnost, že není problém vynásobit dvě velká čísla. Mnohem nesnadnější je inverzní proces, tedy rozložit číslo složené na součin prvočinitelů.
Popíšeme nyní postup při šifrování a dešifrování zprávy. Utajované sdělení převedeme nejprve na přirozené číslo x. K tomu nám mohou posloužit například kódy ASCII, ale jejich použití není podmínkou, existují i jiné a možná i efektivnější způsoby. Dále budeme předpokládat, že x < n, kde n je součin dvou různých prvočísel, která nejsou veřejně známa a mají více než 100 cifer. Psavci musí samozřejmě rozdělit zprávu na několik kratších tak, aby pro každou z nich byla splněna předchozí nerovnost. Zašifrovanou zprávu označíme symbolem x*. Toto přirozené číslo je jednoznačně dáno nerovností x* < n a kongruencí
x* = xe   (mod n), (6-4)
kde e se nazývá šifrovací exponent (z anglického encryption). Čísla e a n jsou veřejně známa a k zašifrování stačí.
Odšifrování probíhá zcela analogicky. Znovu se definuje číslo (x*)° G N splňující nerovnost (x*)° < n tak, aby (x*)° = (x*)d (mod n). Dešifrovací exponent d (z anglického decryption) však není veřejně znám. Je však nutno vyřešit otázku, jak zvolit exponenty e a d tak, aby (x*)° = x, tedy aby zašifrovaná zpráva byla po odšifrování totožná s původní zprávou x.
Nejdříve dokážeme následující větu:
6.2. ŠIFROVÁNÍ ZPRÁ V POMOCÍ PRVOČÍSEL
67
Věta 6.2 Nechť pro přirozené číslo n platí
(e,<p(n)) = l. (6.5)
Potom existuje právě jedno přirozené číslo d < tp(n) takové, že
ed = 1   (mod f(n)). (6.6)
Důkaz: Pro přirozená čísla k = 1,... ,f(n) — 1 definujeme zbytky Zk G {1,..., íp(n)l} pomocí kongruence
ek = Zk   (mod f(n)).
Pokud se dva zbytky rovnají, například je zkl = z^2, je správná kongruence
e(k\ — k2) = 0   (mod f(n)).
Pak podle předpokladu a věty 1. 3. v publikaci [2] existují celá čísla v a, y tak, že ev + íp(ri)y = 1, tedy je e(A;1 — k2)v + ip(n)(ki — ^2)y = k± — k2. Odsud plyne k\ — k2 = 0 (mod f(n)), čili k\ = k2. Všechny zbytky z\. jsou navzájem různá čísla a proto existuje právě jedno d odpovídající zbytku 1, které splňuje (6.4).
Dále dokážeme, že zašifrovaná zpráva x* je po odšifrování totožná s původní zprávou x.
Věta 6.3 Nechť platí (e,ip(n)) = 1. Pak
(x*)° = x. (6.7) Důkaz: Z kongruence (6.6) plyne existence takového čísla r, že
ed = 1 + rip(n) (6-8)
Rozlišujeme dva případy:
1. Nechť platí (x,n) = 1. Potom lze Eulerův vztah umocnit na r-tou a vynásobit jej poté x, čímž obdržíme
Xl+Mn) _ x     (mod n) (qq^
Nyní postupně z (6.7), (6.6), (6.8), a (6.9), plyne, že
(a:*)0 = (x*)d = xed = X1+Mn) = x   (mod n). (6.10)
68
KAPITOLA 6. APLIKACE TEORIE ČÍSEL
Vztah (6.10) tedy platí, neboť obě přirozená čísla x i (x*)° jsou menší než n.
2. Nechť je (x,n) ^ 1. Potom je buď x = p nebo x = q. Bez újmy na obecnosti můžeme předpokládat druhou možnost. Jelikož (PiQ) = 1 můžeme umocnit Fermatův vztah umocnit na r(g — 1), čímž obdržíme
x(P-i)(g-i) = 1   (mod py Jelikož íp(n) = (p — l)(g — 1), platí
xl+r<p(n) — x     (mQC[ pX^
To je opět vztah (6.10), protože px = pq = n. Dál postupujeme jako v bodě 1.
Šifrovací exponent e se volí tak, aby 3 < e < tp(n) a aby platilo (e,íp)n)) = 1. Navíc je třeba zvolit e tak, aby em ^ 1 (mod f(n)) pro malá m, aby nebylo možno odšifrovat zprávu pro d = e — 1. Pokud neznáme hodnoty p a g, je téměř nemožné stanovit hodnotu dešifrovacího exponentu d. Z věty (6.1) však víme, že existuje právě jedno přirozené číslo d < f (n) splňující kongruenci (6.11). Naskytá se otázka jak stanovit jeho hodnotu, známe-li p a q.
Pokud umíme rozložit íp(ri) na prvočísla, pak lze jednoduše vypočítat hodnotu íp(íp(n)). Z Eulerovy věty plyne implikace
(e, y>(n)) = 1 ^ e^(n)) = 1   (mod <p(n)).
Vynásobíme-li předchozí kongruenci d a využijeme-li (6. 6), pak dostaneme explicitní vyjádření pro dešifrovací exponent d < f (n),
d = de^(n)) = edertvW-1 = e^^^1   (mod <p(n)). (6.11)
Pokud íp(n) neumíme rozložit na prvočísla, lze d počítat přímo z kongruence (6.6), a to třebas Eukleidovým algoritmem či prostě zvolíme jiné p či q.
Pro lepší pochopení si ukážeme užití na velmi jednoduchém příkladě. Dejme tomu, že jsme písemnou zprávu převedli na čísla a obdrželi jsme sedm. Volíme n = 15, což dává p = 3 a q = 5. Jako šifrovací klíč můžeme zvolit číslo 3, neboť y?(15) = (3 — 1)(5 — 1) = 8 a (3,8) = 1. Zprávu zašifrujeme, vyřešíme-li kongruenci
6.3. KOUZLA S ČÍSLY
69
73 = Y (mod 15). Máme 343 = 13 (mod 15), můžeme tedy adresátovi napsat třináct. Dešifrovací klíč je opět číslo 3, jak se snadno přesvědčíme vyřešením kongruence ed = 1 (mod íp(íp(n))) = 8. Pro dešifrování musíme vyřešit kongruenci Y3 = X (mod 15), čili 133 = X (mod 15). Snadno se přesvědčíme, že 2197 = 7 (mod 15), tedy jsme obdrželi opět původní zprávu.
6.3   Kouzla s čísly
Když jsem byl ještě malý hošík, bylo vždy obrovskou událostí, když na dědinu přijel kouzelník. Všichni jsme byli nadšeni z jeho triků, ať již to byla kouzla s kartami, mizení či naopak nečekané objevování se věcí a jiné a jiné zázraky, které nás fascinovaly. Kouzelník obvykle v rámci představení jeden trik prozradil, potom všichni žasli, jak je to vlastně jednoduché. Takovým iluzionistou však může být každý a nebude k tomu ani potřebovat hbité prsty, stačí jen využít některé zajímavé vlastnosti čísel. Ostatně v předchozím textu jsme se mohli přesvědčit, že čísla před námi ukrývají spoustu tajemství a je otázkou, zda se nám je vůbec podaří objasnit. Závěrem si proto uvedeme některé čáry s čísly. Další pak může čtenář nalézt v publikacích zaměřených na rekreační matematiku a pokud bude mít i dost času na listování starými novinami, tak i v zábavných okénkách nedělních či později sobotních příloh deníků.
Kouzlo první: Zvolte si libovolné trojciferné číslo tak, aby se první a poslední číslice lišily alespoň o dvě. Utvořte číslo, jehož cifry jsou v opačném pořadí a od většího čísla odečtěte menší. Ve výsledku opět zaměníme pořadí číslic a tato dvě čísla sečteme. Dejme tomu, že si vybereme číslo 115. Pak je třeba spočítat 511-115=396. Dále musíme sečíst čísla a 396 a 693. V našem případě obdržíme 1089. My narozdíl od kouzelníků vysvětlíme každý trik, budeme proto předpokládat, že zvolíme číslo 100a+10&+c, přičemž a > c + 2. Pak 100a + 106 + c- 100c- 106-a = 100(a-c)-a + c = 100(a —c— 1) + 90 + (10 — a + c). Přičteme-li k tomuto výsledku číslo 100(10-a + c)+90 + (a-c-l), obdržíme 900+180+9=1089. Tento výsledek nezávisí na volbě cifer a výsledek 1089 bude při libovolné volbě původního čísla.
70
KAPITOLA 6. APLIKACE TEORIE ČÍSEL
Kouzlo druhé: Zvolme dvě libovolná čísla. Utvořme posloupnost podobným způsobem jak to udělal Fibonacci, tedy každý další člen je součtem dvou předchozích. Sečtěme prvních deset členů této posloupnosti a vydělme ho členem sedmým. Například si zvolíme 3 a 7. Prvních deset členů posloupnosti bude 3, 7, 10, 17, 27, 44, 71, 115, 186, 301 a jejich součet pak 781. Vydělíme-li toto číslo 71, obdržíme 11. Toto číslo musí vyjít vždy. Je-li totiž f\ = m a f2 = n, je f7 = 5m+8n a Y2i=i f i = 55m+88n = U/7. Ke kouzlu lze použít i komplexní čísla, je však třeba dát pozor, aby     / 0.
Kouzlo třetí: Vezměme libovolné přirozené číslo, které je dělitelné třemi. Cifry umocníme na třetí a sečteme, čímž obdržíme nové přirozené číslo. Tento postup opakujeme, avšak zjistíme, že až dospějeme k číslu 153, se celý proces zacyklí. Učeně řečeno budeme-li opakovaně sčítat třetí mocniny cifer přirozeného čísla dělitelného třemi, vždy dospějeme k číslu 153. Mysleme si číslo 1422. Pak platí l3 + 43 + 23 + 23 = 81 i-> 83 + l3 = 513 i-> 53 + l3 + 33 = 153. Označíme-li n = CklOk + • • • + £410 + c0 a m = c\ + • • • + c\ + qj, pak z předpokladu 3\n plyne 3|m. Z kritéria pro dělitelnost trojkou plyne, že n = Y^i=o c? (m°d 3). Podle Malé Fermatovy věty je c3 = q (mod 3). Je tedy
c\ =      Ci = n   (mod 3).
Dále je
m
i=Q i=Q
k
n = ^ CjlO* > ckWk > 10k > (k + 1)93 >      c\ = m.
i=0 i=0
Je-li tedy n > 104, je součet třetích mocnin cifer vždy menší než původní číslo. Zbývá tedy prověřit, jak se řetězec bude chovat po překročení této hranice. Využitím výpočetní techniky lze ověřit, že je zde konečný počet možností aže všechny vedou k číslu 153. Závěrem dodejme, že existují i jiná čísla, která se rovnají součtu třetích mocnin přirozených čísel. Kromě singulárního případu jedničky jsou to i čísla 370, 371 a 407, žádné z nich však není dělitelné třemi.
6.3. KOUZLA S ČÍSLY
71
Kouzlo čtvrté: Zvolme libovolné trojciferné číslo, jehož cifry nejsou všechny stejné. Seřaďme cifry podle velikosti v obou směrech a odečtěme tato dvě čísla. Po konečném počtu kroků dojdeme k číslu 495. Zvolíme-li 169, máme 961-169=792; 972-279=693; 963-369=594; 954-459=495. Pokud by rozdíl měl dvě cifry, je nutno ho doplnit ho zepředu nulou. Stejná vlastnost platí i pro čtyřciferná čísla, kdy se dostaneme k číslu 6174. Toto číslo se na počest objevitele nazývá Kaprekarova konstanta. Vzhledem ke konečnému počtu čísel lze tuto zajímavost ověřit na počítači.
Kouzla s čísly nejsou jedinou skutečností, které mohou žáky upoutat. Podíváme se i na stránku estetickou. Jedničku pythagorejce nepovažovali za číslo, ale za základní stavební kámen čísel ostatních. Co ale druhé mocniny čísel, v jejichž dekadickém zápisu se jiná cifra nevyskytuje? Tož se na to podívejme. I2 = 1, ll2 = 121, lil2 = 12321, 11 ll2 = 1234321 atd. tato krásná symetrie se nám podaří až po číslo 111111111. Je samozřejmé, že pro člověka znalého dekadického zápisu a násobení mnohočlenů to překvapení není. Můžeme si vytvořit hezkou pyramidu
1x8	+ 1	=9	
12x8	+2	=9*	1
123x8	+3	=9*	n
1234x8	+4	=9*	m
12345x8	+5	=9*	Š765
123456x8	+6	=9*	Š7654
1234567x8	+7	=9*	Š76543
12345678x8	+8	=9*	Š765432
123456789x8	+9	=9*	Š7654321
Podobný krásně symetrický obrazec si můžete vytvořit sami podle návodu 9x9+7=88, 98x9+6=888, 987x9+5=8888 atd. Samými jedničkami jsme tento odstavec začínali, proto skončíme návodem, jak si vytvořit krásné vysvědčení, a to tímto způsobem: 1x9+2=11, 12x9+3=111, 123x9+4=1111 atd.
Závěrem této kapitoly zabrousíme do turbodidaktiky. Euler odvodil vzorec em + 1 = 0. V tomto vzorci se vyskytují všechny aritmetické operace (sčítání, násobení, mocnění) a též nej důležitější matematické konstanty (0, l,i,e,7r) právě jednou a je proto matematickými estéty považován za nejkrásnější. (Pokud bychom použili
72
KAPITOLA 6. APLIKACE TEORIE ČÍSEL
synonymum formule, mohli bychom psát Miss formule.) Proveďme turbodidaktické kouzlo a upravujme tento vztah.
Jelikož levá strana rovná se pravé, můžeme odlogaritmovat a máme Í7r=3Í7r či 1=3. Znalec funkce komplexní proměnné rozdíl mezi matematikou a turbodidaktikou odhalí hned; pro jistotu však dodáváme, že pro komplexní proměnnou není logaritmus jednoznačná funkce, takže logaritmování nebylo korektní.
Publikum si určitě žádá další kouzla, jejichž podstata bude utajena, aby se mohlo bavit. Nuže zde jsou.
6.1. Myslete si libovolné číslo od šesti do šedesáti. Toto číslo postupně dělte třemi, čtyřmi a pěti a nahlaste zbytky. Znalec čísel podle zbytků určí původní číslo. Jak je to možné?
6.2. Vynásobte svůj věk deseti od tohoto čísla odečtěte devítiná-sobek libovolného jednociferného čísla. Řekněte výsledek a já uhádnu, jak dlouho již putujete po tomto světě. Jak je to
6.3. A ještě jednu na věk. Své mládí (stáří) vynásobte dvěma, přičtěte pět, součet opět vynásobte pěti a řekněte výsledek. I z tohoto čísla poznám, kolik let jste se dožil. Jak je to možné?
6.4. Nedosti však na tom, umíme uhodnout i přesné datum narození, a to následujícím způsobem. Pořadové číslo měsíce věku vynásobíme stem. K výsledku přičteme číslo značící den a výsledek vynásobíme dvěma. K výsledku přidáme osm. Dále násobíme pěti a přidáme čtyři. Tento výsledek vynásobíme desíti a přidáme čtyři. Poslední operací je přičtení věku v rocích. Odečteme 444 a výsledek rozdělíme na skupiny po dvou cifrách od pravé strany. Kvůli vyváženosti to teď vezmeme zleva; první dvojice určuje měsíc, druhá den a třetí věk zkoumaného člověka.
6.4   Úlohy na procvičení
možné?
6.4. ÚLOHY NA PROCVIČENÍ
73
6.5. Také umíme uhodnout dané číslo. Od mysleného čísla odečteme jedničku, zbytek násobíme dvěma a přičteme myslené číslo. Z tohoto výsledku uhodneme myslené číslo tak, že přičteme dvě a vydělíme třemi.
6.6. Mysli si libovolné číslo, pokud má lichý počet číslic, doplň si dopředu nulu. Libovolným způsobem přesuň cifry na lichých pozicích na sudá místa a naopak. Toto nově vzniklé číslo přičti k původnímu. Součet napiš v opačném pořadí číslic a odečti od součtu původního. Výsledek rozděl na dvojciferné skupiny cl clZ Ilcl jednu mi je prozrad. Já pak uhodnu zbývající skupinu.
Výsledky
6.1. Je-li myšlené číslo x, pak máme x = 3a + r±, x = 46 + r2, x = 5c + r^. Vyjádříme jednotlivé zbytky a spočítáme výraz S = 40ri + 45r2 + 36r3 = 121x - 120a - 1806 - 180c. Výraz S = 120k + x, proto stačí podělit S 120 a zbytek je roven myšlenému číslu.
6.2. Označme věk x a myšlené číslo k. Podle postupu jsme obdrželi lOx — 9k = 10 (x — k) + k. Číslo k je na místě jednotek, zbytek tvoří rozdíl x — k. Z uvedeného je zřejmé, že váš oponent musí být starší devíti let.
6.3. Neznámý věk označíme opět x. Úpravy jsou tyto: (2x + 5)-5 = lOx + 25 = 10(rr + 2) + 5. Dál postupujeme jako v předchozím případě, na rozdíl od předchozího případu to funguje i pro mimina.
6.4. Počítáme vlastně {[(100m + d).2 + 8].5 + 4}.10 + 4 + r -444=10000m + 100d + r.
6.5. Počítáme takto: x = 1; 2{x — 1); 2{x — 1) + x = 3x — 2; 3x-2 + 2.
6.6. Vyjádříme-li číslo v dekadickém zápisu, snadno se vidí, že součet je dělitelný 11. Tímto číslem je dělitelný i součet napsaný v obráceném pořadí. Jedenáctkou je tedy dělitelný i rozdíl, který je navíc dělitelný devíti. Rozdíl je tedy dělitelný
KAPITOLA 6. APLIKACE TEORIE ČÍSEL
číslem 99. Číslo je dělitelné 99 je-li součet dvojciferných skupin dělitelný 99. Sečteme-li všechny prozrazené dvojciferné skupiny a doplníme-li součet do násobku 99, máme zbývající skupinu. Úloha není jednoznačná, pokud je již součet skupin dělitelný 99. Zatajené dvojčíslí může být 00 nebo 99.
Literatura
[1] Dobrovolný B.: Nové matematické rekreace. SNTL Praha 1967
[2] Křížek M., Somer L., Šolcova A.: Kouzlo čísel (Od velkých objevů k aplikacím). Academia Praha 2011
[3] Lepká K.: Historie Fermatových kvocientů (Fermat-Lerch). Dějiny matematiky sv. 14, Prometheus Praha 2000
[4] Lerch M.: Základové ryze arithmetické theorie veličin. Athenaeum 3 (1886), 223-236
[5] Macák K.:Tři středověké sbírky matematických úloh. Prometheus, Praha 2001
[6] Novoveský Š., Križalkovič K., Léčko L: Zábavná matematika. Státní pedagogické nakladatelství Praha 1974
[7] Sierpiňski W.: Co víme a nevíme o prvočíslech. Státní pedagogické nakladatelství Praha 1966
[8] Singh S.: Velká Fermatova věta. Academia Praha 2000
[9] Salát T.: Dokonalé a spriatelené čísla. Škola mladých matematiků. Mladá fronta Praha 1969
[10] Šalát T., Smítal J.: Teória množín. Vydavatelstvo technickej a ekonomickej literatúry Alfa Bratislava 1986.
[11] Vinogradov,  I.  M.:  Základy theorie čísel. Nakladatelství Československé akademie věd. Praha 1953
75
76 LITERATURA
[12] Znám, Š. a kol.: Pohlad do dejín matematiky. Vydavatelstvo technickej a ekonomickej literatúry Alfa Bratislava 1986.
[13] Znám, S.: Teória čísel. Vydavatelstvo technickej a ekonomickej literatúry Alfa Bratislava 1977.
[14] http://www.kodys.cz