Fermat a teorie čísel aneb problematika dělitelů a dokonalá čísla

Cahiers du CEFRES N° 28, Matematik Pierre de Fermat

Alena Šolcová, Michal Křížek, Georges Mink (Ed.)

__________________________________________________ Štefan PORUBSKÝ Fermat a teorie čísel aneb problematika dělitelů a dokonalá čísla

__________________________________________________ Référence électronique / electronic reference : Štefan Porubský, « Fermat a teorie čísel aneb problematika dělitelů a dokonalá čísla », Cahiers du CEFRES. N° 28, Matematik Pierre de Fermat (ed. Alena Šolcová, Michal Křížek, Georges Mink). Mis en ligne en / published on : mai 2010 / may 2010 URL : http://www.cefres.cz/pdf/c28/porubsky_2002_fermat_teorie_cisel.pdf Editeur / publisher : CEFRES USR 3138 CNRS-MAEE http://www.cefres.cz Ce document a été généré par l’éditeur. © CEFRES USR 3138 CNRS-MAEE

1

Bůh viděl, že všechno, co učinil, je velmi dobré. Byl večer a bylo jitro, den šestý. Genesis 1, 31

Je zaznamenáno, že celá boží práce byla dokončena za šest dní, protože šest je dokonalé číslo. … Protože to je první číslo složené z šestiny, třetiny a půlky, nebo jednotka, dvojka a trojka dávají dohromady šest. Sv. Augustin z Hipponu: O Božské obci

Fermat a teorie čísel aneb Problematika dělitelů a dokonalá čísla Štefan Porubský *, Praha Lidé si pravděpodobně již na prahu civilizace, jakmile dospěli ke schopnosti násobit čísla, uvědomovali, že čísla mají různé vlastnosti z pohledu násobení. Podívejme se jen, kolik našich šťastných nebo nešťastných čísel jsou prvočísla. Údajně každá kultura (snad s výjimkou amerických Indiánů) znala číselnou mystiku. Proto je pojem dělitele přirozeného čísla velice přirozený. Jak jinak si můžeme vysvětlit, že číslo 60 se stalo základem číselné soustavy ve starém Babylonu. Je to ještě dosti malé číslo a žádné jiné menší číslo nemá větší počet dělitelů, tj. 12 . Dalším kandidátem je číslo 48, které má ale jenom 10 dělitelů. Bohatá zásoba dělitelů základu číselné soustavy je důležitá z hlediska počítaní s reciprokými hodnotami (nebo se zlomky obecně). Připomeňme si jen tvrzení, že v poziční číselné soustavě se základem M mají konečný rozvoj jenom ta racionální čísla, jejichž jmenovatel je dělitelem M.

1. Dokonalá čísla Práce byla napsána s podporou grantu GA ČR 201/01/0471. Autor děkuje RNDr. Aleně Šolcové za závěrečnou úpravu celého příspěvku.

*

2

Měls vystřelit pětkrát nebo šestkrát, pak bys pobil Arama úplně! Druhá královská 13, 19

Alikvotní částí čísla se ve starověku rozuměly vlastní celočíselné podíly tohoto čísla. Např. 1 = 6 / 6, 2 = 6 / 3 a 3 = 6 / 2 jsou alikvotní části čísla 6, ale samotné číslo 6 není, protože není svým vlastním (tj. menším než číslo samotné) podílem. Existují domněnky, 1 že k pojmu alikvotní části přivedly již staré Egypťany jejich početní metody. Číslo, které bylo součtem svých alikvotních částí, pythagorejci nazývali dokonalé. Pythagorejci studovali dokonalá čísla více pro jejich mystické vlastnosti než pro jejich číselně teoretické vlastnosti. Nejmenší dokonalé číslo je 6 = 1 + 2 + 3 . Číslo 6 se v jisté speciální poloze objevuje již u starých Hebrejců, kdy svět byl stvořen za 6 dní. 2 Podobně další dokonalé číslo 28 bylo Bohem zvoleno za dobu oběhu Měsíce kolem Země. Proto pojem dokonalého čísla bude pravděpodobně staršího data. Informace o stavu pythagorejské teorie čísel představují Knihy VII, VIII a IX Eukleidových Základů a zachovalé dílo novopythagorejce Nikomacha z Gerasy (kolem r. 100 n.l.), zejména jeho Úvod do aritmetiky. 3 Eukleidés (Základy IX, 36) uvádí (a dokazuje) postačující podmínku: 4 Když jest dáno po řadě od jednotky několik čísel v poměru jedné ke dvěma, až součet všech stane se číslem kmenným 5, a když se ten součet znásobí číslem posledním a vznikne jiné, vzniklé číslo bude dokonalé. Aneb v soudobé formulaci: Jestliže p = 1 + 2 + 2 2 +  + 2 n je prvočíslo, pak číslo 2n p je dokonalé. Eukleidés zakládá důkaz na výčtu všech vlastních dělitelů součinu 2 p: n

1

C. M. Taisbak, Perfect numbers: A mathematical pun? An analysis of the last theorem in the ninth book of Euclid‘s Elements, Centaurus 20 (4), (1976), 269-275. 2 S. Rubin, Sod Hasfiroth (Tajemství čísel), Vídeň, 1873, str. 59. Filón Judejský ( I. stol. n. l.), Pojednání o stvoření světa dle Mojžíše; překlad: C. D. Young, Londýn 1854, sv. I, str. 3. 3 Anglický překlad Nicomachus, Introduction to Arithmetic, s podrobnými komentáři vydal Martin Luther d'Ooge, New York 1926. Nikomachova Arithmetike eisagoge byla první knížkou, která je samostatně věnována aritmetice odděleně od geometrie. Více než 1000 let sloužila jako základní text o aritmetice. Na rozdíl od Eukleida neuvádí důkazy, jenom ilustruje tvrzení numerickými příklady. Nikomachos používá arabské číslovky a ne řecké, ale přesto jeho dílo je psáno ve starém mystickém duchu blízkému víc pythagorejcům nežli pozdějším představám o struktuře matematického textu. Její překlad do arabštiny vedle Eukleida hodně ovlivnil arabský příspěvek k teorii čísel. Nikomachos také napsal dvojdílnou Teologii čísel (Theologoumena arithmetikes), která se věnuje zejména mystickým vlastnostem čísel. Dalším jeho dílem je Manuál harmonie, v němž se věnuje hudbě. Lucian (nar. kolem 120 n.l), rétorik a satirik, používal rčení: Počítáš jako Nikomachos. 4 Citováno podle Servítova překladu z roku 1907, str. 154. 5 Kmenné jest číslo (prvočíslo), které měří jednotka jediná. (Kniha 7, definice 11)

3

1, 2,  , 2 n , p, 2 p,  , 2 n −1 p a vztahu 1 + 2 + 2 2 +  + 2 n = 2 n +1 − 1 pro součet geometrické posloupnosti, který je doložen jako známý již ve starém Babylonu. U Nikomacha, který žil o čtyři století později než Eukleidés, můžeme pozorovat více spojitostí s babylónskou matematikou než u Eukleida. Takovým projevem je kupříkladu jeho popis vlastností figurálních čísel. Nicméně Nikomachos uvádí čtyři dokonalá čísla 6 = 2(22 − 1), Zde

28 = 22 (23 − 1),

496 = 24 (25 − 1),

8128 = 26 (27 − 1).

6 =1 + 2 + 3, 28 =1 + 2 + 4 + 7 + 14, 496 =1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248,

a 8128 =1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1 016 + 2 032 + 4 064. Tato čtyři dokonalá čísla se objevují již v antice, a proto se zdá nemožné datovat dobu jejich objevu nebo stanovit jejich objevitele. Nečekaně se objevuje problematika dělitelů přirozených čísel v páté knize Platónových Zákonů. 6 V knize Platón (427 - 347 př.n.l.) doporučuje volit počty bezzemků a majitelů půdy v nově založeném státě tak, aby měli dostatečně mnoho dělitelů. Vhodné je např. číslo 5 040 , které má 60 − 1 dělitelů. Zákonodárce musí natolik ovládat aritmetiku, aby to byl schopen podle velikosti města přiměřeně zařídit. Z těchto příkladů můžeme opět usuzovat, že problematikou dělitelů se v antice zabývali více, než můžeme dedukovat z Eukleidových Základů. V dnešní symbolice můžeme dokonalá čísla definovat pomocí funkce součet alikvotních částí

s ( n) = ∑ d . d |n d
Pak je dokonalé číslo charakterizováno vztahem s (n) = n . Dokonalá čísla mají mnoho dalších zajímavých vlastností. Například každé dokonalé číslo je trojúhelníkové, tj. je možné je reprezentovat pomocí kamínků uložených ve tvaru rovnoramenného pravoúhlého trojúhelníku 6

Zde Platón doporučuje zajistit výrobu otroky a cizinci.

4

(viz obr. 1). Aritmeticky vyjádřeno, jsou tvaru t (t + 1) / 2 pro vhodné přirozené t .

t =1

t=2

t =3

t=4

Obr. 1. Grafické znázornění trojúhelníkových čísel.

