Úvodní slovo autora. Karel Lepka

Základy elementárn´ı teorie ˇc´ısel Karel Lepka

´ Uvodn´ ı slovo autora V´ yznamn´ y nˇemeck´ y matematik Karl Friedrich Gauss napsal, ˇze matematika je královna vˇed a teorie ˇc´ısel je královnou matematiky. Je skuteˇcnost´ı, ˇze bez ˇc´ısel by matematika nebyla matematikou. Samozˇrejmˇe ˇze jiˇz nepovaˇzujeme ˇc´ısla za základ svˇeta jako P´ ythágorás a jeho ˇskola, ale je pravdou, ˇze ˇc´ısla maj´ı v matematice hlubˇs´ı v´ yznam neˇz je poˇc´ıtán´ı. Tento uˇcebn´ı text obsahuje základn´ı poznatky z elementárn´ı teorie ˇc´ısel.

Kapitola 1 Teorie dˇ elitelnosti V této kapitole se seznám´ıme s pojmy teorie dˇelitelnosti jako jsou dˇelitelnost ˇc´ısel, nejmenˇs´ı spoleˇcn´ y násobek, nejvˇetˇs´ı spoleˇcn´ y dˇelitel. Dále se seznám´ıme s kritérii dˇelitelnosti.

1.0.1

Z´ akladn´ı pojmy a vˇ ety

Tuto ˇca´st zaˇcneme letitou ˇzertovnou hádankou. Babiˇcka má pˇet vnouˇcat a dvanáct jabl´ıˇcek. Jak to má udˇelat, aby vˇsechna vnouˇcata byla spravedlivˇe podˇelena? Správná odpovˇed’ je, ˇze jim udˇelá ˇstr˚ udl. Ve v´ yˇse uvedeném pˇr´ıpadˇe babiˇcka jinou moˇznost nemá, pokud by vˇsak pˇrikoupila dalˇs´ı tˇri jabl´ıˇcka, tak by kaˇzdému vnouˇckovi dala tˇri jabl´ıˇcka a mohla by si uˇsetˇrit práci se ˇstr˚ udlem. Babiˇcka ovˇsem m˚ uˇze dvˇe jabl´ıˇcka dˇetem zatajit, ta zbudou a opˇet vnuky spravedlivˇe podˇeli, tentokrát ovˇsem jen dvˇema jabl´ıˇcky. Nyn´ı pˇrevedeme uveden´ y pˇr´ıklad do jazyka matematického a zobecn´ıme ho, jin´ ymi slovy dokáˇzeme následuj´ıc´ı vˇetu. Kaˇzdé celé ˇc´ıslo 𝑎 m˚ uˇzeme jednoznaˇcn´ ym zp˚ usobem vyjádˇrit ve tvaru 𝑎 = 𝑏𝑞 + 𝑟, kde 𝑏 je kladné ˇc´ıslo a 𝑟 je celé ˇc´ıslo vyhovuj´ıc´ı podm´ınce 0 ≥ 𝑟 < 𝑏. D˚ ukaz provedeme sporem. Pˇredpokládejme, ˇze plat´ı 𝑎 = 𝑏𝑞1 + 𝑟1 a souˇcasnˇe 𝑎 = 𝑏𝑞2 + 𝑟2 . Odeˇcteme-li od druhé rovnice prvn´ı, obdrˇz´ıme 0 = 𝑏(𝑞2 − 𝑞1 ) + 𝑟2 − 𝑟1 , tedy 𝑟2 − 𝑟1 je násobkem 𝑏. Jelikoˇz vˇsak je ∣𝑟2 − 𝑟1 ∣, mus´ı platit 𝑟1 = 𝑟2 a tedy i 𝑞1 = 𝑞2 . ´ Uloze, ve které se má k dané dvojici cel´ ych ˇc´ısel 𝑎, 𝑏 na j´ıt dvojici ˇc´ısel 𝑞, 𝑟 splˇ nuj´ıc´ı vztah (), se ˇr´ıká dˇelen´ı; ˇc´ıslo 𝑎 naz´ yváme dˇelenec, ˇc´ıslo 𝑏 dˇelitel. Zamˇeˇrme nyn´ı svou pozornost na ˇc´ıslo 𝑟. Pro 𝑟 > 0 mluv´ıme o dˇelen´ı se zbytkem. V tomto pˇr´ıpadˇe je 𝑞 ˇcásteˇcný pod´ıl a 𝑞 je zbytek. Je-li 𝑟 = 0, mluv´ıme o dˇelen´ı beze zbytku; ˇ ıkáme téˇz, ˇze ˇc´ıslo 𝑎 je dˇelitelné ˇc´ıslem 𝑏, coˇz budeme ˇc´ıslo 𝑞 se naz´ yvá pod´ıl. R´ ˇ ıkáme, ˇze 𝑎 je násobkem 𝑏. znaˇsit 𝑏∣𝑎. R´ Pozor! Zbytek je vˇzdy ˇc´ıslo nezáporné, tedy −41 = 11.(−4) + 3, nikoliv −41 = (−3).11 − 8. Plat´ı následuj´ıc´ı vˇety: Vˇ eta 1.1 Je-li 𝑎 násobkem 𝑚 a je-li souˇcasnˇe 𝑚 násobkem 𝑏, pak 𝑎 je násobkem 𝑚. 3

Vˇ eta 1.2 Jsou-li v rovnosti typu 𝑘 + 𝑙 + . . . + 𝑛 = 𝑝 + 𝑞 + . . . + 𝑠 vˇsechny ˇcleny s výjimkou jednoho násobkem 𝑏, pak i tento ˇclen je násobkem 𝑏. Vˇ eta 1.3 Necht’ 𝑎∣𝑏 a 𝑎∣𝑐. Pak a—(bx+cy) pro libovolná celá ˇc´ısla 𝑎 a 𝑦. D˚ uslekem této vˇety je skuteˇcnost, ˇze pokud ˇc´ıslo 𝑎 dˇel´ı ˇc´ısla 𝑏 a 𝑐, pak dˇel´ı i jejich souˇcet a rozd´ıl. Vˇ eta 1.4 Necht’ 𝑎∣𝑏. Pak 𝑎∣𝑏𝑐, kde 𝑐 je libovolné celé ˇc´ıslo. Vˇ eta 1.5 Necht’ 𝑎∣𝑏 a souˇcasnˇe 𝑏∣𝑐. Pak 𝑎∣𝑐. Této vlastnosti se ˇr´ıká tranzitivita. D˚ ukazy tˇechto tvrzen´ı jsou snadné a doporuˇcujeme, aby si je ˇctenáˇr udˇelal jako cviˇcen´ı. Nask´ ytá se otázka, jak poznat je-li ˇc´ıslo 𝑎 dˇelitelné ˇc´ıslem 𝑏. Ve vˇeku poˇc´ıtaˇc˚ u a kalkulaˇcek se zdá b´ yt nejjednoduˇsˇs´ı tato ˇc´ısla prostˇe vydˇelit. Autor má sice velk´ y obdiv k modern´ı v´ ypoˇcetn´ı technice, pˇresto vˇsak ani tato si neum´ı s mnoha otázkami teorie ˇc´ısel poradit. V nˇekter´ ych pˇr´ıpadech by bylo nasazen´ı této techniky zbyteˇcné, asi jako j´ıt s kanonem na vrabce, nebot’ dˇelitelnost m˚ uˇzeme poznat mnohem snadnˇeji. Uvedeme si proto nˇekolik kritéri´ı pro dˇelitelnost ˇc´ısel, zejména pro pˇr´ıpady, kdy je dˇelitel malé ˇc´ıslo. Vˇ eta 1.6 Pˇrirozené ˇc´ıslo 𝑛 je dˇelitelné: a) dvˇema, je-li posledn´ı cifra sudá, b) tˇremi, je-li jeho ciferný souˇcet dˇelitelný tˇremi, c) ˇctyˇrmi, je-li jeho posledn´ı dvojˇc´ısl´ı dˇelitelné ˇctyˇrmi, d) pˇeti, je-li jeho posledn´ı cifra 0 nebo 5, e) ˇsesti, je-li sudé a dˇelitelné 3, f ) sedmi, je-li dvojnásobek poˇctu stovek zvˇetˇsený o posledn´ı dvojˇc´ısl´ı dˇelitelný 7, g) osmi, je-li posledn´ı trojˇc´ısl´ı dˇelitelné 8, h) dev´ıti, je-li jeho ciferný souˇcet dˇelitelný 9, i) des´ıti, je-li jeho posledn´ı cifra 0. D˚ ukaz: Kaˇzdé pˇrirozené ˇc´ıslo 𝑛 lze v dekadické ˇc´ıselné soustavˇe vyjádˇrit následuj´ıc´ım zp˚ usobem: 𝑛 = 𝑐𝑘 10𝑘 + ⋅ ⋅ ⋅ + 𝑐2 102 + 𝑐1 10 + 𝑐0 , kde 𝑐𝑖 ∈ {0, 1, 2, . . . , 9} a 𝑐𝑘 ∕= 0. Z tohoto vyjádˇren´ı okamˇzitˇe plynou tvrzen´ı a), c), d), g) a i). Necht’ 𝑠 = 𝑐𝑘 + ⋅ ⋅ ⋅ + 𝑐2 + 𝑐1 + 𝑐0 je cifern´ y souˇcet ˇc´ısla 𝑛. Pak je 𝑛 − 𝑠 = (10𝑘 − 1)𝑐𝑘 + ⋅ ⋅ ⋅ + 99𝑐2 + 9𝑐1 . Jelikoˇz kaˇzd´ y sˇc´ıtanec na pravé stranˇe je dˇeliteln´ y dev´ıti a stejnˇe tak je dˇelitelné dev´ıti ˇc´ıslo 𝑠, mus´ı b´ yt dˇelitelné dev´ıti i ˇc´ıslo 𝑛. T´ım je dokázáno h) a souˇcsnˇe i b).

Zb´ yvá dokázat kritérium pro dˇelitelnost sedmi. Dvojnásobek stovek ˇc´ısla 𝑛 zvˇetˇsen´ y o posledn´ı dvojˇc´ısl´ı je roven 𝑚 = 2𝑐𝑘 10𝑘−2 + ⋅ ⋅ ⋅ + 2𝑐2 + 1010𝑐1 + 𝑐0 . Rozd´ıl 𝑛 − 𝑚 = 98𝑐𝑘 10𝑘−2 + ⋅ ⋅ ⋅ + 98𝑐2 je dˇeliteln´ y sedmi, protoˇze 7∣98. Jelikoˇz plat´ı 7∣𝑚, mus´ı b´ yt ˇc´ıslo 𝑛dˇelitelné sedmi. Kritérium dˇelitelnosti sedmi je oproti zb´ yvaj´ıc´ım pomˇernˇe komplikované a pro praxi nepˇr´ıliˇs vhodné. Uvedeme jednoduch´ y pˇr´ıklad. Chceme-li zjistit, zda je ˇc´ıslo 7056 dˇelitelné sedmi, mus´ıme postupovat následuj´ıc´ım zp˚ usobem. 70.7+56=546. ˇ 546:7=48. C´ıslo 𝑚 je dˇelitelné sedmi, je tedy i 7056 dˇelitelné sedmi. Kritéria pro dˇelitelnost dvojcifern´ ymi prvoˇc´ısly menˇs´ımi neˇz dvacet m˚ uˇze ˇctenáˇr naj´ıt napˇr. v [2] na str. 31 resp. 164. Nyn´ı si uvedeme nˇekolik u ´loh na dˇelitelnost ˇc´ısel. Pˇr´ıklad: Urˇcete, jak´ y den bude za 39 dn´ı, je-li dnes stˇreda. ˇ sen´ı: 39=7.5+4. Za 39 dn´ı bude nedˇele Reˇ Pˇr´ıklad: Dokaˇzte, ˇze v´ yraz 𝑎(𝑎 + 1)(2𝑎 + 1) je dˇeliteln´ y 6 pro libovolné celé ˇc´ıslo 𝑎. ˇ sen´ı: 𝑎(𝑎 + 1)(2𝑎 + 1) = 𝑎(𝑎 + 1)(𝑎 + 2) + 𝑎(𝑎 + 1)(𝑎 − 1). Oba sˇc´ıtance jsou Reˇ souˇcinem tˇr´ı po sobˇe jdouc´ıch ˇc´ısel, jedno z nich mus´ı b´ yt dˇelitelné 3 a nejménˇe jedno mus´ı b´ yt dˇelitelné 2. Pˇr´ıklad 1: Dokaˇzte, ˇze pro kaˇzdé 𝑛 ∈ 𝑁 plat´ı 169∣33𝑛+3 − 26𝑛 − 27. Upravme nejdˇr´ıve prvn´ı ˇclen daného v´ yrazu. 33𝑛+3 = 27𝑛 + 1 = (26 + 1)𝑛+1 . Pouˇzit´ım binomické vˇety pak obdrˇz´ıme ( ) ( ) ( ) 𝑛+1 𝑛+1 𝑛+1 𝑛+1 𝑛+1 𝑛 (26 + 1) = 26 + 26 + . . . + 262 + 26(𝑛 + 1) + 1 0 1 𝑛−1 Je zˇrejmé, ˇze vˇsechny ˇcleny tohoto rozvoje s v´ yjimkou posledn´ıch jsou dˇelitelné ’ 169, nebot obsahuj´ı minimálnˇe druhou mocninu ˇc´ısla 26 = 2.13. Posledn´ı dva ˇcleny pak dávaj´ı 26𝑛 + 27 a tud´ıˇz se vyruˇs´ı s posledn´ımi dvˇema ˇcleny daného v´ yrazu.

1.0.2

Nejvˇ etˇ s´ı spoleˇ cn´ y dˇ elitel, nejmenˇ s´ı spoleˇ cn´ y n´ asobek

V této ˇca´sti budeme ˇreˇsit dva problémy. Budeme hledat nejvˇetˇs´ı ˇc´ıslo, které souˇcasnˇe nˇekolik r˚ uzn´ ych ˇc´ısel a naopak nejmenˇs´ı ˇc´ıslo, které je souˇcasnˇe dˇelitelné nˇekolika r˚ uzn´ ymi ˇc´ısly. Definice: Kaˇzdé celé ˇc´ıslo, dˇel´ıc´ı souˇcasnˇe celá ˇc´ısla 𝑎, 𝑏, . . . , 𝑙 se naz´ yvá jejich spoleˇcn´ ym dˇelitelem. Je-li aspoˇ n jedno z uveden´ ych ˇc´ısle r˚ uzné od nuly, pak je poˇcet jejich spoleˇcn´ ych dˇelitel˚ u koneˇcn´ y a tedy jeden z nich je nejvˇetˇs´ı. Ten se naz´ yvá nejvˇetˇs´ım spoleˇcn´ ym dˇelitelem ˇc´ısel 𝑎, 𝑏, . . . , 𝑙 a budeme ho znaˇcit (𝑎, 𝑏, . . . , 𝑙). Je-li (𝑎, 𝑏, . . . , 𝑙) = 1, pak ˇc´ısla 𝑎, 𝑏, . . . , 𝑙 se naz´ yvaj´ı nesoudˇelná. Je-li kaˇzdé z ˇc´ısel 𝑎, 𝑏, . . . , 𝑙 nesoudˇelné s kaˇzd´ ym druh´ ych z nich, pak ˇc´ısla 𝑎, 𝑏, . . . , 𝑙 se naz´ yvaj´ı po dvou nesoudˇelná. Zˇrejmˇe ˇc´ısla po dvou nesoudˇelná jsou vˇzdy nesoudˇelná; v pˇr´ıpadˇe dvou ˇc´ısel se pojmy nesoudˇelná a po dvou nesoudˇelná shoduj´ı. Pˇr´ıklady: a) (15, 18, 63) = 3 b) (15, 21, 31) = 1 c)(11, 18, 25) = 1 V pˇr´ıpadech b a c jsou uvedená ˇc´ısla nesoudˇelná, avˇsak pouze v pˇr´ıpadˇe c jsou i po dvou nesoudˇelná.

V dalˇs´ıch u ´vahách se budeme zab´ yvat jen nejvˇetˇs´ım spoleˇcn´ ym dˇelitelem dvou ˇc´ısel, pro jednoduchost a z u ´sporn´ ych d˚ uvod˚ u budeme pouˇz´ıvat zkratky NSD. Pokud tato ˇc´ısla nejsou pˇr´ıliˇs velká, pak obyˇcejnˇe nalezen´ı NSD neb´ yvá pˇr´ıliˇs sloˇzité, nebot’ se nám podaˇr´ı rozloˇzit obˇe ˇc´ısla na souˇcin prvoˇcinitel˚ u a pak vybereme vybereme ty, které jsou pro obˇe ˇc´ısla spoleˇcné. NSD je pak jejich souˇcin. Pˇr´ıklad: Urˇcete NSD ˇc´ısel 153 a 258. Plat´ı 153 = 32 .17 a 258 = 2.3.43. Je tedy (153, 258) = 3. Ne vˇzdy se nám podaˇr´ı naj´ıt NSD tak jednoduˇse, zejména pro velká ˇc´ısla je mnohdy obt´ıˇzné naj´ıt byt’ jednoho dˇelitele, natoˇz provést jeho rozklad na prvoˇcinitele, pˇr´ıkladem budiˇz ˇc´ısla Fermatova. Ptejme se tedy, zda pro nalezen´ı NSD neexistuje nˇejak´ y jin´ y postup; ideáln´ı by bylo, pokud by se jednalo o algoritmus. Odpovˇed’ zn´ı, ˇze takov´ y algoritmus existuje a je pojmenován po ˇreckém matematikovi Eukleidovi. Mˇejme tedy ˇc´ısla 𝑎 a 𝑏, bez u ´jmy na obecnosti m˚ uˇzeme pˇredpokládat, ˇze 𝑎 > 𝑏. Podle () lze sestavit následuj´ıc´ı systém rovnic 𝑎 = 𝑏𝑞1 + 𝑟1 𝑏 = 𝑟1 + 𝑟2 .........𝑟𝑛−2 = 𝑟𝑛−1 𝑞𝑛 + 𝑟𝑛 𝑟𝑛−1 = 𝑟𝑛 𝑞𝑛+1 + 0. Z posledn´ı rovnice plyne, ˇze 𝑟𝑛 ∣𝑟𝑛−1 , z pˇredposledn´ı pak 𝑟𝑛 ∣𝑟𝑛−2 atd. aˇz z prvn´ıch dvou rovnic obdrˇz´ıme 𝑟∣𝑏 a 𝑟∣𝑎. NSD je tedy nejvˇetˇs´ı nenulov´ y zbytek v Eukleidovˇe algoritmu. Pˇr´ıklad: Urˇcete nejvˇetˇs´ı spoleˇcn´ y dˇelitel ˇc´ısel 1512 a 110. 1512 = 13 × 110 + 82; 110=1x82+28; 82=2x28+26; 28=1x26+2; 23=2x13. (1512, 110) = 2. Pˇr´ıklad: Urˇcete nejvˇetˇs´ı spoleˇcn´ y dˇelitel ˇc´ısel 988 a 35. 988=28x35+8; 35=4x8+3; 8=2x3+2; 3=1x2+1; 2=1x1+1; 1=1x1+0. (988, 35) = 1, tato ˇc´ısla jsou nesoudˇelná. Pˇr´ıklad: Dokaˇzte, ˇze dvˇe po sobˇe jdouc´ı ˇc´ısla jsou nesoudˇelná. ˇreˇsen´ı: (𝑎, 𝑎 + 1)=(𝑎, 𝑎 + 1 − 𝑎)=(𝑎, 1)=1.

1.1

Prvoˇ c´ısla a ˇ c´ısla sloˇ zen´ a

