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 2013 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 Motivační úvod 00 Základní pojmy oooooooooooooooooo Prvočísla oooooooo • Martin Panák, Jan Slovák, Drsná matematika, průběžně pripravovaný 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/podzim2012/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 Number 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' = + 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 £ 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-33k-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)ai + (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, coz je ovšem (si, 32). □ Motivační úvod 00 Základní pojmy OOOOOOOOOOO0OOOOOO 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, a?\ a platí(si, 32) • [si, 32] = \a\ • 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 ai, 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 6 Z tak, že (si, 32) = k\3\ + k2a2. Předpokládejme, že n 6 Z je libovolný společný násobek čísel 3i,32 a ukážeme, že je dělitelný číslem q. Je tedy n/si, n/a2 £ 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 dvou 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í qi, q2 G 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 = c/qi, fa = dq2 a (qi, q2) = 1, pak (a, fa) = (dqi, 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, <7i < <72 < • • • < <7s a 1 < "i < 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 i (neboť pm > 1). Zcela analogicky se dokáže, že qs = pj pro vhodné je {1,2,..., m}. Odtud plyne <7s = Pj < Pm = q; < qs, takže pm = qs. Vydělením dostaneme pi • P2.....Pm-i = qi • cfeqs-i, a tedy z indukčního předpokladu m — 1 = s — 1, pi = qi,..., pm-\ = 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 00 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 m\,..., G No a m\ < n\, m2 < n2, ..., 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