Dále součet reciprokých hodnot alikvotních částí dokonalého čísla se rovná jedné, např. 1

pro n = 6 : 2 pro n = 28 :

1 2

+ 13 + 16 = 1 ,

+ 14 + 17 + 141 + 281 = 1 .

5

Obr. 2. Nikomachos (kolem 100 n. l.). Nikomachos bez důkazů, které nemohly existovat pro všechna tvrzení, protože ne všechna jsou pravdivá (srov. kap. 3), nebo doposud neznáme na ně odpověď, uvádí následující vlastnosti dokonalých čísel:

n -té dokonalé číslo má n cifer. Všechna dokonalá čísla jsou sudá. Každé dokonalé číslo končí střídavě buď cifrou 6 nebo 8. Eukleidem uváděný algoritmus generuje všechna dokonalá čísla. Existuje nekonečně mnoho dokonalých čísel.

1. 2. 3. 4. 5.

Nikomachos též dělí (Kniha I, kap. 14,15) sudá čísla na abundantní, např. 12, 24 , a deficientní, jako např. 8, 14 . Přitom abundantní čísla jsou definována jako čísla, pro která n < s (n) , a pro deficientní čísla je n > s (n ) . Z matematického hlediska je velice zajímavý poznatek, dříve formulovaný Tassiem, 7 že libovolný násobek dokonalého a abundantního čísla je číslo abundantní, 8 zatímco každý dělitel dokonalého čísla je deficientní. Nikomachos pokračuje v rozvíjení číselné mystiky tím, že za hlavní cíl svého Úvodu do aritmetiky klade výklad zázračných a božských vlastností čísel. Podle Nikomacha (I,16) se dokonalá čísla nacházejí mezi nadbytkem a nedostatkem. Prvních devět dokonalých čísel je uvedeno v tabulce: 2 p −1 (2 p − 1)

p 2 3 5 7 13 17 19 31 61

6 28 496 8 128 33 550 336 8 589 869 056 137 438 691 328 2 305 843 008 139 952 128 2 658 455 991 569 831 744 654 692 615 953 842 176

objevitel Pythagoras? Eukleidés? Eukleidés? Eukleidés? anonym anonym Cataldi Euler Pervušin

Desáté číslo (pro p = 89 ) 191 561 942 608 236 107 294 793 378 084 303 638 130 997 321 548 169 216

objevil Powers.

7

J. A. Tassi, Aritmeticae Empiricae Compendium, Hamburgi 1673, pp. 13, 14. Z tohoto poznatku se postupně v pracích Dicksona a Davenporta vyvinul pojem primitivního abundantního čísla, ze kterého později P. Erdős "vypreparoval" pojem primitivní posloupnosti. Pro další zobecnění viz kupř. Š. Porubský, Notes on density and multiplicative structure of sets of generalized integers, Colloquia Mathematica Societatis János Bolyai, 34. Topics in Classical Number Theory, Budapest, 1984, 1295-1315.

8

6

Nikomachovo tvrzení, že Eukleidův vztah dává všechna dokonalá čísla, se objevuje bez ohledu na příspěvek Arabů v evropské renesanční matematice ještě kolem roku 1500. Dokonce se objevili autoři (Pacioli, de Bovelles), kteří nesprávně tvrdili, že formule 2k −1 (2k − 1) dává dokonalé číslo pro každé k . Páté dokonalé číslo se v Evropě objevuje až v jistém rukopisu z roku 1461. Je uvedeno i v jednom Regiomontanově rukopisu, 9 který byl sepsán během jeho pobytu ve Vídni. Páté a šesté dokonalé číslo bylo objeveno též v rukopisu sepsaném neznámým autorem kolem roku 1460. Vše, co o něm víme, je, že žil ve Florencii a byl studentem jistého Domenica d‘Agostina Vaiaio.

Obr. 3. Marin Mersenne (1588-1648). V roce 1638 tvrdil Descartes v dopisu Mersennovi, 10 že může dokázat, že každé sudé dokonalé číslo je Eukleidova typu, že každé liché dokonalé číslo je tvaru ps 2 , kde p je prvočíslo, a že nevidí důvod, proč

9

E. Picutti, Pour l‘historie des sept premiers nombres parfaits, Historia Mathematica 16 (2) (1989), 123-136. 10 Marin Mersenne (8.9.1588 - 1.9.1648) francouzský matematik, filosof a teolog. Jeho nejdůležitější aktivitou byla úloha zprostředkovatele vědecké korespondence v období, kdy neexistovaly vědecké časopisy. Do okruhu jeho korespondentů patřili i Fermat, Descartes, de Roberval, nebo Etienne Pascal. Mersenne navrhl např. Ch. Huygensovi použít kyvadlo jako přístoj na měření času.

7

by liché dokonalé číslo nemohlo existovat.11 První publikovaný důkaz, že každé sudé dokonalé číslo je Eukleidova typu, pochází od Eulera v práci, která vyšla posmrtně 12: Přirozené číslo n je sudým dokonalým číslem, právě když je tvaru n = 2 p −1 (2 p − 1), kde činitel 2 p − 1 je prvočíslo. 13 Tím byl završen dvoutisíciletý proces hledání kritéria, podle kterého můžeme generovat sudá dokonalá čísla. Eulerův-Eukleidův výsledek ukazuje, že sudá dokonalá čísla dokážeme generovat, pokud jsme schopni nalézt prvočísla tvaru M n = 2n − 1, která se nazývají Mersennova a o nichž pojednáme později. To ale neřeší dva ústřední problémy z oblasti dokonalých čísel: • •

Existuje nekonečně mnoho dokonalých čísel? Existuje liché dokonalé číslo? 14

Bachet de Méziriac, který vešel do dějin vydáním latinského překladu Diofantovy Aritmetiky, kterou pak studoval detailně Fermat, podal 15 zdlouhavý důkaz Eukleidovy postačující podmínky pro dokonalá čísla s dodatkem, že pokud m = 2 p − 1 je složené, je číslo 2 p −1 m abundantní. Podobně není důvod omezovat se i u definice abundantních a deficientních čísel na sudá, jak to dělal Nikomachos. Nejmenší liché abundantní číslo je 945. Pokud označíme A( x) počet abundantních čísel nepřesahujících x, pak je známo, že 0,241x < A( x) < 0,314 x, což znamená, že většina čísel je deficientních. 16 V roce 1933 bylo dokázáno, že lim x→ ∞ A( x) / x existuje, ale její hodnota není známá. Pojem dokonalého čísla můžeme bezprostředně zobecnit: Přirozené číslo s (n) = (k − 1)n.

11

n

se

nazývá

dokonalé,

k-násobně

Dnes víme, že neexistuje liché dokonalé číslo menší než 10

300

pokud

. Heath-Brown v roce 1994

dokázal, že když n je liché číslo, pro které σ ( n ) = ∑ d = an, pak n < ( 4 m )

d |n

4k

,

kde m je

jmenovatel čísla a a k je počet různých prvočíselných faktorů čísla n. Speciálně, když n je

4k