V této ˇca´sti se seznám´ıme s pojmem prvoˇc´ıslo a ˇc´ıslo sloˇzené. Dále uvedeme základn´ı vˇetu aritmetiky a nˇekteré aplikace. Vezmeme-li v u ´vahu pˇrirozená ˇc´ısla vˇetˇs´ı neˇz jedna, pak lze s jistotou tvrdit, ˇze kaˇzdé má alespoˇ n dva dˇelitele, totiˇz jedniˇcku a sebe sama. Nenajdeme-li jiˇz ˇzádného dalˇs´ıho dˇelitele, pak se toto ˇc´ıslo naz´ yvá prvoˇc´ıslo. V opaˇcném pˇr´ıpadˇe mluv´ıme o ˇc´ıslech sloˇzených. Jedniˇcku nezaˇrazujeme ani do jedné skupiny, pˇresnˇe v souladu s pythagorejskou ˇskolou. Aˇckoliv se zdá, ˇze se jedná jen o matematickou hˇr´ıˇcku, byt’ velmi krásnou, nen´ı tomu tak. Umˇen´ı rozeznat prvoˇc´ıslo a ˇc´ıslo sloˇzené má v praxi velk´ y v´ yznam, jak o tom bude pojednáno v dalˇs´ım textu. Pouˇzit´ı slova umˇen´ı nen´ı od vˇeci, zejména má-li ˇc´ıslo velk´ y poˇcet cifer je jeho faktorizace mnohdy velmi obt´ıˇzná. Pro malá ˇc´ısla m˚ uˇzeme vyuˇz´ıt Eratosthenova s´ıta. Dejme tomu, ˇze máme nalézt vˇsechna prvoˇc´ısla menˇs´ı neˇz 100. Vˇsechna ˇc´ısla seˇrad´ıme podle velikosti a nejprve ponecháme dvojku a vyˇskrtáme vˇsechny jej´ı násobky. Po této operaci je prvn´ım nevyˇskrtnut´ ym ˇc´ıslem trojka, vyˇskrtáme tedy vˇsechny jej´ı násobky (pokud nejsou jiˇz vyˇskrtnuty pˇri pˇredchoz´ı operaci. Tak postupujeme tak dlouho, aˇz naraz´ıme na nevyˇskrtnuté ˇc´ıslo vˇetˇs´ı neˇz deset, to jiˇz ˇskrtán´ı konˇc´ı a vˇsechna nevyˇskrtnutá ˇc´ısla jsou prvoˇc´ısla.

Vˇ eta 1.7 (Prvn´ı vˇeta Eukleidova). Necht’ 𝑎, 𝑏 ∈ 𝑁 , 𝑝 je prvoˇc´ıslo a 𝑝∣𝑎𝑏. Pak 𝑝∣𝑎 nebo 𝑝∣𝑏. D˚ ukaz: Jestliˇze 𝑝∣𝑎 jsme s d˚ ukazem hotovi. Pokud 𝑝 nedˇel´ı 𝑎, je (𝑎, 𝑝) = 1. Pak existuj´ı celá ˇc´ısla 𝑥 a 𝑦 tak, ˇze plat´ı 𝑎𝑥 + 𝑝𝑦 = 1. Vynásob´ıme-li obˇe strany této rovnice ˇc´ıslem 𝑏, obdrˇz´ıme 𝑎𝑏𝑥 + 𝑝𝑏𝑦 = 𝑏. Jelikoˇz oba sˇc´ıtance na levé stranˇe jsou dˇelitelné 𝑝, mus´ı b´ yt dˇelitelné ˇc´ıslem 𝑝 i ˇc´ıslo 𝑏. D˚ usledkem je skuteˇcnost, ˇze kaˇzdé kaˇzdé pˇrirozené ˇc´ıslo 𝑛 > 1 lze jednoznaˇcnˇe rozloˇzit na souˇcin pˇrirozen´ ych mocnin prvoˇc´ısel 𝑝1 < 𝑝2 < . . . < 𝑝𝑟 . Plat´ı tedy 𝑛=

𝑃1𝑘1 𝑃2𝑘2

⋅ ⋅ ⋅ 𝑃𝑟𝑘𝑟

=

𝑟 ∏ 𝑖=1

Prvoˇc´ıslo 𝑝𝑖 se naz´ yvá prvoˇcinitel. Vˇ eta 1.8 Jestliˇze 𝑝𝛼1 1 𝑝𝛼2 2 ⋅ ⋅ ⋅ 𝑝𝛼𝑟 𝑟 = 𝑞1𝛽1 𝑞2𝛽2 ⋅ ⋅ ⋅ 𝑞𝑠𝛽𝑠 , kde 𝑝1 < 𝑝2 < ⋅ ⋅ ⋅ < 𝑝𝑟 , 𝑞1 < 𝑞2 < ⋅ ⋅ ⋅ < 𝑞𝑠 jsou prvoˇc´ısla a 𝑟, 𝑠, 𝛼𝑖 , 𝛽𝑖 ∈ 𝑁 , pak 𝑟 = 𝑠, 𝑝𝑖 = 𝑞𝑖 , 𝛼𝑖 = 𝛽𝑖 pro kaˇzdé 𝑖 = 1, . . . , 𝑟. D˚ ukaz. Necht’ 𝑚 = 𝑝𝛼1 1 𝑝𝛼2 2 ⋅ ⋅ ⋅ 𝑝𝛼𝑟 𝑟 , 𝑛 = 𝑞1𝛽1 𝑞2𝛽2 ⋅ ⋅ ⋅ 𝑞𝑠𝛽𝑠 a necht’ 𝑚 = 𝑛. Jestliˇze nˇejaké prvoˇc´ıslo 𝑝 dˇel´ı 𝑚, pak podle Prvn´ı Eukleidovy vˇety prvoˇc´ıslo 𝑝 mus´ı dˇelit 𝑝𝑘 pro nˇejaké 𝑘 ∈ {1, . . . , 𝑟}. Z definice prvoˇc´ısla vˇsak plyne, ˇze 𝑝 = 𝑝𝑘 . Protoˇze 𝑚 = 𝑛, mus´ı 𝑝 dˇelit také nˇejaké 𝑞𝑙 pro 𝑙 ∈ {1, . . . , 𝑠} a stejn´ ym zp˚ usobem dostaneme , ˇze 𝑝 = 𝑞𝑙 . Odtud plyne, ˇze 𝑝𝑘 = 𝑞𝑙 . Jelikoˇz prvoˇc´ısla 𝑝𝑖 a 𝑞𝑗 jsou seˇrazena podle velikosti, mus´ı platit 𝑝1 = 𝑞1 , . . . , 𝑝𝑟 = 𝑞𝑟 a 𝑟 = 𝑠. Pˇredpokládejme dále, ˇze 𝛼1 > 𝛽1 pro nˇejaké 𝑖 ∈ {1, . . . , 𝑟}. Vydˇel´ıme-li rovnost 𝑚 = 𝑛 ˇc´ıslem 𝑝𝛽𝑖 , obdrˇz´ıme 𝑝𝛼1 1 ⋅ ⋅ ⋅ 𝑝𝛼𝑖 𝑖 −𝛽𝑖 ⋅ ⋅ ⋅ 𝑝𝛼𝑟 𝑟 = 𝑝𝛽1 1 ⋅ ⋅ ⋅ 𝑝0𝑖 ⋅ ⋅ ⋅ 𝑝𝛽𝑟 𝑟 , coˇz je spor, nebot’ levá strana rovnice je dˇelitelná 𝑝𝑖 , zat´ımco pravá strana t´ımto ˇc´ıslem dˇelitelná nen´ı. Analogicky postupujeme v pˇr´ıpadˇe, ˇze 𝛼𝑖 < 𝛽𝑖 . Je tedy 𝛼𝑖 = 𝛽𝑖 pro vˇsechna 𝑖 ∈ {1, . . . , 𝑟}. Vˇeta o jednoznaˇcnosti rozkladu pˇrirozeného ˇc´ısla na prvoˇcinitele se nám zdá samozˇ ı. Napˇ r´ıklad v tˇelese √ √ √ rejmá, existuj´ı vˇsak algebraické struktury, v nichˇz neplat´ ’ 𝑄(i 5) tato vˇeta neplat´ı, nebot 21 = 3 ⋅ 7 a (1 + 2i 5)(1 − 2i 5). Základn´ı vˇeta aritmetiky je také jedn´ım z d˚ uvod˚ u, proˇc nepovaˇzujeme jedniˇcku za prvoˇc´ıslo. Pokud by tomu tak bylo, tak by v rozkladu nebyla jednoznaˇcnost exponent˚ u. ’ Poloˇz´ıme-li si otázku, kolik je prvoˇc´ısel, odpovˇed nalezneme v Eukleidov´ ych základech, kniha 9, tvrzen´ı?. Druhá Eukleidova vˇeta. Prvoˇc´ısel je nekoneˇcnˇe mnoho. D˚ ukaz provedeme sporem. Budeme pˇredpokládat, ˇze prvoˇc´ısel je koneˇcnˇe mnoho. V tom pˇr´ıpadˇe je m˚ uˇzeme vyjmenovat, budou to ˇc´ısla 𝑝1 , 𝑝2 , . . . , 𝑝𝑛 . Vynásobme je mezi sebou a pˇripoˇctˇeme jedniˇcku. Takto vzniklé ˇc´ıslo 𝑚 = 𝑝1 𝑝2 ⋅ ⋅ ⋅ 𝑝𝑛 + 1 nen´ı ani jedno z uveden´ ych prvoˇc´ısel, ani nen´ı nˇekter´ ym z tˇechto prvoˇc´ısel dˇelitelné. Je zde spor a proto je prvoˇc´ısel nekoneˇcnˇe mnoho. Poznamenejme, ˇze zkonstruované ˇc´ıslo 𝑚 je nˇekdy prvoˇc´ıslo (2.3.5.7+1=211), jindy je to ˇc´ıslo sloˇzené (2.3.5.7.11.13+1=30031=59.509). Pod´ıváme-li se do Základ˚ u,

zjist´ıme, ˇze Eukleides tuto vˇetu uvedl v ponˇekud jiném tvaru. Jelikoˇz ˇreˇct´ı matematikové pojem nekoneˇcna ve smyslu jak ho chápeme dnes nepouˇz´ıvali, museli vˇety formulovat opisem. Tvrzen´ı tedy zn´ı: Prvoˇc´ısel je v´ıc, neˇz dané mnoˇzstv´ı prvoˇc´ısel. D˚ ukaz pak je stejn´ y, jak je uvedeno v´ yˇse, jen poˇcet znám´ ych prvoˇc´ısel je mnohem niˇzˇs´ı, Eukleides si vystaˇcil se tˇremi.

1.1.1

Pythagorejsk´ e trojice

Pythagorovu vˇetu ovládá kaˇzd´ y, kdo se jen trochu potkal s geometri´ı. Kaˇzd´ y zedn´ık si um´ı udˇelat vingl (prav´ yu ´hel) tak, ˇze tˇri latˇe s délkami v pomˇeru 3 : 4 : 5 spoj´ı v troj´ uheln´ık a v´ı, ˇze hledan´ y prav´ yu ´hel je oproti nejdelˇs´ı lati. Pythagorova vˇeta se obvykle uvád´ı slovnˇe, ˇr´ıkáme ˇze obsah ˇctverce nad pˇreponou se rovná souˇctu obsah˚ u ˇctverc˚ u nad obˇema odvˇesnami. Takto formulované tvrzen´ı má ovˇsem tvar implikace a Pythagorova vˇeta nás ke konstrukci pravého u ´hlu v´ yˇse uveden´ ym zp˚ usobem neopravˇ nuje. Dá se vˇsak dokázat, ˇze i obrácená implikace je správná, plat´ı tedy následuj´ıc´ı vˇeta: Vˇ eta 1.9 Troj´ uheln´ık s délkami stran 𝑎, 𝑏, 𝑐 je pravo´ uhlý s pˇreponou délky 𝑐 pr´ avˇe tehdy, kdyˇz plat´ı 𝑐2 = 𝑎2 + 𝑏2 . Definice: Necht’ pro uspoˇra´danou trojici ˇc´ısel [𝑎, 𝑏, 𝑐] plat´ı 𝑎2 + 𝑏2 = 𝑐2 . Tuto trojici naz´ yváme pythagorejská trojice a troj´ uheln´ık s tˇemito délkami stran pythagorejský troj´ uheln´ık. Jestliˇze nav´ıc tato ˇc´ısla nemaj´ı spoleˇcného dˇelitele 𝑑 > 1, mluv´ıme o primitivn´ı pythagorejské trojici. Odpovˇed’ na otázku jak sestavit libovolnou pythagorejskou trojici nalezneme jiˇz u Diofanta. Vˇ eta 1.10 Uspoˇrádaná trojice pˇrirozených ˇc´ısel [𝑎, 𝑏, 𝑐] je primitivn´ı pythagorejskou trojic´ı tehdy a jen tehdy, existuj´ı-li nesoudˇelná pˇrirozená ˇc´ısla 𝑚 > 𝑛 opaˇcné parity tak, ˇze bud’ 𝑎 = 𝑚2 − 𝑛2 ,

𝑏 = 2𝑚𝑛,

𝑐 = 𝑚2 + 𝑛2

𝑏 = 𝑚2 − 𝑛2 ,

𝑐 = 𝑚2 + 𝑛2 .

nebo 𝑎 = 2𝑚𝑛,

ˇ ısla 𝑚 𝑛 jsou urˇcena jednoznaˇcnˇe. C´ D˚ ukaz nen´ı obt´ıˇzn´ y, avˇsak pro jeho délku odkazujeme ˇctenáˇre napˇr. na publikaci [2]. Ani Diofantos nebyl prvn´ı, kdo se zab´ yval tˇemito trojicemi, jejich tabulky byly pouˇz´ıvány jiˇz ve staré Babylónii. S pythagorejsk´ ymi trojicemi se v teorii ˇc´ısel setkáváme pomˇernˇe ˇcasto. Závˇerem uvedeme jednu jejich aplikaci, kterou poprvé uvedl (a zˇrejmˇe i dokázal P. Fermat). ˇadné ˇc´ıslo tvaru 4𝑘 − 1 pro 𝑘 ∈ 𝑁 nen´ı souˇctem dvou ˇctverc˚ Vˇ eta 1.11 Z´ u celých ˇc´ısel. D˚ ukaz je snadn´ y, pokud si uvˇedom´ıme, ˇze sudé ˇc´ıslo je tvaru 2𝑙 a liché 2𝑚 + 1. Jejich ˇctverce jsou pak 4𝑙2 , resp. 4𝑚2 + 4𝑚 + 1 = 4𝑛 + 1. Souˇcet dvou ˇctverc˚ u m˚ uˇze b´ yt tvaru 4𝑘, 4𝑘 + 1 ˇci 4𝑘 + 2, nikdy nem˚ uˇze b´ yt tvaru 4𝑘 + 3 = 4(𝑘 + 1) − 1. Z v´ yˇse uvedeného vypl´ yvá, ˇze ˇc´ıslo tvaru 4𝑘 − 1 nen´ı ani ˇctvercem celého ˇc´ısla.

1.2

Vlastnosti prvoˇ c´ısel

Pro pˇrirozená ˇc´ısla 𝑗, 𝑚 a 𝑛 ˇrekneme, ˇze 𝑚𝑗 pˇresnˇe dˇel´ı n, a budeme psát 𝑚𝑗 ∥𝑛, jestliˇze 𝑚𝑗 ∣𝑛, ale 𝑚𝑗+1 𝑛. Pro 𝑗 = 0 bude symbol 𝑚0 ∥𝑛 znamenat, ˇze 𝑚𝑛. Dokáˇzeme vˇetu, která uvád´ı vztah mezi prvoˇc´ısly a binomick´ ymi koeficienty (kombinaˇcn´ımi ˇc´ısly). ( ) Vˇ eta 1.12 Pˇrirozené ˇc´ıslo 𝑛 je prvoˇc´ıslem právˇe tehdy, kdyˇz 𝑛 ∣ 𝑛𝑘 pro kaˇzdé 𝑘 ∈ {1, . . . , 𝑛 − 1}. D˚ ukaz: Necht’ 𝑛 je prvoˇc´ıslo. Pro 𝑘 ∈ {1, . . . , 𝑛 − 1} je ˇc´ısly 1 a 𝑛 − 1. (𝑛 ) − 𝑘 mezi 𝑛! ´ , je toto ˇc´ıslo C´ıslo 𝑛 nedˇel´ı ani 𝑘! ani (𝑛 − 𝑘)!, ale dˇel´ı 𝑛!. Jelikoˇz 𝑛𝑘 = 𝑘!(𝑛−𝑘)! dˇelitelné 𝑛. Pˇredpokládejme naopak, ˇze 𝑛 je sloˇzené a necht’ 𝑝 je nejmenˇs´ı prvoˇc´ıslo, které dˇel´ı 𝑛. Tedy je 1 < 𝑝 < 𝑛 a ( ) 𝑛 𝑛(𝑛 − 1) ⋅ ⋅ ⋅ (𝑛 − 𝑝 + 1) . = 𝑝(𝑝 − 1) ⋅ ⋅ ⋅ 2 ⋅ 1 𝑝 Dále pˇredpokládejme, ˇze 𝑝𝑗 ∥𝑛 pro nˇejaké pˇrirozené ˇc´ıslo 𝑗. Mezi 𝑝 postupnˇe jdouc´ımi ˇc´ısly 𝑛, 𝑛−1, . . . 𝑛−𝑝+1 je právˇe jedno dˇelitelné 𝑝. Protoˇze 𝑝 ∣ 𝑛, plat´ı 𝑝(𝑛−1)(𝑛− 2) ⋅ ⋅ ⋅ (𝑛 − 𝑝 + 1). Plat´ı tedy 𝑝(𝑗 ∥𝑛(𝑛 ) − 1)(⋅ ⋅)⋅ (𝑛 − 𝑝 + 1) a zˇrejmˇe i 𝑝∥𝑝(𝑝 − 1) ⋅ ⋅ ⋅ 2 ⋅ 1. Podle () dostaneme, ˇze 𝑝𝑗−1 ∥ 𝑛𝑝 . Ale 𝑛 𝑛𝑝 , protoˇze 𝑝𝑗 ∥.

1.3

´ Ulohy k procviˇ cen´ı

1. Druhou mocninu kaˇzdého pˇrirozeného ˇc´ısla je moˇzné napsat bud’ ve tvaru 4𝑘 nebo 4𝑘 + 1. Dokaˇzte. 2. Jestliˇze souˇcasnˇe plat´ı 𝑎∣𝑏 a 𝑏∣𝑎, pak je ∣𝑎∣ = ∣𝑏∣. Dokaˇzte. 3. Otec se synem jeli na dovolenou z Brna do Chorvatska autem. Jelikoˇz cesta je dlouhá, rozhodli se, ˇze se budou kaˇzd´ ych 80 km v ˇr´ızen´ı stˇr´ıdat. Kdo ˇr´ıdil auto pˇri pˇr´ıjezdu do Splitu, je-li vzdálenost Brno - Split 888 km? 4. Necht’ 𝑎 − 𝑏 je násobkem ˇc´ısla 𝑐. Pak i 𝑎𝑛 − 𝑏𝑛 je násobkem 𝑐. 5. Dokaˇzte, ˇze pro libovolné pˇrirozené ˇc´ıslo 𝑛 plat´ı 9∣4𝑛 + 15𝑛 − 1. 6. Dokaˇzte, ˇze rozd´ıl ˇctverc˚ u dvou po sobˇe jdouc´ıch pˇrirozen´ ych ˇc´ısel je dˇeliteln´ y osmi. 7. Souˇcet tˇr´ı po sobˇe jdouc´ıch tˇret´ıch mocnin pˇrirozen´ ych ˇc´ısel je násobkem ˇc´ısla 9. Dokaˇzte. 8. Souˇcet ˇctverc˚ u dvou po sobˇe jdouc´ıch ˇc´ısel zmenˇsen´ y o jednu je dˇeliteln´ y ˇctyˇrmi. Dokaˇzte. item Rozd´ıl ˇctverc˚ u dvou lich´ ych ˇc´ısel je násobkem ˇc´ısla 8. Dokaˇzte. 3 ˇ item C´ıslo 𝑛 + 11𝑛 je dˇelitelné ˇsesti pro libovolné 𝑛. Dokaˇzte.

Kapitola 2 Nˇ ekter´ e funkce pouˇ z´ıvan´ e v teorii ˇ c´ısel V této kapitole se zm´ın´ıme o nˇekter´ ych funkc´ıch, které se zhusta pouˇz´ıvaj´ı v teorii ˇc´ısel. I my se v tomto textu budeme s tˇemito funkcemi setkávat, je proto nutné, abychom poznali jejich definici a základn´ı vlastnosti.

2.1

Funkce [𝑥], {𝑥}

Prvn´ı funkc´ı, s n´ıˇz se seznám´ıme, je celá ˇcást, kterou oznaˇcujeme [𝑥] a která je definována pro vˇsechna reálná ˇc´ısla 𝑥 jako nejvˇetˇs´ı celé ˇc´ıslo, které nen´ı vˇetˇs´ı neˇz 𝑥. Tak napˇr´ıklad [10]=10, [16,12]=16 a [𝜋]=3. Uvedeme i pˇr´ıklady pro ˇc´ısla záporná. [-4]=-4, [-5,2]=-6. Vˇsimnˇeme si, ˇze pro ˇc´ısla kladná je celá ˇca´st v absolutn´ı hodnotˇe vˇzdy menˇs´ı nebo rovna absolutn´ı hodnotˇe daného ˇc´ısla, kdeˇzto u ˇc´ısel záporn´ ych je tomu naopak. Je to obdobné jako v pˇr´ıpadˇe dˇelitelnosti ˇc´ısel. Dˇel´ıme-li dvˇe kladná ˇc´ısla, je souˇcin dˇelitele a (ne´ uplného) pod´ılu vˇzdy menˇs´ı nebo roven dˇelenci. Dˇel´ıme-li naproti tomu záporné ˇc´ıslo kladn´ ym, je absolutn´ı hodnota souˇcinu dˇelitele a (ne´ uplného) pod´ılu vˇzdy vˇetˇs´ı nebo rovna absolutn´ı hodnotˇe dˇelitele. Aby se desetinná ˇca´st reálného ˇc´ısla nec´ıtila odstrˇcená, definujeme i lomenou ˇcástn ˇc´ısla 𝑥 jako rozd´ıl 𝑥 − [𝑥] a znaˇc´ıme ji {𝑥}. Jako pˇr´ıklady uvedeme ˇc´ısla {4} = 0, {1, 6} = 0, 6 a {−6, 26} = 0, 74. Jako pˇr´ıklad vyuˇzit´ı této funkce uvedeme následuj´ıc´ı vˇetu. Vˇ eta 2.1 Mocnitel, s kterým je dané prvoˇc´ıslo 𝑝 obsaˇzeno v souˇcinu 𝑛! je roven ] [ ] [ ] [ 𝑛 𝑛 𝑛 + 2 + 3 + ⋅⋅⋅ 𝑝 𝑝𝑛 𝑝 1

[ ] [ ] D˚ ukaz: Poˇcet souˇcinitel˚ u souˇcinu 𝑛! je 𝑛𝑝 , mezi nimi je 𝑝𝑛2 násobk˚ u ˇc´ısla [ ] 𝑝2 , mezi tˇemito pak zase 𝑝𝑛3 násobk˚ u ˇc´ısla 𝑝3 atd. Souˇcet uveden´ ych ˇc´ısel tedy dá uvedeného mocnitele, nebo´t kaˇzd´ y ˇcinitel souˇcinu 𝑛!, kter´ y je násobkem ˇc´ısla 𝑚 𝑚+1 𝑝 , avˇsak ne ˇc´ısla 𝑝 , poˇc´ıtá se uveden´ ym zp˚ usobem 𝑚−krát jako násobek ˇc´ısel 𝑝, 𝑝2 , . . . , 𝑝𝑚 . 1

V publikaci [8]jsou exponenty mylnˇe uvedeny jako koeficienty.

11

[ ] [ ] ’ 25 + 45 = 2 + 1 = 3. Pˇr´ıklady: V ˇc´ısle 5! je prvoˇc´ıslo 2 s exponentem 3, nebot [ ] [ 57 ] + 25 = 11 + 2 = 13. Snadno se vid´ı, ˇze 5! = 600 = 23 .3.52 . V ˇc´ısle 57! je pˇetka 57 5 ’ Jelikoˇz tˇrináctka je povaˇzována za ˇc´ıslo neˇst astné, ovˇeˇren´ı pˇres kanonick´ y rozklad dˇelat nebudeme, ˇctenáˇri v tom vˇsak nebrán´ıme.

2.2

Souˇ cty vztahuj´ıc´ı se na dˇ elitele ˇ c´ısla

velmi d˚ uleˇzitou u ´lohu v teorii ˇc´ısel hraj´ı multiplikativn´ı funkce. Tyto funkce m˚ uˇzeme definovat následuj´ıc´ım zp˚ usobem: Def. 2.1 Funkce 𝜗(𝑎) se nazývá multiplikativn´ı, je-li definována pro vˇsechna pˇrirozen´ a ˇc´ısla, pˇriˇcemˇz alespoˇ n pro jednu hodnotu 𝑎 je nenulová. Souˇcasnˇe mus´ı platit 𝜗(𝑎1 𝑎2 ) = 𝜗(𝑎1 )𝜗(𝑎2 ) je-li (𝑎1 , 𝑎2 ) = 1. Pˇr´ıkladem multiplikativn´ı funkce je mocnina pˇrirozeného ˇc´ısla, nebot’ plat´ı 𝑎𝑠1 𝑎𝑠2 = (𝑎1 𝑎−2)𝑠 . S dalˇs´ımi multiplikativn´ımi funkcemi seznám´ıme ˇctenáˇre v dalˇs´ı ˇca´sti kapitoly, neˇz vˇsak k tomu dojde, uvedeme jeˇstˇe nˇekteré dalˇs´ı vlastnosti multiplikativn´ı funkce. Vˇ eta 2.2 Necht’ 𝜗(𝑎) je multiplikativn´ı funkce. Pak plat´ı 𝜗(1) = 1. D˚ ukaz: Podle definice mus´ı existovat alespoˇ n jedno pˇrirozené ˇc´ıslo, pro nˇeˇz je funkce nenulová, necht’ je to 𝑎0 . Pak máme 𝜗(𝑎0 ) = 𝜗(1.𝑎0 ) = 𝜗(1)𝜗(𝑎0 ). Vˇ eta 2.3 Necht’ 𝜗1 (𝑎) a 𝜗(𝑎2 ) jsou multiplikativn´ı funkce. Pak i funkce 𝜗0 (𝑎) = 𝜗1 (𝑎)𝜗2 (𝑎) je funkce multiplikativn´ı. D˚ ukaz: 1) 𝜗0 (1) = 𝜗1 (1)𝜗2 (1) = 1 2) Pˇredpokládejme, ˇze je (𝑎1 , 𝑎2 ) = 1. pak je

