Den na planetě X má 259 hodin. Hodiny tam právě ukazují 73 hodin. Kolikrát musí těch 73 hodin uběhnout, než tam bude jedna hodina? Hledané číslo se nazývá inverze čísla 73 modulo 259. Řešení, které lze vygooglovat, je přímo úděsné.
Abyste googlovat nemuseli, “návod” je zde:
Je to prý “nejrychlejší způsob, jak to počítat”. Není. A didakticky je asi nejhorší možný. Můj vážený kolega zde říká, kde co vynásobit a co od čeho odečíst, ale už neříká proč. Ba co hůř – říká, že to vysvětlit nemůže, protože je to příliš složité.
Má tam tabulku se třemi sloupci. Poznáte-li v prvním sloupci zbytky z Euklidova algoritmu postupného dělení a ve třetím rozšíření tohoto algoritmu, je to čistě vaše zásluha. Z videa se to nedovíte. Do prostředního sloupce postupně padají řešení diofantických rovnic plynoucích z Bézoutovy věty, aby se nakonec vylouplo hledané číslo jako poslední neznámý koeficient Bézoutova rozkladu jedničky u*73 – 31*259=1.
To všechno video tají. Kdyby se to totiž vysvětlovalo a rozepisovalo, “nejrychlejší způsob” by za těmi “pomalejšími” velmi rychle zaostal..
Obávám se, že tudy
nevede.
Předkládání dogmat patří do středověku, pojďme tedy vysvětlovat..
Čtenáři znalí základů modulární aritmetiky mohou téměř celý další text přeskočit a podívat se až na poslední tři řádky. Vešlo se mně tam vysvětlení i celý výpočet. Průhledný jak křišťálová studánka, kol níž není les (Cimrmani a Josef Václav Sládek Kch jistě prominou).
S ostatními zájemci o řešení se potřebuji nějak dostat k malé Fermatově větě. Tak pojďme na to.
S modulární matematikou se setkáváme odmalička. Je přesně 22 hodin a já si mohu užít osmihodinový spánek. Na kdy nařídím budík? Třicátou hodinu jsem na něm nikde nenašel… Je čtvrtek. Za osm dní mě čeká zkouška. Který den to bude? Určitě ne dvanáctek.
Hodiny – toť aritmetika modulo 24 (modulo 12 není úplně ono, “stejný” čas by pak totiž nastával dvakrát denně). Týden? Modulo sedm. Měsíce v roce? Modulo dvanáct.
Dny v měsící? V roce? Tady prosté moduly nefungují. Gregoriánský kalendář se moc nepovedl. Co je na něm špatně? Měsíce mají různý počet dní. Roky jakbysmet.
Modul je stále stejné číslo, po kterém se všechno opakuje.
To je alfa a omega celé modulární aritmetiky. V postupu Isibalo je však velmi hluboce zakuklen a (nejspíš záměrně) skryt.
Začněme tedy úplně jinak. Vezměme libovolné celé číslo a zajímejme se, jaký zbytek dostaneme po celočíselném dělení pěti. Hned si asi všimneme dvou věcí: za prvé – možných zbytků je pět a za druhé nemá příliš smysl uvažovat vysoká čísla. Například 144 dá po dělení pěti stejný zbytek jako čtverka, protože 144 = 28*5+4. Je tam dvacet osm krát modul, po každém z nich se všechno opakuje. Těch 28*5 je tam z hlediska naší dělitelnosti úplně zbytečně.
Vezměme dvě vyšší čísla a vynásobme je. 144*58 =8 352. Jaký je zbytek po celočíselném dělení pěti (8 352 : 5)? Úplně stejný jako když celočíselně dělím jen součin zbytků původních čísel, tj. 4*3 = 12. Stačí tedy pracovat jen s těmi zbytky. Můžeme tak snadno sestavit “operační tabulku zbytků”, kde záměrně vynecháme nulové zbytky, které “reprezentují” všechny násobky pěti (ty totiž inverzi mít nebudou):
Takže například 3*3 = 4. Proč? Protože součin 3*3 dá po celočíselném dělení pětkou zbytek čtyři. A aby bylo úplně jasno, co se tím podivným zápisem 3*3 = 4 myslí, píše se podrobně 3*3 ≡ 4 mod 5.
Krátká odbočka k “obyčejným” číslům a “obyčejnému” násobení. Jak vyřešíme rovnici 3*x=6? Samozřejmě – vydělíme třemi. Ale co když z nějakého důvodu dělit nemůžu? Jak zajistím u x na levé straně jedničku? Vynásobím inverzním prvkem ke trojce – jednou třetinou: 3-1*3*x= 3-1*6.
A teď totéž, ale “neobyčejně”: 3*x ≡ 2 mod 5. Čím vynásobit trojku, abych nalevo dostal jedničku? Jaký prvek je inverzní ke trojce teď? Pohledem do tabulky zjistím, že jedničku dostanu jako 2*3. Takže
2*3*x ≡ 2* 2 mod 5 => 1*x ≡ 2* 2 mod 5 => x ≡ 4 mod 5
Přesně tak se řeší ty hodiny na planetě X. Jenom místo trojky mám číslo 73 a modul je místo pětky číslo 259. Takže kolik je x, když vím, že 73*x ≡ 1 mod 259 ? Jak k tomu x dostanu jedničku teď? Jaká je inverze ke zbytku 73 modulo 259?
Zdá se, že mám dvě možnosti: Buď zcela mechanicky opsat řešení z videa a nerozumět ničemu, anebo si po vzoru výše uvedené tabulky pro modulo pět sestavit tabulku pro modulo 259. Sice bych pak rozuměl všemu, ale vypisovat tabulku 259 x 259 buněk bych já osobně nechtěl.
Je zde ale ještě třetí možnost – totiž začít přemýšlet.
Zkusme podle tabulky pro modulo 5 začít počítat výraz (3*1)*(3*2)*(3*3)*(3* 4) . Vynásobme nejdřív závorky
(3*1)*(3*2)*(3*3)*(3* 4) ≡ 3*1*4*2 mod 5
a možná si místo hodnoty toho výrazu všimneme něčeho jiného – vlevo “vytkneme” trojku:
(1*2*3*4)* 34 ≡ (3*1*4*2) mod 5
Součiny v závorkách se liší jen pořadím činitelů. Musejí se tedy rovnat, a to i modulo 5. Mají tedy i stejný inverzní prvek, který ani nemusíme počítat:
(1*2*3*4)-1 * (1*2*3*4)* 34 ≡ (3*1*4*2)-1 * (3*1*4*2) mod 5
34 ≡ 1 mod 5
Úplně stejně to funguje pro libovolný modul p a libovolný nenulový zbytek téhož modulu, který je s ním nesoudělný *)
ap-1 ≡ 1 mod p
Dostáváme velmi důležitý výsledek vynikajícího francozského matematika 17. století Pierra de Fremata – malou Fermatovu větu. Nyní už stačí odvážně ještě jednou násobit inverzním prvkem, který stále ještě nemusíme počítat:
a-1 * ap-1 ≡ a-1 * 1 mod p => ap-2 ≡ a-1 mod p
Ještě kosmeticky přehodíme levou a pravou stranu
a-1 ≡ ap-2 mod p
A je to. Máme zcela jednoduchý a jasný vzoreček pro inverzní prvek. Takže žádné tabulky, sloupce a šarlatánské salonní triky. Jenom prostý výpočet.
Máme a=73; p=259. 73 je prvočíslo, takže soudělné s číslem 259 by mohlo být jen v případě, že by prvek 259 byl jeho násobek. To ale není, protože 3*73 = 219 je málo a 4*73 = 292 už je moc. Takže jedeme:
a-1 ≡ ap-2 mod p => 73-1 ≡ 73259-2 ≡ 73257 mod p
Děsíte se té mocniny? Důvod by byl. Zadávat ji do kalkulačky ani nezkoušete. Ale s opakujícím se modulem se bát nemusíte. Začneme od nejnižších mocnin a budeme jen systematicky likvidovat celočíselné násobky modulu, které nemají na nic vliv. Kalkulačka bude asi potřeba, ale Isibalo ji potřebovalo taky. Všechno je modulo 259, což v zápisu pro stručnost vynechám:
732 = 5 329 = 20*259 + 149 ≡ 149
734 ≡ 1492 = 22 201 = 85*259 +186 ≡ 186
7316 ≡ 1862 = 34 596 = 133*259 + 149 ≡ 149
A nyní už jen opisování, které je legální i při písemce:
7364 ≡ 1492 ≡ 186 ; 73128 ≡ 1862 ≡ 149 ; 73256 ≡ 1492 ≡ 186
OK, takže nakonec přece jenom ještě jednou kalkulačka:
73257 = 73 * 73256 ≡ 73 * 186 = 13 578 = 52 *259 +110 ≡ 110
Vyřešeno. 73-1 ≡ 110 mod 259. Na planetě X by se těch 73 hodin muselo opakovat sto desetkrát. Celkem 8 030 hodin. Přeji X-ťanům dlouhý život.
Pro úplnost dodám, že pokud by šlo o jenom o rychlost, exponent 257 bych rozložil trochu rafinovaněji a nad “nejrychlejším způsobem a la Isibalo” bych i s vysvětlením asi vyhrál:
==================================
*) Čísla soudělná s modulem jsou tzv. dělitelé nuly – dvě nenulová čísla, jejichž součin je nula. Např. pro naše p je p=7*37 ≡ 0 mod 259. Prvky 7 a 37 inverzi nemají. Pokud by na planetě X bylo 7 hodin, bude po 37 sedmihodinových krocích “půlnoc”. Na jednu hodinu se sedmihodinové ani třicetisedmihodinové kroky nikdy nedostanou.