liché dokonalé číslo s k různými prvočíselnými děliteli, pak n < 4 . Hagis a Chain nezávisle na sobě dokázali, že liché dokonalé číslo musí mít alespoň 8 různých prvočíselných dělitelů, abychom uvedli alespoň některé známé výsledky. 12 L. Euler: De numeris amicabilibus, Commen. Arith. 2,514; Opera posthuma 1,1862, 88. 13 Všimněte si zajímavého tvaru dokonalých čísel ve dvojkové soustavě, který plyne z tohoto tvrzení. První čtyři jsou: 110, 11100, 111110000, 1111111000000. Na tuto jednoduchou skutečnost poprvé upozornil F.J. Studnička v Sitzugsberichte der königlichen böhmischen Gessellschaft der Wissenschaften v r. 1899. Nr. 30, str. 1-3. 14 Tento problém je pravděpodobně nejstarším otevřeným matematickým problémem vůbec. 15 Elementorum arithmeticorum libri XIII auctori D …, latinský rukopis v Bibliothéque de l`Institut de France, viz též Henry, Bull. Bibl. Storia Sc. Mat. e Fis. 12, 1879, 619-641. 16 Mezi 10 a 100 je 21 abundantních čísel.

8

Dvojnásobně dokonalá čísla jsou proto dokonalá čísla podle předchozí definice. Číslo 120 je 3-násobně dokonalé, 30 240 je 4-násobně dokonalé a 14 182 439 je 5-násobně dokonalé. Poznamenejme, že problematikou dokonalých čísel se nevyčerpávají všechny problémy o alikvotních částech, které zajímaly Fermata. Například ve své „premier défi aux mathématiciens" ze dne 3. 1. 1657 vyzývá k řešení následujících problémů: •

Najděte třetí mocninu, která dává čtverec, když ji zvětšíme o součet jejích alikvotních částí, 17 jako např. 7 3 + (1 + 7 + 7 2 ) = 20 2.

•

Najděte čtverec, který zvětšený o součet alikvotních částí vede na třetí mocninu. 18

Ve francouzském překladu tohoto problému je špatný překlad požadující, aby výsledný součet byl třetí mocninou, Oeuvres de Fermat 3, str. 311.

17

Poznamenejme, že odpověď na tyto problémy zdaleka není lehká. E. Lucas v roce 2 3 2 1877 první problém přeformuloval na řešení diofantské rovnice 1 + x + x + x = y a konstatoval, že nejmenší složené číslo, které je jejím řešením, je číslo x = 2 ⋅ 3 ⋅ 5 ⋅ 13 ⋅ 41 ⋅ 47 . Takové řešení našel i Frénicle de Bessy v roce 1657. Frénicle de Bessy našel v roce 1658 odpověď na i na druhý problém: čtverec čísla 2 x = 2 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 37 ⋅ 67 ⋅ 163 ⋅ 191 ⋅ 263 ⋅ 439 ⋅ 499 a třetí mocnina čísla 2 3 2 y = 3 ⋅ 7 ⋅ 13 ⋅ 19 ⋅ 31 ⋅ 67 ⋅ 109 . 18

9

2. Spřátelená čísla Pak vzal z toho, co vyzískal, dar na usmířenou pro svého bratra Ezaua: dvě stě koz a dvacet kozlů, dvě stě bahnic a dvacet beranů, … 19 Genesis 32, 14-15

Již dávno (nejpozději v antice) bylo objeveno přirozené zobecnění dokonalých čísel. Spřátelená čísla jsou definována jako taková dvojice čísel, u nichž součet alikvotních částí jednoho čísla se rovná číslu druhému, tj. (m, n) je spřátelená dvojice, když

m = s ( n)

a současně

n = s (m) .

O Pythagorovi se traduje, 20 že na dotaz, co znamená přítel, odvětil,21 že je to druhé já, a připomněl dvojici spřátelených čísel 284 a 220. Spřátelená čísla se opakovaně objevují u Arabů, kde měla své místo v jejich magii a astrologii při tvorbě horoskopů. V 9. stol. n. l. arabský matematik Abu-l-Hasan Thabit ibn Urra 22 z Bagdádu dokázal první algebraické pravidlo pro generování spřátelených čísel, které dnes nese jeho jméno: Jsou-li p = 3 ⋅ 2 n −1 − 1, q = 3 ⋅ 2 n − 1 a r = 9 ⋅ 2 2 n −1 − 1 prvočísla, pak čísla M = 2n pq, N = 2n r jsou spřátelená. Pro n = 2, p = 2, q = 11 a r = 71 dostaneme známou Pythagorovou dvojici. Pro n = 4 a n = 7 dostaneme hodnoty:

n=2 p=5 q = 11 r = 71 M = 220 N = 284

n=4 p = 23 q = 47 r = 1151 M = 17296 N = 18416

n=7 p = 191 q = 233 r = 73727 M = 9363584 N = 9437056

19

E. J. Lee, J. S. Madachy, The history and discovery of amicable numbers, I - III, Journal of Recreational Mathematics 5 (1972), 77-93, 153-174, 231-249. 20 Podle podání Iamblicha (kolem 283-kolem 330), zakladatele syrské školy neoplatonismu a autora Pythagorova životopisu (Iamblichos/Porphyrios, Vita Pythagorica, Ed. A. Nauck, 2. vydání, Lipsko 1886), který pro patetický a nadnesený popis nepovažuje mnoho autorů za důvěryhodný. Takto údajně definuje přátele i Aristotelés ve své Etice. 21 B. L. Van der Waerden, Probouzející se věda (Science Awakening), ruské vydání Moskva 1959, str. 136. 22 Tento Abu-l-Hasan Thabit ibn Urra, známý arabský matematik a směnárník, žil mezi r. 841 a 901. Psal díla z medicíny, filosofie, matematiky, astronomie a astrologie. Překládal také z řečtiny a syrštiny do arabštiny, např. díla Eukleida, Apollonia, Ptolemaia, Prokla, Nikomacha aj.

10

Do r. 1980 byly touto tabulkou vyčerpány všechny známé hodnoty pro n ≤ 20 000 . Není známo, zda Thabit použil svoji větu pro n > 2. Ve 14. stol. objevil 23 znovu Thabitovo pravidlo pro n = 4 a n = 7 Ibn al-Banna (1256 - 1321) z Marakeše (Maroko). V jeho díle najdeme tuto větu: Čísla 17 296 a 18 416 jsou spřátelená; jedno z nich je abundantní, druhé deficientní. Alláh je všemohoucí. Kamaladdin Farisi z Bagdadu našel také dvojici M = 17 296 a N = 18 416 . V 17. stol. objevil Muhammad Baqir Yazdi z Íránu dvojici pro n = 7 : M = 9 363 584 a N = 9 437 056. Ibn al-Haytham dokázal částečné obrácení Eukleidova tvrzení v nepublikovaném díle Pojednání o analýze a syntéze, když dokázal, že dokonalá čísla splňující jisté podmínky musí být tvaru 2k −1 (2k − 1), kde 2k − 1 je prvočíslo. Ibrahim ibn Fallus (1194 -1239) sepsal dílo24 založené na Nikomachově Úvodu do aritmetiky, kde přebírá jeho klasifikaci čísel, uvádí tabulku deseti podle něj dokonalých čísel, z nichž ovšem jenom prvních 7 je dokonalých, zbývající tři dokonalá nejsou. Antičtí a arabští autoři a jejich středověcí následovníci s oblibou zařazovali do svých děl části o dokonalých a spřátelených číslech, v nich ovšem často nebylo nic nového a mnohdy obsahovaly i chyby. Postupem času se ale na Thabitovy formule zapomnělo a jeho dílo bylo znovuobjeveno až v 17. stol. Přes Araby se spřátelená čísla dostala do západní Evropy, kde se objevují kolem roku 1500 u Nicolase Chuqueta, Etienna de la Roche (Villefranche), Michaela Stiefela, Cardana nebo Tartaglii. Nalezl jsem velké množství mimořádně krásných vět. Pierre de Fermat V roce 1636 Pierre de Fermat a nezávisle na něm roku 1638 René Descartes objevili Thabitovy formule. Marin Mersenne, kterému napsali o svých objevech, je nazval velikými úspěchy geniálních matematiků. Mersenne 25 uvádí toto Fermatovo pravidlo: Začni s geometrickou posloupností 2, 4, 8, 16 , … , napiš trojnásobky o řádek níže, odečti 1 ze součinu a napiš výsledek do horního řádku. Spodní řádek je 6 ⋅ 12 − 1, 12 ⋅ 24 − 1, …. Když číslo v posledním řádku je prvočíslo (jako např. 71 ), v horním řádku je také prvočíslo (11) a číslo 23

W. Borho, H. Hoffmann, Breeding amicable numbers in abundance, Mathematics of Computation 46, 1986, 281-293. 24 S. Brentjes, Die ersten sieben vollkommenen Zahlen und drei Arten befreundeter Zahlen in einem Werk zur elementaren Zahlentheorie von Ismail b. Ibrahim ibn Fallus, NTM Schr. Geschichte Natur. Tech. Medizin 24 (1) (1987), 21-30. S. Brentjes, Eine Tabelle mit volkommenen Zahlen in einer arabischen Handschrift aus dem 13. Jahnrhundert, Nieuw Arch. Wisk. (4) 8 (2) (1990), 239-241. 25 R. Descartes, Seconde Partie de l`Harmonie universelle, Paris 1837, str. 26, pozorování 13; též Oeuvres Fermat, 2, 1894, 21.

11

mu předcházející ( 5 ) je též prvočíslo, pak čísla 71 ⋅ 4 = 284, 5 ⋅ 11 ⋅ 4 = 220 jsou spřátelená. Podobně pro 1151 ⋅ 16 = 18 416 , 23 ⋅ 47 ⋅ 16 = 17 256 a stejným způsobem do nekonečna. 5 2 6

11 23 4 8 12 24 71 287

47 16 48 1151

Později Mersenne citoval pravidlo, které mu sdělil Descartes 26 (sice formálně jiné, ale jak sám Descartes napsal, 27 Fermatovo pravidlo je shodné s jeho, takže mnozí autoři často připisují tuto konstrukci Descartovi). Při té příležitosti oba (Fermat i Descartes) objevili i vztah pro hodnotu funkce „součet všech dělitelů“ 28

σ= ( n)

d ∑=

s (n) + n,

d |n

pokud známe rozklad čísla n na prvočinitele. Je historickou kuriozitou, že druhá nejmenší dvojice - 18 416 a 17 296 (první je Pythagorova - 220 a 284) byla znovu nezávisle nalezena až v roce 1866 šestnáctiletým italským školákem se zajímavým jménem Niccolo Paganini. 29 H.-J. Kanold dokázal, že v libovolné dvojici spřátelených čísel musí mít jedno z čísel alespoň tři prvočíselné dělitele. To znamená, že Thabitova věta popisuje nejjednodušší případy. Na druhé straně P. Erdős dokázal, že asymptotická hustota spřátelených čísel se rovná nule, tj. je jich velice málo. Z těchto výsledků ovšem neplyne, zda existuje nekonečně mnoho spřátelených dvojic. Podobně neznáme nutnou a postačující podmínku pro spřátelené dvojice, a ani efektivní metodu na jejich generování. To, že pojmy dokonalých čísel a spřátelených čísel patří do stejné kategorie, ukazuje následující zobecnění. Definujme alikvotní posloupnost jako posloupnost iterací funkce s :