𝜗0 (𝑎1 𝑎2 ) = 𝜗1 (𝑎1 𝑎2 )𝜗2 (𝑎1 𝑎2 ) = 𝜗1 (𝑎1 )𝜗1 (𝑎2 )𝜗2 (𝑎1 )𝜗2 (𝑎2 ) = 𝜗1 (𝑎1 )𝜗2 (𝑎1 )𝜗2 (𝑎1 )𝜗2 (𝑎2 ) = 𝜗0 (𝑎 Vˇ eta 2.4 necht’ 𝜗(𝑎) je multiplikativn´ı funkce a 𝑎 = 𝑝𝛼1 1 𝑝𝛼2 2 . . . 𝑝𝛼𝑘 𝑘 je kanonický rozklad ˇc´ısla 𝑎. Pak plat´ı ∑ 𝜗(𝑑) = (1 + 𝜗(𝑝1 ) + 𝜗(𝑝21 ) + . . . + 𝜗(𝑝𝛼1 𝑘 ) . . . 𝑑∣𝑎

. . . (1 + 𝜗(𝑝𝑘 ) + 𝜗(𝑝2𝑘 ) + . . . + 𝜗(𝑝𝛼𝑘 𝑘 )). Je-li 𝑎 = 1, pak i pravá strana je rovna jedné. D˚ ukaz: Roznásob´ıme-li v´ yraz na pravé stranˇe, dostaneme souˇcet sˇc´ıtanc˚ u tvaru 𝜗(𝑝𝛽1 1 (𝑝𝛽2 2 . . . (𝑝𝛽𝑘𝑘 = 𝜗((𝑝𝛽1 1 (𝑝𝛽2 2 . . . (𝑝𝛽𝑘𝑘 ); 0 ≤ 𝛽1 ≤ 𝛼 1 ,

0 ≤ 𝛽2 ≤ 𝛼 2 , . . . ,

0 ≤ 𝛽𝑘 ≤ 𝛼𝑘 ,

pˇriˇcemˇz ani jeden takov´ y sˇc´ıtanec nebude vynechán a ani se nebude opakovat, takˇze souˇcty na levé i na pravé stranˇe budou stejné.

je-li 𝜗(𝑎) = 𝑎𝑠 , má pˇredchoz´ı rovnost tvar ∑ 𝛼𝑘 𝑠 𝛼1 𝑠 𝑠 2𝑠 𝑑𝑠 = (1 + 𝑝𝑠1 + 𝑝2𝑠 1 + . . . + 𝑝1 ) . . . (1 + 𝑝𝑘 + 𝑝𝑘 + . . . + 𝑝𝑘 )

(2.1)

𝑑∣𝑎

Poloˇz´ıme-li 𝑠 = 1, je levá strana rovnice () rovna souˇctu vˇsech dˇelitel˚ u ˇc´ısla 𝑎, kter´ y oznaˇc´ıme 𝑆(𝑎). Pravou stranu lze zjednoduˇsit, takˇze obdrˇz´ıme vztah pro souˇcet vˇsech dˇelitel˚ u ˇc´ısla 𝑎: 𝜎(𝑎) =

𝑝𝛼1 1 +1 − 1 𝑝𝛼2 2 +1 − 1 𝑝𝛼𝑘 +1 − 1 ⋅ ⋅⋅⋅ 𝑘 . 𝑝1 − 1 𝑝2 − 1 𝑝𝑘 − 1

(2.2)

Poloˇz´ıme-li 𝑠 = 0, je levá strana rovnice () rovna poˇctu dˇelitel˚ u ˇc´ısla 𝑎, kter´ y oznaˇc´ıme 𝜏 (𝑎). Poˇcet vˇsech dˇelitel˚ u tedy urˇc´ıme podle vzorce 𝜏 (𝑎) = (𝛼1 + 1)(𝛼2 + 1) . . . (𝛼𝑘 + 1)

(2.3)

Pˇr´ıklad: Necht’ 𝑎 = 36. Pak jeho kanonick´ y rozklad je 36 = 22 32 a jeho dˇelitelé jsou ˇc´ısla 1, 2, 3, 4, 6, 9, 12, 18, 36. Seˇcteme-li tato ˇc´ısla, obdrˇz´ıme 91. Nu a toto ˇc´ıslo 3 −1 33 −1 dostaneme i pouˇzijeme-li pravou stranu pˇredchoz´ıho vzorce— 22−1 . Seˇcteme-li 3−1 vˇsechny dˇelitele jako kusy, dostaneme se k ˇc´ıslu 9. Ale také je (2 + 1)(2 + 1) = 9. S funkcemi 𝑆(𝑎) a 𝜏 (𝑎) se budeme setkávat v dalˇs´ım textu.

2.2.1

Eulerova funkce

Tato funkce se bude v tomto textu vyskytovat velmi ˇcasto, je tedy nejvyˇsˇs´ı ˇcas, abychom ji definovali a uvedli nˇekteré jej´ı vlastnosti. Def. 2.2 Eulerova funkce 𝜑(𝑎) je definována pro vˇsechna pˇrirozená ˇc´ısla 𝑎 jako poˇcet tˇech ˇc´ısel posloupnosti 0, 1, . . . , 𝑎 − 1 kkterá jsou nesoudˇelná s 𝑎. Pˇr´ıklady: 𝜑(1) = 1, 𝜑(2) = 1, 𝜑(6) = 2, 𝜑(7) = 6, 𝜑(9) = 7, 𝜑(13) = 12. Vˇ eta 2.5 Necht’ 𝑎 = 𝑝𝛼1 1 𝑝𝛼2 2 . . . 𝑝𝛼𝑘 𝑘 je kanonický rozklad ˇc´ısla 𝑎. Pak plat´ı ( )( ) ( ) 1 1 1 𝜑(𝑎) = 𝑎 1 − 1− ⋅⋅⋅ 1 − . 𝑝1 𝑝2 𝑝𝑘

(2.4)

D˚ usledek 1: Je-li 𝑝 prvoˇc´ıslo, pak je 𝜑(𝑝) = 𝑝 − 1 a 𝜑(𝑝𝛼 ) = 𝑝𝛼 − 𝑝𝛼−1 . Pˇr´ıklady: 𝜑(14) = 14(1 − 21 )(1 − 71 ) = 6 𝜑(512) = 83 − 82 = 448 𝜑(11) = 11 − 1 = 10 D˚ usledek 2: Eulerova funkce je multiplikativn´ı.

2.3

Pˇ r´ıklady k procviˇ cen´ı

1. Vypoˇctˇete mocnitele, s n´ımˇz je ˇc´ıslo 3 obsaˇzeno v kanonickém rozkladu 1024! 2. Naleznˇete kanonick´ y rozklad ˇc´ısla 18! 3. Vypoˇctˇete 𝜎(51450) a 𝜏 (51450)

4. Vypoˇctˇete 𝜑(41) a 𝜑(1786050) 5. Kanonick´ y rozklad ˇc´ısla je tvaru 2𝑎 .7𝑏 , souˇcet dˇelitel˚ u pak 6000. Urˇcete ono ˇc´ıslo. 𝑏+1

V´ ysledky 508 216 .38 .5.7.11.13.17 48, 148800 40, 408240 6000 = ( 2 𝑎+1 2 − 1)( 77−1 ). Po u ´pravˇe máme 25 .32 .52 = (2𝑎+1 )(7𝑏+1 ). Prvn´ı závorka mus´ı b´ yt liché ˇc´ıslo a nav´ıc o jednu menˇs´ı neˇz libovolná mocnina 2. Tomuto vyhovuje ˇc´ıslo 15 a 𝑎 = 4. Zb´ yvaj´ı 4000, coˇz je zase ˇc´ıslo o jedniˇcku menˇs´ı neˇz ˇctvrtá mocnina sedmi, tedy 𝑏 = 3.

Kapitola 3 Diofantick´ e rovnice V nejstarˇs´ı ˇcesky psané matematické uˇcebnici, jej´ımˇz autorem je Ondˇrej Klatovsk´ y a která vyˇsla v roce 1530 nalezneme tuto u ´lohu: Dvacet ˇsest osob na jednom kvasu propilo 88 pen´ızk˚ u b´ılých. Pˇri tom kvase byli muˇzi, ˇzeny a panny. Z muˇz˚ u jedna osoba dáti mˇela ˇsest pen´ızk˚ u, z ˇzen ˇctyˇri pen´ızky a z pannen dva. Kolik jest pˇri tom cechu aneb kvasu muˇz˚ u bylo, kolik ˇzen a kolik pannen. Potlaˇcme rozhoˇrˇcen´ı, ˇze se tohoto kvasu z´ uˇcastnily i nevinné panny a pust’me se chutˇe do ˇreˇsen´ı. Tak jak je dnes zvykem, oznaˇcme poˇcet muˇz˚ u 𝑥, poˇcet ˇzen 𝑦 a koneˇcnˇe poˇcet pannen 𝑧. T´ımto z´ıskáme prvn´ı rovnici 𝑥+𝑦+𝑧 = 26𝑦. Spoˇc´ıtáme-li této povedené spoleˇcnosti u ´tratu, dojdeme k druhé rovnici 6𝑥 + 4𝑦 + 2𝑧 = 88. Vyjádˇr´ıme-li z prvn´ı rovnice 𝑧 a dosad´ıme-li do rovnice druhé, obdrˇz´ıme po u ´pravˇe rovnici 2𝑥 + 𝑦 = 18. Vid´ıme, ˇze aˇc máme jednu rovnici, neznámé jsou dvˇe. Takov´ ym rovnic´ım, v nichˇz se vyskytuje v´ıce neznám´ ych, budeme ˇr´ıkat rovnice neurˇcité. Daleko ˇcastˇeji se vˇsak uˇz´ıvá název rovnice diofantické, a to napoˇcest ˇreckého matematika Diofanta z Alexandrie.

3.1

Line´ arn´ı diofantick´ e rovnice

Abchom dovedli problém staroˇceské hostiny ke zdárnému konci, budeme se v této ˇca´sti zab´ yvat rovnicemi tvaru 𝑎𝑥 + 𝑏𝑦 = 𝑐, (3.1) kde 𝑎, 𝑏, 𝑐 jsou celá ˇc´ısla, 𝑎, 𝑏 ∕= 0. Oznaˇcme dále (𝑎, 𝑏) = 𝑑 nejvˇetˇs´ı spoleˇcn´ y dˇelitel ˇc´ısel 𝑎 a 𝑏. Nejdˇr´ıve se budeme zab´ yvat nejjednoduˇsˇs´ım pˇr´ıpadem, kdy 𝑐 = 0. Poloˇzme 𝑏 𝑎 𝐴 = 𝑑 , 𝐵 = 𝑑 . Rovnici () pˇrevedeme na tvar 𝑥 𝑏 𝐵 =− =− , 𝑦 𝑎 𝐴 pˇriˇcemˇz posledn´ı zlomek je v základn´ım tvaru. Vˇ eta 3.1 Vˇsechna celoˇc´ıselná ˇreˇsen´ı rovnice 𝑎𝑥 + 𝑏𝑦 = 0 jsou dvojice ˇc´ısel tvaru 𝑥 = 𝐵𝑡, 𝑦 = −𝐴𝑡, kde 𝑡 je libovolné celé ˇc´ıslo. D˚ ukaz tvrzen´ı pˇrenecháváme ˇctenáˇr˚ um jako cviˇcen´ı. 15

ˇ ste rovnici 10𝑥 − 6𝑦 = 0. Pˇr´ıklad: Reˇ 𝑡= Jelikoˇz (10, 6) = 2, jsou ˇreˇsen´ım vˇsechny dvojice ˇc´ısel 𝑥 = − 26 𝑡 = −3𝑡, 𝑦 = − 10 2 −5𝑡, kde 𝑡 je libovolné celé ˇc´ıslo. Nyn´ı obrát´ıme svou pozornost k pˇr´ıpadu 𝑐 ∕= 0. Nejprve se pod´ıváme, kdy má rovnice ˇreˇsen´ı. Vˇ eta 3.2 Rovnice 𝑎𝑥 + 𝑏𝑦 = 𝑐 má ˇreˇsen´ı právˇe tehdy, kdyˇz (𝑎, 𝑏)∣𝑐. D˚ ukaz: Pˇredpokládejme nejdˇr´ıve, ˇze daná rovnice má ˇreˇsen´ı, které oznaˇc´ıme 𝑥0 a 𝑦0 , plat´ı tedy 𝑎𝑥0 + 𝑏𝑦0 = 𝑐. Z vlastnost´ı ˇc´ısla 𝑑 plyne, ˇze dˇel´ı levou stranu rovnice, mus´ı tedy dˇelit i pravou. Pˇredpokládejme nyn´ı, ˇze 𝑑∣𝑐. V tom pˇr´ıpadˇe mus´ı existovat celá ˇc´ısla 𝑥0 a 𝑦0 taková, ˇze plat´ı 𝑎𝑥0 + 𝑏𝑦0 = 𝑑. Dále plat´ı 𝑐 = 𝑑𝑒, kde 𝑒 je nˇejaké ˇc´ıslo. Poloˇzme 𝑥1 = 𝑒𝑥0 a 𝑦1 = 𝑒𝑦0 . Zˇrejmˇe plat´ı 𝑎𝑥1 + 𝑏𝑦1 = 𝑒(𝑎𝑥0 + 𝑏𝑦0 ) = 𝑒𝑑 = 𝑐. ˇ ısla 𝑥1 a 𝑦1 jsou ˇreˇsen´ım rovnice (), ˇc´ımˇz je d˚ C´ ukaz ukonˇcen. Hledejme nyn´ı zp˚ usob, jak rovnici () vyˇreˇsit. Jednou z moˇznost´ı je vyuˇzit´ı Eukleidova algoritmu a postup ukáˇzeme na konkrétn´ım pˇr´ıkladˇe. nejprve si ukáˇzeme, jak vypadá ˇreˇsen´ı, je-li 𝑐 = (𝑎, 𝑏). ˇ ste rovnici 21𝑥 + 15𝑦 = 3. Pˇr´ıklad. Reˇ Jelikoˇz (21, 15) = 3, má tato rovnice ˇreˇsen´ı. Nejvˇetˇs´ı spoleˇcn´ y dˇelitel ˇc´ısel 21 a 15 nalezneme Eukleidov´ ym algoritmem. 21 = 15.1 + 6 15 = 6.2 + 3 6 = 3.2 + 0 Z pˇredposledn´ı rovnice vyjádˇr´ıme 3, tedy nejvˇetˇs´ıho spoleˇcného dˇelitele ˇc´ısel 21 a 15. Máme 3 = 15.1 + 6.(−2) (3.2) Nyn´ı vyjádˇr´ıme z prvn´ı rovnice 6 a dosad´ıme do (), ˇc´ımˇz obdrˇz´ıme 3 = 15.1 + [21.1 + 15(−1)].(−2) = 21.(−2) + 15.3. Jedn´ım z ˇreˇsen´ı dané rovnice je tedy 𝑥 = −2 a 𝑦 = 3. Mnoˇzina ˇreˇsen´ı diofantické rovnice se nezmˇen´ı, vydˇel´ıme-li vˇsechny jejich koeficienty jejich spoleˇcn´ ym dˇelitelem. Pokud na pravé stranˇe je jiné ˇc´ıslo neˇz 𝑑 a je-li rovnice ˇreˇsitelná, mus´ı b´ yt 𝑐 = 𝑒𝑑. Najdeme tedy nejprve ˇreˇsen´ı rovnice kdy pravá strana je 𝑑 a nalezené ˇreˇsen´ı pak vynásob´ıme ˇc´ıslem 𝑒. ˇ ste rovnici 21𝑥 + 15𝑦 = −6. Pˇr´ıklad: Reˇ V pˇredchoz´ım pˇr´ıkladu jsme nalezli ˇreˇsen´ı rovnice, kdy pravá strana je rovna 3. Máme −6 = 3(−2), je 𝑒 = −2 a ˇreˇsen´ı naˇs´ı rovnice je 𝑥 = (−2)(−2) = 4 a 𝑦 = 3(−2) = 6. Pˇr´ıklad: Uved’te alespoˇ n jeden zp˚ usob, kter´ ym lze vyplatit ˇcástku 37 Kˇc pouze dvoukorunov´ ymi a pˇetikorunov´ ymi mincemi. Máme ˇreˇsit diofantickou rovnici 2𝑥 + 5𝑦 = 37. Protoˇze ˇc´ısla 𝑎 a 𝑏 jsou nesoudˇelná,

tak má rovnice vˇzdy ˇreˇsen´ı. Dáme-li na pravou stranu jedniˇcku, je 5 = 2.2 + 1, tedy 1 = 5.1 + 2(−2) a 𝑥 = −2, 𝑦 = 1. Vynásob´ıme-li toto ˇreˇsen´ı ˇc´ıslem 37, z´ıskáme ˇ sen´ı jsme tedy naˇsli, jenˇze je pro danou u 𝑥 = −74 a 𝑦 = 37. Reˇ ´lohu nepouˇzitelné. Je nad slunce jasné, ˇze se nem˚ uˇzeme spokojit s t´ım, ˇze um´ıme nalézt jedno ˇreˇsen´ı diofantické rovnice a mus´ıme se pokusit nalézt zp˚ usob, jak naj´ıt vˇsechna jej´ı ˇreˇsen´ı. Jedno ˇreˇsen´ı rovnice () nalézt um´ıme, ˇreknˇeme, ˇze je to uspoˇrádaná dvojice (𝑥0 ; 𝑦0 ). Necht’ i uspoˇra´daná dvojice (𝑟; 𝑠) je ˇreˇsen´ım rovnice (). V tom pˇr´ıpadˇe plat´ı 𝑎𝑟 + 𝑏𝑠 = 𝑐 = 𝑎𝑥0 + 𝑏𝑦0 , coˇz m˚ uˇzeme uvést na tvar 𝑎(𝑟 − 𝑥0 ) = −𝑏(𝑠 − 𝑦0 ) a po vydˇelen´ı ˇc´ıslem 𝑑 = (𝑎, 𝑏) máme 𝑏 𝑎 (𝑟 − 𝑥0 ) = − (𝑠 − 𝑦0 ). 𝑑 𝑑

(3.3)

( ) Protoˇze 𝑎𝑑 , 𝑑𝑏 = 1, je zlomek 𝑎𝑑 dˇelitelem ˇc´ısla 𝑠 − 𝑦0 a tedy je 𝑠 − 𝑦0 = 𝑢 𝑎𝑑 . Podobnou u ´vahou zjist´ıme, ˇze plat´ı 𝑟 − 𝑥0 = 𝑡 𝑑𝑏 , pˇriˇcemˇz 𝑢 a 𝑡 jsou celá ˇc´ısla. Po dosazen´ı do () máme ( ) 𝑎 𝑏 𝑏 (𝑎 ) 𝑡 =− 𝑢 , 𝑑 𝑑 𝑑 𝑑 ˇ sen´ım rovnice () jsou tedy ˇc´ısla tedy 𝑡 = −𝑢. Reˇ 𝑏 𝑟 = 𝑥0 + 𝑡, 𝑑

𝑎 𝑠 = 𝑦0 − 𝑡, 𝑑

𝑡 ∈ 𝑍.

(3.4)

Necht’ naopak 𝑟 a 𝑠 jsou dvˇe libovolná ˇc´ısla tvaru (). Dosad´ıme-li je do rovnice (), máme ) ( ( 𝑎 ) 𝑎𝑏 𝑎𝑏 𝑏 𝑎 𝑥0 + 𝑡 + 𝑏 𝑦0 − 𝑡 = (𝑎𝑥0 + 𝑏𝑦0 ) + 𝑡 − 𝑡 = 𝑎𝑥0 + 𝑏𝑦0 = 𝑐. 𝑑 𝑑 𝑑 𝑑 Ponˇekud jsme pˇrehodili obvykl´ y matematick´ y postup, nebot’ v´ yˇse uvedené u ´vahy jsou d˚ ukazem následuj´ıc´ı vˇety: Vˇ eta 3.3 Necht’ 𝑥0 ; 𝑦0 je ˇreˇsen´ım rovnice (). Pak dvojice ˇc´ısel (𝑟, 𝑠) je jej´ım ˇreˇsen´ım tehdy a jen tehdy, má-li tvar (). Poznámka: Jsou-li oba koeficienty rovnice () záporné, je tˇreba ji vynásobit ˇc´ıslem (−1). Je-li záporn´ y jen jeden, dejme tomu 𝑎, zavedeme substituci 𝑥 = −𝑧, ˇc´ımˇz dostaneme rovnici s kladn´ ymi koeficienty. Po jej´ım vyˇreˇsen´ı se pak vrát´ıme k p˚ uvodn´ı neznámé. Takto jsouce vyzbrojeni teori´ı m˚ uˇzeme se pustit do vyˇreˇsen´ı obou pˇredchoz´ıch u ´loh. Zaˇcnˇeme u ´lohou penˇeˇzn´ı. Podle vˇety () budou vˇsechna ˇreˇsen´ı ve tvaru 𝑥 = −74 + 5𝑡,

𝑦 = 37 − 2𝑡,

kde 𝑡 je libovolné celé ˇc´ıslo. Jelikoˇz ˇreˇsen´ım u ´lohy mohou b´ yt pouze ˇc´ısla pˇrirozená, snadno se pˇresvˇedˇc´ıme, ˇze taková ˇreˇsen´ı dostaneme pouze pro 𝑡 = 15, 16, 17, 18.

´ Ukolem bylo nalézt jakékoliv ˇreˇsen´ı, my jako správn´ı ˇc´ıseln´ı teoretici si vybereme jediné prvoˇc´ıslo z nab´ızen´ ych moˇznost´ı. V tomto pˇr´ıpadˇe m˚ uˇzeme 37 Kˇc vyplatit pomoc´ı jedenácti dvoukorun a tˇr´ı pˇetikorun. Nyn´ı jiˇz máme pen´ıze a tak se m˚ uˇzeme vydat na kvas. I zde pˇripadaj´ı jako ˇreˇsen´ı u ´lohy pouze pˇrirozená ˇc´ısla. Jelikoˇz snadno zjist´ıme, ˇze jedno z ˇreˇsen´ı rovnice je 𝑥 = 0, 𝑦 = 18, m˚ uˇzeme obecné ˇreˇsen´ı psát ve tvaru 𝑥 = 𝑡, 𝑦 = 18 − 2𝑡. ˇ sen´ı uvedeme ve Snadno zjist´ıme, ˇze u ´loze vyhovuj´ı pouze ˇc´ısla 𝑡 = 1, . . . , 8. Reˇ formˇe tabulky. 𝑥 1 2 3 4 5 6 7 8 𝑦 16 14 12 10 8 6 4 2 𝑧 9 10 11 12 13 14 15 16 Je zaj´ımavé, ˇze Klatovsk´ y uvád´ı pouze dvˇe ˇreˇsen´ı, a to pˇr´ıpady se ˇsesti a osmi muˇzi. Zaráˇzej´ıc´ı je ovˇsem skuteˇcnost, kolik pannen se onoho kvasu z´ uˇcastnilo, vˇzdyt’ ve v´ıce neˇz polovinˇe pˇr´ıpad˚ u panny kvasu kralovaly a v˚ ubec: Podle naˇseho m´ınˇen´ı bylo mnohem v´ ystiˇznˇejˇs´ı mluvit ne o kvasu, n´ ybrˇz o dámské j´ızdˇe.

3.2

Diofantick´ e rovnice vyˇ sˇ s´ıho stupnˇ e

V pˇredchoz´ı ˇca´sti jsme se nauˇcili ˇreˇsit diofantické rovnice lineárn´ı. M˚ uˇzeme s klidn´ ym svˇedom´ım prohlásit, ˇze dovedeme vyˇreˇsit kaˇzdou lineárn´ı diofantickou rovnici o dvou neznám´ ych, pokud ovˇsem ˇreˇsen´ı má. Ale i o ˇreˇsitelnosti tˇechto rovnic um´ıme rozhodnout jednoznaˇcnˇe. S ˇreˇsen´ım rovnic vyˇsˇs´ıho stupnˇe je to ovˇsem mnohem obt´ıˇznˇejˇs´ı, mnohdy se spokoj´ıme s t´ım, ˇze um´ıme alespoˇ n rozhodnout je-li rovnice v˚ ubec ˇreˇsitelná a jásáme, nalezneme-li alespoˇ n nˇejaké ˇreˇsen´ı. Z tohoto d˚ uvodu uvedeme jen dva typy rovnic, ovˇsem kvantitu nahrad´ıme kvalitou a uvedeme u ´plné ˇreˇsen´ı tˇechto typ˚ u. Nˇekteré rovnice lze pˇrevést na tvar (𝑎𝑥 + 𝑏𝑦)(𝑐𝑥 + 𝑑𝑦) = 𝑘

(3.5)

Pˇredt´ım neˇz ukáˇzeme zp˚ usob ˇreˇsen´ı této rovnice, zavedeme následuj´ıc´ı pojem: Def. 3.1 Celá ˇc´ısla 𝑢 a 𝑣 se nazývaj´ı sdruˇzen´ı dˇelitelé ˇc´ısla 𝑤 plat´ı-li 𝑢.𝑣 = 𝑤. Pˇr´ıkladem budiˇz ˇc´ısla 2 a 5, která jsou sdruˇzen´ ymi dˇeliteli ˇc´ısla 10, nebot’ 10=5.2. Nebo ˇc´ısla -7 a 4 jsou sdruˇzen´ ymi dˇeliteli ˇc´ısla -28, jelikoˇz -28=(-7).4. Jsou-li ˇc´ısla 𝑥 a 𝑦 celoˇc´ıseln´ ym ˇreˇsen´ım rovnice (), tak ˇc´ısla 𝑎𝑥 + 𝑏𝑦 a 𝑐𝑥 + 𝑑𝑦 jsou celá a nav´ıc jsou to sdruˇzen´ı dˇelitelé ˇc´ısla 𝑘. Proto ˇreˇsen´ı rovnice () najdeme následuj´ıc´ım zp˚ usobem. Urˇc´ıme nˇejakého dˇelitele ˇc´ısla 𝑘, dejme tomu ˇze to bude 𝑘1 . Nalezneme sdruˇzeného dˇelitele 𝑘2 a poloˇz´ıme 𝑎𝑥 + 𝑏𝑦 = 𝑘1

𝑐𝑥 + 𝑑𝑦 = 𝑘2

To je ovˇsem soustava dvou lineárn´ıch rovnic o dvou neznám´ ych. Je-li tato soustava ˇreˇsitelná, pak jsou ˇc´ısla 𝑥 a 𝑦 urˇcena jednoznaˇcnˇe a jsou to souˇcasnˇe ˇreˇsen´ı rovnice (). Z uvedené metody vypl´ yvá, ˇze rovnice typu () mohou m´ıt nejv´ yˇs koneˇcn´ y poˇcet ˇreˇsen´ı. Poˇcet dvojic sdruˇzen´ ych dˇelitel˚ u ˇc´ısla 𝑘 je koneˇcn´ y a ke kaˇzdé dvojici sdruˇzen´ ych dˇelitel˚ u pˇr´ısluˇs´ı bud’ jedno nebo ˇzádné ˇreˇsen´ı.

Pod´ıvejme se na rovnici 𝑥2 − 𝑦 2 = 𝑘

(3.6)

Snadno se pˇresvˇedˇc´ıme, ˇze tato rovnice nen´ı ˇreˇsitelná v pˇr´ıpadˇe 𝑘 = 4𝑡 + 2. Kaˇzdá mocnina celého ˇc´ısla je totiˇz bud’ tvaru 4𝑠 nebo 4𝑠 + 1. Pokud jsou obˇe mocniny stejného tvaru, je jejich rozd´ıl tvaru 4𝑡. Je-li 𝑥2 = 4𝑠 + 1 a 𝑦 = 4𝑣, je jejich rozd´ıl 4𝑡 + 1. Je-li naopak 𝑥2 = 4𝑠 a 𝑦 = 4𝑣 + 1, je jejich rozd´ıl 4𝑡 − 1 = 4𝑤 + 3. Naopak nen´ı-li 𝑘 = 4𝑡+2 je rovnice vˇzdy ˇreˇsitelná. Pro sudé 𝑘 = 4𝑡 je 𝑥 = 𝑘4 +1 a 𝑦 = 𝑘4 −1. Pro liché 𝑘 = 2𝑠 + 1 jsou ˇreˇsen´ım ˇc´ısla 𝑥 = 𝑠 + 1 a 𝑦 = 𝑠. Pod´ıvejme se jeˇstˇe na rovnici 𝑎𝑛 𝑥𝑛 + . . . + 𝑎1 𝑥 + 𝑎0 = 𝑘𝑦,

(3.7)

kde 𝑎𝑖 a 𝑘 jsou celá ˇc´ısla. Skuteˇcnost, ˇze jedna neznámá se vyskytuje pouze v prvn´ı mocninˇe bude pro dalˇs´ı u ´vahy d˚ uleˇzitá. Ne kaˇzdá taková rovnice má ˇreˇsen´ı jak si ukáˇzeme v následuj´ıc´ım pˇr´ıkladu. Zkusme vyˇreˇsit rovnici 𝑥2 + 2 = 4𝑦. Jiˇz bylo zm´ınˇeno, ˇze druhá mocnina celého ˇc´ısla je bud’ tvaru 4𝑡 ˇci 4𝑡+1. Pˇriˇcteme-li k obˇema tvar˚ um dvojku, nikdy nedostaneme ˇc´ıslo dˇelitelné ˇctyˇrmi. Nyn´ı dokáˇzeme jednu vˇetu, kterou budeme potˇrebovat pro ˇreˇsen´ı rovnice (). Vˇ eta 3.4 Necht’ 𝑥 = 𝑎 + 𝑘𝑡, kde 𝑎,𝑘, 𝑡 jsou celá ˇc´ısla. Je-li 𝑚 ∈ 𝑁 , je 𝑥𝑚 tvaru 𝑘𝑇 + 𝑎𝑚 , kde 𝑇 je celé ˇc´ıslo. D˚ ukaz provedeme matematickou indukc´ı. Je-li 𝑚 = 1, tak tvrzen´ı evidentnˇe plat´ı. Budeme tedy pˇredpokládat, ˇze tvrzen´ı plat´ı pro 𝑚 = 𝑛 a dokáˇzeme, ˇze za tohoto pˇredpokladu plat´ı i pro 𝑚 = 𝑛 + 1. 𝑥𝑛+1 = (𝑎 + 𝑘𝑡)𝑛+1 = (𝑎 + 𝑘𝑡)𝑛 (𝑎 + 𝑘𝑡). Podle indukˇcn´ıho pˇredpokladu je (𝑎 + 𝑘𝑡)𝑛 rovno 𝑘𝐿 + 𝑎𝑛 , m˚ uˇzeme tedy pokraˇcovat vu ´pravách. (𝑘𝐿 + 𝑎𝑛 )(𝑎 + 𝑘𝑡) = 𝑘𝐿𝑎 + 𝑘 2 𝐿𝑡 + 𝑘𝑡𝑎𝑛 + 𝑎𝑛+1 . Vytkneme-li z prvn´ıch tˇr´ı ˇclen˚ u 𝑘 a oznaˇc´ıme-li 𝑇 = 𝐿𝑎 + 𝑘𝐿𝑡+ 𝑡𝑎𝑛 , je d˚ ukaz hotov. Vˇ eta 3.5 Necht’ (𝑥0 , 𝑦0 ) je ˇreˇsen´ım rovnice () a 𝑡 je celé ˇc´ıslo. Pak ke kaˇzdému ˇc´ıslu tvaru 𝑥 = 𝑥0 + 𝑘𝑡 existuje takové 𝑦, ˇze (𝑥, 𝑦) je ˇreˇsen´ım rovnice (). Pˇri d˚ ukazu vyuˇzijeme pˇredchoz´ı vˇety. Je-li (𝑥0 , 𝑦0 ) ˇreˇsen´ım rovnice (), má mocnina tvar 𝑥𝑗 = (𝑥0 + 𝑘𝑡)𝑗 tvar 𝑘𝑇𝑗 + 𝑥𝑗0 . Máme tedy 𝑎𝑛 (𝑥0 + 𝑘𝑡)𝑛 + . . . + 𝑎1 (𝑥0 + 𝑘𝑡) + 𝑎0 = 𝑎𝑛 (𝑘𝑇𝑛 + 𝑥𝑛0 ) + . . . + 𝑎1 (𝑥0 + 𝑘𝑡) + 𝑎0 = 𝑘(𝑎𝑛 𝑇𝑛 + . . . + 𝑎1 𝑡) + (𝑎𝑛 𝑥𝑛0 + . . . + 𝑎1 𝑥0 + 𝑎0 ) = 𝑘𝑇 + 𝑘𝑦0 = 𝑘(𝑇 + 𝑦0 ). Dvojice 𝑥0 + 𝑘𝑡, 𝑇 + 𝑦0 je ˇreˇsen´ım rovnice (), ˇc´ımˇz je d˚ ukaz hotov. Tato vˇeta nám ˇr´ıká, ˇze známe-li jedno ˇreˇsen´ı, um´ıme naj´ıt nekoneˇcnˇe mnoho ˇreˇsen´ı, které tvoˇr´ı tˇr´ıdu. To je sice hezké, ale um´ıme nˇejak´ ym zp˚ usobem naj´ıt alespoˇ n jedno ˇreˇsen´ı rovnice ()? Vˇeta () má jeden pro nás d˚ uleˇzit´ y d˚ usledek. Je-li

rovnice () ˇreˇsitelná, pak existuje takové ˇreˇsen´ı, ˇze ∣ 𝑋 ∣<∣ 𝑘 ∣. Skuteˇcnˇe, k dan´ ym nezáporn´ ym cel´ ym ˇc´ısl˚ um 𝑥0 a 𝑘 existuj´ı nezáporná ˇc´ısla 𝑠 a 𝑟 taková, ˇze plat´ı 𝑥0 = ∣𝑘∣𝑠 + 𝑟,

0 ≤ 𝑟 < ∣𝑘∣,

tedy 0 ≤ 𝑥0 − ∣𝑘∣𝑠 = 𝑟 < ∣𝑘∣. Je-li 𝑘 > 0, poloˇz´ıme 𝑡 = −𝑠, pro 𝑘 < 0 dáme 𝑡 = 𝑠 a obdrˇz´ıme ˇc´ıslo 𝑋 = 𝑥0 + 𝑘𝑡 < ∣𝑘∣. Nu a podle vˇety () existuje k tomuto ˇc´ıslu i 𝑌 takové, ˇze dvojice (𝑋, 𝑌 ) je ˇreˇsen´ım rovnice (). D´ıky tomuto d˚ usledku m˚ uˇzeme odehnat chmury z ˇcela. Staˇc´ı zjistit, zda nˇekteré z ˇc´ısel 0, 1, . . . , ∣𝑘∣ − 1 nen´ı ˇreˇsen´ım rovnice (). Pokud se nám to podaˇr´ı, má rovnice () nekoneˇcnˇe mnoho ˇreˇsen´ı, pokud ne, ˇreˇsen´ı tato rovnice nemá. ˇ ste rovnici 𝑥2 + 3𝑥 + 1 = 4𝑦. Pˇr´ıklad: Reˇ Do levé strany dosad´ıme postupnˇe ˇc´ısla 0, 1, 2, 3. V´ ysledkem jsou ˇc´ısla 1, 5, 11, 19 z nichˇz ani jedno nen´ı dˇelitelné ˇctyˇrmi, tato rovnice ˇreˇsen´ı nemá. ˇ ste rovnici 𝑥2 + 2𝑥 + 4 = 4𝑦. Pˇr´ıklad: Reˇ Zde budeme m´ıt jiˇz v´ıce ˇstˇest´ı. Dosad´ıme-li do levé strany postupnˇe ˇc´ısla 0, 1, 2, 3, obdrˇz´ıme 4, 7, 12, 19; prvn´ı a tˇret´ı ˇc´ısla v této ˇradˇe jsou násobky ˇctyˇr, máme tedy dvˇe tˇr´ıdy ˇreˇsen´ı 4𝑡, 4𝑡 + 2.

3.3

´ Ulohy k procviˇ cen´ı

1. Z uveden´ ych rovnic vyberte ty, které jsou ˇreˇsitelné: a) 7𝑥 + 3𝑦 = 2 b)18𝑥 + 40𝑦 = 3 c) 64𝑥 − 72𝑦 = 44

d) 15𝑥 + 35𝑦 = 100

ˇ ste rovnici 15𝑥 − 20𝑦 = 100 Z3/40 2. Reˇ 3. Pro která 𝑥 je v´ yraz

17𝑥−2 15

celé ˇc´ıslo? (Z4/40

4. Jist´ y staˇreˇsina vedl stoˇclenn´ y rod. Po sklizni se jim rozhodl dát 100 mˇeˇric obil´ı, pˇriˇcemˇz muˇzi mˇeli dostat 3 mˇeˇrice, ˇzeny dvˇe a kaˇzdé d´ıtˇe p˚ ul mˇeˇrice. At’ ˇrekne, kdo se domn´ıvá, ˇze v´ı, kolik bylo muˇz˚ u, kolik ˇzen a kolik dˇet´ı. 5. Nˇejak´ y muˇz chtˇel za sto zlat´ ych koupit sto zv´ıˇrat. Naˇr´ıdil svému sluhovi, at’ je velbloud koupen za pˇet zlat´ ych, osel za jeden zlat´ y a dvacet ovc´ı za jeden ˇ zlat´ y. Rekni kdo chceˇs, kolik bylo za sto zlat´ ych koupeno velbloud˚ u, kolik osl˚ u a kolik ovc´ı. 6. Ani mezi kleriky nepanovala rovnost, jak se m˚ uˇzeme pˇresvˇedˇcit v této u ´loze: Nˇejak´ y biskup kázal rozdˇelit klerik˚ um 12 chleb˚ u. Naˇr´ıdil, aby kaˇzd´ y knˇez dostal dva chleby, kaˇzd´ y jáhen polovinu chleba a kaˇzd´ y lektor ˇctvrtinu chleba, ˇ pˇriˇcemˇz klerik˚ u bylo stejnˇe jako chleb˚ u. Rekni, kdo jsi s to, kolik muselo b´ yt knˇeˇz´ı, kolik jáhn˚ u a kolik lektor˚ u. 7. Najdˇete vˇsechny dvojice navzájem r˚ uzn´ ych sdruˇzen´ ych dˇelitel˚ u ˇc´ısla 36. Z1/47 ˇ ste rovnici 6𝑥2 − 5𝑥𝑦 + 𝑦 2 = 21 Z2/47 8. Reˇ

ˇ ste rovnici 2𝑥2 + 3𝑥𝑦 + 𝑦 2 = 35 Z3/35 9. Reˇ 10. Najdˇete vˇsechna celoˇc´ıselná ˇreˇsen´ı rovnice 𝑥2 − 4 = 11𝑦. Z8/47 11. Pro jaká 𝑥 je v´ yraz 𝑥3 + 2𝑥 + 2 násobkem ˇc´ısla 125? Z10/47 12. Pro jaké 𝑛 je 6𝑛 + 2 tˇret´ı mocninou celého ˇc´ısla? Z11/47 13. Cviˇcenci nastoupili do obdéln´ıku, pˇriˇcemˇz na jedné stranˇe je o pˇet cviˇcenc˚ u v´ıc neˇz na druhé. Po skonˇcen´ı cviˇcen´ı nastoupili do ˇctyˇrstupu a odpochodovali z plochy. V posledn´ı ˇradˇe vˇsak jeden cviˇcenec chybˇel. Kolik cviˇcenc˚ u vystoupilo? Z12/47

Kapitola 4 Kongruence ˇ Necht’ 𝑎, 𝑏, 𝑚 ∈ 𝑍, pˇriˇcemˇz 𝑚 > 1. Rekneme, ˇze ˇc´ıslo 𝑎 je kongruentn´ı s ˇc´ıslem 𝑏 podle modulu 𝑚, jestliˇze 𝑚∣)𝑎 − 𝑏), neboli ˇc´ısla 𝑎 a 𝑏 dávaj´ı po dˇelen´ı ˇc´ıslem 𝑚 t´ yˇz zbytek. P´ıˇseme 𝑎 ≡ 𝑏. Plat´ı tedy, ˇze 14 ≡ 39 mod 5, nebot’ 5∣(39 − 14). Naproti tomu 5(27 − 14), p´ıˇseme tedy 27 ∕≡ 14 mod 5.

4.1

Vlastnosti kongruenc´ı podobn´ e vlastnostem rovnic

Z definice plyne, ˇze kongruence jsou tranzitivn´ı, tedy je-li 𝑎 ≡ 𝑏 mod 𝑚 a 𝑏 ≡ 𝑐 mod 𝑚, pak je 𝑎 ≡ 𝑐 mod 𝑚. Kongruence podle téhoˇz modulu je moˇzné ˇclen po ˇclenu sˇc´ıtat. D˚ ukaz: Necht’ 𝑎1 ≡ 𝑏1 mod 𝑚 a 𝑎2 ≡ 𝑏2 mod 𝑚. V tomto pˇr´ıpadˇe je 𝑎1 = 𝑏1 +𝑚𝑡1 a 𝑎2 = 𝑏2 +𝑚𝑡2 a 𝑎1 + 𝑎2 = 𝑏1 + 𝑏2 + 𝑚(𝑡1 + 𝑡2 ), tedy 𝑎1 + 𝑎2 ≡ 𝑏1 + 𝑏2 . D˚ usledkem je, ˇze podobnˇe jako u rovnic lze v kongruenci pˇrevádˇet z jedné strany na druhou. Jin´ ymi slovy ke kaˇzdé stranˇe kongruence lze pˇriˇc´ıst totéˇz ˇc´ıslo. Kongruence podle téhoˇz modulu lze navzájem násobit. D˚ ukaz: Vyjádˇr´ıme opˇet 𝑎1 a 𝑎2 stejn´ ym zp˚ usobem jako v pˇredchoz´ım pˇr´ıpadˇe, pak plat´ı 𝑎1 𝑎2 = 𝑏1 𝑏2 + 𝑚𝑁 , kde 𝑁 je celé ˇc´ıslo. Je tedy 𝑎1 𝑎2 ≡ 𝑏1 𝑏2 mod 𝑚. D˚ usledkem je, ˇze obˇe strany kongruence m˚ uˇzeme umocnit t´ ymˇz exponentem. Dalˇs´ım d˚ usledkem je, ˇze obˇe strany kongruence m˚ uˇzeme vynásobit t´ ymˇz ˇc´ıslem, násob´ıme totiˇz evidentnˇe správnou kongruenc´ı 𝑘 ≡ 𝑘 mod 𝑚. Narozd´ıl od rovnic m˚ uˇze b´ yt 𝑘 = 0, i kdyˇz o smysluplnosti této operace lze s u ´spˇechem pochybovat. Obˇe strany kongruence je moˇzno vydˇelit jejich spoleˇcn´ ym dˇelitelem, je-li nesoudˇeln´ y s modulem. D˚ ukaz: Z podm´ınek𝑎 ≡ 𝑏 (mod 𝑚), 𝑎 = 𝑎1 𝑑,𝑏 = 𝑏1 𝑑, (𝑑, 𝑚) = 1 plyne,ˇze rozd´ıl 𝑎 = 𝑏, rovn´ y (𝑎1 − 𝑏1 )𝑑, je dˇeliteln´ y ˇc´ıslem 𝑚. Proto je 𝑎1 − 𝑏1 je dˇelitelné ˇc´ıslem 𝑚, tedy 𝑎1 ≡ 𝑏1 (mod 𝑝).

4.2

Dalˇ s´ı vlastnosti kongruenc´ı

Obˇe strany kongruence i modul je moˇzno vynásobit t´ ymˇz cel´ ym ˇc´ıslem. D˚ ukaz: Z 𝑎 ≡ 𝑏 (mod 𝑝) plyne 𝑎 = 𝑏 + 𝑚𝑡, 𝑎𝑘 = 𝑏𝑘 + 𝑚𝑘𝑡 a tedy je 𝑎𝑘 ≡ 𝑏𝑘 (mod 𝑏𝑘) 23

Obˇe strany kongruence i modul je moˇzno vydˇelit jejich libovoln´ ym spoleˇcn´ ym dˇelitelem. D˚ ukaz: Necht’ 𝑎 ≡ 𝑏 (mod 𝑝), 𝑎 = 𝑎1 𝑑, 𝑏 = 𝑏1 𝑑, 𝑚 = 𝑚1 𝑑. Máme 𝑎 = 𝑏 + 𝑚𝑡, 𝑎1 𝑑 = 𝑏1 𝑑 + 𝑚1 𝑑𝑡, 𝑎1 = 𝑏1 + 𝑚1 𝑡, z ˇcehoˇz plyne 𝑎1 ≡ 𝑏1 (mod 𝑚)1 . Plat´ı-li kongruence 𝑎 ≡ 𝑏 podle nˇekolika modul˚ u, pak plat´ı i podle modulu, kter´ y je roven nejmenˇs´ımu spoleˇcnému násobku tˇechto modul˚ u. D˚ ukaz je zˇrejm´ y, rozd´ıl 𝑎−𝑏 je dˇeliteln´ y vˇsemi moduly, je tedy dˇeliteln´ y i jejich nejmenˇs´ım spoleˇcn´ ym násobkem. Plat´ı-li kongruence podle modulu 𝑚 podle modulu 𝑚, pak plat´ı i podle modulu 𝑑, kde 𝑑 je libovoln´ y dˇelitel ˇc´ısla 𝑑. D˚ ukaz je zˇrejm´ y nebot’ je-li rozd´ıl 𝑎 − 𝑏 dˇeliteln´ y ˇc´ıslem 𝑚, je dˇeliteln´ y i jeho libovoln´ ym dˇelitelem. Jsou-li jedna strana kongruence a modul dˇelitelné kter´ ymkoliv ˇc´ıslem, pak je i druhá strana kongruence dˇelitelná t´ımto ˇc´ıslem. D˚ ukaz: Plat´ı 𝑎 = 𝑏 + 𝑚𝑡. Je-li 𝑚 a 𝑎 dˇelitelné 𝑑, mus´ı b´ yt t´ımto ˇc´ıslem dˇelitelné i 𝑏. Je-li 𝑎 ≡ 𝑏 (mod 𝑚), pak (𝑎, 𝑚) = (𝑏, 𝑚). D˚ ukaz plyne z ????

4.3

´ Upln´ a soustava zbytk˚ u

ˇ ısla kongruentn´ı podle modulu 𝑚 vytváˇrej´ı tˇr´ıdu ˇc´ısel podle modulu m. Z této C´ definice plyne, ˇze vˇsem ˇc´ısl˚ um tˇr´ıdy odpov´ıdá jeden a t´ yˇz zbytek 𝑟 a ˇze vˇsechna ˇc´ısla tˇr´ıdy dostaneme, kdyˇz ve v´ yrazu 𝑚𝑞 + 𝑟 bude 𝑞 prob´ıhat vˇsechna celá ˇc´ısla. V souhlasu s t´ım, ˇze 𝑟 m˚ uˇze nab´ yvat 𝑚 r˚ uzn´ ych hodnot, máme 𝑚 tˇr´ıd podle modulu 𝑚. Libovolné ˇc´ıslo tˇr´ıdy se naz´ yvá zbytkem podle modulu m. Zbytek z´ıskan´ y pro 𝑞 = 0, kter´ y je roven samotnému zbytku 𝑟 se naz´ yvá nejmenˇs´ı nezáporný zbytek. Zbytek 𝜚 s nejmenˇs´ı absolutn´ı hodnotou se naz´ yvá absolutnˇe nejmenˇs´ı zbytek. Pro 𝑟 < 𝑚2 je zˇrejmˇe 𝜚 = 𝑟; pro 𝑟 > 𝑚2 je 𝜚 = 𝑟 − 𝑚; koneˇcnˇe je-li 𝑚 sudé a 𝑟 = 𝑚2 je za 𝜚 moˇzné vz´ıt kterékoliv ze dvou ˇc´ısel 𝑚2 a − 𝑚2 . Vezmeme-li z kaˇzdé tˇr´ıdy po jednom zbytku, dostaneme u ´plnou soustavu zbytk˚ u podle modulu m. Nejˇcastˇeji se pouˇz´ıvaj´ı jako u ´plná soustavu zbytk˚ u nejmenˇs´ı nezáporné ´ zbytky, pˇr´ıpadnˇe absolutnˇe nejmenˇs´ı zbytky. Pˇr´ıklad: Uplnou soustavu zbytk˚ u podle modulu 5 m˚ uˇzeme vyjádˇrit bud’ jako 0, 1, 2, 3, 4 nebo −2, −1, 0, 1, 2. Vˇ eta 4.1 Libovolných 𝑚 ˇc´ısel po dvou nekongruentn´ıch podle modulu 𝑚 vytv´ aˇr´ı u ´plnou soustavu zbytk˚ u podle modulu 𝑚. Vˇ eta 4.2 Necht’ (𝑎, 𝑚) = 1 a 𝑥 prob´ıhá u ´plnou soustavu zbytk˚ u podle modulu 𝑚, pak 𝑎𝑥 + 𝑏, kde 𝑏 je libovolné celé ˇc´ıslo, prob´ıhá také u ´plnou soustavu zbytk˚ u podle modulu 𝑚. D˚ ukazy obou tvrzen´ı jsou snadné a ponecháváme je na ˇctenáˇri jako cviˇcen´ı.

4.4

Redukovan´ a soustava zbytk˚ u

ˇ ısla jedné a téˇze zbytkové tˇr´ıdy podle modulu 𝑚 maj´ı s modulem jednoho a téhoˇz C´ nejvˇetˇs´ıho spoleˇcného dˇelitele. Tˇr´ıdy obsahuj´ıc´ı zbytky nesoudˇelné s modulem tvoˇr´ı redukovanou soustavu zbytk˚ u. Redukovanou soustavu zbytk˚ u tedy m˚ uˇzeme sestavit

z ˇc´ısel u ´plné soustavy, které jsou nesoudˇelné s modulem. Redukovanou soustavu obvykle vytváˇr´ıme ze soustavy nejmenˇs´ıch nezáporn´ ych zbytk˚ u. Ponˇevadˇz mezi ˇc´ısly u ´plné soustavy je jich právˇe 𝜑(𝑚) nesoudˇeln´ ych s modulem 𝑚, je poˇcet ˇc´ısel redukované soustavy stejnˇe jako poˇcet tˇr´ıd obsahuj´ıc´ı ˇc´ısla nesodˇelná s modulem 𝜑(𝑚). Pˇr´ıklad: Redukovaná soustava zbytk˚ u podle modulu 16 je 1, 3, 5, 7, 9, 11, 13, 15. Je-li modul prvoˇc´ıseln´ y, pak je redukovaná soustava zbytk˚ u totoˇzná s u ´plnou soustavou zbytk˚ u. Vˇ eta 4.3 Libovolných 𝜑(𝑚) ˇc´ısel, po dvou nekongruentn´ıch podle modulu 𝑚 a nesoudˇelných s modulem, tvoˇr´ı redukovanou soustavu zbytk˚ u podle modulu 𝑚. Vˇ eta 4.4 Je-li (𝑎, 𝑚) = 1 a 𝑥 prob´ıhá redukovanou soustavu zbytk˚ u podle modulu 𝑚, pak 𝑎𝑥 rovnˇeˇz prob´ıhá redukovanou soustavu zbytk˚ u podle modulu 𝑚. D˚ ukazy obou vˇet jsou analogické d˚ ukaz˚ um vˇet ??? a rovnˇeˇz je pˇrenecháváme ˇctenáˇri jako cviˇcen´ı.

4.5

Kongruence o jedn´ e nezn´ am´ e

V této kapitole budeme studovat kongruence obecného tvaru 𝑓 )𝑥) ≡ 0

(mod 𝑚);

𝑓 (𝑥) = 𝑎𝑛 𝑥𝑛 + 𝑎𝑛−1 𝑥𝑛−1 + . . . + 𝑎0 .(?)

ˇ sit kongruNen´ı-li 𝑎𝑛 dˇelitelné ˇc´ıslem 𝑚, pak se 𝑛 naz´ yvá stupeˇ n kongruence. Reˇ enci znamená naj´ıt vˇsechny hodnoty 𝑥, které j´ı vyhovuj´ı. Dvˇe kongruence, kter´ ym vyhovuj´ı stejné hodnoty 𝑥, se naz´ yvaj´ı ekvivalentn´ı. Vyhovuje-li kongruenci (?) jistá hodnota 𝑥0 , pak j´ı vyhovuj´ı i vˇsechna ˇc´ısla 𝑥 splˇ nuj´ıc´ı kongruenci 𝑥 ≡ 𝑥0 (mod 𝑚). Celá tato tˇr´ıda se povaˇzuje za jedno ˇreˇsen´ı. Za této u ´mluvy bude m´ıt kongruence (?) tolik ˇreˇsen´ı, kolik zbytk˚ uu ´plné soustavy j´ı vyhovuje. Pˇr´ıklad: Kongruenci 𝑥3 + 3𝑥2 + 3 ≡ 0 (mod 5) vyhovuje 𝑥 = 4. Kongruence má jediné ˇreˇsen´ı 𝑥 ≡ 4 (mod 5).

4.5.1

Line´ arn´ı kongruence

Budeme nyn´ı studovat lineárn´ı kongruenci, tedy kongruenci tvaru 𝑎𝑥 ≡ 𝑏 mod 𝑚.

(4.1)

Pˇredpokládejme, ˇze je (𝑎, 𝑚) = 1. Tato kongruence má právˇe tolik ˇreˇsen´ı, kolik zbytk˚ u u ´plné soustavy j´ı vyhovuje. Prob´ıhá-li 𝑥 u ´plnou soustavu sbytk˚ u podle modulu 𝑚, pak i 𝑎𝑥 prob´ıhá u ´plnou soustavu zbytk˚ u podle modulu 𝑚. Z tohoto d˚ uvodu bude 𝑎𝑥 kongruentn´ı s 𝑏 právˇe pro jednu hodnotou 𝑥 z u ´plné soustavy zbytk˚ u, jin´ ymi slovy kongruence () má právˇe jedno ˇreˇsen´ı. Necht’ nyn´ı je (𝑎, 𝑚) = 𝑑 > 1. Aby kongruence () mˇela ˇreˇsen´ı, je nutné, aby 𝑏 bylo dˇelitelné ˇc´ıslem 𝑑, jinak kongruence () nen´ı moˇzná pˇri ˇza´dném celém ˇc´ısle 𝑥. Budeme proto pˇredpokládat, ˇze 𝑏 je násobkem 𝑑 a poloˇz´ıme 𝑎 = 𝑎1 𝑑, 𝑚 = 𝑚1 𝑑 a 𝑏 = 𝑏1 𝑑. V tomto pˇr´ıpadˇe m˚ uˇzeme kongruenci zkrátit ˇc´ıslem 𝑑 a novˇe vzniklá kongruence 𝑎1 𝑥 ≡ 𝑏1 bude m´ıt jedno ˇreˇsen´ı podle moduli 𝑚1 , nebot’ je (𝑎1 , 𝑚1 ) = 1.

Necht’ 𝑥1 je nejmenˇs´ı nezáporn´ y zbytek tohoto ˇreˇsen´ı podle modulu 𝑚1 , pak vˇsechna ˇc´ısla 𝑥, tvoˇr´ıc´ı toto ˇreˇsen´ı, jsou tvaru 𝑥≡𝑥−1

(mod 𝑚1 ).

(4.2)

Podle modulu 𝑚 vˇsak ˇc´ısla () netvoˇr´ı jedno ˇreˇsen´ı, ale právˇe tolik ˇreˇsen´ı, kolik se najde v ˇradˇe 0, 1, 2, . . . , 𝑚 − 1 nejmenˇs´ıch nezáporn´ ych zbytk˚ u podle modulu 𝑚. Sem patˇr´ı vˇsechna tato ˇc´ısla )): 𝑥1 , 𝑥1 + 𝑚 𝑥1 + 2𝑚 . . . , 𝑥1 + (𝑑 − 1)𝑚, tedy celkkem 𝑑 ˇc´ısel (2), a tud´ıˇz kongruence () má 𝑑 ˇreˇsen´ı. V´ yˇse uvedené u ´vahy dokazuj´ı tuto vˇetu: Vˇ eta 4.5 Necht’ (𝑎, 𝑚) = 𝑑. Kongruence 𝑎𝑥 ≡ 𝑏 (mod 𝑚) nemá ˇreˇsen´ı, nen´ı-li pravá strana dˇelitelná 𝑑. V pˇr´ıpadˇe, ˇze je 𝑏 násobkem 𝑑, má kongruence 𝑑 ˇreˇsen´ı. ˇ ste kongruenci Nyn´ı si ukáˇzeme nˇekteré metody ˇreˇsen´ı kongruenc´ı. Pˇr´ıklad 1: Reˇ 4𝑥 ≡ 1 (mod 6). Tato kongruence nemá ˇreˇsen´ı, nebot’ (4, 6) = 2 a 21. Pokud nen´ı modul pˇr´ıliˇs velk´ y, lze kongruenci ˇreˇsit tak, ˇze zjist´ıme, která ˇc´ısla j´ı vyhovuj´ı, obvykle ze soustavy nejmenˇs´ıch nezáporn´ ych zbytk˚ u. Pˇr´ıklad 2: ˇreˇste kongruenci 3𝑥 ≡ 2 (mod 5). Jelikoˇz (3, 5) = 1, má kongruence právˇe jedno ˇreˇsen´ı. Soustava nejmenˇs´ıch nezáporn´ ych zbytk˚ u má tvar 0, 1, 2, 3, 4. Snadno se pˇresvˇedˇc´ıme, ˇze této kongruenci vyhovuje ˇ sen´ım kongruence jsou tedy vˇsechna ˇc´ısla 𝑥 ≡ 4 (mod 5). právˇe ˇc´ıslo 4. Reˇ ˇ ste kongruenci 6𝑥 ≡ 9 (mod 1)5. Pˇr´ıklad 3: Reˇ Jelikoˇz (6, 15) = 3 a 3 ∣ 9, bude m´ıt kongruence 3 ˇreˇsen´ı. Vydˇel´ıme-li obˇe strany kongruence 3, obdrˇz´ıme novou kongruenci 2𝑥 ≡ 3 (mod 5). Vzhledem k tomu, ˇze modul je pomˇernˇe malé ˇc´ıslo, lze ˇreˇsen´ı urˇcit postupn´ ym dosazován´ım ˇc´ısel ze soustavy nejmenˇs´ıch nezáporn´ ych zbytk˚ u. Snadno zjist´ıme, ˇze jej´ım ˇreˇsen´ım je ˇc´ıslo ˇ sen´ı p˚ 𝑥1 = 4. Dalˇs´ım ˇreˇsen´ım jsou ˇc´ısla 𝑥2 = 𝑥1 + 5 a 𝑥3 = 𝑥1 + 2.5. Reˇ uvodn´ı kongruence lze uvést ve tvaru 𝑥𝑞𝑒𝑞𝑢𝑖𝑣4; 9; 14 (mod 2)0. Pˇri ˇreˇsen´ı kongruenc´ı, kde (𝑎, 𝑚) = 1, lze vyuˇz´ıt Eulerovu vˇetu. Skuteˇcnˇe, je-li 𝑎𝜑(𝑚) ≡ 1 (mod 𝑚), je i 𝑎𝜑(𝑚) 𝑏 ≡ 𝑏 (mod 𝑚). Odsud máme 𝑎𝑥 ≡ 𝑎𝜑(𝑚) 𝑏, a proto je 𝑥 ≡ 𝑎𝜑(𝑚)−1 𝑏. Staˇc´ı tedy vypoˇc´ıtat ˇc´ıslo 𝑎𝜑(𝑚)−1 𝑏. Toto ˇc´ıslo sice nebude patˇrit mezi nejmenˇs´ı nezáporné zbytky, nen´ı vˇsak problém nejmenˇs´ı nezáporn´ y zbytek naj´ıt. ˇ Pˇr´ıklad 4: Reˇste kongruenci 6𝑥 ≡ 2 (mod 7). Jelikoˇz 𝜑7 = 6, je 𝑥 = 65 ⋅ 2 a kv˚ uli eleganci a jednoduchosti ho zap´ıˇseme ve tvaru 𝑥 ≡ 5 (mod 7).

