15 n = a (m). Mezi dělitele čísla m přitom patří čísla m i n (a protože »22 _ 2k+1 — 1 > 1? jsou tato čísla nutně různá), proto 2k+1 ■ n = a (m) >m + n = 2k+1 ■ n, a tedy o~(m) = m + n. To znamená, že m je prvočíslo s jedinými děliteli m a n = 1, odkud a = 2k ■ (2k+1 — 1), kde 2k+1 — 1 = m je prvočíslo. □ poznámka. Na druhou stranu, popsat lichá dokonalá čísla se dodnes nepodařilo, dokonce se ani neví, jestli vůbec nějaké liché dokonalé číslo existuje. Mersenneho prvočísla jsou právě prvočísla tvaru 2k — 1. Není bez zajímavosti, že právě Mersenneho prvočísla jsou mezi všemi prvočísly nejlépe „vidět" - pro Mersenneho čísla existuje poměrně jednoduchý a rychlý postup, jak ověřit, že jde o prvočísla. Proto není náhodou, že největší známá prvočísla jsou obvykle tvaru 2k — 1. Jakkoliv může být hledání největšího známého prvočísla chápáno jako pochybná zábava bez valného praktického užitku2, jednak posunuje hranice matematického poznání a zdokonaluje použité metody (a často i hardware), navíc může přinést benefit i samotným objevitelům (Electronic Frontier Foundation vypsala odměny EFF Cooperative Computing Awards za nalezení prvočísla majícího alespoň 106,107,108 a 109 číslic - odměny 50, resp. 100 tisíc dolarů za první dvě kategorie byly vyplaceny v letech 2000, resp. 2009 - v obou případech projektu GIMPS - na další odměny si ještě zřejmě nějaký čas počkáme). 2.2. Rozložení prvočísel. There are two facts about the distribution of prime numbers. The first is that, [they are] the most arbitrary and ornery objects studied by mathematicians: they grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision. Don Zagier příklad. Dokažte, že pro libovolné přirozené číslo n existuje n po sobě jdoucích přirozených čísel, z nichž žádné není prvočíslo. Řešení. Zkoumejme čísla (n + 1)! + 2, (n + 1)! + 3,..., (n + 1)! + (n + 1). Mezi těmito n po sobě jdoucími čísly není žádné prvočíslo, protože pro libovolné k g {2,3,... ,n + 1} platí k | (n + 1)!, a tedy k I (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo. □ 2Viz např. titulek iDnes z 6.února 2013: Největší známé prvočíslo na světě má 17 milionů číslic a je k ničemu 16 PŘÍKLAD. Dokažte, že pro každé celé n > 2 existuje mezi čísly n a n\ alespoň jedno prvočíslo. řešení. Označme p libovolné prvočíslo dělící číslo n\ — 1 (takové existuje podle věty 7, protože n\ — 1 > 1). Kdyby p < n, muselo by p dělit číslo n\ a nedělilo by n\ — 1. Je tedy n < p. Protože p | (n\ — 1), platí p < n\ — 1, tedy p < n\. Prvočíslo p splňuje podmínky úlohy. □ Nyní uvedeme několik důkazů toho, že existuje nekonečně mnoho prvočísel (i když tvrzení v podstatě vyplývá už z předchozího příkladu). VĚTA 8. Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. DŮKAZ. (Eukleides) Předpokládejme, že prvočísel je konečně mnoho a označme je p±,P2, ■ ■ ■ ,pn- Položme N = pľ-p2 .. .pn + l. Toto číslo je buď samo prvočíslem nebo je dělitelné nějakým prvočíslem různým od Pi,... ,pn (čísla pi,... ,pn totiž dělí číslo N — 1), což je spor. (Kummer, 1878): Předpokládejme, že prvočísel je konečně mnoho a označme je p\ < p2 < ■ ■ ■ < pn. Položme N = p\ ■ p2 • • • pn > 2. Číslo N — 1 je podle věty 7 dělitelné některým prvočíslem pi, které dělí zároveň číslo N a tedy i N — (N — 1) = 1. Spor. (Fúrstenberg, 1955): V této poznámce uvedeme elementární „topologický" důkaz existence nekonečně mnoha prvočísel. Zavedeme topologii prostoru celých čísel pomocí báze tvořené aritmetickými posloupnostmi (od — oo do +00^. Lze snadno ověřit, že jde skutečně o topologický prostor, navíc lze ukázat, že je normální a tedy metrizovatelný. Každá aritmetická posloupnost je uzavřená i otevřená množina (její komple-ment je sjednocení ostatních aritmetických posloupností se stejnou diferencí). Dostáváme, že sjednocení konečného počtu aritmetických posloupností je uzavřená množina. Uvažme množinu A = UAP, kde Ap je tvořena všemi násobky p ap probíhá všechna prvočísla. Jediná celá čísla nepatřící do A jsou —lala protože množina { — 1,1} zřejmě není otevřená, množina A nemůže být uzavřená. A tedy není konečným sjednocením uzavřených množin, což znamená, že musí existovat nekonečně mnoho prvočísel. □ PŘÍKLAD. Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3A; + 2, kde k E N0. řešení. Předpokládejme naopak, že existuje pouze konečně mnoho prvočísel tohoto tvaru a označme je p\ = 2, p2 = 5, p% = 11, ..., pn. Položme N = 3p2 ■ p%.....pn + 2. Rozložíme-li N na součin prvočísel podle věty 7, musí v tomto rozkladu vystupovat aspoň jedno prvočíslo p tvaru 3A; + 2, neboť v opačném případě by bylo N součinem prvočísel 17 tvaru 3A; + 1 (uvažte, že N není dělitelné třemi), a tedy podle příkladu na str. 5 by bylo i N tvaru 3k + l, což neplatí. Prvočíslo p ovšem nemůže být žádné z prvočísel p±,P2, ■ ■ ■ ,pn, jak plyne z tvaru čísla N, a to je spor. □ POZNÁMKA. Analogicky se dokáže i tvrzení o prvočíslech tvaru Ak+3, bohužel na obecný případ nám naše omezené prostředky nestačí. V kapitole o kvadratických kongruencích budeme alespoň schopni dokázat obdobné tvrzení pro prvočísla tvaru Ak + 1. Poslední příklad (o nekonečnosti počtu prvočísel tvaru 3k + 2) zobecňuje Díríchletova věta o aritmetické posloupností: VĚTA 9. (Díríchletova) Jsou-li a,m nesoudělná přirozená čísla, existuje nekonečně mnoho přirozených čísel k tak, že mk+a je prvočíslo. Jinými slovy, mezí čísly l-m+a,2-m+a, 3-m+a,... existuje nekonečně mnoho prvočísel. DŮKAZ. Jde o hlubokou větu teorie čísel, k jejímuž důkazu je zapotřebí aparát značně přesahující její elementární část. Viz např. [3, kap. 16, s. 249-257] □ POZNÁMKA. Dirichletovo tvrzení je ve skutečnosti daleko hlubší, říká totiž, že zvolíme-li libovolnou zbytkovou třídu modulo m, pak v ní buď není (až na jednu možnou výjimku) žádné prvočíslo, nebo je ve všech takových třídách prvočísel „zhruba stejně" (tj. pravděpodobnost, že náhodně zvolené prvočíslo bude patřit do konkrétní třídy, je pro všechny třídy stejná a je rovna -t^t)- Předchozí příklady je možné značně zobecnit. Platí totiž tvrzení, které bývá nazýváno Bertrandovým postulátem nebo Cebyševovou větou: VĚTA 10. (Čebyševova) (1) libovolné přirozené číslo n > 5 existují mezí čísly n a 2n alespoň dvě prvočísla. (2) Pro každé číslo n > 3 existuje mezí čísly n a 2n — 2 alespoň jedno prvočíslo. DŮKAZ. Důkaz lze provést elementárními prostředky, je však poměrně dlouhý, proto zde není uveden. □ Z tvrzení uvedených v této kapitole je možné si udělat hrubou představu o tom, jak „hustě" se mezi přirozenými čísla prvočísla vyskytují. Přesněji (i když „pouze" asymptoticky) to popisuje tzv. „prime number theorem", dokázaná nezávisle J. Hadamardem a Ch. J. de la Vallée-Poussinem v roce 1896. 18 VĚTA 11. (o hustotě prvočísel) Nechť tt(x) udává počet prvočísel menších nebo rovných číslu x G IR. Pak ir(x) ~ Inx tj. podíl funkcí tt(x) a x/ \nx se pro x —> oo limitně blíží k 1. Hustotu rozmístění prvočísel v množině přirozených čísel, rovněž částečně popisuje následující Eulerův výsledek. VĚTA 12. (Euler) Je-li P množina všech prvočísel, pak peP POZNÁMKA. Přitom např. X^neN ~t? = ^eT' co^ znamená, že prvočísla jsou v N rozmístěna „hustěji" než druhé mocniny. DŮKAZ. Buď n libovolné přirozené číslo a Pi,... ,pn(n) všechna prvočísla nepřevyšující n. Položme 7r(n) K ' í 1 \ M-)-n(i-ä i=l Jednotlivé činitele lze chápat jako součet geometrické řady, proto u(n) / 00 1 \ 1 i=l V=0 ťí 7 Pl " 'Pir(n) kde sčítáme přes všechny 7r(n)-tice nezáporných celých čísel (a1}..., ctn(n)] Protože každé číslo nepřevyšující n se rozkládá pouze na prvočísla z množiny {pi,... ,pn(n)}, Je určitě každé takové číslo v tomto součtu zahrnuto. Tedy X(n) > 1 + | + • • • + ^, a protože harmonická řada diverguje, je i limn^oo \(n) = oo. S využitím rozvoje funkce ln(l+rr) do mocninné řady dále dostáváme 7r(n) 7r(n) oo ln A(n) = -Eln(1-Ä)=EE W)"1 = i=l i=l m=l 7r(n) oo =vr + • • •++ E E wr1 • i=l m=2 Protože vnitřní součet lze shora odhadnout jako oo oo X) ("»prr1 což jsme chtěli dokázat. □ SW UKÁZKA. O tom, jak odpovídá asymptotický odhad tt(x) ~ x/\n(x), v některých konkrétních příkladech vypovídá následující tabulka (získaná s využitím funkce primepi(x) v Pari-GP. ? v=[100,1000,10000,100000,500000]; ? for(k=l,5,print(v[k],primepi(v[k]),"&",\ v[k]/log(v[k]) ,"&",\ (primepi(v[k])-v[k]/log(v[k]))/primepi(v[k]))) x tt(x) x/\n(x) relativní chyba 100 25 21.71 0.13 1000 168 144.76 0.13 10000 1229 1085.73 0.11 100000 9592 8685.88 0.09 500000 41538 38102.89 0.08 OZNAČENÍ. Pro libovolné prvočíslo p a libovolné přirozené číslo n je podle věty 7 jednoznačně určen exponent, se kterým vystupuje p v rozkladu čísla n na prvočinitele (pokud p nedělí číslo n, považujeme tento exponent za nulový). Budeme jej označovat symbolem vp(n). Pro záporné celé číslo n klademe vp(n) = vp(—n). Podle důsledku 2 můžeme právě zavedené označení vp(n) charakterizovat tím, že pvp(n"> je nejvyšší mocninou prvočísla p, která dělí číslo n, nebo tím, že n = pvp(n) ■ m, kde m je celé číslo, které není dělitelné číslem p. Odtud snadno plyne, že pro libovolná nenulová celá čísla a, b platí vp(ab) = vp(a) + vp(b) (8) vp(a) vp(a) (9) vp(a) < vp(b) =^ vp(a + b) = vp(a) (10) vp{a) < vp(b) =^ vp((a,b)) = vp(a) A vp([a, b]) = vp(b) (11) Na následujícím příkladu demonstrujme užitečnost zavedeného označení. PŘÍKLAD. Dokažte, že pro libovolná přirozená čísla a,b,c platí ([a, b], [a, c], [b, c]) = [(a, b), (a, c), (6, c)] ŘEŠENÍ. Podle věty 7 budeme hotovi, ukážeme-li, že vp(L) = vp(P) pro libovolné prvočíslo p, kde L, resp. P značí výraz na levé, resp. pravé straně. Nechť je tedy p libovolné prvočíslo. Vzhledem k symetrii obou výrazů můžeme bez újmy na obecnosti předpokládat, že vp(a) < vp(b) < vp(c). Podle (11) platí vp([a,b\) = vp(b), vp([a,c]) = vp([b,c]) = vp(c); vp((a,b)) = vp((a,c)) = vp(a), vp((b,c)) = vp(b), odkud vp(L) = vp(b) = vp(P), což jsme měli dokázat. □ 20 3. Kongruence Pojem kongruence byl zaveden Gaussem. Ačkoliv je to pojem velice jednoduchý, jeho důležitost a užitečnost v teorii čísel je nedocenitelná; projevuje se zejména ve stručných a přehledných zápisech některých i velmi komplikovaných úvah. Definice. Jestliže dvě celá čísla a, b mají při dělení přirozeným číslem m týž zbytek r, kde 0 < r < m, nazývají se a, b kongruentní modulo m (též kongruentní podle modulu to), což zapisujeme takto: a = b (mod m). V opačném případě řekneme, že a, b nejsou kongruentní modulo m, a píšeme a ^ b (mod m). Lemma. Pro libovolná a, b £ Z, m £ N jsou následující podmínky ekvivalentní: (1) a = b (mod m), (2) a = b + mt pro vhodné t £ Z, (3) m\a-b. DŮKAZ. „(1)=^(3)" Jestliže a = qľm + r, b = q2m + r, pak a — b = „(3)=^(2)" Jestliže m \ a — b, pak existuje ŕ G Z tak, žem-t = a — b, tj. a = b + mt. „(2)=^(1)" Jestliže a = b + mt, pak z vyjádření b = mq + r plyne a = m{q + ť) + r, tedy a i b mají při dělení číslem m týž zbytek r, tj. a = b (mod m). □ 3.1. Základní vlastnosti kongruencí. Přímo z definice plyne, že kongruence podle modulu m je reflexivní (tj. a = a (mod m) platí pro každé a G Z), symetrická (tj. pro každé a, b G Z z a = 6 (mod m) plyne b = a (mod m)) a tranzitivní (tj. pro každé a, b, c G Z z a = 6 (mod m) a 6 = c (mod m) plyne a = c (mod m)) relace, jde tedy o ekvivalenci. Dokážeme nyní další vlastnosti: VĚTA 13. (Základní vlastnosti kongruencí) (1) Kongruence podle téhož modulu můžeme sčítat. Libovolný sčítanec můžeme přenést s opačným znaménkem z jedné strany kongruence na druhou. K libovolné straně kongruence můžeme přičíst jakýkoliv násobek modulu. DŮKAZ. Je-li a\ = bi (mod m) a a2 = b2 (mod m), existují podle lemmatu t1; t2 G Z tak, že aľ = bľ + mti, a2 = b2 + mt2. Pak ovšem aľ + a2 = bľ + b2 + m(ti + Í2) a opět podle lemmatu ax + a2 = ^1 + b2 (mod m). Sečteme-li kongruencí a + b = c (mod m) s kongruencí —b = —b (mod m), která zřejmě platí, dostaneme a = c — b (mod m). Sečteme-li 21 kongruenci a = b (mod m) s kongruencí mk = 0 (mod m), jejíž platnost je zřejmá, dostaneme a + m A; = b (mod m). □ (2) Kongruence podle téhož modulu můžeme násobit. Obě strany kongruence je možné umocnit na totéž přirozené číslo. Obě strany kongruence je možné vynásobit stejným celým číslem. DŮKAZ. Je-li ai = bi (mod m) a «2 e 62 (mod m), existují podle ti,t2 £ 1* tak, že a\ = b\ + mti, cl2 = b2 + rrit2. Pak ovšem aia2 = (h + mti){b2 + mŕ2) = &1&2 + m{t1b2b1t2 + mt1t2), odkud podle dostáváme = (mod m). Je-li a = b (mod m), dokážeme indukcí vzhledem k přirozenému číslu n, že platí an = bn (mod m). Pro n = 1 není co dokazovat. Platí-li an = bn (mod m) pro nějaké pevně zvolené n, vynásobením této kongruence a kongruence a = b (mod m) dostáváme an ■ a = bn -b (mod m), tedy an+1 = bn+1 (mod m), což je tvrzení pro n + 1. Důkaz indukcí je hotov. Jestliže vynásobíme kongruenci a = b (mod m) a kongruenci c = c (mod m), dostaneme ac = bc (mod m). □ ^ Obě strany kongruence můžeme vydělit jejich společným dělitelem, jestliže je tento dělitel nesoudělný s modulem. DŮKAZ. Předpokládejme, že a = b (mod m), a = a\ ■ d, b = bi ■ d a (m,d) = 1. Podle lemmatu je rozdíl a — b = {di — b\)-d dělitelný číslem m. Protože (m,d) = 1, je podle věty 5 číslo ai — bi také dělitelné číslem m, odtud podle lemmatu plyne aľ = bľ (mod m). □ (4) Obě strany kongruence i její modul můžeme současně vynásobit tímtéž přirozeným číslem. DŮKAZ. Je-li a = b (mod m), existuje podle lemmatu celé číslo t tak, že a = b+mt, odkud pro c G N platí ac = bc+mc-t, odkud opět podle lemmatu plyne ac = bc (mod mc). □ (5) Obě strany kongruence i její modul můžeme vydělit jejich společným kladným dělitelem. DŮKAZ. Předpokládejme, že a = b (mod m), a = aľ ■ d, b = bi ■ d, m = ni\ ■ d, kde d G N. Podle lemmatu existuje ŕ G Z tak, že a = b+mt, tj. a\-d = bi-d+midt, odkud a\ = bi + rriit, což podle lemmatu znamená, že a\ = b\ (mod mi). □ (6) Jestliže kongruence a = b platí podle modulů mi,..., , platí i podle modulu, kterým je nejmenší společný násobek [mi,..., mk] těchto čísel. 22 DŮKAZ. Jestliže a = b (mod nii), a = b (mod 1112),... ,a = b (mod nik), podle lemmatu je rozdíl a — b společný násobek čísel mi,m2, ..., nik a tedy je dělitelný jejich nej menším společným násobkem [m1; m2,..., nik], odkud plyne a = b (mod [m1;..., nik]). □ (7) Jestliže kongruence platí podle modulu ni, platí podle libovolného modulu d, který je dělitelem čísla m. DŮKAZ. Jestliže a = b (mod ni), je a — b dělitelné ni, a proto také dělitelem d čísla ni, odkud a = b (mod d). □ (8) Jestliže je jedna strana kongruence a modul dělitelný nějakým celým číslem, musí být tímto číslem dělitelná i druhá strana kongruence. DŮKAZ. Předpokládejme, že a = b (mod m), b = b\d, ni = ni\d. Pak podle lemmatu existuje ŕ G Z tak, že a = b + nit = b\d + ni\dt = (61 + ni\t)d, a tedy d \ a. □ poznámka. Některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli - například příklad ze strany 5 lze přeformulovat do tvaru „jestliže a = 1 (mod ni), 6 = 1 (mod ni), pak také ab = 1 (mod m)", což je speciální případ tvrzení věty 13 (2). Nejde o náhodu. Libovolné tvrzení používající kongruence můžeme snadno přepsat pomocí dělitelnosti. Užitečnost kongruencí tedy netkví v tom, že bychom pomocí nich mohli řešit úlohy, které bez nich řešit nejsme schopni, ale v tom, že jde o velmi vhodný způsob zápisu. Osvojíme-li si ho, výrazně tím zjednodušíme jak vyjadřování, tak i některé úvahy. Je to typický jev: v matematice hraje vhodná symbolika velmi závažnou úlohu. příklad. Nalezněte zbytek po dělení čísla 520 číslem 26. Řešení. Protože 52 = 25 = -1 (mod 26), platí podle věty 13 (2) 520 = (.^io = x (mod 26)? a tedy zbytek po dělení čísla 520 číslem 26 je jedna. □ příklad. Dokažte, že pro libovolné n G N je 37n+2 + 16n+1 + 23n dělitelné sedmi. řešení. Platí 37 = 16 = 23 = 2 (mod 7), a tedy podle 13 (2) a (1) platí 37n+2+16n+1+23n = 2n+2+2n+1+2n = 2n(4+2+l) = 2n-7 = 0 (mod 7), což jsme chtěli dokázat. □ příklad. Dokažte, že číslo n = (8355 + 6)18 — 1 je dělitelné číslem 112. 23 řešení. Rozložíme 112 = 7-16. Protože (7,16) = 1, stačí ukázat, že 7 | n a 16 | n. Platí 835 = 2 (mod 7), a tedy podle 13 n = (25+6)18-l = 3818-1 = 318-1 = 276-l = (-1)6-1 = 0 (mod 7), proto 7 | n. Podobně 835 = 3 (mod 16), a tedy n = (35 + 6)18 - 1 = (3 • 81 + 6)18 - 1 = (3 • 1 + 6)18 - 1 = = 918 - 1 = 819 - 1 = l9 - 1 = 0 (mod 16), proto 16 | n. Celkem tedy 112 | n, což jsme měli dokázat. □ příklad. Dokažte, že pro libovolné prvočíslo p a libovolná a, b g Z platí ď + bp = (a + b)p (mod p). Řešení. Podle binomické věty platí (a + bf = ď+ Qď^b + Qap~2b2 + ■■■+ (/Jay-1 + V. Podle příkladu za větou 6 pro libovolné k g {1,... ,p — 1} platí (^) = 0 (mod p), odkud plyne tvrzení. □ Následující tvrzení je další užitečnou vlastností kongruencí: Lemma. Dokažte, že pro libovolné přirozené číslo m a libovolná a, b g Z taková, že a = b (mod mn), káe n g N, platí, že am = bm (mod mn+1). DŮKAZ. Platí am - bm = (a - b)(a"1"1 + am-2b + ■■■ + aW1'2 + 6m_1) (12) a protože m \ mn, tak podle 13 (7) platí i a = b (mod m). Jsou tedy všechny sčítance ve druhé závorce v (12) kongruentní s am_1 modulo m, a tedy am-l + am-2h + . . . + abm-2 + &m-l _ m . flm-l _ g (mod m^ proto je am~1+am~2 + - ■ ■+abm~2+bm~1 dělitelné m. Z a = b (mod mn) plyne, že mn dělí a — b, a tedy mn+1 dělí jejich součin, což vzhledem k (12) vede k závěru, že am = bm (mod mn+1). □ 3.2. Aritmetické funkce. Aritmetickou funkcí zde rozumíme funkci, jejímž definičním oborem je množina přirozených čísel. Definice. Rozložme přirozené číslo n na prvočísla: n = p"1 • • -p^k. Hodnotu Môbiovy funkce fi(n) definujeme rovnu 0, pokud pro některé i platí olí > 1 a rovnu (—\)k v opačném případě. Dále definujeme Mi) = i- příklad. /x(4) = /x(22) = 0,M6) = M2-3) = (-i^M2) = A*(3) = -1.