s 0 ( n ) = n,

s k +1 (n) = s ( s k (n)), k > 0.

Descartes sám o něm tvrdí, že souhlasí s Fermatovým (Oeuvres de Descartes, 2, 1898, 93-94). Oeuvres de Descartes, 2, 1898,148; dopis Mersennovi ze dne 27. 5. 1638. 28 Funkce „součet všech dělitelů" nemá jednotně ustálené označení. Poznamenejme, že Euler 26 27

(Opusc. var. argum. 2, 1759, str. 23 = Comm. arithm. 1, str. 102) používal označení ∫ n nebo

∫ (n ) pro součet všech dělitelů čísla n L. Euler (Comm. arithm. 1, str. 104-109, 147) sestavil jako první tabulku hodnot této funkce. Pro informace o jejím dalším zobecnění viz Lucas, Théorie des nombres, 1891, str. 378. Např. Liouville používal označení ξ (n ) nebo obecněji

ξ k ( n) = ∑ d

k

.

d |n

Čtenář možná sáhne po práci E. J. Lee, J. S. Madachy, The history and discovery of amicable numbers, I, II, III, Journal of Recreational Mathematics 5, 1972, 77-93, 153-173, 231-249.

29

12

Pak dokonalá čísla jsou čísla n, pro která s1 (n) = n. Spřátelená čísla m, n splňují podmínku

s1 (n) = m,

s 2 (n) = n.

Když pro dané n dostaneme cyklus délky k , pak alikvotní posloupnost n , s(n), s 2 (n), … , s k −1 (n) tvoří přátelskou skupinu řádu k . První takovouto skupinu pro k ≥ 3 objevil P. Poulet 30 pro (k , n) = (5,12 496) a (k , n) = (28,14 316).

30

P. Poulet, Question 4865, l'Indetermediare des Math. 25, 1918, 100-101; viz též A. Flammenkamp, New sociable numbers, Mathematics of Computation 56, 194, 1991, 871-873.

13

3. Mersennova čísla Informovat Mersenna o objevu znamená oznámit to celé Evropě. Dobové rčení

V minulosti často vyslovovaná domněnka, že M p = 2 p − 1 je prvočíslo, když p je prvočíslo, neplatí. V r. 1536 Hudalricus Regius našel ve svém díle Utriusque Arithmetices rozklad čísla 211 − 1 =2 047, čímž dokázal, že není prvočíslem (2047 = 23 ⋅ 89). Objevil tak první prvočíslo p, pro které 2 p −1 (2 p − 1) není dokonalé. Současně zjistil, že 213 − 1 = 8191 je prvočíslo tím, že dokázal, že pátým dokonalým číslem 12 13 je 2 (2 − 10) = 33 550 336. Protože toto dokonalé číslo má 8 cifer, popřel současně Nikomachovou domněnku o počtu cifer dokonalého čísla (viz kap.1). V r. 1555 uvádí J. Scheybl v poznámkách k překladu Eukleidových Základů páté dokonalé číslo. Dílo ovšem bylo znovu objeveno až v roce 1977. V r. 1603 Pietro Cataldi 31 v díle Trattato de numeri perfetti předkládá prvočinitele všech čísel do 800 a tabulku prvočísel do 750. Pomocí této tabulky dělením prvočísly menšími než druhá odmocnina dokázal, že 217 − 1 = 131 071 je prvočíslem 32 a současně dokonalým číslem 216 (217 − 1) = 8 589 869 056 . Popřel tak další Nikomachovo pravidlo o střídání 6 a 8 na konci dokonalých čísel. Ověřil také, že 219 − 1 =524 287 je prvočíslem, čímž našel sedmé dokonalé číslo. Na druhé straně, ve své Utriusque Arithmeticae nesprávně tvrdil, že 2 p − 1 je prvočíslem i pro p = 23, 29, 31, 37. Na to, že se Cataldi mýlil v případě 23 a 37, upozornil Fermat v roce 1640. Euler roku 1738 ukázal, že Cataldi se mýlil i v případě 29, ale později potvrdil jeho tvrzení pro 31.

31

P. A. Cataldi (1552-1626) profesor matematiky ve Florencii i Bologni. Cataldi se pokusil založit v Bologni nejstarší známou matematickou akademii. V práci Traktát o nejkratším způsobu nalezení druhých odmocnin z čísel, Bologna 1613, poprvé navrhl počítaní odmocnin pomocí řetězových zlomků, které zapisoval tak, jak to děláme my. 32

Poznamenejme, že 750

2

= 562 500 > 131 071 .

14

Obr. 4. Deska označující náměstí Marina Mersenna v jeho rodném Oizé (v départmentu Sarthe, dříve dépt. Maine, Francie, foto M. Křížek). Mersennovým prvočíslem rozumíme číslo tvaru M p = 2 p − 1, které je současně prvočíslem. M. Mersenne 33 v roce 1644 píše, že pro p ∈ {2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257} je M p prvočíslem, zatímco pro jiné hodnoty p ≤ 257 dostaneme čísla složená. Ověření tohoto tvrzení nebylo jednoduché a trvalo až do období kolem roku 1947. V roce 1750 Euler ověřil hodnotu 31 a v roce 1867 Lucas 34 hodnotu 127. Roku 1877 Pervušin našel mezeru v Mersennově seznamu, když dokázal, že 261 − 1 je prvočíslem. Kolem roku 1900 zjistil Powers, že v seznamu chybějí i hodnoty 89 a 107. V roce 1922 ukázal Kraitchik, že exponent 257 nevede na prvočíslo. Jak bylo řečeno, teprve kolem 1947 bylo definitivně zjištěno, že Mersennův seznam má mít tvar:

p ∈ {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127}.

33

M. Mersenne, Cogitata Physico Mathematica, Paris, 1644. F. E. A. Lucas (1842-1891) pracoval po skončení studia na Ecole Normale jako asistent na pařížské observatoři a později učil matematiku na střední škole v Paříži. V roce 1975 ve francouzsko-pruské válce byl důstojníkem francouzského dělostřelectví. V roce 1885 při slavnostném udělování cen podněcoval školáky, aby napadli Německo. V matematické komunitě je známý, kromě jiného, zejména svým testem prvočíselnosti a tzv. Lucasovými čísly. Proslavil se také svými počtářskými schopnostmi. Zemřel na infekci po pořezání úlomkem spadlého talíře na společenské slavnosti. 34

15

Obr. 5. Pamětní deska věnovaná Marinu Mersennovi, iniciátorovi vědeckého života v Evropě a duchovnímu otci Francouzské akademie věd (foto P. Křížek). Mersenne později 35 tvrdil, že M p je prvočíslem, pokud p je prvočíslem, které je o 3 větší nebo menší než nějaká mocnina 2k se sudým exponentem. Podle toho by číslo M 67 mělo být prvočíslem, protože 67 = 3 + 2 6.

35

M. Mersenne, Novarum Observationum Physico-Mathematicarum, Tomus III, Parisiis 1647, Cap. 21, p. 182.

16

Obr. 6. Kostel v Oizé, v němž byl Marin Mersenne pokřtěn. Pamětní deska z obr. 5 je umístěna vpravo od vchodu. Vlevo od kostela se nachází Mersennovo náměstí (viz obr. 4, foto M. Křížek). V Cogitata Physico Mathematica 36 Mersenne dále píše: Ověření toho, že dané 15- nebo 20-místné číslo je prvočíslem, všemi známými současnými metodami by vyžadovalo celý život. Toto tvrzení by zůstalo pravdivé, kdyby se postupně na scéně neobjevily nové myšlenky a počítače. Dnes poměrně snadno zjistíme, že z čísel M p , kde p je prvočíslo, je pro p < 50 000 jenom 27 prvočísel. Není těžké nalézt kritéria, která znějí jednoduše, ale jejich realizace jednoduchá není. Např. lze nahlédnout 37, že k tomu, aby přirozené číslo n bylo Mersennovým prvočíslem, je nutné a stačí, aby n bylo prvočíslo a aby číslo n + 1 nemělo lichého prvočíselného dělitele. Proto na nalezení všech Mersennových prvočísel „postačí“ dvojnásobná aplikace Eratosthenova síta. Přijatelnější kritérium prvočíselnosti pro prvočísla p > 2 našel Lucas. 38. Původně bylo formulováno poněkud nejasně, ani jeho důkaz nebyl úplný. Lucasovo kritérium zjednodušil Derrick H. Lehmer. 39 40 Nechť S 1= 2 a S k = 2 ⋅ S k2−1 − 2 pro k = 2, 3,  . Pak pro p >2 je M p prvočíslem, právě když M p | S p −1 . Ekvivalentní formulace je: Nechť s1 = 4 a sk = sk2−1 − 2 (mod (2 p − 1)) pro k = 2,3,  . Pak pro p >2 je M p prvočíslem, právě když s p −1 = 0. K důkazu, že M 11 = 2 047 není prvočíslem, vede posloupnost