4.5.2

Soustava line´ arn´ıch kongruenc´ı

Jelikoˇz nˇekteré vlastnosti kongruenc´ı jsou stejné ˇci analogické vlastnostem rovnic, je nam´ıstˇe si poloˇzit otázku, zda lze ˇreˇsit i soustavu lineárn´ıch kongruenc´ı. Omez´ıme se na soustavu kongruenc´ı o jedné neznámé s r˚ uzn´ ymi, po dvou nesoudˇeln´ ymi moduly, tedy na soustavu tvaru 𝑎 ≡ 𝑏1

(mod 𝑚1 ),

𝑥 ≡ 𝑏2

(mod 𝑚2 ), . . . , 𝑥 ≡ 𝑏𝑘

ˇ sit soustavu () je moˇzno podle následuj´ıc´ı vˇety. Reˇ

(mod 𝑚𝑘 ).

(4.3)

Vˇ eta 4.6 Necht’ ˇc´ısla 𝑀𝑠 a 𝑀´𝑠 jsou definována podm´ınkami 𝑀𝑠 𝑚´𝑠 ≡ 1

𝑚1 𝑚2 . . . 𝑚𝑘 = 𝑀𝑠 𝑚𝑠 ,

(mod 𝑚𝑠 )

a necht’ 𝑥0 = 𝑀1 𝑀´1 𝑏1 + 𝑀2 𝑀´2 + . . . + 𝑀𝑘 𝑀´𝑘 𝑏𝑘 . Pak souhrn hodnot 𝑥 vyhovuj´ıc´ıch soustavˇe () je urˇcen kongruenc´ı 𝑥 ≡ 𝑥0

