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 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 = 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. Odpověď na otázku jak sestavit libovolnou pythagorejskou trojici nalezneme již u Diofanta.4. 4Diofantos z Alexandrie žil ve 3. století. Z jeho hlavního díla Aritmetika se 14 KAPITOLA 1. TEORIE DĚLITELNOSTI 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 bud' 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 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. Dokážeme větu, která uvádí vztah mezi prvočísly a binomickými koeficienty (kombinačními čísly). zachovala jen část. 1.5. ÚLOHY K PROCVIČENÍ 15 Věta 1.14 Přirozené číslo n je prvočíslem právě tehdy, když n dělí (^) pro každé k E {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 číslo 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 ti(ti- l)---(n-p+l) p(p- l)---2- 1 ' 1 ' ' 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 \\n(n — 1) • • • (n — p + 1) a zřejmě i p||p(p — 1) • • • 2 • 1. Podle (1. 2) dostaneme, že (n). Ale (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 Ak nebo Ak + 1. Dokažte. 1.2. Jestliže současně platí a|6 a 6|a, pak je |a| = 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. 16 KAPITOLA 1. TEORIE DELITEĽNOSTI 1.8. Součet čtverců dvou po sobě jdoucích čísel zmenšený o jednu je dělitelný čtyřmi. 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 jsou dělitelná 17. 1.16. Dokažte, že číslo n +("+2) je pro celá 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.9 Číslo n3 + lln je dělitelné šesti pro libovolné n. Dokažte. 1.4 bn = (a - 6) (a™-1 + a -% + ■■■ + bn-1). 1.5. ÚLOHY K PROCVIČENÍ 17 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ě A;3 + 3A;2 + 3A; + 1 + + 11. Výraz 3(A;2 + k + 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)(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. 18 KAPITOLA 1. TEORIE DĚLITELNOSTI 1.14. Číslo iV = (m2 + 2n2)2 — Am2n2, což lze psát jako iV = [(m + n)2 + íí2] [(m — n)2 + íí2] • 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 = 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 a^. Pak máme ů(clq) = ů(l.a0)=ů(l)ů(ao). Věta 2.3 Nechťů^a) aů2(a) 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) = = $i(ai)$2(ai)$i (02)^2(02) = $0(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 + $(pi)+tf(p?) + ... + tf(Pife))... 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 . .. ů(pl*) = ů(j£pfc . . . (p^); 0 <(31 1 a //(a) = (—l)k v opačném případě. Číslo k udává počet prvočinitelů čísla a. 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) = 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ž číslo jedna na součin prvočísel být rozloženo nemůže, je /i(l)=0. Věta 2.5 Nechť ů(a) je multiplikativní funkce a a = p^p^2 ■ ■ -P^ je kanonický rozklad čísla a. Pak platí 5>(d)0(d) = (1 - 0(pi))(l - "9{p\))... (1 - ů(pk)). (2.5) d\a 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) = /i(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 íí|a Důsledek 2.2 Volíme-li ů(a) = \, obdržíme 1-^1-^ -1-^1, a>l dl« ^ 1, a = 1 24KAPITOLA 2. NĚKTERÉ FUNKCE POUŽÍVANÉ V TEORII ČÍSEL 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 0,1,..., a — 1 která jsou nesoudělná s a. Příklad 2.4 = 1, y?(2) = 1, y?(6) = 2, y?(7) = 6, y?(9) = 6, 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 Necht a = PiľP22 ■■■pf* 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 - - \) = 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.8) pa — p' 2.5. PŘÍKLADY K PROCVIČENÍ 25 2.3. Vypočtěte tr(51450) a r(51450) 2.4. Vypočtěte y?(41) a ^(1786050) 2.5. Kanonický rozklad čísla je tvaru 2a.76, součet dělitelů pak 6000. Určete ono číslo. 2.6. Stanovte nejmenší kladné číslo n = 2e.pi.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 'Pl-lp2-l po uprave l)(p1 + l).(p2 + l).... 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áti 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 \ i 1 , 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 — 21 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 = k2 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 + kty tvar kTj + x^. Máme tedy an(x0 + kt)n + . . . + CLi(xo + kť) + CLq = an(kTn + x%) + ... + cli{xq + kť) + a0 = k(anTn + .. . + a1t) + (anxq +.. . + airr0 + 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 < 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 + 19t, 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 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. 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\ = b\+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 vy dě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 + m\dt, a\ = b\ + m\t, 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ě 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 x% = 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 = 1 (mod m), je i ď^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ž 3 je liché. Nechť dále n = p1p2...pr, kde Pí 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) aJ 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 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 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 o~(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 o~(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 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 _ i _ 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 = 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) ... (ak + 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 = p"1, nebo je n = p"1 .p22. V prvním případě je «i = 3, ve druhém a± = 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 Em = 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 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ů (n)) = 1 ^ e^(n)) = 1 (mod c + 2. Pak 100a + 106 + c- 100c- 106-a = 100(a-c)-a + c = 100(a —c— l) + 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(x + 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