s1 ≡ 4; s2 ≡ 14; s3 ≡ 194; s4 ≡ 788; s5 ≡ 701; s6 ≡ 119; s7 ≡ 1877; s8 ≡ 240; s9 ≡ 282; s10 ≡ 1736 (mod 2047 ) .

Je zajímavé poznamenat, že zde se také ptá, které číslo má 60 dělitelů, a nalézá Platónovo řešení. 37 S. W. Golomb, Sets of primes with intermediate density, Mathematica Scandinavica 3, 1955, 270. 38 F. E. A. Lucas, Théorie des fonctions numériques simplement périodiques, American Journal of Mathematics 1, 1878, 184-240, 289-321, zejména str. 316. 39 D. H. Lehmer (1905-1991) je často nazýván otcem výpočetní teorie čísel. Navrhl více jednoúčelových zařízení pro číselně teoretické výpočty. Na protest proti mccarthismu opustil univerzitu v Berkeley a čínskou větu o zbytcích ironicky nazýval tchajwanskou zbytkovou větou. 40 D. H. Lehmer, An extended theory of Lucas functions, Annals of Mathematics 31, 1930, 419448. On Lucas' test for the primality of Mersenne's numbers, J. London Mathematical Society 10, 1935, 162-165. 36

17

Tento tzv. Lucas-Lehmerův test je velmi výhodný, protože umožňuje využívat dvojkovou soustavu používanou v počítačích. Jeho nevýhodou je, že nedává informaci o prvočinitelích. Tak např. Lucas pomocí svého testu dokázal v r. 1876 již jednou uvedený fakt, že číslo M127 , které má 39 cifer, je prvočíslem. Je to současně největší prvočíslo nalezené v předpočítačové éře. Ve stejném roce dokázal Lucas, že M 67 je složené. Ale až v roce 1903 F. N. Cole 41 faktorizoval číslo 267 − 1 , o kterém Mersenne tvrdil, že je prvočíslo. Této faktorizaci věnoval neděle tří let. V r. 1903 přednesl na půdě Americké matematické společnosti dnes již legendární přednášku beze slov, kterou Eric Temple Bell popsal slovy: Cole, beztak málomluvný člověk, přistoupil k tanuli, beze slov vzal křídu a spočítal 2 na 67-mou. Pak starostlivě odečetl 1 a jako výsledek získal číselné monstrum 147 573 952 589 676 412 927. Poté pořád beze slov, vyhledal ještě volné místo na tabuli a ručně vynásobil krok za krokem 193 707 721 ⋅ 761 838 257 287 . Když oba výpočty souhlasily, dostalo se mu bouřlivých ovací. Cole se vrátil na své místo, stále bez jediného slova. Mersennova domněnka tak zmizela ve hlubinách matematických hrdinných ság.

41

Bulletin of the American Mathematical Society 10, 1903-4, 134-137. Frank Nelson Cole (20.9. 1861-26.5. 1926) po skončení středoškolských studií se vzdělával soukromně, dříve než nastoupil v r. 1878 na Harvard. Jeho nadání mu otevřelo cestu ke stipendiu během studia a k podpoře jeho cesty do Evropy v letech 1883-85, kdy studoval u F. Kleina. Po návratu napsal disertaci A contribution to the theory of the general equation of the sixth degree, za kterou mu byla v r. 1886 udělena hodnost Ph.D. Od roku 1895 byl až do své smrti profesorem na Columbia University (jeho studenty byli kupř. Osgood a M. Bôcher). V letech 1896-1920 byl tajemníkem Americké matematické společnosti a od r. 1987 hlavním editorem Bulletinu Americké matematické společnosti. Založil dnes po něm pojmenovanou vysoce prestižní cenu z algebry a teorie čísel.

18

Obr. 7. Frank Nelson Cole. V r. 1750 formuloval Euler následující tvrzení, které úplně dokázal až Lagrange v roce 1775: Když p je prvočíslo takové, že p ≡ 3 (mod 4), pak 2 p + 1 je dělitelem čísla M p právě tehdy, když 2 p + 1 je prvočíslo. V případě, že p > 3 , je

M p složené číslo. 42 Z tohoto tvrzení okamžitě dostaneme, že M11 je dělitelné prvočíslem 23 = 2 ⋅ 11 + 1. Doposud známe nejméně (protože vývoj jde rychle kupředu) 39 Mersennových prvočísel. 43 Jmenovitě 44 pro p : 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1 279, 2 203, 2 281, 3 217, 4 253, 4 423, 9 689, 9 941, 11 213, 19 937, 21 701, 23 209, 44 497, 86 243, 110 503, 132 049, 216 091, 756 839, 859 433, 1 257 787, 1 398 269, 2 976 221, 3 021 377, 6 972 593, 13 466 917.

42

Ve skutečnosti nevíme, zda existuje nekonečně mnoho složených čísel typu

Mp .

Z tzv. Schinzelovy hypotézy H plyne, že existuje nekonečně mnoho prvočísel p takových, že i 2p+1 je prvočíslo. 43 Dvacáté páté z nich objevili osmnáctiletí kalifornští středoškoláci Curt Noll a Laura Nickel v roce 1987. 44 Pro případné další hodnoty viz http://www.utm.edu/research/primes/largest.html.

19

Existuje více názorů na počet Mersennových prvočísel. Jedna z hypotéz 45 říká, že existuje konečná nenulová limita lim x→ ∞ M ( x) / log x, kde M ( x) je počet Mersennových prvočísel nepřesahujících x.

4. Malá Fermatova věta Nikdo ještě neobjevil válečný záměr, kterému by posloužila teorie čísel nebo relativity, a je nepravděpodobné, že by se to v blízké době někomu podařilo. G. H. Hardy, Obrana matematikova

Ve studiu dokonalých a Mersennových čísel velice pokročil Pierre de Fermat. V roce 1636 píše Robervalovi, že pracuje na této problematice, v níž udělal velký pokrok, přestože je velice obtížná, a míní na to téma napsat pojednání. Dílo nebylo nikdy sepsáno. Fermat v dopisu 46 Mersennovi napsal, že zná metodu, která mu umožňuje řešit všechny otázky kolem alikvotních částí. Na tuto poznámku navázal Frénicle de Bessy47 a přes Mersenna vyzval Fermata, aby našel dokonalé číslo, které má dvacet nebo více cifer. Fermat na to odpověděl Mersennovi, 48 že dokonalé číslo s 20 nebo 21 ciframi neexistuje, což odporovalo tehdejšímu přesvědčení, že existuje dokonalé číslo mezi každými dvěma mocninami čísla 10. Přesněji píše: Našel jsem zkratku pro hledání dokonalých čísel a hned na začátku říkám, že není takové s 20 nebo 21 ciframi. To vyvrací domněnku těch, kteří věřili, že v rozsahu každé mocniny 10 existuje takové; takové jako od 1 do 10, jiné od 10 do 100, další od 100 do 1 000, atd. Tomu není tak, jak ukazuje tento příklad: od 10 000 000 000 000 000 000 do další mocniny 10 neexistuje žádné, stejně jako od této mocniny 10 po následující. Fermat později 49 oznamuje Mersennovi tři tvrzení, která je údajně schopen bez velkých potíží dokázat a která tvoří základ práce s dokonalými čísly. Tato tvrzení jsou následující: 1. Je-li n složené, je i 2n − 1 složené. 2. Je-li n prvočíslem, pak je 2n − 2 dělitelné číslem 2n . 3. Je-li n prvočíslem, pak 2n − 1 je dělitelné jedině prvočísly tvaru 2kn + 1.

45

D. B. Gilles, Three new Mersenne primes and a statistical theory, Mathematics of Computation 18, 1964, 93-97. 46 Ze dne 26.12.1638. 47 Bernard Frénicle de Bessy (1605?-1675), astronom, fyzik a číselný teoretik z Paříže. 48 Květen 1640. 49 Červen 1640.

20

Fermat pracoval s Mersennovými čísly M p asi do hodnoty p = 23. Zjistil přitom zajímavou skutečnost: Každé prvočíslo q, které dělí M p , dává zbytek 1 po dělení

p, tj.

když q | M p , pak q ≡ 1 (mod p ). Protože každý dělitel d čísla M p je součinem prvočísel, nutně d ≡ 1 (mod p ) pro každého dělitele čísla M p , speciálně i pro d = M p , tj. 2 p − 1 ≡ 0 (mod p ) .

Později Fermat zjistil 50, že základ 2 nemá v tomto tvrzení žádnou speciální roli, což jej vedlo k tvrzení, dnes nazývanému Malá Fermatova věta (MFV), výsledku, který hraje fundamentální roli v mnoha důkazech v teorii čísel a je prototypem důležitých vět algebry: 51 Malá Fermatova věta: nesoudělné s p platí

