Něco málo o kongruencích
Dušan Polanský
Čísla se dělí v matematice všelijak, ale jak, raději nebudu připomínat, protože máme prázdniny a na učivo ze školy je teď lépe nemyslet. Dnes si budeme povídat o takovém rozdělení celých čísel, které se na základní, ani střední a občas ani na vysoké škole nebere, čímž by vás to mohlo zaujmout, jelikož co není povinné, to člověka spíš baví než to, co musí. Alespoň u mě to tak funguje.
Přístup k novému rozdělení si vysvětlíme na číslu 3 a pro větší srozumitelnost budeme uvažovat pouze celá kladná čísla. Nejprve si napišme všechna čísla dělitelná 3, tedy taková čísla, která při dělení čísla číslem 3 dávají zbytek 0. Jsou to čísla 0, 3, 6, 9, 12 atd. Teď vemem všechna čísla, která dávají při dělení číslem 3 zbytek 1, což jsou čísla: 1, 4, 7, 10, 13. Teď vemem čísla, které dají zbytek 2, což jsou čísla: 2, 5, 8, 11, 14 atd. Matematici by nám řekli, že jsme celá kladná čísla rozdělili podle modulo 3 do třech tříd. Pokud bychom z každé takto vytvořené třídy, vzali jedno číslo jako reprezentanta, v našem případě ať jsou to ta nejmenší čísla z každé třídy, tedy 0, 1, 2, tak by nám zase řekli, že tyhle čísla tvoří rovněž úplný systém zbytků modulo 3, což je jistě pravda, jelikož jiný zbytek při dělení číslem 3 v oboru celých kladných čísel není možný. Teď se pokusíme vyřešit příklad, kde tyhle zdánlivě jednoduché úvahy proměníme v jakž takž smysluplný výpočet.
Představme si, že potkáme selku, která ve dvou velikých koších nese na trh vajíčka. Jsme zvědavci, a tak se jí zeptáme, kolik že těch vajíček vlastně v těch dvou koších má. Selka je chytrá a chce nás potrápit a praví: pokud bych vajíčka dávala do košů po 2, zůstane mi nakonec 1 vajíčko, to stejné platí pro čísla 3, 4, 5, 6, ale pokud vajíčka budu dávat do koše po 7, nezůstane mi nakonec žádné vajíčko. Takže, vy chytráci, kolik jich v koších mám?
Hned zde vidíme určitou analogii s naším úvodním povídáním o rozdělení celých čísel modulo 3, pouze zde je číslo 3 nahrazeno číslem 7 a neuvažovali jsme dávání do košíku po 1 vajíčku, tak z logiky věci jí žádné nemůže zůstat. Také ze zadání je zřejmé, že výsledný počet vajíček musí být dělitelný číslem 7. Jenomže takový počet čísel je obecně nekonečně mnoho, my se budeme snažit najít takové rozumné číslo, kdy by ještě selka vajíčka ve dvou koších zvládla unést, ovšem při důležitém omezení, že celkový počet vajíček musí dávat při dělení čísly 2, 3, 4, 5 a 6 zbytek 1. Z toho plyne, že nejprve musíme najít nějaké číslo, které je dělitelné čísly 2, 3, 4, 5 a 6, pak budeme tvořit násobky tohoto čísla nějakým přirozeným číslem a pokaždé přidáme k takto vzniklému číslu 1 a budeme testovat, zda je číslo dělitelné 7. Uvidíme, jaké číslo nám vyjde, podle něho pak posoudíme, zda selka je schopna tolik vajíček unést, pokud by to číslo bylo malé, vajíčka by šlo naskládat např. do malého koše, budeme hledat další číslo vyhovující našemu zadání.
Náš první úkol tedy zní: najít číslo dělitelné čísly 2, 3, 4, 5 a 6. Ze školy víme, že takové číslo je jejich nejmenší společný násobek, v našem případě prvním takovým číslem je číslo 60. Teď stojí před námi vyřešit rovnici 60k + 1 = 7p, přičemž k a p jsou přirozená čísla. Je to jedna rovnice o dvou neznámých, což vždy přináší problémy v jednoznačnosti řešení, ale my víme, že vajíček musí být rozumný počet, proto rovnici budeme řešit metodou pokus omyl. Postupně budeme za k dosazovat přirozená čísla 1, 2, 3, 4, 5, 6 atd., pak připočteme 1 a vzniklé číslo vydělíme číslem 7. Pokud takové číslo nebude beze zbytku dělitelné 7, zvolíme další k.
Dvě řešení naší úlohy vidíte na obrázku č. 1, přičemž číslo obrázku zjistíte po najetí kurzoru myši na obrázek. První číslo, které vyhovuje zadání je číslo 301, další až 721. Když si představíme dva veliké koše, tak zůstaneme u počtu vajíček 301. Tohle číslo splňuje veškerá omezení naší úlohy.
Matematici na základě podobných úvah vybudovali již dávno celou teorii, kterou hodně využívali a využívají např. v teorii čísel nebo v teorii kolem řešení algebraických rovnic, což jsou takové rovnice, jejichž koeficienty jsou racionální čísla. My si o teorii, kterou jsme již nakousli, to nejzákladnější povíme, důkazy si ale odpustíme, jelikož pak by rozsah článku byl takový, že by většinu zájemců výklad unavil, a nemluvě o tom, že máme prázdniny.
Základem všeho povídání bude tahle definice, tu si proto pořádně zafixujeme: Nechť m > 1 je celé číslo. Budeme říkat, že celá čísla a, b jsou kongruentní podle modulu m, jestli existuje takové celé číslo k, že b = a + km. Jestli takové číslo k existuje, zapíšeme to tímto způsobem: a ≡ b (mod m). Vidíme, že dvě čísla a, b jsou kongruentní podle modulu m, když dají po dělení číslem m stejný celočíselný zbytek. V našem úvodním příkladu jsou čísla 1, 4, 7, 10, 13 navzájem kongruentní podle modulu 3, jelikož po dělení číslem 3 dají stejný zbytek, a to 1. Lze snadno dokázat, že pokud a ≡ b (mod m), pak rovněž b ≡ a (mod m).
Praktické příklady na zápis a ověření kongruentnosti vidíte na obrázku č. 2 v bodě č. 1. V matematice se veliká pozornost věnuje případu, kdy m je prvočíslo, pak se místo m používá označení p. Proč právě prvočíslům? Stručně proto, že tyhle případy mají velikou aplikovatelnost v praxi, kupříkladu v teorii šifrování nebo čísel. I my v dalších příkladech zůstaneme u prvočíselného modulu, který budeme značit p.
Ve světě kongruenci lze zavést i pojem řešení rovnice. Jak, to můžete vidět na obrázku č. 2 pod bodem č. 2. Na řešení takových rovnic existují poměrně sofistikované metody, ovšem pokud modul není moc veliké číslo, lze postupovat metodou postupného zkoušení. Nakonec tuto metodu jsme použili v příkladu se selkou. Ovšem pokud je p veliké nemusí to být nejlepší nápad, příklad rovnice 37x ≡ 25 (mod107) má řešení x = 99, takže než bychom se k tomu řešení postupně od čísla x = 1 dopracovali, to bychom se nadřeli jako koně.
Na obrázku č. 3 jsou uvedeny 3 nejčastěji používané věty ze světa kongruencí. Se znalostmi, které již máme, je jistě pochopíte. Každou větu jsem ilustroval konkrétním příkladem.
Pokud vás svět kongruencí zaujal zkuste si sehnat k tomu literaturu a své znalosti si rozšířit. Bohužel v češtině toho až tak moc není, ale přece jenom alespoň jeden základní titul: Karel Rychlík: Úvod do elementární číselné teorie, Přírodovědecké nakladatelství, Praha, 1950. A to je vše.
V Brně 22. července 2020.