(mod 𝑚1 𝑚2 . . . 𝑚𝑘 ).

(4.4)

Vskutku, vzhledem k dˇelitelnosti vˇsech ˇc´ısel 𝑀𝑗 , r˚ uzn´ ych od 𝑀𝑠 , ˇc´ıslem 𝑚𝑠 pˇri libovolném 𝑠 = 1, 2, . . . , 𝑘 je 𝑥0 ≡ 𝑀𝑠 𝑀´𝑠 𝑏𝑠 ≡ 𝑏𝑠

(mod 𝑚𝑠 ),

a tedy soustavˇe () vyhovuje 𝑥 = 𝑥0 . Odtud pˇr´ımo plyne, ˇze soustava () je ekvivalentn´ı se soustavou 𝑥 ≡ 𝑥0

(mod 𝑚1 ),

𝑥 ≡ 𝑥0

(mod 𝑚2 ), . . . , 𝑥 ≡ 𝑥0

(mod 𝑚𝑘 ),

(4.5)

tedy soustavám () a () vyhovuj´ı tytéˇz hodnoty 𝑥. Soustavˇe () pak vyhovuj´ı jen ty hodnoty 𝑥, které vyhovuj´ı kongruenci (). Vˇ eta 4.7 Necht’ 𝑏1 , 𝑏2 , . . . , prob´ıhaj´ı nezávisle jedno na druhém u ´plné soustavy zbytk˚ u podle modul˚ u 𝑚1 , 𝑚2 , . . . , 𝑚𝑘 , pak 𝑥0 prob´ıhá u ´plnou soustavu zbytk˚ u podle modul˚ u 𝑚1 , 𝑚2 , . . . , 𝑚𝑘 . D˚ ukaz: Vskutku, 𝑥0 prob´ıhá 𝑚1 , 𝑚2 , . . . , 𝑚𝑘 hodnot, vzhledem k () mekongruentn´ıch podle modulu 𝑚1 , 𝑚2 , . . . , 𝑚𝑘 . ˇ ste soustavu kongruenc´ı Pˇr´ıklad: Reˇ 𝑥 ≡ 𝑏1

(mod 4),

𝑥 ≡ 𝑏2

𝑥 ≡ 𝑏3

(mod 5),

Plat´ı 4.5.7=4.35=5.28=7.20, pˇriˇcemˇz 35.3 ≡ 1

(mod 4),

28.2 ≡ 1

(mod 5),

20.6 ≡ 1

(mod 7).

Proto je 𝑥0 = 35.3𝑏1 + 28.2𝑏2 + 20.6𝑏3 = 105𝑏1 + 56𝑏2 + 120𝑏3 , a tedy souhrn hodnot 𝑥 vyhovuj´ıc´ıch soustavˇe m˚ uˇze b´ yt vyjádˇren ve tvaru 𝑥 ≡ 105𝑏1 + 56𝑏2 + 120𝑏3

(mod 140).

tak napˇr. souhrn hodnot 𝑥, vyhovuj´ıc´ıch soustavˇe 𝑥≡1

(mod 4),

𝑥≡3

(mod 5),

,𝑥 ≡ 2

(mod 7),

je 𝑥 ≡ 105.1 + 56.3 + 120.2 ≡ 93

(mod 140).

a souhrn hodnot 𝑥, vyhovuj´ıc´ıch soustavˇe 𝑥≡3

(mod 4),

𝑥≡2

(mod 5),

𝑥≡6

(mod 7),

je 𝑥 = 105.3 + 56.2 + 120.6 ≡ 27

(mod 140).

4.6

Kongruence libovoln´ eho stupnˇ e podle prvoˇ c´ıseln´ eh modulu

Budeme se zab´ yvat kongruenc´ı tvaru 𝑎𝑛 𝑥𝑛 + 𝑎1 𝑥𝑛−1 + . . . + 𝑎0 ≡

(mod 𝑝)

(4.6)

kde 𝑝 je prvoˇc´ıslo. Kongruence tvaru () je ekvivalentn´ı s kongruenc´ı stupnˇe nejv´ yˇs 𝑝 − 1. Toto tvrzen´ı plyne ze skuteˇcnosti, ˇze 𝑓 (𝑥) lze psát jako 𝑓 (𝑥) = (𝑥𝑝 − 𝑥)𝑄(𝑥) + 𝑅(𝑥),

kde 𝑅(𝑥) je zbytek po dˇelen´ı 𝑓 (𝑥) polynomem 𝑥𝑝 −𝑥, jehoˇz stupeˇ n nem˚ uˇze pˇrev´ yˇsit 𝑝 𝑝 − 1. Podle Malé Fermatovy vˇety zase máme 𝑥 − 𝑥 ≡ 0 (mod 𝑝), je tedy 𝑓 (𝑥) ≡ 𝑅(𝑥) (mod 𝑝). Necht’ kongruence () má v´ıce neˇz 𝑛 ˇreˇsen´ı. Pak plat´ı, e vˇsechny koeficienty 𝑎𝑖 jsou násobky 𝑝. Oznaˇcme zbytky vˇsech ˇreˇsen´ı kongruence () p´ısmeny 𝑓 (𝑥) =𝑎(𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) . . . (𝑥 − 𝑏(𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) . . . (𝑥 − 𝑥𝑛 +...+ 𝑥1 , 𝑥2 , . . . 𝑥𝑛 , 𝑥𝑛+1 . Polynom 𝑓 (𝑥) m˚ uˇzeme vyjádˇr´ıt jako +𝑙(𝑥 − 𝑥1 ) +𝑚. Sˇc´ıtance na pravé stranˇe pˇremˇen´ıme v mnohoˇcleny a zvol´ıme 𝑏 tak, aby souˇcet koeficient˚ u dvou prv´ ych mnohoˇclen˚ u u 𝑥𝑛−1 byl 𝑎1 ; známe-li 𝑏, zvol´ıme c tak, aby souˇcet korficient˚ u prv´ ych tˇr´ı mnohoˇclen˚ u u 𝑥𝑥−2 byl 𝑎2 atd. klademe-li postupnˇe 𝑥 = 𝑥1 , 𝑥2 , . . . , 𝑥𝑛 , 𝑥𝑛+1 , pˇresvˇedˇc´ıme se, ˇze vˇsechna ˇc´ısla 𝑚, 𝑙, 𝑘, . . . , 𝑐, 𝑏, 𝑎 jsou násobky 𝑝. Protoˇze 𝑎𝑖 jsou souˇcty ˇc´ısel dˇeliteln´ ych 𝑝, jsou také dˇelitelná 𝑝.

4.7

Kongruence druh´ eho stupnˇ e

V tomto odd´ıle budeme vyˇsetˇrovat kongruence tvaru 𝑥2 ≡ 𝑎 (mod 𝑝);

(𝑎, 𝑝) = 1,

(4.7)

kde 𝑝 je liché prvoˇc´ıslo. Pokud má tato kongruence ˇreˇsen´ı, naz´ yváme ˇc´ıslo 𝑎 kvadratickým zbytkem, v opaˇcném pˇr´ıpadˇe kvadratickým nezbytkem podle modulu 𝑝. Vˇ eta 4.8 Necht’ 𝑎 je kvadratický zbytek podle modulu 𝑝. pak kongruence () m´ a právˇe dvˇe ˇreˇsen´ı. D˚ ukaz: Jelikoˇz 𝑎 je kvadratick´ y zbytek, mus´ı m´ıt kongruence () alespoˇ n jedno ˇreˇsen´ı, 2 2 ˇreknˇeme ˇze je to 𝑥1 . Protoˇze je (−𝑥1 ) = 𝑥1 , má tato kongruence i druhé ˇreˇsen´ı 𝑥 ≡ −𝑥1 (mod 𝑝). Dále nem˚ uˇze platit 𝑥1 ≡ −𝑥1 (mod 𝑝), nebot’ pak by bylo2𝑥1 ≡ 0 (mod 𝑝). Toto vˇsak nen´ı moˇzné, protoˇze (2, 𝑝) = (𝑥1 , 𝑝) = 1. Dalˇs´ı ˇreˇsen´ı jiˇz tato kongruence nem˚ uˇze m´ıt, jak bylo dokázáno v ?? kvadraVˇ eta 4.9 Redukovaná soustava zbytk˚ u podle modulu 𝑝 se skládá z 𝑝−1 2 ( 𝑝−1 )2 𝑝−1 2 2 tických zbytk˚ u, které jsou kongruentn´ı s ˇc´ısly 1 , 2 , . . . , 2 a 2 kvadratických nezbytk˚ u.

D˚ ukaz: Mezi zbytky redukované soustavy podle modulu 𝑝 jsou kvadratick´ ymi zbytky ty a jenom ty, které jsou kongruentn´ı s ˇctverci ˇc´ısel −

𝑝−1 𝑝−1 , . . . , −2, −1, 1, 2, . . . , 2 2

(4.8)

podle modulu 𝑝. pˇritom ˇctverce ˇc´ısel () nejsou kongruentn´ı podle modulu 𝑝, nebot’ by plynulo, ˇze kongruenci 𝑥2 ≡ 𝑙2 z podm´ınek 𝑘 2 ≡ 𝑙2 (mod 𝑝), 0 < 𝑘 < 𝑙 ≤ 𝑝−1 2 (mod 𝑝) z ˇc´ısel )) vyhovuj´ı ˇctyˇri: 𝑥 ≡ −𝑙, −𝑘, 𝑙, 𝑘, coˇz je spor. Vˇ eta 4.10 Necht’ 𝑎 je kvadratický zbytek podle modulu 𝑝. Pak plat´ı 𝑎

𝑝−1 2

≡1

(mod 𝑝);

(4.9)

Je-li 𝑎 kvadratický nezbytek podle moduli 𝑝, plat´ı 𝑎

𝑝−1 2

≡ −1

(mod 𝑝).

(4.10)

D˚ ukaz: Malá Fermatova vˇeta nám ˇr´ıká, ˇze 𝑎𝑝−1 ≡ 1 (mod 𝑝). Tuto kongruenci lze psát také ve tvaru ( 𝑝−1 ) ( 𝑝−1 ) 2 2 𝑎 −1 𝑎 + 1 ≡ 0 (mod 𝑝). Jelikoˇz rozd´ıl obou závorek je roven dvˇema, tak plat´ı pouze jedna z kongruenc´ı (), (). Kaˇzd´ y kvadratick´ y zbytek 𝑎 vyhovuje pˇri nˇekterém 𝑥 kongruenci 𝑎 ≡ 𝑥2

(mod 𝑝),

(4.11)

a proto vyhovuje i kongruenci (), kterou obdrˇz´ıme, umocn´ıme-li obˇe strany kongruence na 𝑝−1 . Kvadratick´ ymi zbytky jsou vyˇcerpána vˇsechna ˇreˇsen´ı kongruence 2 (). Kvadratické nezbytky mus´ı tedy nezbytky vyhovovat kongruenci ().

4.8

Legendre˚ uv symbol ( ) 𝑎 𝑝

je roven 1 je-li 𝑎 kvadratick´ y zbytek a -1, je-li 𝑎 kvadratick´ y ˇ ıslo 𝑎 se naz´ nezbytek podle modulu 𝑝, pˇriˇcemˇz je )𝑎, 𝑝) = 1. C´ yvá ˇcitatel a ˇc´ıslo 𝑝 ˇ jmenovatel Legendreova symbolu. Cteme 𝑎 vzhledem k 𝑝. Zˇrejmˇe plat´ı ( ) 𝑝−1 𝑎 ≡𝑎 2 (mod 𝑝). 𝑝 Legendre˚ uv symbol

Jelikoˇz ˇc´ısla jedné a téˇze tˇr´ıdy jsou souˇcasnˇe kvadratické zbytky nebo nezbytky, plat´ı dále následuj´ıc´ı tvrzen´ı. Vˇ eta 4.11 Necht’ 𝑎 ≡ 𝑎1 (mod 𝑝). Pak plat´ı

( ) 𝑎 𝑝

=

( ) 𝑎1 𝑝

.

