V předchozím článku na toto téma Pierre Fermat deklasoval Euklida s Bézoutem. Organizace Isibalo je prohlásila za nejrychlejší na světě a demonstrovala to úlohou, kterou podrazila těmto svým favoritům nohy, takže si na nich Fermat vyloženě smlsnul. Ode mě to nebylo úplně fér, a proto teď Euklides s Bézoutem vyrovnají skóre.
Čtenáři, který nečetl můj předchozí článek, vřele doporučuji, aby tak učinil (zde). Přesto stručně zopakuji: šlo o výpočet inverze k prvku 73 modulo 259. Isibalo řešení prezentovalo zde
s tím, že je to nejrychlejší způsob, jak to udělat.
Je jasné, že když starý počítačník uvidí Isibalem naprosto nešťastně zvolený modul 259, okamžitě mu naskočí 256= 28 . A když navíc ještě úplně nezapomněl matematiku a vzpomene si na Fermata, mají Euklides s Bézoutem prostě smůlu. Zvlášť když jejich postup Isibalo prezentovalo jako nevysvětlitené dogma.
Jenže za tu ťafku v mém minulém článku nemůže ani Euklides, ani Bézout, ale organizace Isibalo promine, organizace Isibalo.
Před několika dny (opět zde) jsem úlohu motivoval 259 hodinovým ciferníkem. Kolik sedmdesáti tří hodinových cyklů musí proběhnout, než budou hodiny ukazovat jednu po půlnoci? To se mi to vytahovalo když fermatovské řešení vyžaduje modul 257 =1+44 …
Uvažujme stejný problém. Jen ciferník bude trochu větší – bude mít 99 380 952 hodin a ručička bude ukazovat naopak o dost míň – pouhých 19 hodin.
Co vy na to, pane Femate?
V minulém článku jsem napsal, abyste se nebáli velkých exponentů. A bylo to správně. Jenže to rozumně funguje pouze v případě, že exponent lze rozumně rozložit. S exponentem 257= 1+44 se to Fematovi panečku vítězí!
Teď? Musím začít mocninou devatenáctky, která bude vyšší než ten bezmála stotisícový modul. Jen tak mohu začít s jeho likvidací. Takže
197 = 893 871 739 = 8* 99 380 952 + 98 824 123 ≡ 98 824 123
Co teď? Znovu na sedmou? 1949 = 98 8241237? To číslo má 56 cifer !! Budu muset slevit. A to tak, že pořádně…
1914 = 98 824 1232 = 9 766 207 286 719 129 = 98 270 413*99 380 952 + 89 345 953
Teď? Na třetí?
1942 = 89 345 953 193 = 713 221 878 032 540 139 838 177
Copak o to, windowsovská kalkulačka to pořád ještě stráví, ale mně už se dělá pomalu špatně. A to jsem ještě ani nedokončil 1942 . Jak dlouho mi asi potrvá, než po těch čtrnáctkách, trojkách a podobných číslech doskáču k bezmála sto tisícům? Obávám se, že je to práce na několik životů…
Opustím tedy k smrti odsouzeného Fermata a poohlédnu se jinde. Místo několika životů to bude jenom několik minut.
O dělitelnost čísel se již dva tisíce let před Fermatem totiž zajímal Euklides a všiml si zajímavé věci. Když dělí se zbytkem dvě větší čísla, např. 80 784 : 6 552 = 12 zbytek 2160, zapíše to jako
80 784 = 12* 6 552 +2 160
a pokračuje tak, že minulého dělitele povýší na budoucího dělence a minulý zbytek na budoucího dělitele
6 552 = 3*2 160 +72
a znovu a znovu, pak dříve či později…
2 160 =30*72 + 0
…dostane zbytek nula. A navíc – poslední nenulový dělitel je Největší Společný Dělitel původních čísel: NSD ( 80 784 ; 6 552 ) = 72. Tuto zajímavou skutečnost zjistí v mnoha případech daleko rychleji, než kdyby obě čísla rozkládal na prvočinitele a porovnával nějaké exponenty. Tolik Euklides.
Více než dva tisíce let po Euklidovi a zhruba sto let po Fermatovi si antického klasika vzal do parády Étienne Bézout. Řádky Euklidova algoritmu
doplnil o vyjádření zbytků z příslušného řádku
a uvědomil si, že pak tím kromě největšího společného dělitele získá něco víc. Když totiž teď do rovnosti pro největšího společného dělitele (podtrženo) dosadí 2 160 z rovnosti nad tím, dostane
Pro něj jako pro matematika nebylo těžké dokázat, že to, co provedl se dvěma konkrétními přirozenými čísly, lze provést s každými dvěma přirozenými čísly a dokázal obecně, že nevětší společný dělitel dvou čísel lze napsat jako rozdíl vhodných násobků původních čísel, jako jejich “kombinaci” *) . Pro každá dvě přirozená čísla a;p existují přirozená čísla u;v tak, že * * )
Étienne Bézout tak prodloužil řadu matematiků, kteří po sobě zanechali nějakou větu. A právě tato věta aplikovaná na náš mamutí ciferník smete větu Fermatovu.
Hledejme Bézoutovy koeficienty u; v pro našich a = 19 hodin na ciferníku, který má p = 99 380 952 hodin. Zopakujme Bézoutův postup:
Je to, pravda, poněkud delší než náš příklad předchozí, ale – Fermate, div se – jsme už zhruba v polovině řešení našeho obrovského ciferníku.
Podtržená rovnost nám mimo jiné říká, že čísla 19 a 99 380 952 jsou nesoudělná (jejich NSD je jedna), což není nijak zvlášť objevné, a ještě méně překvapivé je, že 1 = 3 – 2. Ovšem právě tato úsměvná rovnost nastartuje věci vážnější.
Pojďme na “zpětný chod”.
První zpětné dosazení (za dvojku) rozepisuje jedničku jako “kombinaci” dělence a dělitele ve třetím řádku a pozornější čtenář už možná tuší…
Druhé zpětné dosazení (za trojku) :
Máme jedničku jako “kombinaci” dělence a dělitele ve druhém řádku. Už je tam našich 19 hodin a na prvním řádku už čeká celý obří ciferník. Tak pojďme ještě pomocí prvního řádku zlikvidovat tu osmičku:
To je celý postup, který Isibalo namačkalo do tří sloupců svojí tabulky a neodvážilo se ji vysvětlit.
Máme vyřešeno.
Abychom se na takových hodinách dočkali jedné hodiny po půlnoci, potřebuje devatenáctihodinový interval uplynout téměř třicet sedm milionkrát. A se než “malá ručička” devatenáctihodinovými intervaly do té jedničky trefí, oběhne celý ciferník sedmkrát.
Vrátíme-li se k modulární aritmetice, je celočíselný násobek modulu zbytečný
1 ≡ 36 614 035 * 19 mod 99 380 952
a pro naši inverzní devatenáctku je
1 * 19-1 ≡ 36 614 035 * 19 * 19-1 mod 99 380 952
Chceš-li, milý čtenáři, zkontrolovat, zda je to správně, věz, že naše poslední čtyři rovnosti říkají: devatenáctku vynásob číslem 36 614 035 a od získaného součinu odečti jedničku. Dostaneš číslo dělitelné číslem 99 380 952. A v jednom z těch vzorečků dokonce najdeš i ten podíl.
V mém minulém článku byl Fermat rychlejší než Bézout, ale nikde tam nenajdete ani čárku o tom, že Fermat je vždy nejrychlejší. To proto, že pro jiná čísla mohou být naopak rychlejší Euklides s Bézoutem, jak jsem ukázal zde.
Milé Isibalo, mnohé matematické úlohy lze řešit více metodami a málokdy se dá říci, že jedna z nich je vždycky nejlepší. O výhodnosti té či oné metody většinou rozhoduje až zcela konkrétní zadání.
==================================
*) Poznamenejme, že Bézoutova rovnost bývá standardně uváděna ve tvaru N(a;b)=u.a+v.b, kde ovšem a;b;u;v nejsou čísla přirozená, ale celá, tj. připouštějí se i záporné hodnoty. Ale i náš vzoreček je pak tohoto tvaru: 72=37*a+(-3)*b .
* * ) Místo standardního b máme p jako “parametr” či “perioda”, neboť, jak uvidíme za chvíli, toto číslo bude počet hodin v jednom dni.