Když p je prvočíslo, pak pro každé b b p −1 ≡ 1 (mod p ).

Velikou úlevou při hledání faktorů Mersennových čísel bylo právě třetí tvrzení, které si zde dokážeme, abychom ukázali roli MFV: Když p > 2 je prvočíslo, pak prvočíselní dělitelé čísla 2 p − 1 jsou tvaru 2kp + 1. D ů k a z: Nechť q > 2 je prvočíselným dělitelem čísla 2 p − 1. Nechť d označuje nejmenší exponent, pro který q | 2 d − 1 . Zřejmě d > 1. Z minimálnosti d plyne: když 2 x ≡ 1 (mod q ), pak d | x. Pak nutně d | p , protože q | 2 p − 1 . Jelikož d > 1, platí d = p. Z MFV plyne q | 2 q −1 − 1 , což z předchozího implikuje, že d | q − 1 . Na druhé straně jsme viděli, že d = p, a proto q − 1 = tp pro t přirozené. Protože p je liché a q − 1 je sudé, číslo t musí být sudé, tj.= q 2kp + 1. Když chceme ověřit, že číslo 2 047 = 211 − 1 je prvočíslo, pak použitím nejjednodušší techniky, jakou je Eratosthenovo síto,52 potřebujeme toto číslo vydělit všemi lichými prvočísly ne většími než 2047 < 46. Tato jsou 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 a 43. Použitím uvedeného tvrzení dostaneme, že mezi těmito 50

Dopis Fréniclu de Bessy ze dne 18.10.1640. W. Sierpiński uvádí ve své Teoria liczb, II, PWN, Varšava 1959, str. 177, že podle H. Barycze (Dzielo literacke Jana Brożka, Pamiętnik Literacki XLV, 1954, sešit 1, str. 3) tento výsledek objevil před Fermatem Jan Brożek (1585-1672), profesor Krakovské akademie. 52 Připomeňme jen, že v původní formě Eratosthenova síta se vyškrtávají postupně všechny celé násobky. Škrtání pouze násobků prvočísel menších než druhá mocnina prověřovaného čísla navrhl poprvé Leonardo Pisano (Fibonacci) ve své Liber Abaci vydané v r. 1202 v Bologni. 51

21

prvočísly je jenom jediné, které je tvaru 22k + 1 , a to 23 . To skutečně vede na faktorizaci 2 047 = 23 ⋅ 89 , tj. M 11 je složené. Použitím tohoto výsledku pravděpodobně nahlédl Fermat, že Cataldiho domněnka o prvočíselnosti čísla 223 − 1 není správná, což sdělil Mersennovi dopisem v červnu 1640. Frénicle de Bessy začal komunikovat s Mersennem v r. 1634 a asi od poloviny roku 1640 přímo s Fermatem. Jejich vzájemná korespondence obsahovala nejméně 11 dopisů, z nichž jenom šest je známých v plném rozsahu. 53 Když Frénicle vyzval k nalezení dokonalého čísla „qui ayt 20 lettres, ou le prochainement suivant“, tak s největší pravděpodobností znal M 31 , které, jak vidíme z tabulky, má 19 cifer. Následující prvočíslo připadající v úvahu je pro p = 37. To však vede na číslo v hranicích mezi 94 ⋅ 10 20 a 95 ⋅ 10 20 , tj. k číslu s 22 ciframi. Existují náznaky, že si Fermat původně myslel, že toto číslo dává dokonalé číslo. V polovině června 1640 píše Mersennovi: Konečně, vy nebo já jsem udělal chybu v některých cifrách čísla, o kterém jsem si myslel, že je dokonalé, kterou lehce poznáte, protože jsem dal 137 438 953 471 pro jeho kmen, pro které jsem mezičasem našel zkratkou pomocí mého třetího tvrzení, že je dělitelné číslem 223. Udané číslo je 237 − 1 . Podle Fermatova třetího tvrzení stačí ověřit dělitelnost pro 75, 149 a 223. Weil 54 si myslí, že se jednalo o nastraženou past, do níž se Fermat téměř chytil. 55 Je velmi nepravděpodobné, že by se Fermat nepokoušel i o faktorizaci dalšího kandidáta p = 41, jehož nejmenší prvočíselný faktor je poměrně velký: 13 367. Na druhé straně nejmenší prvočíselný faktor čísla 243 − 1 je malý: 431. Fermat nikdy nepublikoval důkaz MFV, přestože tvrdil, že jej může kdykoli dodat. První publikovaný důkaz tohoto výsledku pochází od Eulera z r. 1736. První důkaz 56 podal Euler 57 nejdřív pro prvočíselný modul. Důkaz byl založen na binomické větě

(a + b ) p

= a p + b p (mod p ) .

Gauss 58 zakládá svůj důkaz na její polynomiální verzi 53

C. R. Fletcher, A reconstruction of the Frénicle-Fermat correspondence, Historia Mathematica 18, 1991, 344-351. 54 A. Weil, Number Theory, Birkhäuser, Boston 1983, str. 55. 55 I když je možné, že s částečnou pomocí Frénicla de Bessy z ní vycouval. Nezapomínejme, že i když Frénicle de Bessy nebyl matematikem Fermatova formátu, jako samouk dosáhl pozoruhodných výsledků a je často označován po Fermatovi za druhého francouzského číselného teoretika své doby. Od r. 1666 byl členem Francouzské akademie věd. 56 Podle Gausse (Disquisitiones Arithmeticae v poznámce k článku 50) důkaz měl i G. W. Leibniz; viz. Leibnizens Math. Schriften, (G. J. Gerhardt ed.) 18, 1640. Stejný důkaz jako Leibniz našel i A. Cauchy, Mém. Acad. Sci. Paris 2, 1841, 79-81; Oeuvres, (1), 3, 163-164. 57 Petrop. Comm. 8, 1736, str. 141 = Comm. Ar. Coll. 1, str. 21; podobný důkaz našel i J. H. Lambert, Act. Erudit. 1769, str. 109.

22

(a + b + c +

 ) = a p + b p + c p +  (mod p ) . p

Důkaz založený na jiném postupu podal Lagrange. 59 Hlavní myšlenka vychází z rozvoje součinu ( x + 1) ( x + 2 )  ( x + p − 1) . Později Euler 60 našel další důkaz, který spočívá na stejné myšlence jako jeden z Gaussových důkazů. 61 Euler nakonec zobecnil62 Fermatovou větu na libovolný modul. K její fomulaci potřebuje definovat novou funkci: Eulerova funkce 63 ϕ (n ) je definována jako počet přirozených čísel nepřevyšujících n , která jsou nesoudělná s n. Eulerova - Fermatova věta pak zní: Pro každé přirozené n a každé celé číslo a nesoudělné s n platí a − 1 ≡ 0 (mod n). ϕ (n)

Jak Malá Fermatova věta, tak i její Eulerovo zobecnění přitahovaly (a stále přitahují) pozornost pro svoji jednoduchost a důležitost, s cílem najít jejich další zobecnění. Uveďme jenom několik z nich. P. A. MacMahon 64 ověřil 65 MFV tím, že dokázal, že počet cyklických permutací s opakováním p různých prvků n -té třídy se rovná 1 ϕ (d ) p n / d . ∑ n d |n Když n je prvočíslo, dostaneme odtud p n + (n − 1) p ≡ 0 (mod n), tj.

p n ≡ p (mod n).

Tímto způsobem je možné dokázat i Eulerovo rozšíření. 66

Disquisitiones Arithmeticae, čl. 51. Ac. De Berlin, Nouv. mém. 2 (1773), année 1771, str. 125 = Oeuv. 3, str. 425. 60 Petr. Comm. nov. 7 (1758/59), str. 49 = Comm. Ar. coll. 1, str. 260. 61 Disquisitiones Arithmeticae, čl. 49. 62 Petrop. Comm. nov. 8 (1760/61), str. 74 = Comment. Ar. coll. 1, str. 274. 63 Označení ϕ ( n) použil poprvé Gauss (Disquisitiones Arithmeticae, čl. 38), který tuto funkci zavedl. Přesto se používá označení Eulerova funkce, protože Euler (Petrop. N. Comment. 8, 1760/61, str. 74 = Comm. Arithm. coll. 1, str. 531) jako první udal její obecný vztah pro mocniny prvočísel. 64 Percy Alexander MacMahon byl majorem v British Royal Artillery a byl znám jako skvělý počtář. Pomocí rekurentního vztahu pro počet p(n) vyjádření přirozeného čísla n jako součet přirozených čísel určil přesné hodnoty p(n) pro n nepřesahující 200. Např. p(200) = 3 972 999 029 388. Ve svých pracích z kombinatorické teorie permutací dokázal mnoho zajímavých výsledků. 65 Proc. London Math. Soc. 23, 1891-2, 305-313. 66 Jiné důkazy založené na permutacích (nebo modifikacích) podali: J. Petersen, Tidsskrift for Mathematik (3), 2, 1872, 64-65 (dánsky); Petersen tu hlavně dokazuje Wilsonovou větu, ale speciální volbou dostává i MFV. Petersenův důkaz Wilsonovy věty objevil i K. Petr v Časopise pro pěstování mathematiky a fysiky 34, 1905, 164; J. Perrot, Bull. des Sc. Math. 24, I, 1900, 175; Bricard, Nouv. Ann. Math. (4), 3, 1903, 340-342. 58 59