Jelikoˇz 1 = 12 , je jedniˇcka kvadratick´ y zbytek pro kaˇzd´ y modul a tedy plat´ı: ( ) 𝑎 = 1. 𝑝 Lichá prvoˇc´ısla m˚ uˇzeme vyjádˇrit bud’ ve tvaru 4𝑘 + 1 nebo 4𝑘 + 3. V prvn´ım ˇ ıslo −1 je proto pˇr´ıpadˇe je ale v´ yraz 𝑝−1 vˇzdy ˇc´ıslo sudé, ve druhém pak liché. C´ 2 kvadratick´ ym zbytkem prvoˇc´ısel tvaru 4𝑘 + 1 a kvadratick´ ym nezbytkem prvoˇc´ısel tvaru 4𝑘 + 3. Plat´ı tedy ( ) 𝑝−1 −1 = (−1) 2 𝑝 Pro Legendre˚ uv symbol také plat´ı: ( ) ( )( ) ( ) 𝑎𝑏 . . . 𝑙 𝑎 𝑏 𝑙 = ⋅⋅⋅ . 𝑝 𝑝 𝑝 𝑝 Vskutku máme ) ( )( ) ( ) ( 𝑝−1 𝑝−1 𝑝−1 𝑝−1 𝑎 𝑏 𝑙 𝑎𝑏 . . . 𝑙 ≡ (𝑎𝑏 . . . 𝑙) 2 ≡ (𝑎) 2 (𝑏 2 . . . (𝑙) 2 ≡ ... 𝑝 𝑝 𝑝 𝑝

(mod 𝑝).

D˚ usledkem je, ˇze v ˇcitateli m˚ uˇzeme vypustit kaˇzd´ y kvadratick´ y ˇcinitel, tedy plat´ı ( 2) ( ) 𝑎𝑏 𝑎 = . 𝑝 𝑝 Vˇ eta 4.12 Necht’ 𝑝 a 𝑞 jsou lichá prvoˇc´ısla. Pak plat´ı ( )( ) 𝑝−1 𝑞−1 𝑝 𝑞 = (−1) 2 2 . 𝑞 𝑝 Tato vˇeta je v teorii ˇc´ısel známa jako Gauss˚ uv zákon kvadratické reciprocity. Jako prvn´ı ho dokázal Gauss, kter´ y ho nazval theorema aurea (zlatá vˇeta). Tento zákon nám umoˇzn ˇuje ve spojen´ı s v´ yˇse uveden´ ymi vlastnostmi znaˇcnˇe zjednoduˇsit v´ ypoˇcet Legendreova symbolu jak ukáˇzeme n´ıˇze. D˚ ukaz zákona kvdratické reciprocity neuvád´ıme pro jeho délku, ˇctenáˇr ho m˚ uˇze naj´ıt napˇr. v ( ) 111 Pˇr´ıklad: vypoˇctˇete Legendre˚ uv symbol 𝐿 = 1999 . Nejpre si vˇsimneme, ˇze 111 je ˇc´ıslo sloˇzené a ˇze plat´ı 111 = 3.37. Plat´ı tedy ( ) ( )( ) 3 37 111 = . 1999 1999 1999 Nyn´ı vyuˇzijeme zákon kvadratické reciprocity, ˇc´ımˇz v ”ˇcitateli”Legendreova symbolu obdrˇz´ıme vˇetˇs´ı ˇc´ıslo neˇz ve ”jmenovateli”. Máme tedy ( ) ( ) 1999 1999 999 999⋅18 𝐿 = (−1) × (−1) 3 37 Pokud dˇel´ıme ˇc´ıslo 1999 trojkou ˇci tˇriceti sedmi, dostaneme v obou pˇr´ıpadech jedniˇcku. Jin´ ymi slovy 1999 je kongruentn´ı s jedniˇckou jak podle modulu 37, tak i podle modulu 3. M˚ uˇzeme tedy v´ ypoˇcet ukonˇcit. ( )( ) 1 1 𝐿 = (−1) = −1. 3 37

Nask´ ytá se otázka, zda by neˇslo zavést podobn´ y symbol i v pˇr´ıpadˇe, ˇze ve ”jmenovateli”nen´ı prvoˇc´ıslo. T´ımto problémem se zab´ yval nˇemeck´ y matematik C. G. Jacobi, kter´ y Legendre˚ uv symbol rozˇs´ıˇril následuj´ıc´ım zp˚ usobem. Def. 4.1 Necht’ 𝑎 je celé ˇc´ıslo a necht’ 𝑛 ≥ 3 je liché. Necht’ dále 𝑛 = 𝑝1 𝑝2 . . . 𝑝𝑟 , kde 𝑝𝑖 jsou lichá prvoˇc´ısla, nikoliv nutnˇe r˚ uzná. Jacobiho symbol je definován vztahem 𝑟 ( ) (𝑎) ∏ 𝑎 = , (4.12) 𝑛 𝑝 𝑖 𝑖=1 ( ) kde 𝑝𝑎𝑖 je Legendre˚ uv symbol. Vlastnosti Jacobiho symbolu jsou analogické vlastnostem symbolu Legendreova vˇcetnˇe zákona kvadratické reciprocity, jeden v´ yznamn´ y rozd´ıl vˇsak pˇrece najdeme. Je-li Legendre˚ uv symbol roven jedné, je vˇzdy 𝑎 kvadratick´ y zbytek modulo 𝑝, to plyne z jeho definice. V pˇr´ıpadˇe Jacobiho symbolu to vˇsak platit nemus´ı, jak se m˚ uˇzeme pˇresvˇedˇcit z následuj´ıc´ıho pˇr´ıkladu. ( ) ( )( ) 2 2 1 = = (−1)(−1) = 1, 15 3 5 dvojka vˇsak nen´ı kvadratick´ y zbytek modulo 15.

4.9

Nˇ ekter´ e d˚ uleˇ zit´ e vˇ ety z teorie ˇ c´ısel

Závˇerem této kapitoly uvedeme nˇekolik vˇet z teoreie ˇc´ısel. Vˇ eta 4.13 Malá Fermatova vˇeta. Necht’ 𝑝 je prvoˇc´ıslo a plat´ı (𝑎, 𝑝) = 1. Pak je 𝑎𝑝−1 ≡ 1

(mod 𝑝).

(4.13)

Dnes je známo nˇekolik d˚ ukaz˚ u této vˇety, autor si dovol´ı pˇrihˇrát svou pol´ıvˇciˇcku a odkázat ˇctenáˇre na publikaci [3]. Aby ˇctenáˇri nebyli zcela oˇsizeni, uvedeme elegantn´ı d˚ ukaz pro speciáln´ı pˇr´ıpad 𝑎 = 2. Jednou z nejd˚ uleˇzitˇejˇs´ıch vˇet turbodidaktiky je vˇeta Tesákova, která prav´ı, ˇze 1 + 1 = 2. Vyuˇzijeme-li tuto vˇetu, máme ( ) ( ) ( ) ( ) 𝑝 𝑝 𝑝 𝑝 𝑝 𝑝 2 = (1 + 1) = + + ⋅⋅⋅ + + . 0 1 𝑝−1 𝑝 () Jelikoˇz 𝑝 je prvoˇc´ıslo, jsou vˇsechny binomické koeficienty 𝑘𝑝 dˇelitelné 𝑝 s v´ yjimkou 𝑘 = 0 a 𝑘 = 𝑝. M˚ uˇzeme tedy od rovnosti pˇrej´ıt ke kongruenci, ˇc´ımˇz obdrˇz´ıme 2𝑝 ≡ 2

(mod 𝑝) ⇒ 2𝑝−1 ≡ 1

(mod 𝑝).

Posledn´ı u ´prava plyne ze skuteˇcnosti, ˇze podle pˇredpokladu Malé Fermatovy vˇety je (2, 𝑝) = 1. D˚ usledkem Malé Fermatovy vˇety je skuteˇcnost, ˇze pod´ıl 𝑞(𝑎) =

𝑎𝑝−1 − 1 𝑝

je celé ˇc´ıslo. Pod´ıl 𝑞(𝑎) se naz´ yvá Fermat˚ uv kvocient. Malou Fermatovu vˇetu pozdˇeji zobecnil Euler.

Vˇ eta 4.14 (Euler). Necht’ 𝑎 a 𝑛 jsou pˇrirozená ˇc´ısla a (𝑎, 𝑛) = 1. Pak plat´ı 𝑎𝜑(𝑛) ≡ 1

(mod 𝑛),

(4.14)

kde 𝜑(𝑛) je Eulerova funkce, kterou jsme definovali v kapitole druhé. Pˇripomeneme, ˇze v´ yraz 𝑛! = 𝑛.(𝑛 − 1) . . . 2.1 naz´ yváme 𝑛 faktoriál. Dá se dokázat vˇeta Vˇ eta 4.15 (Wilson) Necht’ 𝑝 je prvoˇc´ıslo. pak plat´ı (𝑝 − 1)! ≡ −1

(mod 𝑝).

(4.15)

Jelikoˇz byla uvedena Malá Fermatova vˇeta, sluˇs´ı se téˇz uvést i Velkou Fermatovu vˇetu, i kdyˇz tato pˇr´ımo do tematiky tohoto textu nezapadá. Vˇ eta 4.16 Diofantická rovnice 𝑥𝑛 + 𝑦 𝑛 = 𝑧 𝑛

(4.16)

nemá pro 𝑛 > 2 ˇreˇsen´ı v oboru celých ˇc´ısel. Jak jiˇz bylo ˇreˇceno, tato vˇeta se pˇr´ımo net´ yká prob´ırané problematiky, avˇsak jedná se o velmi znám´ y problém, takˇze pokud by se s n´ım chtˇel nˇekdo bl´ıˇze seznámit, doporuˇcujeme knihu [6].

4.10

Pˇ r´ıklady k procviˇ cen´ı

1. Zjistˇete, které z následuj´ıc´ıch kongruenc´ı jsou ˇreˇsitelné a) 6𝑥 ≡ 1 (mod 9) b) 9𝑥 ≡ 3 (mod 6) c) 14𝑥 ≡ 21 (mod 70) Z2/110 ˇ ste kongruence 2. Reˇ a) 20𝑥 ≡ 4 (mod 30) b) 20𝑥 ≡ 30 (mod 4) c) 353𝑥 ≡ 254 (mod 400) Z3/110 3. Najdˇete nejmenˇs´ı pˇrirozené ˇc´ıslo vˇetˇs´ı neˇz 1, které vyhovuje kongruenc´ım 𝑥 ≡ 1 (mod 3), 𝑥 ≡ 1 (mod 5), 𝑥 ≡ 1 (mod 7). Z8/111 ˇ ste soustavu kongruenc´ı 𝑥 ≡ 2 (mod 3), 𝑥 ≡ 3 (mod 5), 𝑥 ≡ 5 (mod 2). 4. Reˇ Z9/111 ˇ ste soustavu kongruenc´ı 𝑥 ≡ 1 (mod 4), 𝑥 ≡ 0 (mod 3), 𝑥 ≡ 5 (mod 7). 5. Reˇ Z10/141 6. Najdˇete vˇsechna celá ˇc´ısla, která pˇri dˇelen´ı ˇc´ısly 3, 4 a 5 dáv aj´ı zbytky 1, 2 a 3. Z11/141

Kapitola 5 Speci´ aln´ı typy pˇ rirozen´ ych ˇ c´ısel V této kapitole uvedeme nˇekteré speciáln´ı typy ˇc´ısel, a to jak prvoˇc´ısel, tak ˇc´ısel sloˇzen´ ych. Tato kapitola nebude m´ıt charakter uˇcebn´ıho textu jako pˇredchoz´ı, ˇctenáˇr se v n´ı seznám´ı s nˇekter´ ymi speciáln´ımi typy ˇc´ısel a pozná r˚ uzné zaj´ımavosti, ˇ ısla jsou totiˇz velmi zaj´ımavá a m˚ které pak bude moci uplatnit ve v´ yuce. C´ uˇzeme ˇr´ıci ˇze i tajuplná. Jednotlivé podkapitoly budeme ˇradit podle abecedy.

5.1

Dokonal´ aˇ c´ısla

Jak jiˇz bylo ˇreˇceno, má kaˇzdé pˇrirozené ˇc´ıslo 𝑛 > 1 pˇrinejmenˇs´ım dva dˇelitele, a sice 1 a 𝑛. Oznaˇcme 𝜎(𝑛) souˇcet vˇsech dˇelitel˚ u ˇc´ısla 𝑛. Zˇrejmˇe plat´ı 𝜎(𝑛) ≥ 1, porovnejme vˇsak souˇcet dˇelitel˚ u s dvojnásobkem ˇc´ısla 𝑛. Zvol´ıme-li tuto hranici, tak se mnoˇzina pˇrirozen´ ych ˇc´ısel 𝑛 > 1 rozloˇz´ı na tˇri navzájem disjunkntn´ı podmnoˇziny. Do prvn´ı zaˇrad´ıme ta ˇc´ısla, pro nˇeˇz 𝜎(𝑛) < 2𝑛 a budeme je naz´ yvat deficientn´ı (numeri deficientes). Tato mnoˇzina je nekoneˇcná, nebot’ sem patˇr´ı mj. vˇsechna ˇ ısla pro nˇeˇz 𝜎(𝑛) > 2𝑛 nazveme abundatn´ı (numeri abundantes). I tato prvoˇc´ısla. C´ mnoˇzina je nekoneˇcná, m˚ uˇzeme sem zaˇradit ˇc´ısla tvaru 𝑛 = 2𝑘 ⋅3, 𝑘 > 1. D˚ ukaz je snadn´ y pro toho, kdo ovládá vzorec pro souˇcet prvn´ıch 𝑛 ˇclen˚ u geometrické posloupnosti. Plat´ı 𝜎(𝑛) =

2𝑘+1 − 1 32 − 1 = (2𝑘+1 − 1) ⋅ 4 > 2 ⋅ (2𝑘 ⋅ 3) = 2𝑛. 2−1 3−1

Tˇret´ı mnoˇzinu pak tvoˇr´ı ˇc´ısla 𝑛 > 1, pro nˇeˇz je 𝜎(𝑛) = 2𝑛. Tato ˇc´ısla naz´ yváme ˇc´ısla dokonalá (numeri perfecti), nˇekdy téˇz pouˇz´ıváme název dokonalá ˇc´ısla prvn´ıho druhu. Nˇekdy se dokonalé ˇc´ıslo (prvn´ıho druhu) také definuje tak, ˇze je rovno souˇctu vˇsech sv´ ych prav´ ych dˇelitel˚ u, tedy dˇelitel˚ u menˇs´ıch neˇz je ˇc´ıslo samo. Nejmenˇs´ı dokonalé ˇc´ıslo je 6=1+2+3. Ve starovˇeku byla známa jeˇstˇe tˇri dalˇs´ı dokonalá ˇc´ısla, a to 28, 496 a 8128. Je zaj´ımavé, ˇze jiˇz v Eukleidov´ ych Základech je uvedena postaˇcuj´ıc´ı podm´ınka pro to, aby sudé ˇc´ıslo bylo dokonalé, ovˇeˇrován´ı vˇsak bylo zˇrejmˇe nad s´ıly tehdejˇs´ıch poˇctáˇr˚ u. Jak si jistˇe ˇctenáˇri vˇsimli, tak uvedená dokonalá ˇc´ısla jsou sudá. Uvedeme proto nutnou a postaˇcuj´ıc´ı podm´ınku pro to, aby sudé ˇc´ıslo bylo dokonalé. Vˇ eta 5.1 Sudé ˇc´ıslo 𝑛 > 1 je dokonalé právˇe tehdy, kdyˇz je tvaru 𝑛 = 2𝑠−1 (2𝑠 − 1), 33

(5.1)

kde 𝑠 > 1 je pˇrirozené ˇc´ıslo a 𝑀𝑠 = 2𝑠 − 1 je prvoˇc´ıslo. ˇ ısla 𝑀𝑠 se naz´ C´ yvaj´ı Mersennova ˇc´ısla. V následuj´ıc´ım d˚ ukazu je vˇsak pro zjednoduˇsen´ı zápisu budeme oznaˇcovat p´ısmenem 𝑝. D˚ ukaz: D˚ ukaz postaˇcuj´ıc´ı podm´ınky je snazˇs´ı, proto j´ım zaˇcneme. Necht’ nˇejaké ˇc´ıslo je tvaru (); tento tvar pˇredstavuje zároveˇ n jeho kanonick´ y rozklad. Proto je 𝜎(𝑛) =

2𝑠 − 1 𝑝2 − 1 . 2−1 𝑝−1

Odtud jednoduchou u ´pravou zjist´ıme, ˇze 𝜎(𝑛) = 2𝑠 𝑝 = 2(2𝑠−1 𝑝), tedy 𝑛 je dokonalé. Dokáˇzeme dále podm´ınku nutnou. Necht’ 𝑛 je sudé dokonalé ˇc´ıslo. Snadno nahlédneme, ˇze jeho kanonick´ y rozklad mus´ı obsahovat pˇrinejmenˇs´ım jedno liché ’ prvoˇc´ıslo, nebot pak by bylo tvaru 2𝑘 , 𝑘 ≥ 1 a 𝜎(𝑛) = 2𝑘+1 − 1 a ˇc´ıslo 𝑛 by tedy nebylo dokonalé. Kanonick´ y rozklad ˇc´ısla 𝑛 necht’ je 𝑛 = 2𝛼 𝑝𝛼1 1 ⋅𝑝𝛼2 2 ⋅ ⋅ ⋅ 𝑝𝛼𝑘 𝑘 . Poloˇzme 𝛼𝑘 𝛼1 𝛼2 𝑙 = 𝑝1 ⋅ 𝑝2 ⋅ ⋅ ⋅ 𝑝𝑘 a 𝛼 = 𝑠 − 1. Jelikoˇz 𝑛 je dokonalé, mus´ı b´ yt 2𝑠 − 1 𝑝𝛼1 1 +1 − 1 𝑝𝛼1 𝑘 +1 − 1 𝜎(𝑛) = ⋅⋅⋅ = (2𝑠 − 1)𝜎(𝑙) = 2𝑠 𝑙, 2 − 1 𝑝1 − 1 𝑝1 − 1 protoˇze 𝜎(𝑙) =

𝑝𝛼1 1 +1 − 1 𝑝𝛼𝑘 +1 − 1 ⋅⋅⋅ 1 . 𝑝1 − 1 𝑝𝑘 − 1

Rovnost (2𝑠 − 1).𝜎(𝑙) = 2𝑠 .𝑙

(5.2)

ˇ ıslo 2𝑠 je vˇsak dˇelitelné pouze ˇc´ısly ±1, ±2𝑟 , ukazuje, ˇze 2𝑠 dˇel´ı souˇcin (2𝑠 −1).𝜎(𝑙). C´ kde 1 ≤ 𝑟 ≤ 𝑠. Jelikoˇz 2𝑠 − 1 je liché, pak je zˇrejmé, ˇze ˇc´ısla 2𝑠 a 2𝑠 − 1 jsou nesoudˇelná, tedy 2𝑠 ∣ 𝜎(𝑙). Mus´ı tedy existovat ˇc´ıslo 𝑞 ≥ 1 takové, ˇze 𝜎(𝑙) = 2𝑠 .𝑞. Dosad´ıme-li do pˇredchoz´ı rovnosti (), obdrˇz´ıme po zkrácen´ı 2𝑠 (2𝑠 − 1).𝑞 = 𝑙

(5.3)

2𝑠 .𝑞 = 𝜎(𝑙) = 𝑙 + 𝑞.

(5.4)

neboli ˇ ıslo 𝑙 > 1 je dˇelitelné 𝑙 a podle () i 𝑞. Z rovnosti () vypl´ C´ yvá, ˇze 𝑙 ∕= 𝑞, rovnost () pak ˇr´ıká, ˇze ˇc´ıslo 𝑙 nem˚ uˇze m´ıt jiné dˇelitele neˇz 𝑙 a 𝑞. Pokud by totiˇz existovalo ˇc´ıslo 𝑑 ≥ 1 a souˇcasnˇe by 𝑑 bylo r˚ uzné od ˇc´ısel 𝑙 a 𝑞, byl by souˇcet dˇelitel˚ u ˇc´ısla 𝑙 roven pˇrinejmenˇs´ım 𝑙 + 𝑞 + 𝑑, coˇz je v rozporu s (). Proto 𝑙 má pouze dva dˇelitele, a to sebe sama a 𝑞 = 1, je to tedy prvoˇc´ıslo. Podle () je 𝑙 = 2𝑠 − 1, dokonalé ˇc´ıslo 𝑛 je pak tvaru 2𝑠−1 .(2𝑠 − 1), 𝑠 > 1 a 2𝑠 − 1 je prvoˇc´ıslo. Dokonalé ˇc´ıslo druhého druhu je takové ˇc´ıslo, které je rovno souˇcinu vˇsech sv´ ych prav´ ych dˇelitel˚ u. Pˇr´ıkladem je ˇc´ıslo 6 (6=1.2.3), které je dokonalé i prvn´ıho druhu. I pro dokonalá ˇc´ısla druhého druhu existuje jednoduch´ y vzorec pro jejich urˇcen´ı, nav´ıc z nˇeho vypl´ yvá, ˇze je jich nekoneˇcnˇe mnoho. ˇ ıslo 𝑛 > 1 je dokonalé ˇc´ıslo druhého druhu právˇe tehdy, kdyˇz je bud’ Vˇ eta 5.2 C´ tˇret´ı mocninou prvoˇc´ısla, nebo je souˇcinem dvou prvoˇc´ısel.

Je-li 𝑛 = 𝑝3 , jsou jeho dˇelitelé 1, 𝑝 a 𝑝2 a jejich souˇcin je roven 𝑛. Je-li 𝑛 = 𝑝1 .𝑝2 , Pak jsou tato prvoˇc´ısla spolu s jedniˇckou jedin´ı dˇelitelé a jejich souˇcin je roven ˇc´ıslu 𝑛. Necht’ naopak je 𝑛 > 1 dokonalé ˇc´ıslo druhého druhu. Pˇredpokládejme, ˇze jeho kanonick´ y rozklad je 𝑛 = 𝑝𝛼1 1 𝑝𝛼2 2 . . . 𝑝𝛼𝑘 𝑘 . Vˇsechny dˇelitele ˇc´ısla 𝑛 seˇrad´ıme podle velikosti, je tedy 1 = 𝑑1 < 𝑑2 . . . < 𝑑𝑠 = 𝑛. Poloˇzme 𝜏 (𝑛) = 𝑠. Je tedy 𝑛 = 𝑑1 .𝑑2 . . . 𝑑𝑠=1 . Vynásob´ıme-li tuto rovnost ˇc´ıslem 𝑛 = 𝑑𝑠 , obdrˇz´ıme 𝑛2 = 𝑑1 .𝑑2 . . . 𝑑𝑠 .

(5.5)

Je-li 𝑑 dˇelitelem ˇc´ısla 𝑛, je jeho dˇelitelem i 𝑛𝑑 . Proto m˚ uˇzeme psát 𝑛2 =

𝑛 𝑛 𝑛 ⋅ ⋅⋅⋅ . 𝑑1 𝑛2 𝑑𝑠

(5.6)

Vynásob´ıme-li pˇredchoz´ı dvˇe rovnosti, máme 𝑛4 = 𝑛𝑠 , z ˇcehoˇz plyne 𝑠 = 4. Jelikoˇz je 𝜏 (𝑛) = (𝛼1 + 1) . . . (𝛼𝑘 + 1), jsou vˇsechny závorky vˇetˇs´ı nebo rovny dvˇema, proto je 𝑘 ≤ 2. Jsou tedy moˇzné pouze dva kanonické rozklady ˇc´ısla 𝑛. Bud’ je 𝑛 = 𝑝𝛼1 1 , 𝛼1 𝛼2 nebo je 𝑛 = 𝑝1 .𝑝2 . V prvn´ım pˇr´ıpadˇe je 𝛼1 = 3, ve druhém 𝛼1 = 𝛼2 = 1.

5.2

Fermatova ˇ c´ısla

V této ˇcásti se opˇet setkáváme se jménem Fermat. Tento pán studoval také ˇc´ısla tvaru 𝑚 𝐹𝑚 = 22 + 1, 𝑚 = 0, 1, 2, . . . . Fermat byl pˇresvˇedˇcen o tom, ˇze jsou to prvoˇc´ısla, pˇres veˇskeré u ´sil´ı se mu to vˇsak nepodaˇrilo ani dokázat, ani vyvrátit, aˇckoliv nástroje k tomu mˇel. Prvn´ıch pˇet tˇechto ˇc´ısel jsou skuteˇcnˇe prvoˇc´ısla, uslyˇs´ıme-li pojem Fermatovo prvoˇc´ıslo, pak se bude jednat právˇe o tato ˇc´ısla. Zdálo by se, ˇze zápis tˇechto ˇc´ısel je zbyteˇcnˇe kommplikovan´ y, následuj´ıc´ı tvrzen´ı vˇsak ukáˇze, ˇze Fermat dobˇre vˇedˇel, proˇc zvolil tento tvar. Vˇ eta 5.3 Necht’ 𝑛 je pˇrirozené ˇc´ıslo. Je-li 𝑛 = 2𝑛 + 1 prvoˇc´ıslo, pak 𝑚 = 2𝑚 pro nˇejaké 𝑚 ∈ {0, 1, 2, . . .}. Necht’ 𝑘 a 𝑙 jsou pˇrirozená ˇc´ısla, pˇriˇcemˇz 𝑙 je liché a souˇcasnˇe je 𝑙 ≥ 3. V tomto pˇr´ıpadˇe plat´ı formule 𝑘 +1)

