O aritmetice zbytků modulo p
Dušan Polanský
Doufám, že vás nadpis nevyděsil, proto hned slibuji, že to nebude nic strašného. Možná, že jste četli od Roberta Fulghuma sbírku postřehů: Všechno co opravdu potřebuji znát, jsem se naučil znát v mateřské školce (např. Odeon, 1993), já zase tvrdím, že se znalostmi aparátu matematiky ze základní školy se dá bohatě vystačit nejen v praktickém životě, ale někdy dokonce i v čistě matematické teorii. Abych o tom moc nepovídal, naservírujeme si malou ukázku teoretických úvah, přičemž si vystačíme s učivem ze základky. Jenom si připomeňme, že na základce v matematice se učí aritmetika, geometrie a algebra. Dnes si vystačíme s aritmetikou a algebrou.
Vysvětlíme si na první pohled trochu podivnou aritmetiku, tzv. p-aritmetiku, někdy se také mluví o aritmetice zbytkových tříd. Písmeno p bude v dalším znamenat libovolné prvočíslo, např.: 3, 5, 7, 11. O co v p-aritmetice, neboli učeně nazývané aritmetice zbytků podle modulu p, jde? Představme si, že místo desítkové soustavy, v níž používáme číslice 0, 1, 2, 3, 4, 5, 6, 7, 8 a 9, použijeme v prvním kroku např. sedmičkovou soustavu (7 je prvočíslo), tedy pro zápis čísla budeme smět použít jenom číslice 0, 1, 2, 3, 4, 5 a 6, např. 235 je korektní zápis čísla 7-aritmetice. Ovšem v druhém kroku si to ještě zkomplikujeme tím, že pokud číslo bude větší než 7, tak je vydělíme sedmi a coby výsledek budeme uvažovat jenom zbytek po tomto dělení. Malý příklad, nějakým výpočtem v 7-aritmetice jsme dopracovali k číslu 23, ovšem bacha, 23 není náš výsledek, ten dostaneme až po vydělení čísla 23 číslem 7, což je 3 a zbytek po dělení je 2, a právě 2 je výsledek v 7-aritmetice! Pokud nám nějakým výpočtem vyjde číslo 5, tak se nic neděje, 5 je definitivní výsledek, protože 5 je menší než 7. To je celá pointa p-aritmetik, kde p je libovolné prvočíslo. Když jste to pochopili, tak vše ostatní bude pro vás již malina.
Určitě si všichni vzpomínáme, jak jsme se pracně učili na základce malou násobilku, tedy vzájemné násobení čísel od 1 do 9, násobení 10 bylo již lehké. Podobná násobilka je docela pracná je i v p-aritmetikách. Teď si ukážeme, jak by takové násobení např. čtyřmi vypadalo v 7-aritmetice. Výsledek je na obrázku pod bodem 1. K výpočtů jsou přikresleny tři orientované grafy. Jak jsme se k ním dopracovali? Jednoduše: čísla 0 až 6 (jiné výsledky v 7-aritmetice nejsou možné!) jsou znázorněny tečkami a orientovaná šipka směřuje do čísla, které dostaneme při násobení číslem 4. Příklad: při násobení 5 . 4 je výsledek 20, ten ovšem není v 7-aritmetice přípustný, ale po vydělení 7 dostaneme zbytek 6, což již je v pořádku, a tedy šipka z čísla 5 musí směřovat do čísla 6, ovšem to platí jenom v 7-aritmetice! V p-aritmetice lze poměrně jednoduše dokázat, že náš případ není náhoda, pokud neuvažujeme cyklus s 0, zbývající cykly budou mít stejnou délku. V našem příkladu nám vyšli dva stejně dlouhé cykly o délce 3. Můžete si vyzkoušet v 7-aritmetice např. násobilku 6 a uvidíte, že nenulové cykly budou mít stejnou délku.
Pochopitelně vás napadne se zeptat, jak je to v aritmetice modulo p s klasickými aritmetickými operacemi, tedy sčítáním, násobením a dělením. Mocnina je opakované násobení, odmocniny si odpustíme. Ukážeme si to na příkladech.
Sčítání funguje zcela přirozeně, kupříkladu 47 + 23 = 69 Pak 69 : 7 = 9 (zb. 6), výsledek je 6. Ovšem můžeme na výpočet jít i takto 47 : 7 = 6 (zb. 5) 22 : 7 = 3 (zb. 1). Sečteme zbytky 5 + 1 = 6. Kdyby součet zbytků vyšel větší než 7, pak výsledek vydělíme 7 a nový zbytek je výsledek.
S násobením je to velice podobné, kupříkladu 9 . 8 = 72 pak 72 : 7 = 10 (zb. 2). Výsledek 2. Zkusme to i jinak: 9 : 7 = 1 (zb. 2), 8 : 7 = 1 (zb. 1). Vynásobíme zbytky 2 . 1 = 2. Kdyby násobení zbytků vyšlo větší než 7, pak výsledek vydělíme 7 a nový zbytek je výsledek.
S dělením je to o něco složitější. Kupříkladu máme vydělit 16 : 12. Musíme si uvědomit, že číslo 16 po dělení 7 dává zbytek 2. Označme třídu všech takových čísel t2. Podobně 12 po dělení 7, dává zbytek 5, označme třídu všech takových čísel t5. Teď dělení vypadá v třídách takto: t2 : t5, což se dá přepsat na násobení jako t2 . t5-1. Ovšem platí, že t5 . t5-1 = t1, podobně jako 3/3 = 3 . 3-1 = 1. Tedy za t5-1 musíme najít takovou třídu, která dá při vynásobení t5 třídu t1. Ale to není problém, takovou třídou je t3, opravdu t5 . t3 = t1. Takže 16 : 12 = t2 . t3 = t6. Řešením budou čísla, které po dělením 7 dávají zbytek 6, tedy např. čísla 6, 13, 20.
V devátém ročníku základky dojde i na algebru, tedy místo konkrétních čísel se žáci učí pracovat s obecným vyjádřením čísel pomocí písmen. Kupříkladu učí se řešit rovnici 2 . x = 24, kde x je neznámé číslo vyjádřené písmenem x. Nebo se učí, že když platí a . b = 0, tak jedno z čísel a, nebo b musí být nula. Tohle poslední tvrzení platí i v p-aritmetikách. Intuitivně si to můžete vyzkoušet v 7-aritmetice. Zkuste dosazovat do součinu a.b za a a b všechny možné kombinace čísel od 1 do 6, ale k nule se nedopracujete. Kupříkladu vynásobíme 3 . 6 = 18, vydělím 18 : 7 = 2 (zb. 4), výsledek je 4, ale ne nula; a tak to můžete zkoušet se všemi kombinacemi, ale k 0 se nedopracujete, pouze v případě, že jedno číslo bude 0.
Jak je to s řešením rovnic v naší 7-aritmetice by mělo být zřejmé z obrázku v bodě 2. U první rovnice najdeme řešení bez problémů, jelikož pracujeme s čísly menšími než 7, vypadá to, že řešení dopadne jako v desítkové soustavě. Vyšlo to. Ovšem u druhé rovnice tomu tak již není. Sice opět pracujeme s čísly menšími než 7, jenomže řešení x = 2/5 není coločíselné. Správné řešení je x = 6, i když v desítkově soustavě jistě neplatí 2 . 6 = 5, což ale v 7-aritmetice pravda je!
Zkusme druhou rovnici 2 . x = 5 vyřešit s využitím operace dělení, jak byla výše vysvětlena. Vidíme, že x = t2/t5, coz můžeme zapsat jako x = t2.t5-1. Teď musíme za t5-1 najít takovou třídu, která po vynásobení t5 dá třídu t1. Výše jsme si ukázali, že je to třída t3.. Naše řešení tedy bude x = t2.t3 = t6. Řešením budou čísla, které po dělením 7 dávají zbytek 6, tedy např. čísla 6, 13, 20.
V bodě 3 je uvedena rovnost, která se hodně používá při důkazu složitějších vět v teorii čísel.
V teorii čísel, algebře, při šifrování, kódování ale i v dalších vědních oborech nachází uplatnění další dvě důležité věty; také je lze odvodit poměrně snadno, ale z hlediska cílů tohoto textu, důkazy vypouštíme.
V bodě 4 je uvedena malá věta Fermatova (Pierre Fermat 1601–1665).
V bodě 5 je uvedena věta Wilsonova (John Wilson 1741–1793). V této větě ! má význam faktoriálu, který je definován pro přirozená čísla takto: n! = 1.2.3. … .(n-1).n, kupříkladu 5! = 1.2.3.4.5 = 120.
Možná někoho napadne: Nedala by se modulární aritmetika (neboli aritmetika zbytkových tříd) využít i v případě, že p by nebylo prvočíslo? Dalo, kupříkladu pro dodatečnou kontrolu správnosti násobení. K tomu se využívá aritmetiky podle modulo 9 (9 není prvočíslo). Jak to funguje si ukážeme na jednoduchém příkladu. Vynásobme 56 . 95, výsledek je 5320. Teď zjistíme zbytky po dělení 9: 56 : 9 = 6 (zb. 2), 95 : 9 = 10 (zb. 5), 5320 : 9 = 591 (zb. 1). A teď uděláme kontrolu přes zbytky: 2 . 5 = 10 a 10 : 9 = 1 (zb. 1). Kontrola pomocí zbytků dopadla na výbornou. A proč právě kontrola pomocí aritmetiky modulo 9? Ze základky si možná pamatujete, že číslo je dělitelné 9, pokud jeho ciferný součet je dělitelný 9. V našem příkladu u násobence je ciferný součet 5 + 6 = 11, a po dělení 9 je zbytek 2. Podobně postupujeme u násobitele a výsledku. Takže při kontrole přes 9 se lehce vyhneme pracnému dělení velikých čísel devítkou.
Pokud by vás problematika aritmetik modulo p zajímala hlouběji, tak jsem v doporučené literatuře uvedl dva tituly z mé knihovny, které tuhle látku obsahují. I jakákoliv jiná publikace např. z teorie čísel, moderní algebry či kódování tuhle látku určitě podrobně probírá.
A co závěrem. Snad jsem vás alespoň trochu přesvědčil, že se znalostmi matematiky ze základní školy si nejednou vystačíme i v poměrně sofistikovaném světě teorie čísel. Takže nemyslet si, že úspěšné absolvování základní školy je málo. Kdepak, často je to docela moc.
Doporučená literatura:
Dynkin, J.B., Uspenskij, V.A.: Matematické besedy, SNTL, 1955, Praha.
Rychlík, K.: Úvod do elementární číselné teorie, Přírodovědecké nakladatelství, 1950, Praha.
V Brně 12. listopadu 2023.