23

Jacobi 67 jako první obrátil pozornost k úloze vyšetřovat, kdy kongruence a p −1 ≡ 1 (mod p ) pro nějaké a ∈ {1, 2, ... , p − 1} platí i pro modulo p 2 . V tomto směru pak pokračovali Eisenstein, 68 Stern, 69 Mirimanoff 70 a Sylvester. 71 Dnes víme, že MFV je speciálním případem Lagrangeovy věty z teorie grup, která říká: V každé konečné grupě je řád každého prvku dělitelem řádu grupy. V našem případě konečnou grupou je multiplikativní grupa Z *n redukovaných zbytkových tříd modulo n. V případě, že n je prvočíslo, je tato grupa navíc cyklická. V obecném případě Eulerova funkce ϕ (n) udává vlastně řád grupy Z *n . Budeme-li pokračovat v této grupové terminologii, pak víme, že řád grupy není nejmenším číslem s touto vlastností. Tím nejmenším číslem je tzv. exponent grupy, který dostaneme jako nejmenší společný násobek řádů všech prvků dané konečné grupy. Zobecnění EulerovyFermatovy věty nalezená ve snaze použít ji jako test prvočíselnosti vedla k tomu, že první formuli pro tento exponent objevil v případě Z *n matematik Carmichael. 72 Dnes nazýváme Carmichaelovou funkcí:

1   α −2 2  λ (n ) =  ϕ (n )  α  n.s.n. λ p i ; i = 1,  , k

{( )

}

pro pro pro pro

n = 1, n = 2α , α > 2, n = 2, 4 nebo p α pro liché p, n = p1α i  p kα i ,

kde ϕ je Eulerova funkce, p a p1 < p 2 <  < p k jsou prvočísla a kde n.s.n. je nejmenší společný násobek. O obecně rozdílných hodnotách obou funkcí svědčí následující tabulka:

n 2 ϕ ( n) 1

6

8

15 18 21 24 32 36 42 63 70 80

2

4

8

6

12

8

16 12 12 36 24 32

67

Journ. f. Math. 3, 1828, 301. Berl. Monatsber. 1850, str. 41. 69 Journ. f. Math. 100, 1887, str. 182. 70 Journ. f. Math. 115, 1895, str. 295. 71 C.R. Paris 52, 1861, str. 161. 72 Americký matematik Robert Daniel Carmichael (1879 - 1967), jehož široký matematický záběr zahrnoval reálnou analýzu, diferenciální rovnice, matematickou fyziku, teorii grup a teorii čísel. Jeho PhD disertace z r. 1911 z Princetonu, napsaná pod vedením G. D. Birkhoffa, byla prvním významným americkým příspěvkem k teorii diferenciálních rovnic. Note on a new number theory function, Bulletin of the American Mathematical Society 16, 1909/10, 232-238. 68

24

λ ( n)

1

2

2

4

6

6

2

8

6

6

6

12

4

Carmichaelova funkce vede k výsledku, že nejefektivnější (vzhledem k velikosti exponentu) je následující verze Eulerovy-Fermatovy věty: Pro každé přirozené n > 1 a každé celé číslo a nesoudělné s n platí a λ ( n ) − 1 ≡ 0 (mod n). „Nevýhodou“ této formulace je, že neplatí pro všechna a. Z tohoto pohledu našel univerzální zobecnění P. Bachmann, 73 podle něhož platí: 74 Nechť n = p1α1 ... pkα k je rozklad čísla na mocniny různých prvočísel. Pak pro každé a je a H ( n ) + λ ( n ) ≡ a H ( n ) (mod n), kde H (n) = max{α1 ,..., α k }. Čísla H (n) a λ (n) jsou nejmenší možná, pro která kongruence platí pro každé a.

5. Fermatovská pseudoprvočísla Problém rozlišení prvočísel od čísel složených a rozkladu složených čísel na prvočísla je jedním z nejdůležitějších a nejužitečnějších v celé aritmetice. Carl Friedrich Gauss

V nedávné minulosti vzrostl z důvodu silného zájmu o faktorizaci celých čísel zájem o MFV jako prostředku ke zjišťování, zda konkrétní číslo je složené či nikoliv. A právě MFV byla jedním z prvních nástrojů v tomto směru, jak již naznačily předchozí řádky. Hlavní problém je v tom, že MFV se v obecnosti nedá obrátit, tj. pokud platí tvrzení věty a p −1 ≡ 1 (mod p ) pro nějaké a, pro které (a, p ) = 1, pak p ještě nemusí být prvočíslo. Lucas 75 uvádí příklad n = 2 701 = 73 ⋅ 37 . Vidíme, že 29 ≡ 1 (mod 73), a proto též 236 ≡ 1 (mod 73). Protože 236 ≡ 1 (mod 37), pak spojením dostaneme 236 ≡ 1 (mod n). Jelikož n − 1 = 36 ⋅ 75 , protipříklad platí. Nejmenším protipříkladem je číslo 341 = 11 ⋅ 31 , pro

73

P. Bachmann, Niedere Zahlentheorie, I, 1902, 157-158; II, 1910, 43-44. Pro další zobecnění viz M. Laššák, Š. Porubský, Fermat-Euler theorem in algebraic number fields, Journal of Number Theory 60, 1996, 254-290. 75 F. E. A. Lucas, Théorie des nombres, 1891, str. 422. 74

25

které 2 340 ≡ 1 (mod 341) . Tato vlastnost čísla 341 byla poprvé zaznamenána v r. 1830. 76 Logická konverze MFV dává následující „fermatovský test složenosti“: Jestliže neplatí a N −1 ≡ 1 (mod N ) pro nějaké a splňující (a, N ) = 1, pak N je složené.

Obr. 8. Pierre de Fermat.

76

Anonymous, Théorèmes et problèmes sur les nombres; Journal für die reine und angewandte Mathematik 6, 1830, 100-106.

26

Poznamenejme, že tento fermatovský test je výpočetně velmi výhodný, vyžaduje nejvíce 2 log 2 N kroků, kde pod krokem rozumíme násobení dvou čísel modulo N a následnou redukci modulo N . Tento odhad souvisí se skutečností, že složitost výpočtu a d (mod N ) závisí na počtu jedniček v binárním rozvoji čísla d , který se pohybuje od

log 2 d  do 2 log 2 d  , což v průměru vede k odhadu 1,5 log 2 d  . Pro d= N − 1 dostaneme průměrný počet nutných násobení a redukcí (mod N ) rovný přibližně 1,5 log 2 N  , což je tzv. algoritmus polynomiálního řádu. Když použijeme základ a = 3, pak číslo 341 propadne: 340 3 = 56 (mod 341) , tj. 341 je skutečně složené. Liché složené číslo N , pro které a N −1 ≡ 1 (mod N ) se nazývá (fermatovské) pseudoprvočíslo při základu a. Snadno lze ověřit, že existuje 245 fermatovských pseudoprvočísel menších než 1 000 000 , zatímco existuje 78 498 prvočísel pod touto mezí. Z výpočtů plyne, 77 že existuje 21853 fermatovských pseudoprvočísel při základu 2 mezi čísly menšími než 25 ⋅ 10 9 . Když je prozkoušíme i pro základ 3, pak z nich zůstane jenom 4 709 . Z nich dále přežije základ 5 jenom 2 552 a základ 7 již jen 1 770. Otázka, zda přijatelnou volbou základů můžeme eliminovat fermatovská pseudoprvočísla v testech prvočíselnosti, má zápornou odpověď. Složená čísla N , která mají tu vlastnost, že a N −1 ≡ 1 (mod N ) pro každé a splňující (a, N ) = 1, existují a nazývají se Carmichaelova. 78 Nejmenší z nich je 561 = 3 ⋅ 11 ⋅ 17 . Existuje 2 163 Carmichaelových 79 prvočísel menších než 25 ⋅ 10 9 . Po dlouhém úsilí matematiků se podařilo W. R. Alfordovi, A. Granvillemu a C. Pomerancemu 80 dokázat, že existuje nekonečně mnoho Carmichaelových čísel. 81 Chceme-li najít obrácení MFV, je třeba analyzovat uvedený Lucasův protipříklad. Budiž k nejmenší exponent, pro který a k ≡ 1 (mod n). Pak 77

C. Pomerance, J. L. Selfridge, S. S. Wagstaff, The pseudoprimes to 25.109, Mathematics of Computation 35, 1980, 1003-1026. P -1

(

)