2𝑘𝑙 + 1 = (2𝑘 + 1)(2𝑘(𝑙−1) − 2𝑘(𝑙−2)+⋅⋅⋅−2

.

ˇ ıslo tvaru 2𝑛 +1 je vˇzdy sloˇzené, je-li exponent dˇeliteln´ C´ y lich´ ym pˇrirozen´ ym ˇc´ıslem vˇetˇs´ım neˇz jedna. Formule pro Fermatova ˇc´ısla tedy zabezpeˇcuje splnˇen´ı nutné podm´ınky pro to, aby tato ˇc´ısla byla prvoˇc´ısla. Nyn´ı si od ˇc´ısel odpoˇcineme a pod´ıváme se do geometrie ˇci chcete-li do planimetrie. Eukleidovské konstrukce kruˇz´ıtkem a prav´ıtkem patˇr´ı mezi krásné partie matematiky. Na jedné stranˇe máme v hlavˇe absolutnˇe pˇresné u ´vahy, tyto vˇsak nelze nikdy v praxi realizovat. Je to vlastnˇe pˇekn´ y pˇr´ıklad platónské filozofie, kdy na pap´ır dáváme jen st´ıny ˇci odlesky ideáln´ı geometrie. Takové oˇrezávátko jeˇstˇe vynalezeno

nebylo a v budoucnu ani nebude, aby j´ım ostrouhaná tuˇzky nar´ ysovala pˇr´ımku, tedy délku bez ˇs´ıˇrky ˇci jiné ideáln´ı geometrické u ´tvary. Z velkého mnoˇzstv´ı geometrick´ ych konstrukc´ı si vybereme sestrojen´ı pravidelného 𝑛-´ uheln´ıka. Nar´ ysovat rovnostrann´ y troj´ uheln´ık, ˇctverec ˇci pravideln´ y ˇsesti´ uheln´ık je procházka r˚ uˇzov´ ym sadem, s menˇs´ımi problémy zvládneme i pravideln´ y pˇeti´ uheln´ık. Aˇckoliv sedmiˇcka je povaˇzována za ˇst’astné ˇc´ıslo, v pˇr´ıpadˇe pravidelného sedmi´ uheln´ıka to neplat´ı. Generace geometr˚ u se o takovou konstrukci pokouˇsely, leˇc marnˇe. Teprve Gaussovi se podaˇrilo tento oˇr´ıˇsek rozlousknout, kdyˇz dokázal následuj´ıc´ı vˇetu: Vˇ eta 5.4 Pravidelný 𝑛-´ uheln´ık lze sestrojit prav´ıtkem a kruˇz´ıtkem právˇe tehdy kdyˇz, 𝑛 = 2𝑖 𝐹𝑚1 𝐹𝑚2 ⋅ ⋅ ⋅ 𝐹𝑚𝑗 , kde 𝑛 ≥ 3, 𝑖 ≥ 0, 𝑗 ≥ 0 a 𝐹𝑚1 , . . . 𝐹𝑚𝑗 jsou navz´ ajem r˚ uzná Fermatova prvoˇc´ısla. D˚ ukaz této vˇety pˇresahuje rámec tohoto textu, sdˇel´ıme jen, ˇze problém geometrick´ y je pˇreveden na algebraick´ y . Napˇ r ´ ıklad pro stˇ r edov´ y u ´ hel pravideln´ e ho pˇ e ti´ u heln´ ıka √ 5−1 = . Nu a kosinus je roven délce pˇrilehlé odvˇesny pravo´ uhlého plat´ı cos 2𝜋 5 4 troj´ uheln´ıka s pˇreponou jedna a tuto u ´seˇcku dovedeme sestrojit kruˇz´ıtkem a prav´ıtkem. Jelikoˇz jediná dosud známá prvoˇc´ısla jsou 3, 5, 17, 257 a 65537, je zˇrejmé, ˇze eukleidovská konstrukce pravidelného sedmi´ uheln´ıka (a samozˇrejmˇe mnoha dalˇs´ıch s lich´ ym poˇctem stran) z principu nen´ı moˇzná. Existuj´ı i dalˇs´ı souvislosti mezi Fermatov´ ymi prvoˇc´ısly a geometri´ı, jelikoˇz pˇresahuj´ı rozsah obvykle prob´ırané látky na základn´ıch ˇci stˇredn´ıch ˇskolách, tak je neuvád´ıme a zájemce odkazujeme napˇr. na publikaci [2]. Po návratu z geometrického v´ yletu uzavˇreme ˇcást vˇenovanou Fermatov´ ym ˇc´ısl˚ um. Je tak trochu záhada, proˇc Fermat nenaˇsel, ˇze 𝐹5 = 641.6700417, to se podaˇrilo aˇz Eulerovi. Na druhou stranu dnes chápeme, ˇze tento geniáln´ı Francouz nenaˇsel v tomto smˇeru ˇza´dn´ y d˚ ukaz. Ten se totiˇz nenaˇsel dodnes, pˇrestoˇze je tˇemto ˇc´ısl˚ um vˇenována souˇcasn´ ymi matematiky velká pozornost. Tato ˇc´ısla jsou totiˇz velká, ˇci pˇresnˇeji jejich dekadick´ y zápis obsahuje mnoho cifer (napˇr. 𝐹18 jich má témˇeˇr 80 000. Byly zapojeny i poˇc´ıtaˇce a vyvinuty metody na faktorizaci velk´ ych ˇc´ısel, zat´ım máme jedinou jistotu, a sice ˇze pro 5 ≥ 𝑚 ≥ 32 se jedná o ˇc´ısla sloˇzená, pˇrestoˇze pro 𝐹20 a 𝐹24 neznáme ˇza´dného netriviáln´ıho dˇelitele. Nepodaˇrilo se zat´ım ani naj´ıt nˇejakou zákonitost, která by v tomto smˇeru nˇeco napovˇedˇela. Teorie ˇc´ısel tedy pˇred nás stav´ı dalˇs´ı v´ yzvu.

5.3

Spˇ r´ atelen´ aˇ c´ısla

Def. 5.1 Dvˇe r˚ uzná pˇrirozená ˇc´ısla 𝑎 a 𝑏 nazýváme spˇrátelená, jestliˇze souˇcet pravých dˇelitel˚ u ˇc´ısla 𝑎 je roven 𝑏 a souˇcasnˇe je souˇcet pravých dˇelitel˚ u ˇc´ısla 𝑏 roven 𝑎. Pˇr´ıkladem budiˇz dvojice 220 a 284, kterou znali jiˇz pythagorejci. Skuteˇcnˇe, prav´ı dˇelitelé prvn´ıho z nich jsou ˇc´ısla 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 a 110; souˇcet ˇ ıslo 284 nemá tolik prav´ tˇechto ˇc´ısel je 284. C´ ych dˇelitel˚ u jsou jen ˇc´ısla 1, 2, 4, 71 a 142 a jejich souˇcet je 220. Do publikace [7], která byla urˇcena pˇredevˇs´ım ˇreˇsitel˚ um matematické olympiády, se vloudila malá chybiˇcka, kdy m´ısto 71 je uvedeno 7. ˇ ısla 𝑎 a 𝑏 jsou spˇrátelená právˇe tehdy, kdyˇz 𝜎(𝑎) = 𝜎(𝑏) = 𝑎 + 𝑏. Vˇ eta 5.5 C´

D˚ ukaz: Je zˇrejmé, ˇze poˇcet prav´ ych dˇelitel˚ u ˇc´ısla 𝑚 je 𝜎(𝑚) − 𝑚. Jsou-li 𝑎 a 𝑏 spˇrátelená je souˇcasnˇe 𝜎(𝑎) − 𝑎 = 𝑏 a 𝜎(𝑏) − 𝑏 = 𝑎. Vypoˇc´ıtáme-li z druhé rovnice 𝑏 a dosad´ıme do prvn´ı, máme 𝜎(𝑎) = 𝜎(𝑏). Je-li naopak 𝜎(𝑎) = 𝜎(𝑏) = 𝑎 + 𝑏, snadno nahlédneme, ˇze 𝜎(𝑎) − 𝑎 = 𝑏 a souˇcasnˇe 𝜎(𝑏) − 𝑏 = 𝑎 a ˇze tedy ˇc´ısla 𝑎 a 𝑏 jsou spˇrátelená. I v pˇr´ıpadˇe spˇrátelen´ ych ˇc´ısel nebylo zat´ım vˇse objasnˇeno. Nev´ıme napˇr´ıklad, zda je jich koneˇcnˇe ˇci nekoneˇcnˇe mnoho. Zat´ım vˇsechny dvojice spˇra´telen´ ych ˇc´ısel maj´ı nejvˇetˇs´ı spoleˇcn´ y dˇelitel vˇetˇs´ı neˇz jedna. Známe vˇsak dvojici lich´ ych spˇrátelen´ ych ˇc´ısel 𝑎 = 33 .5.7.11 a 𝑏 = 3.5.7.139. Hledat spˇrátelená ˇc´ısla m˚ uˇzeme podle návodu, kter´ y udal v 9. stol. arabsk´ y matematik Ben Korrah. Vˇ eta 5.6 Necht’ existuj´ı pro 𝑛 > 1 prvoˇc´ısla tvaru 𝑝 = 3.2𝑛−1 − 1, 𝑞 = 3.2𝑛 − 1 a 𝑟 = 9.22𝑛−1 − 1. Pak ˇc´ısla 𝑘 = 2𝑛 𝑝𝑞 a 𝑙 = 2𝑛 .𝑟 jsou spˇrátelená. D˚ ukaz: Jako prvn´ı krok dokáˇzeme, ˇze souˇcet vˇsech dˇelitel˚ u ˇc´ısla 𝑘 je roven souˇctu dˇelitel˚ u ˇc´ısla 𝑙. Pro souˇcet dˇelitel˚ u 𝜎(𝑘) plat´ı 𝜎(2𝑛 .𝑝.𝑞) = (2𝑛+1 − 1).(𝑝 + 1).(𝑞 + 1) = (2𝑛+1 − 1).9.22𝑛−1 . Pro souˇcet dˇelitel˚ u 𝜎(𝑙) zase plat´ı 𝜎(2𝑛 .𝑟) = (2𝑛+1 − 1)(𝑟 + 1) = (2𝑛+1 − 1)9.22𝑛−1 . Jako druh´ y krok mus´ıme dokázat, ˇze tento souˇcet je roven 𝑘 + 𝑙. 𝑘 + 𝑙 = 2𝑛 𝑝𝑞 + 2𝑛 𝑟 = 2𝑛 (𝑝𝑞 + 𝑟) = 9.22𝑛−1 (2𝑛+1 − 1) = 𝜎(𝑘) = 𝜎)𝑙).

5.4

Z´ avˇ er kapitoly

V závˇerem této kapitoly uvedeme struˇcnˇe nˇekterá dalˇs´ı speciáln´ı prvoˇc´ısla. Pˇripomeˇ nme si nejdˇr´ıve Eukleid˚ uv d˚ ukaz o nekoneˇcném poˇctu prvoˇc´ısel, v nˇemˇz stˇeˇzejn´ı u ´lohu ˇ ıslo 𝑛 m˚ hrál v´ yraz 𝑛 = 𝑝1 𝑝2 . . . 𝑝𝑘 + 1. C´ uˇze, ale také nemus´ı b´ yt prvoˇc´ıslo. Je-li prvoˇc´ıslo, pak je budeme naz´ yvat Eukleidovo prvoˇc´ıslo. Eukleid˚ uv d˚ ukaz m˚ uˇzeme lehce pozmˇenit tak, ˇze m´ısto ˇc´ısla 𝑛 sestav´ıme ˇc´ıslo 𝑚 = 𝑝! + 1, kde 𝑝 je nejvˇetˇs´ı prvoˇc´ıslo, jichˇz pˇredpokládáme koneˇcn´ y poˇcet. Ani v tomto pˇr´ıpadˇe nen´ı ˇc´ıslo 𝑚 dˇelitelné ˇzádn´ ym prvoˇc´ıslem, nebot’ pro kaˇzdé 𝑞 ≤ 𝑝 je zbytek po dˇelen´ı ˇc´ısla 𝑚 ˇc´ıslem 𝑞 vˇzdy roven jedné. To jsme ale zkonstruovali prvoˇc´ıslo vˇetˇs´ı neˇz 𝑝, nebo je 𝑚 dˇelitelné prvoˇc´ıslem vˇetˇs´ı neˇz 𝑝, v kaˇzdém pˇr´ıpadˇe jsme se dostali do sporu s pˇredpokladem. Prvoˇc´ısla tvaru 𝑘! + 1 naz´ yváme faktoriáln´ı. T´ ymˇz názvem se oznaˇcuj´ı i prvoˇc´ısla tvaru 𝑘! − 1. V obou pˇr´ıpadech nevyˇzadujeme, aby 𝑘 bylo prvoˇc´ıslo.

Kapitola 6 Aplikace teorie ˇ c´ısel Pokud se ˇctenáˇr v tomto textu propracoval aˇz k této kapitole, tak si mohl myslet následuj´ıc´ı. Teorie ˇc´ısel je velmi hezkou souˇca´st´ı matematiky, obsahuje ˇradu zaj´ımav´ ych tvrzen´ı, nˇekteré d˚ ukazy jsou velmi elegantn´ı, ˇrada poznatk˚ u se dá vyuˇz´ıt pro zpestˇren´ı v´ yuky, zaj´ımavá jsou i nˇekterá dosud nedokázaná ani nevyvrácená tvrzen´ı, ale jak´ y to má v´ yznam pro praxi? Nejedná se zde jen o sice krásnou, ale jinak neuˇziteˇcnou vˇedu? V této kapitole se pokus´ıme dokázat, ˇze tomu tak nen´ı, ˇze teorie ˇc´ısel je pro praxi velice v´ yznamná a jej´ı d˚ uleˇzitost posledn´ı dobou neustále roste. A zaˇcneme t´ım, s ˇc´ım je spojen kaˇzd´ y obˇcan naˇseho státu od kolébky aˇz po rakev. Ano, zaˇcneme rodn´ ym ˇc´ıslem.

6.1

Rodn´ aˇ c´ısla

ˇ e republiky má jiˇz od narozen´ı pˇridˇelené rodné ˇc´ıslo, které se Kaˇzd´ y obˇcan Cesk´ sestav´ı tak, ˇze prvn´ıch ˇsest ˇc´ısel je dáno datem narozen´ı. Prvn´ı dvojˇc´ısl´ı udává rok, druhé mˇes´ıc a tˇret´ı den narozen´ı. Kv˚ uli rozliˇsen´ı pohlav´ı se druhé dvojˇc´ısl´ı u d´ıvek pˇriˇc´ıtá padesátka. Rodné ˇc´ıslo hoch˚ u, kteˇr´ı se narodili napˇr´ıklad 10. prosince 1996 zaˇc´ıná ˇsestiˇc´ısl´ım 961210, u dˇevˇcat je to 966210. Protoˇze se dennˇe rod´ı v´ıce dˇet´ı, pˇridávaj´ı se za tuto ˇsestici jeˇstˇe dalˇs´ı ˇc´ısla. U nás se od roku 1986 pˇridávaj´ı jeˇstˇe dalˇs´ı ˇctyˇri ˇc´ısla, rodná ˇc´ısla jsou tedy deseticiferná. Posledn´ı ˇctyˇrˇc´ısl´ı se vˇsak nevol´ı náhodnˇe, n´ ybrˇz tak, aby celé rodné ˇc´ıslo bylo dˇelitelné jedenácti. Jak´ y je k tomu d˚ uvod, nestaˇcilo by napˇr´ıklad seˇradit dˇeti narozené v jednom dni napˇr´ıklad podle ˇcasu, kdy pˇriˇsly na svˇet a pak jim pˇriˇradit ˇc´ısla odpov´ıdaj´ıc´ı poˇrad´ı? Abychom mohli zodpovˇedˇet tuto otá∑ zku, dokáˇzeme nejdˇr´ıve kritérium pro dˇelitelnost jedenácti. Necht’ k∈ {0, 1, 2, . . .} a 𝑚 = 𝑘𝑛=0 𝑐𝑛 10𝑛 pro 𝑐𝑛 ∈ {0, 1, 2, . . . , 9}, 𝑐𝑘 ∕= 0, tedy 𝑐𝑘 , . . . , 𝑐0 jsou cifry pˇrirozeného ˇc´ısla 𝑚 v des´ıtkové soustavˇe. Pak ( 𝑘 ) ∑ 11 ∣ 𝑚 ⇔ 11 ∣ (−1)𝑛 𝑐𝑛 . (6.1) 𝑛=0

D˚ ukaz. Podle vzorce pro rozd´ıl dvou 𝑛-t´ ych mocnin plat´ı 10𝑛 − (−1)𝑛 = (10 + 1)[10𝑛−1 + 10𝑛−2 (−1) + ⋅ ⋅ ⋅ + 10(−1)𝑛−2 + (−1)𝑛−1 ], (6.2) kde hranatá závorka obsahuje právˇe 𝑛 sˇc´ıtanc˚ u. Rozd´ıl 10𝑛 −(−1)𝑛 je tedy dˇeliteln´ y 39

11. Pouˇzijeme-li nyn´ı vzorec () na kaˇzd´ y sˇc´ıtanec v () kromˇe posledn´ıho, pak dostaneme 11 ∣ ((−1)𝑘 𝑐𝑘 + (−1)𝑘−1 𝑐𝑘−1 + ⋅ ⋅ ⋅ + 𝑐1 + 𝑐0 ). (6.3) Podobnˇe zjist´ıme, ˇze kdyˇz plat´ı (), je splnˇen i vztah (). Vrat’me se nyn´ı k naˇsemu chlapci, jehoˇz rodné ˇc´ıslo m˚ uˇze b´ yt 9612107032. Dejme tomu, ˇze se pˇri jeho zadáván´ı spleteme v jedné cifˇre. Pak rozd´ıl mezi správn´ ym a 𝑛 ˇspatnˇe zadan´ ym ˇc´ıslem bude ±𝑐 ⋅ 10 , kde 𝑐 ∈ {1, 2, . . . , 9}. Tento rozd´ıl nen´ı nikdy dˇeliteln´ y ˇc´ıslem 11, ale m˚ uˇze b´ yt dˇeliteln´ y sloˇzen´ ymi ˇc´ısly 12, 14, 15 atd. Nap´ıˇseme-li v naˇsem rodném ˇc´ısle m´ısto sedmiˇcky jedniˇcku, je rozd´ıl mezi správn´ ym a ˇspatn´ ym rodn´ ym ˇc´ıslem 6 000. Nalezen´ı vˇsech jeho dvojcifern´ ych dˇelitel˚ u pak pˇrenecháváme ˇctenáˇri. Protoˇze ˇc´ıslo 11 nám umoˇzn ˇuje odhalit chybu, hovoˇr´ıme o jedenáctkovém samodetekuj´ıc´ım kódu. Pˇri pouˇzit´ı jednocifern´ ych prvoˇc´ısel se obecnˇe nedá odhalit chyba pˇri vloˇzen´ı jedné nesprávné cifry. Pouˇzit´ı vˇetˇs´ıch dvojcifern´ ych prvoˇc´ısel nám zase sniˇzuje poˇcet pouˇziteln´ ych rodn´ ych ˇc´ısel. Jedenáctka je tedy pro potˇreby rodného ˇc´ısla opˇ a dvoukoruna je pravideln´ timáln´ı. Závˇerem pˇridáme jeˇstˇe jednu zaj´ımavost. Cesk´ y jedenácti´ uheln´ık. Poloˇz´ıme minci do základn´ı polohy a pak ji stˇr´ıdavˇe otáˇc´ıme po a proti smˇeru hodinov´ ych ruˇciˇcek o tolik vrchol˚ u, kolik je pˇr´ısluˇsná cifra. Po posledn´ım pootoˇcen´ı se mince mus´ı vrátit do p˚ uvodn´ı polohy. Na podobném principu funguj´ı rovnˇeˇz kódy ISBN a ISSN pro knihy ˇci ˇcasopisy, ˇ identifikaˇcn´ı ˇc´ısla organizac´ı (ICO), bankovn´ı u ´ˇcty a pod. V´ıce se lze doˇc´ıst napˇr na [10]. Samodetekuj´ıc´ı kódy dovedou chybu naj´ıt, nikoliv opravit. Z tohoto d˚ uvodu byly vyvinuty kódy samoopravné. Ty nám umoˇzn ˇuj´ı pomoc´ı redundantn´ı (nadbyteˇcné) informace obsaˇzené v kódov´ ych slovech stanovit, ve kterém znaku doˇslo k chybˇe, a opravit ji. Velká budoucnost je vkládána do tzv. dvourozmˇern´ ych kód˚ u s vysokou informaˇcn´ı kapacitou a schopnost´ı detekce a opravy chyb. Tyto kódy se pouˇz´ıvaj´ı mj. v americk´ ych ˇridiˇcsk´ ych pr˚ ukazech ˇci r˚ uzn´ ych identifikaˇcn´ıch kartách. Jejich v´ yhodou je, ˇze se tisknou a pˇrenáˇsej´ı na pap´ıru a ˇze zde nen´ı nutnost vkládat data z klávesnice.

6.2

ˇ Sifrov´ an´ı zpr´ av pomoc´ı velk´ ych prvoˇ c´ısel

Potˇreba utajit p´ısemná sdˇelen´ı je patrnˇe tak stará, jako p´ısmo samo. V pr˚ ubˇehu tis´ıcilet´ı lidé vynalezli ˇradu zp˚ usob˚ u, jak zabránit nepovolané osobˇe, které se dostala do rukou tajná zpráva, aby ji pˇreˇcetla. Jako pˇr´ıklad m˚ uˇzeme uvést ˇsifrován´ı pomoc´ı mˇr´ıˇzky, které pouˇz´ıval Matyáˇs Sandorf a jeho pˇra´telé. Staˇcilo vˇsak, aby se padouch Sarkany dostal k mˇr´ıˇzce a pˇreˇcten´ı zpráv jiˇz pro nˇej nepˇredstavovalo ˇza´dn´ y problém. Jindy k rozluˇstˇen´ı staˇcilo logické uvaˇzován´ı. Geniáln´ı detektiv Sherlock Holmes ˇ takové ˇsifry luˇstil bˇeˇznˇe. Sifru spoˇc´ıvaj´ıc´ı v tom, ˇze kaˇzdé p´ısmeno bylo nahrazeno tanˇc´ıc´ı figurkou, rozluˇstil pomoc´ı frekvence v´ yskytu jednotliv´ ych p´ısmen. Zat´ımco v ˇceské abecedˇe je to p´ısmeno a, v angliˇctinˇe to je litera e. Stejn´ y postup vol´ı i luˇstitelé tzv. ˇc´ıseln´ ych kˇr´ıˇzovek. Jiná metoda spoˇc´ıvá v tom, ˇze se slovo nahrad´ı ˇc´ıslem, urˇcuj´ıc´ım poˇrad´ı slova na jisté stránce knihy, kterou maj´ı obˇe strany k dispozici. V tomto pˇr´ıpadˇe se nedoporuˇcuje, aby kl´ıˇcem byly kniha o v´ıce d´ılech. ˇ Dobr´ y voják Svejk logicky nafasoval pro pány ofic´ıry prvn´ı d´ıl knihy Hˇr´ıchy otc˚ u, jenˇze kl´ıˇcem byl d´ıl druh´ y a jedenáctá marˇskumpanie nemohla tuto ˇsifru pouˇz´ıvat.

Uvedené pˇr´ıpady jsou starˇs´ıho data, kdy si luˇstitel ˇsifry musel vystaˇcit jen se sv´ ym intelektem. V dobˇe poˇc´ıtaˇc˚ u se zdá, ˇze nen´ı v lidsk´ ych silách vymyslet ta’ kovou ˇsifru, která by pˇred ˇreˇsiteli obstálo, nebot co jeden ˇclovˇek vymysl´ı, druh´ y rozluˇst´ı, jak pravil Sherlock Holmes. Avˇsak matematika nen´ı nadarmo povaˇzována za královnu vˇed. Pánové Rivest, Shamir a Adelman objevili v roce 1978 metodu, která se podle poˇcáteˇcn´ıch p´ısmen jejich pˇr´ıjmen´ı naz´ yvá RSA. Oˇc je metoda jednoduˇsˇs´ı, o to je u ´ˇcinnˇejˇs´ı, dokonce nen´ı nutné tajit ˇsifrovac´ı kl´ıˇc, ˇsifrovat m˚ uˇze kaˇzd´ y. Zat´ım vˇsak bez znalosti deˇsifrovac´ıho kl´ıˇce nen´ı a vypadá to, ˇze ani v budoucnu nebude moˇzné tyto ˇsifry rozluˇstit. Jádrem pudla je totiˇz skuteˇcnost, ˇze nen´ı problém vynásobit dvˇe velká ˇc´ısla. Mnohem nesnadnˇejˇs´ı je inverzn´ı proces, tedy rozloˇzit ˇc´ıslo sloˇzené na souˇcin prvoˇcinitel˚ u. Pop´ıˇseme nyn´ı postup pˇri ˇsifrován´ı a deˇsifrován´ı zprávy. Utajované sdˇelen´ı pˇrevedeme nejprve na pˇrirozené ˇc´ıslo 𝑥. K tomu nám mohou poslouˇzit napˇr´ıklad kódy ASCII, ale jejich pouˇzit´ı nen´ı podm´ınkou, existuj´ı i jiné a moˇzná i efektivnˇejˇs´ı zp˚ usoby. Dále budeme pˇredpokládat, ˇze 𝑥 < 𝑛, kde 𝑛 je souˇcin dvou r˚ uzn´ ych prvoˇc´ısel, která nejsou veˇrejnˇe známa a maj´ı v´ıce neˇz 100 cifer. Psavci mus´ı samozˇrejmˇe rozdˇelit zprávu na nˇekolik kratˇs´ıch tak, aby pro kaˇzdou z nich byla splnˇena pˇredchoz´ı nerovnost. Zaˇsifrovanou zprávu oznaˇc´ıme symbolem 𝑥∗. Toto pˇrirozené ˇc´ıslo je jednoznaˇcnˇe dáno nerovnost´ı 𝑥∗ < 𝑛 a kongruenc´ı 𝑥∗ ≡ 𝑥𝑒

