Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Diskrétni matematika B - 1. týden Elementární teorie čísel Michal Bulant Masarykova univerzita Fakulta informatiky jaro 2014 Motivační úvod Základní pojmy Prvočísla 00 oooooooooooooooooo oooooooo Obsah přednášky Motivační úvod Základní pojmy • Dělitelnost • Největší společný dělitel Prvočísla • Faktorizace • Rozložení prvočísel Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo » Jan Slovák, Martin Panák, Michal Bulant, Matematika drsně a svižně, MU Brno, 2013, 774 s. (též jako e-text). • Předmětové záložky v IS MU • Michal Bulant, výukový text k přednášce Elementární teorie čísel, http: //is .muni. cz/el/1431/podzim2013/M6520/ um/main-print.pdf • Jiří Herman, Radan Kučera, Jaromír Šimša, Metody řešení matematických úloh. MU Brno, 2001. • William Stein, Elementary N um ber Theory: Primes, Congruences, and Secrets, Springer, 2008. Dostupné na http://wstein.org/ent/ent.pdf • Radan Kučera, výukový text k přednášce Algoritmy teorie čísel, http://www.math.muni.cz/~kucera/texty/ATC10.pdf Motivační úvod •O Základní pojmy oooooooooooooooooo Prvočísla oooooooo Na této přednášce se budeme zabývat úlohami o celých číslech. Prevážne v nich půjde o dělitelnost celých čísel, poprípade o řešení rovnic v oboru celých nebo přirozených čísel. Ačkoli jsou přirozená a konec konců i celá čísla v jistém smyslu nejjednodušší matematickou strukturou, zkoumání jejich vlastností postavilo před generace matematiků celou řadu velice obtížných problémů. Často jsou to problémy, které je možno snadno formulovat, přesto však dodnes neznáme jejich řešení. God made integers, all else is the work of man. (L. Kronecker) Motivační úvod O* Základní pojmy oooooooooooooooooo Prvočísla oooooooo Notorické problémy teorie čísel Uveďme některé z nejznámějších: • problém prvočíselných dvojčat - rozhodnout, zda existuje nekonečně mnoho prvočísel p takových, že i p + 2 je prvočíslo, • problém existence lichého dokonalého čísla - tj. čísla jehož součet dělitelů je roven dvojnásobku tohoto čísla • Goldbachovu hypotézu (rozhodnout, zda každé sudé číslo větší než 2 je možno psát jako součet dvou prvočísel), • nebo klenot mezi problémy teorie čísel velkou Fermatovu větu (Fermaťs Last Theorem) - rozhodnout, zda existují přirozená čísla n, x, y, z tak, že n > 2 a platí x" + y" = z"; Pierre de Fermat jej formuloval cca 1637, vyřešil Andrew Wiles v roce 1995. Motivační úvod 00 Základní pojmy •ooooooooooooooooo Prvočísla oooooooo Definice Řekneme, že celé číslo a dělí celé číslo b (neboli číslo b je dělitelné číslem a, též b je násobek a), právě když existuje celé číslo c tak, že platí a ■ c = b. Píšeme pak a | b. Přímo z definice plyne několik jednoduchých tvrzení : Číslo nula je dělitelné každým celým číslem; jediné celé číslo, které je dělitelné nulou, je nula; pro libovolné číslo a platí a | a; pro libovolná čísla a, b, c platí tyto čtyři implikace: a j b A b | c a | b A a | c alfa A b > O a | c a|fa + c A a | b — c (a | b <í=^> ac | fac) a < b Motivační úvod 00 Základní pojmy o»oooooooooooooooo Prvočísla OOOOOOOO Príklad Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem Řešení Platí n2 — 1 = (n + l)(n — 1), a tedy číslo n + 1 dělí číslo n2 — 1. Předpokládejme, že n + 1 dělí i číslo n2 + 1. Pak ovšem musí dělit i rozdíl (n2 + 1) - (n2 - 1) = 2. Protože n G N, platí n + 1 > 2, a tedy z n + 1 | 2 plyne n + 1 = 2, proto n = 1. Uvedenou vlastnost má tedy jediné přirozené číslo 1. □ Motivační úvod Základní pojmy Prvočísla 00 oo»ooooooooooooooo oooooooo Dělení se zbytkem Věta (o dělení celých čísel se zbytkem) Pro libovolně zvolená čísla a 6 Z, m £ N existují jednoznačně určená čísla q 6 Z, r £ {0,1,..., m — 1} tak, že a = qm + r. Důkaz. Dokažme nejprve existenci čísel q, r. Předpokládejme, že přirozené číslo m je dáno pevně a dokažme úlohu pro libovolné a 6 Z. Nejprve budeme předpokládat, že a £ No a existenci čísel q, r dokážeme indukcí: Je-li O < a < m, stačí volit q = O, r = a a rovnost a = qm + r platí. Předpokládejme nyní, že a > m a že jsme existenci čísel q, r dokázali pro všechna a' 6 {0,1, 2,..., a — 1}. Speciálně pro a' = a — m tedy existují q', r' tak, že a' = q'm + r' a přitom r' £ {0,1,..., m — 1}. Zvolíme-li q = q' + 1, r = r', platí a = a' + m = (q' + l)m + r' = qm + r, což jsme chtěli dokázat. □ Motivační úvod 00 Základní pojmy 000*00000000000000 Prvočísla oooooooo Dokončení důkazu. Existenci čísel q, r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < O, pak ke kladnému číslu —a podle výše dokázaného existují q' G Z, r' G {0,1,..., m — 1} tak, že —a = q'm + r', tedy a = —q'm — r'. Je-li r' = O, položíme r = O, q = —q'; je-li r > O, položíme r = m — r', q = —q' — 1. V obou případech a = q ■ m + r, a tedy čísla q, r s požadovanými vlastnostmi existují pro každé a G Z, m G N. Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla gi, <72 £ Z; 1, r2 G {0,1,..., m — 1} platí a = gim + r\ = (72^ + ^2- Úpravou dostaneme ri — r2 = (<72 — <7i)™, a tedy m | ri — r2. Ovšem z O < ri < m, O < r2 < m plyne —m < ri — r2 < m, odkud dostáváme ri — r2 = 0. Pak ale i (92 — 0 čísel 3i,32, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel 3i,32, se nazývá největšíspolečný dělitel (resp. nejmenšíspolečný násobek) čísel 3i,32 a značí se (31,32) (resp. [31,32]). Motivační úvod 00 Základní pojmy oooooo»ooooooooooo Prvočísla oooooooo Poznámka Přímo z definice plyne, že pro libovolné a, b G Z platí (a, b) = (b, a), [a, b] = [b, a], (a, 1) = 1, [a, 1] = \a\, (a, 0) = \a [a,0] =0. Poznámka Analogicky se definuje i největší společný dělitel a nejmenší společný násobek více než dvou celých čísel a snadno se následně dokáže, že platí (ai,..., an) = ((ai,..., a„-i), a„) [ai,..., an] = [[ai,..., a„-i], an] Dosud jsme nijak nezdůvodnili, zda pro každou dvojici a, b G Z čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla /r?i, /r?2 G No totiž podle definice platí, že pokud m\ \ rri2 a zároveň rr>2 | mi, je nutně m\ = rrt2- Důkaz existence čísla (a, b) podáme (spolu s algoritmem jeho nalezení) v následující větě, důkaz existence čísla [a, b] pak dostaneme snadno ze vztahu mezi (a, b) a [a,b]. Věta (Euklidův algoritmus) Necht 3i, 32 _/sou přirozená čísla. Pro každé n > 3, pro Ateré 7^ 0, označme an zbytek po dělení čísla a„_2 číslem a„_i. Pa/c po konečném počtu kroků dostaneme a^ = 0 a p/ař/ = (ai, 32)- Motivační úvod 00 Základní pojmy oooooooo»ooooooooo Prvočísla oooooooo Důkaz. Podle Věty o dělení se zbytkem platí 32 > 33 > 34 > .... Protože jde o nezáporná celá čísla, je každé následující alespoň o 1 menší než předchozí, a proto po určitém konečném počtu kroků dostáváme ak = O, přičemž 3/<_i 7^ 0. Z definice čísel an plyne, že existují celá čísla qi, q2,..., qk-2 tak, že 3\ = qi ■ a2 + a3, 3k-3 = qk-3 ■ 3k-2 + 3/r-l 3k-2 = qk-2 ■ 3k-í- Z poslední rovnosti plyne, že 3/<_i | 3/<_2, dále 3/<_i | 3/<_3, atd., je tedy 3/<_i společný dělitel čísel 3i,32- Naopak jejich libovolný společný dělitel dělí i číslo 33 = a\ — q\32, proto i 34 = 32 - 9233,..., a proto i ak-i = ak_3 - qk_3ak-2. Dokázali jsme, že ak_\ je největší společný dělitel čísel a\, 32. □ Poznámka Z definice, z předchozího tvrzení a z toho, že pro libovolná a, b G Z platí (a, í?) = (a, —Ď) = (—a, Ď) = (—a, —Ď), plyne, že existuje největší společný dělitel libovolných dvou celých čísel. Věta (Bezoutova) Pro libovolná celá čísla a\, 32 existuje jejich největší společný dělitel (ai, 32), přitom existují celá čísla k\, /c2 tak, že (ai, a2) = /qsi + k2a2. Motivační úvod 00 Základní pojmy oooooooooo»ooooooo Prvočísla oooooooo Důkaz. Jistě stačí větu dokázat pro a\, a2 G N. Všimněme si, že jestliže je možné nějaká čísla r, s G Z vyjádřit ve tvaru r = r\3\ + r2a2, s = s\3\ + S232, kde ri, r2, si,s2 G Z, můžeme tak vyjádřit i r + s = (n + si)si + (r2 + s2)a2 a také c • r = (c • ri)ai + (c • r2)a2 pro libovolné c G Z. Protože 3i = 1 • a\ + O • 32, 32 = O • 3i + 1 • 32, plyne z (5), že takto můžeme vyjádřit i 33 = 3l — <7l32, 34 = 32 — <7233, . . . , 3fr_i = 3fr_3 — qk-3ak-2, C°Ž je ovšem (si, 32). □ Motivační úvod 00 Základní pojmy ooooooooooo»oooooo Prvočísla oooooooo Príklad Výpočet největšího společného dělitele pomocí Euklidova algoritmu je s využitím výpočetní techniky i pro relativně velká čísla poměrně rychlý. V našem příkladu to vyzkoušíme na 2 číslech A,B, z nichž každé je součinem dvou 101-ciferných prvočísel. Všimněme si, že výpočet největšího společného dělitele i takto velkých čísel trval zandbatelný čas. Příklad v systému SAGE je dostupný na https://sage.math.muni.cz/home/pub/6/. i Motivační úvod 00 Základní pojmy oooooooooooo»ooooo Prvočísla oooooooo Poznámka Euklidův algoritmus a Bezoutova věta jsou základními výsledky elementární teorie čísel a tvoří jeden z pilířů algoritmů algebry a teorie čísel. To, že znalost těchto základů je občas důležitá i v praktickém životě, dokazuje Bruče Willis a Samuel Jackson ve filmu Smrtonosná past 3, kde mají za úkol zlikvidovat bombu pomocí 4 galonů vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonů. Zde stačí s využitím Euklidova algoritmu najít celá čísla k, I tak, že bude platit 3k + 5/ — 4. Netroufám si tvrdit, že zmínění herci ovládají uvedené základy teorie čísel (tuto konkrétní úlohu jistě snadno vyřešíte experimentálně), nicméně předchozí věty dávají návod, jak vyřešit úlohu tohoto typu s libovolnými zadanými parametry. Motivační úvod 00 Základní pojmy ooooooooooooo»oooo Prvočísla oooooooo Věta Pro libovolná celá čísla a\, 32 existuje jejich nejmenší společný násobek [si, 32] a platí (si, 32) • [si, 32] = |si • 321- Důkaz. Věta jistě platí, je-li některé z čísel 3i, 32 rovno nule. Můžeme navíc předpokládat, že obě nenulová čísla 3i,32 jsou kladná, neboť jejich znaménka se v dokazovaném vzorci neprojeví. Budeme hotovi, ukážeme-li, že q = a\ • 32/(31, 32) je nejmenší společný násobek čísel 3i, 32. □ Motivační úvod 00 Základní pojmy oooooooooooooo»ooo Prvočísla oooooooo Dokončení. Protože (ai, 32) je společný dělitel čísel 3i, 32, jsou 31/(31,32) i 32/(31,32) celá čísla, a proto _ 3i32 _ 3i _ 32 (31,32) (31,32) (31,32) je společný násobek čísel a\, 32. Podle věty 3 existují k\, k2 £ Z tak, že (si, 32) = k\3\ + k2a2. Předpokládejme, že n £ Z je libovolný společný násobek čísel 3i,32 a ukážeme, že je dělitelný číslem q. Je tedy n/si, 0/32 6 Z, a proto je i celé číslo n n n(k1a1 + k2a2) n(a1,a2) n — • K\ H--• «2 = - = - = — ■ 32 3l 3i32 3i32 Cf To ovšem znamená, že q \ n, což jsme chtěli dokázat. □ —1 Motivační úvod 00 Základní pojmy ooooooooooooooo^oo Prvočísla OOOOOOOO Definice Čísla 3i, 32,..., an G Z se nazývají nesoudělná, jestliže platí (si, 32,..., an) = 1. Čísla 3i, 32,..., sn G Z se nazývají po cŕVou nesoudělná, jestliže pro každé /',_/' takové, že 1 2 plyne z nesoudělnosti po dvou nesoudělnost, ne však naopak: například čísla 6, 10, 15 jsou nesoudělná, ale nejsou nesoudělná po dvou, neboť dokonce žádná dvojice z nich vybraná nesoudělná není: (6,10) = 2, (6,15) = 3, (10,15) = 5. Motivační úvod 00 Základní pojmy oooooooooooooooo»o Prvočísla oooooooo Věta Pro libovolná přirozená čísla a, b, c platí O (ac, bc) = (a, b) • c, 0 jestliže a \ bc, (a, b) = 1, pak a \ c, 0 d = (a, b) právě tehdy, když existujíqi, q2 £ N tak, že a = dqi, b = dq2 a (qi, q2) = 1- Motivační úvod 00 Základní pojmy 00000000000000000» Prvočísla oooooooo Důkaz. ad 1. Protože (a, b) je společný dělitel čísel a, b, je (a, b) ■ c společný dělitel čísel ac, bc, proto (a, b) ■ c | (ac, fac). Podle Bezoutovy věty existují k, I G Z tak, že (a, Ď) = /ca + A£>. Protože (ac, fac) je společný dělitel čísel ac, fac, dělí i číslo kac + Ibc = (a, Ď) • c. Dokázali jsme, že (a, b) • c a (ac, fac) jsou dvě přirozená čísla, která dělí jedno druhé, proto se rovnají. ad 2. Předpokládejme, že (a, b) = 1 a a | fac. Podle Bezoutovy věty existují It.lsZ tak, že ka + Ib = 1, odkud plyne, že c = c(/ca + A£>) = /cca + A£>c. Protože a | fac, plyne odsud, že i a | c. ad 3. Nechť d = (a, fa), pak existují gi, 92 £ N tak, že a = c/qi, fa = c/<72- Pak podle 1. části platí d = (a, b) = (dqx, dq2) = d ■ (qi, q2), a tedy (qi, q2) = 1- Naopak, je-li a = dqi, b = dq2 a (qi, q2) = 1, pak (a, fa) = (c/gi, dq2) = d(qi, q2) = d ■ 1 = d (opět užitím 1. části tohoto tvrzení). □ Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla •ooooooo Prvočíslo je jeden z nejdůležitějších pojmů elementární teorie čísel. Jeho důležitost je dána především větou o jednoznačném rozkladu libovolného přirozeného čísla na součin prvočísel, která je silným a účinným nástrojem při řešení celé řady úloh z teorie čísel. Definice Každé přirozené číslo n > 2 má aspoň dva kladné dělitele: lan. Pokud kromě těchto dvou jiné kladné dělitele nemá, nazývá se prvočíslo. V opačném případě hovoříme o složeném čísle. V dalším textu budeme zpravidla prvočíslo značit písmenem p. Nejmenší prvočísla jsou 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (zejména číslo 1 za prvočíslo ani za číslo složené nepovažujeme, je totiž invertibilní, neboli tzv. jednotkou okruhu celých čísel). Prvočísel je, jak brzy dokážeme, nekonečně mnoho, máme ovšem poměrně limitované výpočetní prostředky na zjištění, zda je dané číslo prvočíslem (největší známé prvočíslo 257885161 — 1 má pouze 17425170 cifer). Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla o»oooooo Uveďme nyní větu, která udává ekvivalentní podmínku prvočíselnosti a je základní ingrediencí při důkazu jednoznačnosti rozkladu na prvočísla. Věta (Euklidova o prvočíslech) Přirozené číslo p > 2 je prvočíslo, právě když platí: pro každá celá čísla a, b z p | ab plyne p | a nebo p | b. Důkaz. "^"Předpokládejme, že p je prvočíslo a p | ab, kde a, b G Z. Protože (p, a) je kladný dělitel p, platí (p, a) = p nebo (p, a) = 1. V prvním případě p | a, ve druhém p | fa podle části 2. předchozí věty. " <í=" Jestliže p není prvočíslo, musí existovat jeho kladný dělitel různý od 1 a p. Označíme jej a; pak ovšem b = - G N a platí p = afa, odkud l 2 je možné vyjádřit jako součin prvočísel, přičemž je toto vyjádření jediné, nebereme-li v úvahu pořadí činitelů. (Je-li n prvočíslo, pak jde o „součin" jednoho prvočísla.) Poznámka Dělitelnost je možné obdobným způsobem definovat v libovolném oboru integrity (zkuste si rozmyslet, proč se omezujeme na obory integrity). V některých oborech integrity přitom žádné prvky s vlastností prvočísla (říkáme jim ireducibilní) neexistují (např. Q), v jiných sice ireducibilní prvky existují, ale zase tam neplatí věta o jednoznačném rozkladu (např. v Z(\/—5) máme následující rozklady: 6 = 2 • 3 = (1 + V—5) • (1 — \f—5); zkuste si rozmyslet, že všichni uvedení činitelé jsou skutečně v Z(\/—5) ireducibilní). Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla 000*0000 Důkaz. Nejprve dokážeme indukcí, že každé n > 2 je možné vyjádřit jako součin prvočísel. Je-li n = 2, je n součin jediného prvočísla 2. Předpokládejme nyní, že n > 2 a že jsme již dokázali, že libovolné n', 2 < n' < n, je možné rozložit na součin prvočísel. Jestliže n je prvočíslo, je součinem jediného prvočísla. Jestliže n prvočíslo není, pak existuje jeho dělitel d, 1 < d < n. Označíme-li c = ^, platí také 1 < c < n. Z indukčního předpokladu plyne, že c i d je možné vyjádřit jako součin prvočísel, a proto je takto možné vyjádřit i jejich součin c • d = n. Nyní dokážeme jednoznačnost. Předpokládejme, že platí rovnost součinů pi • p2.....pm = qi ■ <72gs, kde pi,... ,pm, <7i,..., qs jsou prvočísla a navíc platí pi < P2 < • • • < pm, qi < <72 < • • • < <7s a 1 < m < s. Indukcí vzhledem k m dokážeme, že m = s, pi = gi,..., pm = qm. □ Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla 0000*000 Dokončení. Je-1i m = 1, je pi = qi.....qs prvočíslo. Kdyby s > 1, mělo by číslo pi dělitele q\ takového, že 1 < q\ < pi (neboť <72<73 • • • qs > 1), což není možné. Je tedy s = 1 a platí pi = q\. Předpokládejme, že m > 2 a že tvrzení platí pro m — 1. Protože Pi • P2Pm = qi ■ <72<7s, dělí pm součin gi.....qs, což je podle Euklidovy věty možné jen tehdy, jestliže pm dělí nějaké q, pro vhodné / 6 {1, 2,..., s}. Protože qf- je prvočíslo, plyne odtud Pm = q\ (neboť pm > 1). Zcela analogicky se dokáže, že qs = pj pro vhodné je {1,2,..., m}. Odtud plyne qs = pj < Pm = q; < qs, takže pm = qs. Vydělením dostaneme pi • P2.....Pm-i = qi • q2.....<7s-i, a tedy z indukčního předpokladu m — 1 = s — 1, pi = qi,..., pm_i = qm-i- Celkem tedy m = s a pi = qi,..., pm-i = qm-i, Pm = qm-Jednoznačnost, a proto je i celá věta dokázána. □ Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla 00000*00 Poznámka Již jsme se zmínili, že je složité o velkých číslech s jistotou rozhodnout, jde-li o prvočíslo (na druhou stranu je o naprosté většině složených čísel snadné prokázat, že jsou skutečně složená). Přesto se v roce 2002 podařilo indickým matematikům (Agrawal, Saxena, Kayal: http://www.cse.iitk.ac.in/users/manindra/ algebra/primality_v6.pdf) dokázat, že problém prvočíselnosti je možné rozhodnout algoritmem s časovou složitostí polynomiálně závislou na počtu cifer vstupního čísla. Nic podobného se zatím nepodařilo v otázce rozkladu čísla na prvočísla (třebaže se obecně nevěří, že je to možné, exaktní důkaz zatím nebyl podán). Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooo»o Nie podobného se zatím nepodarilo v otázce rozkladu čísla na prvočísla (třebaže se obecně nevěří, že je to možné, exaktní důkaz zatím nebyl podán). Nej rychlejší obecně použitelný faktorizační algoritmus, tzv. síto v číselném tělese1, je sub-exponenciální časové složitosti 0(eL9(logA/)1/3(l°g'°8w)2/3). Poznámka Peter Shor v roce 1994 vymyslel algoritmus, který faktorizuje v kubickém čase (tj. 0((log A/)3)) na kvantovém počítači. Je k tomu nicméně třeba sestrojit počítače s dostatečným počtem qubits - jak je to obtížné, lze vysledovat z toho, ze v roce 2001 se IBM podařilo pomocí kvantového počítače rozložit číslo 15 a v roce 2012 byl dosažen další faktorizační rekord rozkladem čísla 21. 1Pro podrobnosti navštivte M8190 Algoritmy teorie čísel Motivační úvod Základní pojmy Prvočísla oo oooooooooooooooooo 0000000» RSA Challenge Poznámka Že je problém rozkladu přirozeného čísla na prvočísla výpočetně složitý, o tom svědčí i (již neplatná) výzva učiněná v roce 1991 firmou RSA Security (viz http://www.rsasecurity.com/rsalabs/node.asp?id=2093). Pokud se komukoliv podařilo rozložit čísla označená podle počtu cifer jako RSA-100, ..., RSA-704, RSA-768, .. ., RSA-2048, mohl obdržet 1000_____ 30 000, 50 000, ..., resp. 200 000 dolarů (číslo RSA-100 rozložil v temže roce Arjen Lenstra, číslo RSA-704 bylo rozloženo v roce 2012, některá dosud rozložena nebyla). Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Díky jednoznačnosti rozkladu na prvočísla jsme schopni (se znalostí tohoto rozkladu) snadno odpovědět i na otázky ohledně počtu či součtu dělitelů konkrétního čísla. Stejně snadno dostaneme i (z dřívějška intuitivně známý) postup na výpočet největšího společného dělitele dvou čísel ze znalosti jejich rozkladu na prvočísla. Důsledek • Každý kladný dělitel čísla a = p"1.....p"kk je tvaru p™1.....p™k, kde mi,..., m/t 6 No a mi < ni, /7i2 < fl2, - - -, mk < nk. • Číslo a má tedy právě r(a) = (n\ + l){n2 + 1).....{nk + 1) kladných dělitelů, jejichž součet je Pl - 1 pk - 1 Motivační úvod 00 Základní pojmy OOOOOOOOOOOOOOOOOO Prvočísla oooooooo Důsledek (Pokr.) • Jsou-li pi, . . . , pk navzájem různá prvočísla a n\, nk, m-í, ..., mk G N0 a označíme-li r\ = min{n/, m,-}, t; = max{n/, m,-} pro každé / = 1, 2,..., k, platí (Pľ .....PľSPľ1 ••••pD p?-- ■ti, [pT ••••pľspľ1 ••••Pľ1=PÍ1---- S pojmem součet všech kladných dělitelů čísla a souvisí pojem tzv. dokonalého čísla a, které splňuje podmínku a(a) = 2a, resp. slovně: součet všech kladných dělitelů čísla a menších než a samotné je roven číslu a. Takovými čísly jsou např. 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 +14, 496 a 8128 (jde o všechna dokonalá čísla menší než 10 000). Lze ukázat, že sudá dokonalá čísla jsou v úzkém vztahu s tzv. Mersenneho prvočísly. Platí totiž: Číslo a je sudé dokonalé, právě když je tvaru a kde 2q — 1 je prvočíslo. 2<í-i . (2q-l), Na druhou stranu popsat lichá dokonalá čísla se dodnes nepodařilo, resp. dodnes se neví, jestli vůbec nějaké liché dokonalé číslo existuje. Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Mersenneho prvočísla jsou právě prvočísla tvaru 2k — 1. Bez zajímavosti není ani to, ž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 (viz např. http://www.utm.edu/research/primes/largest.html). 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 poznania zdokonaluje použité metody (a často i hardware), jednak 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 $ za první dvě kategorie byly vyplaceny v letech 2000, resp. 2009 - v obou případech projektu GIMPS - na další odměny si ieště zřejmě něiakv řas nořkámpl Motivační úvod Základní pojmy Prvočísla 00 oooooooooooooooooo oooooooo Jak testovat Mersenneho prvočísla? Přestože zatím nemáme jasno v tom, jak efektivně implementovat použité operace, ani neumíme dokázat jeho správnost, uveďme si pro ilustraci test, kterým lze zjistit, je-li dané Mersenneho číslo prvočíslem. Lucas-Lehmerův test Definujme posloupnost (sn)^L0 rekurzívně předpisem So = 4, sn+i = s„ — 2. Pak je číslo Mp = 2P — 1 prvočíslo, právě tehdy, když Mp dělí sp_2- Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Nyní se budeme snažit zodpovědět následující otázky: O Je prvočísel nekonečně mnoho? O Je prvočísel nekonečně mnoho v každé (nebo aspoň některé) aritmetické posloupnosti? O Jak jsou prvočísla rozložena mezi přirozenými čísly? 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 Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Věta (Eukleidés) Mezi přirozenými čísly existuje nekonečně mnoho prvočísel. Důkaz. Předpokládejme, že prvočísel je konečně mnoho a označme je Pi, p2,..., pn. Položme A/ = pi • p2 ... pn + 1. Toto číslo je bud' samo prvočíslem neboje 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. □ Poznámka Existuje mnoho variant důkazů nekonečnosti prvočísel z různých oblastí matematiky, uveďme ještě alespoň některá tvrzení, z nichž zároveň získáme alespoň částečnou informaci o rozložení prvočísel mezi přirozenými čísly. Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Príklad Pro 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 Základní věty aritmetiky, 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 j (n! — 1), platí p < n! — 1, tedy p < n!. Prvočíslo p splňuje podmínky úlohy. □ Z této věty rovněž vyplývá nekonečnost prvočísel, její tvrzení je ale velice slabé. Následující tvrzení, uvedené bez důkazu, je podstatně silnější. Věta (Čebyševova, Bertrandův postulát) Pro libovolné číslo n > 1 existuje alespoň jedno prvočíslo p solňuiící n < o < 2n. Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Prí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 j (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo. □ Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Prvočísla jsou relativně rovnoměrně rozložena v tom, smyslu, že v libovolné „rozumné" aritmetické posloupnosti je jich nekonečně mnoho. Například zbytek 1 po dělení čtyřmi, stejně jako zbytek 3 po dělení čtyřmi dá vždy nekonečně mnoho prvočísel (zbytek O nedá samozřejmě žádné a zbytek 2 pouze jediné). Obdobná situace je pak při uvažování zbytků po dělení libovolným jiným přirozeným číslem, jak uvádí následující věta, jejíž důkaz je ovšem velmi obtížný. Věta (Dirichletova o prvočíslech v aritmetické posloupnosti) 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, mezi čísly 1 • m + a, 2 • m + a, 3 • m + a,... existuje nekonečně mnoho prvočísel. Uveďme proto alespoň důkaz ve speciálním případě. Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Prvočísel tvaru 3k + 2 je nekonečně mnoho Příklad Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3/c + 2, kde k G N0. Řešení Předpokládejme naopak, že existuje pouze konečně mnoho prvočísel tohoto tvaru a označme je pi = 2, p2 = 5, P3 = 11, ..., p„. Položme N = 3p2 • P3.....p„ + 2. Rozložíme-li N na součin prvočísel, musí v tomto rozkladu vystupovat aspoň jedno prvočíslo p tvaru 3/c + 2, neboť v opačném případě by bylo N součinem prvočísel tvaru 3/c + 1 (uvažte, že N není dělitelné třemi), a tedy podle dřívějšího příkladu by bylo i N tvaru 3/c + 1, což není pravda. Prvočíslo p ovšem nemůže být žádné z prvočísel pi,p2, ...,pn, jak plyne z tvaru čísla N, a to je spor. Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo 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 velmi důležitá tzv. "Prime Number Theorem": Věta (Prime Number Theorem, věta o hustotě prvočísel) Necht 7r(x) udává počet prvočísel menších nebo rovných číslu xěí Pak 7r(x) ~--, Inx tj. podíl funkcí tt(x) a x j Inx se pro x —> oo limitně blíží k 1. Poznámka To, jak jsou prvočísla hustě rozmístěna v množině přirozených čísel, rovněž udává Eulerův výsledek J2PeP \ = 00• Přitom např. zCneN 7? = T' co^ znamená, že prvočísla jsou v N rozmístěna „hustěji" než druhé mocniny. Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Věta Je-li P množina všech prvočísel, pak J2peP p = 00• Důkaz. Buď n libovolné přirozené číslo a pi,..., p7r(n) všechna prvočísla nepřevyšující n. Položme x 1 v -1 *»>=nK) • Jednotlivé činitele lze chápat jako součet geometrické řady, proto x 00 1 , 1 A(")=n( e^ľ)=e-^— /=1 V—O K' 7 Pl • • • Pvrfn) kde sčítáme přes všechny 7r(n)-tice nezáporných celých čísel («1,..., a^n))- Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Důkaz. Protože každé číslo nepřevyšující n se rozkladá pouze na prvočísla z množiny {pi,..., pn^}, je určitě každé takové číslo v tomto součtu zahrnuto. Tedy X(n) >l + | + -- - + ^,a protože harmonická řada diverguje , je i \\mn^00X(n) = oo. S využitím rozvoje funkce In(1 + x) do mocninné řady dále dostáváme 7r(n) 7r(") oo InA(n) = -J^ln i1 - i) = e e (-pH-1 /=1 m=l oo = p1-1 + -- i=l m=2 Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Důkaz. ir(n) oo in A(n) = pr1 + • • •+Pjn) + ee (^r1 ■ i=l m=2 Protože vnitřní součet lze shora odhadnout jako oo oo £ (mpfT1 < e Pim = m—2 m—2 umíme shora odhadnout i divergující posloupnost InA(n) < YU=i PT1 + ^ YU=i P~\2 ■ Druhý součet přitom zřejmě konverguje (viz konvergence řady Yl^Li n~2)> proto musí nutně divergovat první součet Yll=i PÍ1* což jsme chtěli dokázat. □ Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo Příklad O tom, jak odpovídá asymptotický odhad 7r(x) ~ x/ ln(x), v některých konkrétních přík adech vypovídá následující tabulka: x tt(x) x/ln(x) rel. chyba Li(x) rel. chyba 100 25 21,7 0,13 29,1 0,04 1000 168 144,7 0,13 176,6 0,01 10000 1229 1085,7 0,11 1245,1 0,002 100000 9592 8685,9 0,09 9628,8 0,0004 500000 41538 38102,9 0,08 41605,2 0,0001 Li(x) = §2 Wi značí tzv. logaritmický integrál.