On composite numbers P which satisfy the Fermat congruence A ≡ 1 mod P , American Mathematical Monthly 19, 1912, 22-27. 79 Pro pozorného čtenáře necháme k zodpovězení otázku, jak je možné, že existuje „víc“ Carmichaelových čísel pod hranicí 25.109, než oněch 1770 čísel, která nejsou fermatovskými pseudoprvočísly při základech 2, 3, 5 a 7. 80 W. R. Alford, A. Granville, C. Pomerance, There are infinitely many Carmichael numbers, Annals of Mathematics (2) 139, No.3, 1994, 703-722. 81 Přehled a diskusi výsledků kolem Carmichaelových čísel najde čtenář v práci C. Pomerance, Carmichael numbers, Nieuw Archiv foor Wiskunde, IV. Ser., 11, No. 3, 1993, 199-209. 78

27

je možné jednoduše dokázat, že k | ϕ (n), tj. k ≤ ϕ (n). Když k= n − 1 pro nějaké a, pak z výše uvedené dělitelnosti plyne n − 1 ≤ ϕ (n). Na druhé straně, z definice ϕ (n) plyne, že ϕ (n) ≤ n − 1. Ovšem rovnost n −1 = ϕ (n) je možná, jedině když n je prvočíslo. Tímto způsobem Lucas 82 dokázal následující obrácení MFV: Jestliže je a x − 1 dělitelné číslem x pro x= n − 1, ale žádným dělitelem čísla n − 1, který je menší n − 1 , pak n je prvočíslo. Např. pro a = 3 a n = 65537 = 216 + 1 jsou mocniny 1, 2, 22 , 23 , ... , 216 dělitelé čísla n − 1. Ovšem jedině pro x = 216 je 3 x = 1 (mod 65 537 ) , a proto 65 537 je prvočíslem. D. H. Lehmer přeformuloval Lucasův výsledek následujícím způsobem: Nechť N − 1 =p1β1 ... pkβ k je rozklad čísla N − 1 na součin mocnin různých prvočísel. Když existuje a takové, že pro každé j = 1, 2, ... , k neplatí ( N −1) / p j a ≡ 1 (mod N ), ale platí a N −1 ≡ 1 (mod N ), pak N je prvočíslem. Myšlenka důkazu této věty spočívá na faktu, že pokud N je prvočíslo, pak pro řád ϕ (n) grupy nesoudělných tříd platí ϕ ( N= ) N − 1. Pokud N je složené, je ϕ ( N ) < N − 1. Navíc je tato grupa v případě prvočísla cyklická, tj. generovaná jedním svým prvkem, který musí být řádu N − 1. Uvedené podmínky garantují, že takový prvek existuje. Je poměrně málo známou skutečností, že jedním z prvních, kdo se zajímal o obrácení MFV, byl János Bolyai. 83 V jednom nedatovaném dopisu píše svému otci: Nepochybuji, že se mi velice brzo podaří najít formuli pro prvočísla. Přitom měl na mysli nejenom racionální prvočísla, ale i prvočísla v oboru Gaussových celých čísel. „Hlavní zbraní“ přitom měla být s největší pravděpodností MFV. V dopisu otci z května 84 1855 informuje o objevu, že 341 je pseudoprvočíslem při základu 2 (v naší terminologii). Při té příležitosti objevil i výsledek, že pokud p a q

82

F. E. A. Lucas, Théorie des nombres, 1891, str. 423, 441. J. Bolyai (1802-1860), jeden z objevitelů neekleidovkých geometrií. 84 E. Kiss, Notes on János Bolyai's researches in number theory, Historia Mathematica 26, 1999, 68-76. 83

28

jsou různá prvočísla (tj. 2 p −1 ≡ 1 (mod p ) a 2 q −1 ≡ 1 (mod q ) ) , pak 2 pq −1 ≡ 1 (mod pq ) ; tento výsledek je často připisován Jeansovi. 85

6. Wilsonova věta Stěží se najde matematik, který by neztratil spoustu času na to, aby odhalil tajemství prvočísel. Leonhard Euler

Příbuzný výsledek k MFV, známý dnes pod jménem Wilsonova věta, publikoval v r. 1770 Edward Waring 86 a připsal jej Siru Johnu Wilsonovi (1741-1793): Je-li p je prvočíslo, pak součet 1 + 1.2  ( p − 1) je dělitelný číslem p.

Tento výsledek v následující modifikové formě byl objeven i v rukopisu Leibnizově 87: Je-li p je prvočíslo, pak ( p − 1) ! ≡ 1 (mod p ) . V roce 1773 Lagrange publikoval 88 první důkaz tohoto výsledku a též dokázal, že tvrzení platí i obráceně: když 1 + 1.2...(n − 1) je dělitelné n, pak n je prvočíslo. To ukazuje, že tvrzení je ekvivalentní prvočíselnosti. Protože ( p − 1)! může být obrovské číslo, 89 je tento výsledek nepoužitelný pro testování prvočíselnosti. Na druhé straně je zajímavé, že Lagrange odvodil MFV z Wilsonovy věty. 85

J. H. Jeans, The converse of Fermat's theorem, Messenger of Mathematics 27, 1897/98, 174. Meditationes Algebraicae, Cambridge 1770, str. 218, 3 .vydání 1782, str. 380. 87 G. W. Leibniz, Manuscrits inédits conservés à Bibliothèque de Hannover et publiés dans le Formulaire de Mathématique, t. 2, N.3,1899, par M.Vacca, t. 3., B. 11, fol. 10. 88 Nouv. Mém. Acad. Roy. Berlin 2, 1773, anneé 1771, p. 125 = Oeuvres 3, 1869, str. 425. 89 Ze Stirlingova vzorce (J. Stirling, Methodus differentialis, Londýn 1730, str.135) dostaneme, 86

pro jisté neboli 0 <θ <1 2πn exp(− n + θ / (12 n )) n n − n 1/12 n Tyto nerovnosti jsou těsné pro velké n 2πn < n ! < n e e 2πn .

že

n != n

n

hodnoty n, protože e ≈ 1. Logaritmováním získáme odhad počtu cifer. Např. pro n = 10 000 dostaneme log 10 000! ≈ 35 659,454, protože log e ≈ 0,43429, log π ≈ 0,49715, log 2 ≈ 0,30103 . 10 000! má 35 660 dekadických cifer. 1/12 n

29

Další důkaz Wilsonovy věty podal Euler. 90 Gauss našel další dva91 její důkazy. První spočívá na binomických kongruencích a druhý na teorii tzv. „asociovaných čísel (socii)“. Druhý přístup mu umožnil rozšířit Wilsonovou větu na libovolný modul: 92 Nechť P je součinem čísel menších než A a nesoudělných s A. Pak číslo P + 1 je dělitelné číslem A, pokud A ∈ {3, p m , 2 p m }, kde p je liché prvočíslo. Pokud A nemá jeden z těchto uvedených tvarů, pak A dělí P − 1. Spojením Malé Fermatovy věty a Wilsonovy věty dostaneme kritérium prvočíselnosti: 93 K tomu, aby liché číslo p > 1 bylo prvočíslem, je nutné a stačí, aby platilo p | ( p − 1) ! + 2 p −1 . *** Mezi problémy, které jsou v matematice vyšetřovány, neexistují takové, které by se v současnosti považovaly za méně plodné a méně užitečné než problémy, týkající se podstaty čísel a jejich dělitelů. V tomto směru se soudobí matematikové silně odlišují od starověkých, kteří připisovali bádání tohoto druhu mnohem větší význam … Ti nejenom považovali hledání jistoty za chvályhodné samo o sobě a důstojné lidského poznání, ale kromě toho se naprosto správně domnívali, že se tím pozoruhodným způsobem rozvíjí vynalézavost a před lidským intelektem se takto otvírají nové možnosti řešení spletitých úloh … Matematika by pravděpodobně nikdy nedosáhla takového vysokého stupeně dokonalosti, kdyby ve starověku nevynaložili tolik úsilí na studium problémů, kterými dnes mnozí opovrhují pro jejich zdánlivou marnost … Leonhard Euler

Adresa: Prof. RNDr. Štefan Porubský, DrSc., Ústav matematiky, Vysoká škola chemicko-technologická, Technická 5, 166 28 Praha 6, e-mail: [email protected] „ Skutečná“ matematika „skutečných“ matematiků, 90

Opusc. analyt., Petrop. 1773, I str. 329 = Comm. ar. coll. 2, str. 44. C. F. Gauss, Disquisitiones Arithmeticae, Lipsko 1801, čl. 76 a 77. 92 Viz též M. Laššák, Wilson's theorem in algebraic number fields, Mathematica Slovaca 50, 2000, 303-314. 93 W. Sierpiński, Teoria liczb, sv. II, PWN Warszawa 1959, str. 216, cvič. 4. Odpověď na otázku v poznámce č. 78 pod čarou: 91

(

)

Číslo dělitelné 2, 3, 5, nebo 7 nutně propadne u fermatovského testu, kde a , N > 1 . Rozdíl 393 = 2 163 – 1 770 vznikne Carmichaelovými čísly, která jsou dělitelná alespoň jedním z těchto čísel.

30

matematika Fermatova, Eulerova, Gaussova, Abelova a Riemannova, je skoro celá „neužitečná“ (a to platí jak o „aplikované“, tak o „čisté“ matematice). G. H. Hardy, Obrana matematikova

31