(mod 𝑛),

(6.4)

ˇ ısla 𝑒 a 𝑛 jsou kde 𝑒 se naz´ yvá ˇsifrovac´ı exponent (z anglického encryption). C´ veˇrejnˇe známa a k zaˇsifrován´ı staˇc´ı. Odˇsifrován´ı prob´ıhá zcela analogicky. Znovu se definuje ˇc´ıslo (𝑥∗)0 ∈ 𝑁 splˇ nuj´ıc´ı 0 0 𝑑 nerovnost (𝑥∗) < 𝑛 tak, aby (𝑥∗) ≡ (𝑥∗) (mod 𝑛). Deˇsifrovac´ı exponent d (z anglického decryption) vˇsak nen´ı veˇrejnˇe znám. Je vˇsak nutno vyˇreˇsit otázku, jak zvolit exponenty 𝑒 a 𝑑 tak, aby (𝑥∗)0 = 𝑥, tedy aby zaˇsifrovaná zpráva byla po odˇsifrován´ı totoˇzná s p˚ uvodn´ı zprávou 𝑥. Nejdˇr´ıve dokáˇzeme následuj´ıc´ı vˇetu: Necht’ pro pˇrirozené ˇc´ıslo 𝑛 plat´ı (𝑒, 𝜑(𝑛)) = 1.

(6.5)

Potom existuje právˇe jedno pˇrirozené ˇc´ıslo 𝑑 < 𝜑(𝑛) takové, ˇze 𝑒𝑑 ≡ 1

(mod 𝜑(𝑛)).

(6.6)

D˚ ukaz: Pro pˇrirozená ˇc´ısla 𝑘 = 1, . . . , 𝜑(𝑛)−1 definujeme zbytky 𝑧𝑘 ∈ {1, . . . , 𝜑(𝑛)1} pomoc´ı kongruence 𝑒𝑘 ≡ 𝑧𝑘 (mod 𝜑(𝑛)). Pokud se dva zbytky rovnaj´ı, napˇr´ıklad je 𝑧𝑘1 = 𝑧𝑘2 , je správná kongruence 𝑒(𝑘1 − 𝑘2 ) ≡ 0

(mod 𝜑(𝑛)).

Pak podle pˇredpokladu a vˇety 1. 3. (Kˇr´ıˇzek) existuj´ı celá ˇc´ısla 𝑣 a 𝑦 tak, ˇze 𝑒𝑣 + 𝜑(𝑛)𝑦 = 1, tedy je 𝑒(𝑘1 − 𝑘2 )𝑣 + 𝜑(𝑛)(𝑘1 − 𝑘2 )𝑦 = 𝑘1 − 𝑘2 . Odsud plyne 𝑘1 − 𝑘2 ≡ 0 (mod 𝜑(𝑛)), ˇcili 𝑘1 = 𝑘2 . Vˇsechny zbytky 𝑧𝑘 jsou navzájem r˚ uzná ˇc´ısla a proto existuje právˇe jedno 𝑑 odpov´ıdaj´ıc´ı zbytku 1, které splˇ nuje (). Dále dokáˇzeme, ˇze zaˇsifrovaná zpráva 𝑥∗ je po odˇsifrován´ı totoˇzná s p˚ uvodn´ı zprávou 𝑥.

Vˇ eta 6.1 Necht’ plat´ı (𝑒, 𝜑(𝑛)) = 1. Pak (𝑥∗)0 = 𝑥.

(6.7)

D˚ ukaz: Z kongruence () plyne existence takového ˇc´ısla 𝑟, ˇze 𝑒𝑑 = 1 + 𝑟𝜑(𝑛)

(6.8)

Rozliˇsujeme dva pˇr´ıpady: 1. Necht’ plat´ı (𝑥, 𝑛) = 1. Potom lze Euler˚ uv vztah umocnit na 𝑟-tou a vynásobit jej poté 𝑥, ˇc´ımˇz obdrˇz´ıme 𝑥1+𝑟𝜑(𝑛) ≡ 𝑥 (mod 𝑛)

(6.9)

Nyn´ı postupnˇe z (), (), (), a (), plyne, ˇze (𝑥∗)0 ≡ (𝑥∗)𝑑 ≡ 𝑥𝑒𝑑 ≡ 𝑥1+𝑟𝜑(𝑛) ≡ 𝑥 (mod 𝑛).

(6.10)

Vztah () tedy plat´ı, nebot’ obˇe pˇrirozená ˇc´ısla 𝑥 i (𝑥∗)0 jsou menˇs´ı neˇz 𝑛. 2. Necht’ je (𝑥, 𝑛) ∕= 1. Potom je bud’ 𝑥 = 𝑝 nebo 𝑥 = 𝑞. Bez u ´jmy na obecnosti m˚ uˇzeme pˇredpokládat druhou moˇznost. Jelikoˇz (𝑝, 𝑞) = 1 m˚ uˇzeme umocnit Fermat˚ uv vztah umocnit na 𝑟(𝑞 − 1), ˇc´ımˇz obdrˇz´ıme 𝑥(𝑝−1)(𝑞−1) ≡ 1

(mod 𝑝).

Jelikoˇz 𝜑(𝑛) = (𝑝 − 1)(𝑞 − 1), plat´ı 𝑥1+𝑟𝜑(𝑛) ≡ 𝑥 (mod 𝑝𝑥) To je opˇet vztah (), protoˇze 𝑝𝑥 = 𝑝𝑞 = 𝑛. Dál postupujeme jako v bodˇe 1. ˇ Sifrovac´ ı exponent 𝑒 se vol´ı tak, aby 3 ≤ 𝑒 < 𝜑(𝑛) a aby platilo (𝑒, 𝜑)𝑛)) = 1. Nav´ıc je tˇreba zvolit 𝑒 tak, aby 𝑒𝑚 ∕≡ 1 (mod 𝜑(𝑛)) pro malá 𝑚, aby nebylo moˇzno odˇsifrovat zprávu pro 𝑑 = 𝑒−1. Pokud neznáme hodnoty 𝑝 a 𝑞, a pokud je neznáme, je témˇeˇr nemoˇzné stanovit hodnotu deˇsifrovac´ıho exponentu 𝑑. Z vˇety x. x. vˇsak v´ıme, ˇze existuje právˇe jedno pˇrirozené ˇc´ıslo 𝑑 < 𝜑(𝑛) splˇ nuj´ıc´ı kongruenci (). Naskytá se otázka jak stanovit jeho hodnotu, známe-li 𝑝 a 𝑞. Pokud um´ıme rozloˇzit 𝜑(𝑛) na prvoˇc´ısla, pak lze jednoduˇse vypoˇc´ıtat hodnotu 𝜑(𝜑(𝑛)). Z Eulerovy vˇety plyne implikace (𝑒, 𝜑(𝑛)) = 1 ⇒ 𝑒𝜑(𝜑(𝑛)) ≡ 1

(mod 𝜑(𝑛)).

Vynásob´ıme-li pˇredchoz´ı kongruenci 𝑑 a vyuˇzijeme-li (), pak dostaneme explicitn´ı vyjádˇren´ı pro deˇsifrovac´ı exponent 𝑑 < 𝜑(𝑛), 𝑑 ≡ 𝑑𝑒𝜑(𝜑(𝑛)) ≡ 𝑒𝑑𝑒𝜑(𝜑(𝑛))−1 ≡ 𝑒𝜙(𝜑(𝑛))−1

(mod 𝜑(𝑛)).

(6.11)

Pokud 𝜑(𝑛) neum´ıme rozloˇzit na prvoˇc´ısla, lze 𝑑 poˇc´ıtat pˇr´ımo z kongruence (), a to tˇrebas Eukleidov´ ym algoritmem ˇci prostˇe zvol´ıme jiné 𝑝 ˇci 𝑞.

6.3

Kouzla s ˇ c´ısly

Kdyˇz jsem byl jeˇstˇe mal´ y hoˇs´ık, bylo vˇzdy obrovskou událost´ı, kdyˇz na dˇedinu pˇrijel kouzeln´ık. Vˇsichni jsme byli nadˇseni z jeho trik˚ u, at’ jiˇz to byla kouzla s kartami, mizen´ı ˇci naopak neˇcekané objevován´ı se vˇec´ı a jiné a jiné zázraky, které nás fascinovaly. Kouzeln´ık obvykle v rámci pˇredstaven´ı jeden trik prozradil, potom vˇsichni ˇzasli, jak je to vlastnˇe jednoduché. Takov´ ym iluzionistou vˇsak m˚ uˇze b´ yt kaˇzd´ y a nebude k tomu ani potˇrebovat hbité prsty, staˇc´ı jen vyuˇz´ıt nˇekteré zaj´ımavé vlastnosti ˇc´ısel. Ostatnˇe v pˇredchoz´ım textu jsme se mohli pˇresvˇedˇcit, ˇze ˇc´ısla pˇred námi ukr´ yvaj´ı spoustu tajemstv´ı a je otázkou, zda se nám je v˚ ubec podaˇr´ı objasnit. Závˇerem si proto uvedeme nˇekteré ˇcáry s ˇc´ısly. Dalˇs´ı pak m˚ uˇze ˇctenáˇr nalézt v publikac´ıch zamˇeˇren´ ych na rekreaˇcn´ı matematiku a pokud bude m´ıt i dost ˇcasu na listován´ı star´ ymi novinami, tak i v zábavn´ ych okenkách nedˇeln´ıch ˇci pozdˇeji sobotn´ıch pˇr´ıloh den´ık˚ u. Kouzlo prvn´ı: Zvolte si libovolné trojciferné ˇc´ıslo tak, aby se prvn´ı a posledn´ı ˇc´ıslice liˇsily alespoˇ n o dvˇe. Utvoˇrte ˇc´ıslo, jehoˇz cifry jsou v opaˇcném poˇrad´ı a od vˇetˇs´ıho ˇc´ısla odeˇctˇete menˇs´ı. Ve v´ ysledku opˇet zamˇen´ıme poˇrad´ı ˇc´ıslic a tato dvˇe ˇc´ısla seˇcteme. Dejme tomu, ˇze si vybereme ˇc´ıslo 115. Pak je tˇreba spoˇc´ıtat 511115=396. Dále mus´ıme seˇc´ıst ˇc´ısla a 396 a 693. V naˇsem pˇr´ıpadˇe obdrˇz´ıme 1089. My narozd´ıl od kouzeln´ık˚ u vysvˇetl´ıme kaˇzd´ y trik, budeme proto pˇredpokládat, ˇze zvol´ıme ˇc´ıslo 100𝑎+10𝑏+𝑐, pˇriˇcemˇz 𝑎 ≥ 𝑐+2. Pak 100𝑎+10𝑏+𝑐−100𝑐−10𝑏−𝑎 = 100(𝑎 − 𝑐) − 𝑎 + 𝑐 = 100(𝑎 − 𝑐 − 1) + 90 + (10 − 𝑎 + 𝑐). Pˇriˇcteme-li k tomuto v´ ysledku ˇc´ıslo 100(10 − 𝑎 + 𝑐) + 90 + (𝑎 − 𝑐 − 1), obdrˇz´ıme 900+180+9=1089. Tento v´ ysledek nezávis´ı na volbˇe cifer a v´ ysledek 1089 bude pˇri libovolné volbˇe p˚ uvodn´ıho ˇc´ısla. Kouzlo druh´ e: Zvolme dvˇe libovolná ˇc´ısla. Utvoˇrme posloupnost podobn´ ym zp˚ usobem jak to udˇelal Fibonacci, tedy kaˇzd´ y dalˇs´ı ˇclen je souˇctem dvou pˇredchoz´ıch. Seˇctˇeme prvn´ıch deset ˇclen˚ u této posloupnosti a vydˇelme ho ˇclenem sedm´ ym. Napˇr´ıklad si zvol´ıme 3 a 7. Prvn´ıch deset ˇclen˚ u posloupnosti bude 3, 7, 10, 17, 27, 44, 71, 115, 186, 301 a jejich souˇcet pak 781. Vydˇel´ıme-li toto ˇc´ıslo 71, obdrˇz´ıme 11. Toto ˇc´ıslo mus´ı vyj´ıt vˇzdy. Je-li totiˇz 𝑓1 = 𝑚 a 𝑓2 = 𝑛, je 𝑓7 = 5𝑚 + 8𝑛 a ∑ 10 z´ıt i komplexn´ı ˇc´ısla, je vˇsak tˇreba 𝑖=1 𝑓𝑖 = 55𝑚 + 88𝑛 = 11𝑓7 . Ke kouzlu lze pouˇ dát pozor, aby 𝑓7 ∕= 0. Kouzlo tˇ ret´ı: Vezmˇeme libovolné pˇrirozené ˇc´ıslo, které je dˇelitelné tˇremi. Cifry umocn´ıme na tˇret´ı a seˇcteme, ˇc´ımˇz obdrˇz´ıme nové pˇrirozené ˇc´ıslo. Tento postup opakujeme, avˇsak zjist´ıme, ˇze aˇz dospˇejeme k ˇc´ıslu 153, se cel´ y proces zacykl´ı. Uˇcenˇe ˇreˇceno budeme-li opakovanˇe sˇc´ıtat tˇret´ı mocniny cifer pˇrirozeného ˇc´ısla dˇelitelného tˇremi, vˇzdy dospˇejeme k ˇc´ıslu 153. Mysleme si ˇc´ıslo 1422. Pak plat´ı 13 +43 +23 +23 = 81 7→ 83 + 13 = 513 7→ 53 + 13 + 33 = 153. Oznaˇc´ıme-li 𝑛 = 𝑐𝑘 10𝑘 + ⋅ ⋅ ⋅ + 𝑐1 10 + 𝑐0 a 𝑚 = 𝑐3𝑘 + ⋅ ⋅ ⋅ + 𝑐31 + 𝑐30 , pak z pˇredpokladu 3∣𝑛 plyne 3∣𝑚. Z kritéria pro dˇelitelnost ∑𝑘 3 trojkou plyne, ˇze 𝑛 ≡ e Fermatovy vˇety je 𝑐3𝑖 ≡ 𝑐𝑖 𝑖=0 𝑐𝑖 (mod 3). Podle Mal´ (mod 3). Je tedy 𝑘 𝑘 ∑ ∑ 3 𝑐𝑖 ≡ 𝑐𝑖 ≡ 𝑛 (mod 3). 𝑚= 𝑖=0

𝑖=0

Dále je 𝑛=

𝑘 ∑ 𝑖=0

𝑖

𝑘

𝑘

3

𝑐𝑖 10 ≥ 𝑐𝑘 10 ≥ 10 > (𝑘 + 1)9 ≥

𝑘 ∑ 𝑖=0

𝑐3𝑖 = 𝑚.

Je-li tedy 𝑛 ≥ 104 , je souˇcet tˇret´ıch mocnin cifer vˇzdy menˇs´ı neˇz p˚ uvodn´ı ˇc´ıslo. Zb´ yvá tedy provˇeˇrit, jak se ˇretˇezec bude chovat po pˇrekroˇcen´ı této hranice. Vyuˇzit´ım v´ ypoˇcetn´ı techniky lze ovˇeˇrit, ˇze je zde koneˇcn´ y poˇcet moˇznost´ı aˇze vˇsechny vedou k ˇc´ıslu 153. Závˇerem dodejme, ˇze existuj´ı i jiná ˇc´ısla, která se rovnaj´ı souˇctu tˇret´ıch mocnin pˇrirozen´ ych ˇc´ısel. Kromˇe singulárn´ıho pˇr´ıpadu jedniˇcky jsou to i ˇc´ısla 370, 371 a 407, ˇzádné z nich vˇsak nen´ı dˇelitelné tˇremi. Kouzlo ˇ ctvrt´ e: Zvolme libovolné trojciferné ˇc´ıslo, jehoˇz cifry nejsou vˇsechny ’ stejné. Seˇrad me cifry podle velikosti v obou smˇerech a odeˇctˇeme tato dvˇe ˇc´ısla. Po koneˇcném poˇctu krok˚ u dojdeme k ˇc´ı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ˇel dvˇe cifry, je nutno ho doplni zepˇredu nulou. Stejná vlastnost plat´ı i pro ˇctyˇrciferná ˇc´ısla, kdy se dostaneme k ˇc´ıslu 6174. Toto ˇc´ıslo se na poˇcest objevitele naz´ yvá Kaprekarova konstanta. Vzhledem ke koneˇcnému poˇctu ˇc´ısel lze turo zaj´ımavost ovˇeˇrit na poˇc´ıtaˇci. Závˇerem této kapitoly zabrous´ıme do turbodidaktiky. Euler odvodil vzorec 𝑒i𝜋 + 1 = 0. V tomto vzorci se vyskytuj´ı vˇsechny aritmetické operace (sˇc´ıtán´ı, násoben´ı, mocnˇen´ı) a téˇz nejd˚ uleˇzitˇejˇs´ı matematické konstanty (0, 1, i, 𝑒, 𝜋 právˇe jednou a je proto matematick´ ymi estéty povaˇzován za nejkrásnˇejˇs´ı. (Pokud bychom pouˇzili synonymum formule, mohli bychom psát Miss formule.) Proved’me turbodidaktické kouzlo a upravujme tento vztah. 𝑒i𝜋 = −1 = (−1)3 = (𝑒i𝜋 )3 = 𝑒3i𝜋 . Jelikoˇz levá strana rovná se pravé, m˚ uˇzeme odlogaritmovat a máme i𝜋=3i𝜋 ˇci 1=3. Znalec funkce komplexn´ı promˇenné rozd´ıl mezi matematikou a turbodidaktikou odhal´ı hned; pro jistotu vˇsak dodáváme, pro komplexn´ı promˇennou nen´ı logaritmus jednoznaˇcná funkce, takˇze logaritmován´ı nebylo korektn´ı.

6.4

´ Ulohy na procviˇ cen´ı

Abychom uˇcinili poˇzadavk˚ um projektu zadost, pˇrece jen uvedeme nˇekolik u ´loh, na kter´ ych si ˇctenáˇr procviˇc´ı znalosti z pˇredchoz´ıho textu. 1. Myslete si libovolné ˇc´ıslo od ˇsesti do ˇsedesáti. Toto ˇc´ıslo postupnˇe dˇelte tˇremi, ˇctyˇrmi a pˇeti a nahlaste zbytky. Znalec ˇc´ısel podle zbytk˚ u urˇc´ı p˚ uvodn´ı ˇc´ıslo. Jak je to moˇzné? 2. Vynásobte sv˚ uj vˇek deseti od tohoto ˇc´ısla odeˇctˇete dev´ıtinásobek libovolného ˇ jednociferného ˇc´ısla. Reknˇ ete v´ ysledek a já uhádnu, jak dlouho jiˇz putujete po tomto svˇetˇe. Jak je to moˇzné? 3. A jeˇstˇe jednu na vˇek. Své mlád´ı (stáˇr´ı) vynásobte dvˇema, pˇriˇctˇete pˇet, souˇcet opˇet vynásobte pˇeti a ˇreknˇete v´ ysledek. I z tohoto ˇc´ısla poznám, kolik let jste se doˇzil. Jak je to moˇzné? 4. Nedosti vˇsak na tom, um´ıme uhodnout i pˇresné datum narozen´ı, a to následuj´ıc´ım zp˚ usobem. Poˇradové ˇc´ıslo mˇes´ıce vˇeku vynásob´ıme stem. K v´ ysledku pˇriˇcteme ˇc´ıslo znaˇc´ıc´ı den a v´ ysledek vynásob´ıme dvˇema. K v´ ysledku pˇridáme osm. Dále násob´ıme pˇeti a pˇridáme ˇctyˇri. Tento v´ ysledek vynásob´ıme des´ıti a

pˇridáme ˇctyˇri. Posledn´ı operac´ı je pˇriˇcten´ı vˇeku v roc´ıch. Odeˇcteme 444 a v´ ysledek rozdˇel´ıme na skupiny po dvou cifrách od pravé strany. Kv˚ uli ’ vyváˇzenosti to ted vezmeme zleva; prvn´ı dvojice urˇcuje mˇes´ıc, druhá den a tˇret´ı vˇek zkoumaného ˇclovˇeka. 5. Také um´ıme uhodnout dané ˇc´ıslo. Od myˇsleného ˇc´ısla odeˇcteme jedniˇcku, zbytek násob´ıme dvˇema a pˇriˇcteme myˇslené ˇc´ıslo. Z tohoto v´ ysledku uhodneme myˇslené ˇc´ıslo tak, ˇze pˇriˇcteme dvˇe a vydˇel´ıme tˇremi. V´ ysledky aplikace teorie ˇc´ısel. Je-li myˇslené ˇc´ıslo 𝑥, pak máme 𝑥 = 3𝑎 + 𝑟1 , 𝑥 = 4𝑏 + 𝑟2 , 𝑥 = 5𝑐 + 𝑟3 . Vyjádˇr´ıme jednotlivé zbytky a spoˇc´ıtáme v´ yraz 𝑆 = 40𝑟1 + 45𝑟2 + 36𝑟3 = 121𝑥 − 120𝑎 − 180𝑏 − 180𝑐. V´ yraz 𝑆 = 120𝑘 + 𝑥, proto staˇc´ı podˇelit 𝑆 120 a zbytek je roven myˇslenému ˇc´ıslu. Oznaˇcme vˇek 𝑥 a myˇslené ˇc´ıslo 𝑘. Podle postupu jsme obdrˇzeli 10𝑥 − 9𝑘 = ˇ ıslo 𝑘 je na m´ıstˇe jednotek, zbytek tvoˇr´ı rozd´ıl 𝑥 − 𝑘. Z uvedeného 10(𝑥 − 𝑘) + 𝑘. C´ je zˇrejmé, ˇze váˇs oponent mus´ı b´ yt starˇs´ı dev´ıti let. ´ Neznám´ y vˇek oznaˇc´ıme opˇet 𝑥. Upravy jsou tyto: (2𝑥 + 5).5 = 10𝑥 + 25 = 10(𝑥+2)+5. Dál postupujeme jako v pˇredchoz´ım pˇr´ıpadˇe, na rozd´ıl od pˇredchoz´ıho pˇr´ıpadu to funguje i pro mimina. Poˇc´ıtáme vlastnˇe {[(100𝑚 + 𝑑).2 + 8].5 + 4}.10 + 4 + 𝑟 − 444=10000𝑚 + 100𝑑 + 𝑟. Poˇc´ıtáme takto: 𝑥 = 1; 2(𝑥 − 1); 2(𝑥 − 1) + 𝑥 = 3𝑥 − 2; 3𝑥 − 2 + 2.

Literatura [1] Dobrovoln´ y B.: Nové matematické rekreace. SNTL Praha 1967 ˇ [2] Kˇr´ıˇzek M., Somer L., Solcov´ a A.: Kouzlo ˇc´ısel (Od velk´ ych objev˚ u k aplikac´ım. Academia Praha 2011 [3] Lepka K.: Historie Fermatov´ ych kvocient˚ u (Fermat-Lerch). Dˇejiny matematiky sv. 14, Prometheus Praha 2000 ˇ Kriˇzalkoviˇc K., Leˇcko I.: Zábavná matematika. Státn´ı pedago[4] Novovesk´ y S., gické nakladatelstv´ı Praha 1974 [5] Sierpi´ nski W.: Co v´ıme a nev´ıme o prvoˇc´ıslech. Státn´ı pedagogické nakladatelstv´ı Praha 1966 [6] Singh S.: Velká Fermatova vˇeta. Academia Praha 2000 ˇ at T.: Dokonalé a spriatelené ˇc´ısla. Skola ˇ [7] Sal´ mlad´ ych matematik˚ u. Mladá fronta Praha 1969 ˇ [8] Vinogradov, I. M.: Základy theorie ˇc´ısel. Nakladatelstv´ı Ceskoslovensk´ e akademie vˇed. Praha 1953 ˇ Teória ˇc´ısel. Vydavatelstvo technickej a ekonomickej literat´ [9] Znám, S.: ury Alfa Bratislava 1977. [10] http://www.kodys.cz

47

Úvodní slovo autora. Karel Lepka

Recommend Documents