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. 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. Budeme se snažit text doplnit 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. Ponořme se tedy do tajemného světa čísel a začněme hledat zajímavé vlastnosti a překvapující souvislost. 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 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ř. [11], str. 168. 3 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 < 0. (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í (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 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. Říkáme, že 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 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. 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. Této vlastnosti se říká tranzitivita. 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 O 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 = cfcH-----h c2 + ci + c0 je ciferný součet čísla n. Pak je n - s = (10fc - l)cfc + • • • + 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). 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 = 2cfc10fc~2 + • • • + 2c2 + IOIOci + c0. Rozdíl n-m = 98cfc10fc~2 + • • • + 98c2 je dělitelný sedmi, protože 7|98. Jelikož platí 7|m, musí být čí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.7+56=546. 546:7=48. Číslo m je dělitelné sedmi, je tedy i 7056 dělitelné sedmi. 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(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 = + . Použitím binomické věty pak obdržíme (26 + 1)»« = (" + M 26»« + (" | M 26» + ... + + \) 26*+ n J \n + 1J 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 čísle 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 (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. 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ů 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 čísel 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. 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. 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 = uq, b = n\ a r = n2, má tato rovnice tvar (n0,Tii) = (ni,n2). Nyní mohou nastat dva případy: Je-li n2 = 0, je n\ hledaný největší společný dělitel čísel uq = a a n\ = b. Je-li n2 Ý 0 musíme dělit číslo ni číslem n2 a celý proces zopakovat. Obdržíme systém rovnic (n0,Tii) = (nun2) (m,n2) = (n2,n3) (n2,n3) = (n3,n4) {nk-Unk) = (nk,nk+1) Jelikož je ni+1 je zbytek po dělení rií_1 číslem n,i pro {i = 1,2,..., k) a množina N je dobře uspořádaná, musí platit rii > n2 ... > 0. Musí být nk+i = 0 a {nk_i,nk) = nk. Podle předchozích úvah obdržíme (n0, ni) = (ni, n2) = ... = (nk-Unk) = nk, odkud (n0,Tii) = (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 = 13x110+82; 110=1x82+28; 82=2x28+26; 28=1x26+2; 23=2x13. (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=28x35+8; 35=4x8+3; 8=2x3+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. 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, zejména má-li číslo velký počet cifer je jeho faktorizace mnohdy velmi obtížná. Pro malá čísla můžeme využít Eratosthenova síta2. Dejme tomu, že máme nalézt všechna prvočísla menší než 100. Všechna čísla 2Eratosthenes 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 číslo. Změřil též zemský poloměr 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. 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 1=1 Prvočíslo p,i se nazývá prvočinitel. Věta 1.9 Jestliže „«1 „"2 . . . „Oř _ nPl „ft . . . Ps Pl P2 ľr ~ Hl H2 i kde pi < P2 < ■■■ < pr,Qi < Q2 < ••• < Qs Jsou prvočísla a r, s, cti, A G N, pak r = s, pi = qi, cti = fy pro každé i = 1,..., r. Důkaz: Nechť m = p^p^2 • • 'Prri n = Qi1^2 ''' 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 a r = s. Předpokládejme dále, že «1 > fy pro nějaké i G {l,...,r}. Vydělíme-li rovnost m = n číslem př\ obdržíme nai . . . nai_/3i . . . 1, mluvíme o primitivní pythagorejské trojici. Odpověď na otázku jak sestavit libovolnou pythagorejskou trojici nalezneme již u Diofanta. Věta 1.12 Uspořádaná trojice 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é Babylónu. 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 4Jc, Ak + 1 či 4/c + 2, nikdy nemůže být tvaru Ak + 3 = 4(A; + 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 Tn?\n, jestliže Tn?\n, ale mJ+1 )(n. Pro j = 0 žmde symbol m°||n znamenat, že m)fn. 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 G {1,..., n — 1} je n — k mezi čísly 1 a n — 1. Číslo n nedělí ani k\ ani (n — &)!, ale dělí n\. Jelikož (fc) = k\(n'-k)\i 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(n-l)---(n-p+l) \pj p(p-l)---2-l • l'J Dále předpokládejme, že p'Hn 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 ||n(n — 1) • • • (n — p + 1) a zřejmě i — 1) • • • 2 • 1. Podle (1. 2) dostaneme, že p5-1!! (n). Ale n)( (n), protože pi\\. 1.5 Úlohy k procvičení 1.1. Druhou mocninu každého přirozeného čísla je možné napsat buď ve tvaru Ak nebo Ak + 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. 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ŕ + An4. 1.15. Dokažte, že čísla tvaru 34n+4 — 43«+3 jsou dělitelná 17. 1.16. Dokážte, že číslo n +(>+2) je pro ce\£ n vždy celé a složené. 1.17. Dokažte, že výraz V = 24n+1 - 22n - 1 je dělitelný devíti. 1.18. Dokažte, že každé čí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|6 =>- b = ka, b\a =>- a = Ib. Je tedy b = k(lb). Čísla a a 6 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 vyjetí z Brna. 1.4. an -bn = (a- b)^1 + an-2b + ■■■ + 6n_1). 1.5. Důkaz provedeme indukcí. Pro n = 1 tvrzení platí. Volba n = k+1 dává po úpravě 4k+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 = 8A; 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 = 3A; + 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 - \)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 = Uk2(k2 - l)(k2 - 4) = Uk2(k - l)(k - 2)(k + 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. 1.14. Číslo N = (m2 + 2n2)2 — Am2n2, což lze psát jako N = [(m + n)2 + n2] [(m — n)2 + n2]. Jelikož V 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á N = 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 + l)(n2 + 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_3 bude dělitelno 63. Ale ani jedno z čísel A0 = 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 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). 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 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, ,p m 1 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áníme. 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íplatiťů(a1a2) = ů^a^ů^) je-li (a!,a2) = 1. 1V publikaci [10] jsou exponenty mylně uvedeny jako koeficienty. 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 a^. Pak máme ů(clq) = ů(l.a0)=ů(l)ů(ao). Věta 2.3 Nechť ů^a) aů(a2) jsou multiplikativní funkce. Pak také funkce $0(0) = $1 (o)$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)^2(01)^2(02) = ^o(oi)^o(o2)- Věta 2.4 Nechť ů(a) je multiplikativní funkce a a = Piľp22 ■ ■ -Pkk je kanonický rozklad čísla a. Pak platí J2$(d) = {l + ů(Pl) + ů(pi) + ... + Ů(p1k)... d\a (l+ů(pk)+ů(p2k) + ...+ů(ptk))- (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 0(př)tf(p?) • • • $(pík) = tf(př(p? • • • (pík); 0 <(31 1 a //(a) = (—l)k v opačném případě. Číslo k udává počet prvočinitelů čísla a. 2 Möbius Příklad 2.3 Môbíova 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) = O, /x(343) = O, /x(245) = 0. V ostatních případech už musíme počítat prvočinitele, je tedy /x(39) = 1, /x(110) = — 1 atd. Jelikož jednička být na součin prvočísel být rozložena nemůže, je Věta 2.5 Nechť ů(a) je multiplikativní funkce a a = p^p^2 ■ ■ - Pk je kanonický rozklad čísla a. Pak platí 5>(d)0(d) = (1 - 0(pi))(l - 0(p?)) ... (1 - ů(pk)). (2.5) Je-Zž 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 Mi) = o. d\a a > 1 a = 1 (2.6) Důsledek 2.2 Volíme-li ů(a) 2, obdržíme 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. 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, 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 není ř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í 3.1. Z uvedených rovnic vyberte ty, které jsou řešitelné: a)7x + 3y = 2 b)18x + A0y = 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. 3.11. Pro jaká x je výraz x3 + 2x + 2 násobkem čísla 125? Z10/47 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, 6) / c 3.2. x = -20 + At,y = -20 + 3í, t G Z 3.3. x = 1 + 15í, t G Z 3.4. m = -100 + 3í, z = 200 - 5ŕ, ŕ = 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 í = 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 + í, 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 í = — 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, í G Z 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 4 Kongruence V této kapitole se budeme zabývat kongruencemi. Tento pojem zavedl do teorie čísel Gauss a umožňuje nám zkráceně zapsat důležité vztahy mezi čísly. Def. 4.1 Nechi 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 Nechi 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. Důkaz: Nechť a\ = b\ mod m a a2 = b2 mod m. V tomto případě je ai = bi + mt\ a a2 = b2 + mt2 a a\ + a2 = b\ + b2 + m(ti + t2), 39 tedy ai + a2 = bi + b2. 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). Narozdí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± — bi)d, je dělitelný číslem m. Proto je ai — bi 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 + ni\dt, a\ = b\ + ni\t, z čehož plyne a\ = b\ (mod m)i. 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 d. 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; pro r > y je g = r — m; konečně je-li m sudé a r = y je za g 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 Nechi (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ě 1. Aby kongruence (4.2) měla řešení, je nutné, aby b bylo dělitelné číslem d, jinak kongruence (4.2) není (4.2) možná při žádném celém čísle 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á kon-gruence 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 m1? 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\ + mii + 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.1 Řešte kongruenci Ax = 1 (mod 6). Tato kongruence nemá řešení, neboi (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ů. Příklad 4.2 Ř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.3 Řešte kongruenci 6x = 9 (mod 15). Jelikož (6,15) = 3 a 3 | 9, bude mít kongruence 3 řešení. Vydělíme-li obě strany kongruence 3, obdržíme novou kongruencí 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í kongruencí, kde (a,m) = 1, lze využít Eulerovu větu. Skutečně, je-li a^(m) = 1 (mod m), je i af^b = b (mod m). Odsud máme ax = af^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.4 Řešte kongruencí 6x = 2 (mod 7). Jelikož ,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. Věta 4.20 Nechť a je kvadratický zbytek podle modulu p. Pak kongruence (4-9) má právě dvě řešeni. 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 = x\, 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) = (x1}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 P-y- kvadratických zbytků, které jsou kongruentní s čísly 12,22,..., (2Y')2 a ^Y' 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 < / < 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í p—i a~ = 1 (mod p); (4.11) Je-li a kvadratický nezbytek podle modulu p, platí = -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 (a1^ — ŕj (a1^ + 1 j = 0 (mod p). Jelikož rozdíl obou závorek je roven dvěma, tak platí pouze jedna z kongruenci (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 nezbytky vyhovovat kongruenci (4.12). 4.8 Legendreův symbol Legendreův symbol yj^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 = at (mod p). Pak platí (jf) = (^j . Důkaz: Jelikož 1 = l2, je jednička kvadratický zbytek pro každý modul a tedy platí: 1. P/ Lichá prvočísla můžeme vyjádřit buď ve tvaru Ak + 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 4/c+l a kvadratickým nezbytkem prvočísel tvaru Ak + 3. Platí tedy p ) Věta 4.24 Pro Legendreův symbol platí: 'ab... A /a\ íb\ (l p / \p/ \p/ \p Důkaz Vskutku máme - = (afe... /) 2 = 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 Naskýtá se otázka, zda by nešlo zavést podobný symbol i v (4.14) 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. 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 ď'1 = 1 (modp). (4.15) 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 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 (mod p). 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 g (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í a^(n) = 1 (mod n), (4.16) 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 (Wílson) 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á. Věta 4.29 Diofantická rovnice xn + yn = zn (4.18) nemá pro n > 2 řešení 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 [7]. 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) Z2/110 4.2. Řešte kongruence a) 20x = 4 (mod 30) b) 20x = 30 (mod 4) c) 353x = 254 (mod 400) Z3/110 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). Z8/111 4.4. Řešte soustavu kongruenci x = 2 (mod 3), x = 3 (mod 5), x = 5 (mod 2). Z9/111 4.5. Řešte soustavu kongruenci x = 1 (mod 4), x = 0 (mod 3), x = 5 (mod 7). Z10/141 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. Zll/141 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 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ěž 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 n členů geometrické posloupnosti. Platí ofc+l _ i Q2 _ i a(n) =------ = (2fc+1 - 1) • 4 > 2 • {2k • 3) = 2n. 2 1 3 1 Třetí množinu pak tvoří čísla n > 1, pro něž je 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 čísla. 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 a(n) = - 2-1p-1 Odtud jednoduchou úpravou zjistíme, že la ai+1 — 1 r>ak+1 — 1 a(n) = __LEi__... ti__ - o* - 1 wn - 9"/ y } 2-1 Pl protože Rovnost (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).g = / (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 / + g + d, což je v rozporu s (5.2). Proto / má pouze dva dělitele, a to sebe sama a g = 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. Pi ~ 1 Pl ~ 1 Pl_ Pl ~ 1 Pk ~ 1 ak+l 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 = Piľp22 ■ ■ -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\.d2 ... 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 = Pi1 -P22■ V prvním případě je «i = 3, ve druhém «i = a2 = 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 n = 2n + 1 prvočíslo, pak m = 2m pro nějaké m G {0,1,2,...}. 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) 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 nenašel, že F$ = 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 [8], 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ž o~(a) = o"(6) = a + 6. Důkaz: Je zřejmé, že počet pravých dělitelů čísla m je o~(m) — m. Jsou-li a a 6 spřátelená je současně o~(a) — a = b a a(b) — b = a. Vypočítáme-li z druhé rovnice b a dosadíme do první, máme a(a) = 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(l) 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 ■ ■ .p^ + 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 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 juktoriá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 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 + (-\)k-lck^ + • • • + Cl + c0). (6.3) 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 [13]. 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 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: Věta 6.2 Nechť pro přirozené číslo n platí (e,(n)) = 1 ^ e^(n)) = 1 (mod ^(n)). Vynásobíme-li předchozí kongruenci d a využijeme-li (), pak dostaneme explicitní vyjádření pro dešifrovací exponent d < f (n), d = de^(n)) = ede^vW-1 = e^^^1 (mod 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. 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 k k m = c3 = q = n (mod 3). i=q i=q Dále je k k n = ^CilQŕ > ck10k > 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. 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 doplni 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. 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, 1, i, e, 7r) právě jednou a je proto matematickými estéty považován za nejkrásnější. (Pokud bychom použili 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.4 Úlohy na procvičení možné? 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.5. Také umíme uhodnout dané číslo. Od myšleného čísla odečteme jedničku, zbytek násobíme dvěma a přičteme myšlené číslo. Z tohoto výsledku uhodneme myšlené čí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 + r1? x = 46 + r2, x = 5c + r3. Vyjádříme jednotlivé zbytky a spočítáme výraz S = A0r1 + 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ámy věk označíme opět x. Úpravy jsou tyto: (2x + 5).5 = 10x + 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ý čí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, Prométheus Praha 2000 [4] Lerch M.: [5] Novoveský Š., Križalkovič K., Léčko L: Zábavná matematika. Státní pedagogické nakladatelství Praha 1974 [6] Sierpiňski W.: Co víme a nevíme o prvočíslech. Státní pedagogické nakladatelství Praha 1966 [7] Singh S.: Velká Fermatova věta. Academia Praha 2000 [8] Salát T.: Dokonalé a spriatelené čísla. Škola mladých matematiků. Mladá fronta Praha 1969 [9] Šalát T., Smítal J.: Teória množín. Vydavatelstvo technickej a ekonomickej literatúry Alfa Bratislava 1986. [10] Vinogradov, I. M.: Základy theorie čísel. Nakladatelství Československé akademie věd. Praha 1953 [11] Znám, Š. a kol.: Pohlad do dejín matematiky. Vydavatelstvo technickej a ekonomickej literatúry Alfa Bratislava 1986. [12] Znám, Š.: Teória čísel. Vydavatelstvo technickej a ekonomickej literatúry Alfa Bratislava 1977. 75 [13] http://www.kodys.cz