Home Page Literatura Title Page Contents [1] J. Herman, R. Kučera a J. Simša. Metody řešení matematických úloh I. MU Brno, druhé vydání, 2001. 1. Základní pojmy 1.1. Dělitelnost. 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í, jejichž důkaz přenecháváme čtenáři jako cvičení s návodem v [1, §12]: Čí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: ►► Page 1 of 21 Go Back Full Screen a | b A b | c a | b A a \ c a I b A b > 0 a | c a | b + c A a \ b — c (a | b <í=^ ac | be) a < b (1) (2) (3) (4) Close Quit Home Page Title Page PŘÍKLAD. Zjistěte, pro která přirozená čísla n je číslo n2 n + 1. 1 dělitelné číslem Contents Ř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 neN, 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. D VĚTA 1. (Věta o dělení celých ěísel se zbytkem) Pro libovolně zvolená ěísla a E Z, m E N existují jednoznačně určená ěísla q E Z, r E {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 E Z. Nejprve budeme předpokládat, že a E N0 a existenci čísel q,r dokážeme indukcí: Je-li 0 < a < m, stačí volit q = 0, 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' E {0,1, 2,..., a — 1}. Speciálně pro a' = a — m tedy existují q', r1 tak, že a' = q'm + r' a přitom r' E {0,1,..., m — 1}. Zvolíme-li q = q' + 1, r = r', platí a = a' + m = (q' + l)m, + r' = gm + r, což jsme chtěli dokázat. Existenci čísel q, r jsme tedy dokázali pro libovolné a > 0. Je-li naopak a < 0, pak ke kladnému číslu —a podle výše dokázaného existují q' E Z, r' E {0,1,..., m— 1} tak, že —a = q'rn + r', tedy a = —q'm — r'. Je-li r' = 0, položíme r = 0, q = —q'; U ►► < ► Page 2 of 21 Go Back Full Screen Close Quit Home Page Title Page 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 E Z, m E N. Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla gi, g2 E Z; n>r2 £ {0,1,... ,m — 1} platí a = q\vn + r\ = q2vn + r2. Úpravou dostaneme ?"i — r2 = (?2 — Qi)m, a tedy m | fi — r2. Ovšem z 0 < r\ < m, 0 < r2 < m plyne —m < r\ — r2 < m, odkud podle (4) platí r\ — r2 = 0. Pak ale i (g2 — q\)m = 0, a proto #i = g2, r\ = r2. Čísla g, r jsou tedy určena jednoznačně. Tím je důkaz ukončen. D Číslo q, resp. r z věty se nazývá (neúplný) podíl, resp. zbytek při dělení čísla a číslem m se zbytkem. Vhodnost obou názvů je zřejmá, přepíšeme-li rovnost a = mq + r do tvaru ar r — = q H-----, pritom 0 < — < 1. mm m Je vhodné též si uvědomit, že z věty 1 plyne, že číslo m dělí číslo a, právě když zbytek r je roven nule. Příklad. Dokažte, že jsou-li zbytky po dělení čísel a, b E Z číslem m E N jedna, je jedna i zbytek po dělení čísla ab číslem m. Řešení. Podle věty 1 existují s,t E Z tak, že a = sm + 1, b = tm + 1. Vynásobením dostaneme vyjádření ab = (sm + l)(tm + 1) = (stm + s + ť) m + 1 = qm + r, Contents U ►► < ► Page 3 of 21 Go Back Full Screen Close Quit Home Page Title Page kde q = stm + s + t, r = 1, které je podle věty 1 jednoznačné, a tedy zbytek po dělení čísla ab číslem m je jedna. D 1.2. Největší společný dělitel a nejmenší společný násobek. Definice. Mějme celá čísla ai,ci2- Libovolné celé číslo m takové, že m \ ci\, m | ci2 (resp. a\ \ m, ci2 \ m) se nazývá společný dělitel (resp. společný násobek) čísel ai,ci2- Společný dělitel (resp. násobek) m > 0 čísel ai,ci2, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel a\, ci2, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel ai,ci2 a značí se (ai,ß2) (resp. [ai,ß2])- Poznámka. Přímo z definice plyne, že pro libovolné a, b G Z platí (a, b) = (b,a), [a,b] = [b,a], (a,l) = 1, [a, 1] = \a\, (a,0) = \a\, [a,0] = 0. Ještě však není jasné, zda pro každou dvojici a, b E Z čísla (a, b) a [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi,m2 G N0 totiž podle (4) platí, že pokud rri\ \ m2 a zároveň m2 | mi, je nutně rri\ = m2. Důkaz existence čísla (a, b) podáme (spolu s algoritmem jeho nalezení) ve větě 2, důkaz existence čísla [a, b] a způsob jeho určení pak popíšeme ve větě 4. VĚTA 2. (Euklidův algoritmus) Nechť a\,a2 jsou přirozená čísla. Pro každé n > 3, pro které an-\ ^ 0; označme an zbytek po dělení čísla an-2 číslem an-i-Pak po konečném počtu kroků dostaneme au = 0 a platí au-i = («i, «2)- Contents « ►► < ► Page 4 of 21 Go Back Full Screen Close Quit Home Page Title Page DŮKAZ. Podle věty 1 platí a2 > «3 > «4 > .... 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 dk = 0, přičemž cik-i 7^ 0. Z definice čísel an plyne, že existují celá čísla qi, q2, ■ ■., qu-% tak, že Contents « ►► «1 = O čísel 01,02,... ,an, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) těchto čísel, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel 01, o2,..., an a značí se (oi,o2,..., an) (resp. [01, 02,..., an\). ,an G Contents u ►► Page 7 of 21 Go Back Full Screen Close Quit Home Page Title Page Snadno se přesvědčíme, že platí Contents [Cil, ■ ■ ■ ,Cln-l,Cln) — ({Cil, ■ ■ ■ , Cln-l), Cln), \U\ , ... , Cln—l, Cln ] — [[al, ■ ■ ■ , Cln-l], Cln]- (6) (7) Největší společný dělitel (aÍ3..., cin) totiž dělí všechna čísla ax,,.. ,ein, a tedy je společným dělitelem čísel «i, ..., cin~i, a proto dělí i největšího společného dělitele (ci\, ■ ■ ■, cin-i), tj. (<2i,. -., cin) \ ((«i, • • •, «n-i), ««)• Naopak největší společný dělitel čísel (cii, ■ ■ ■ ,cin-i),cin musí kromě čísla cin dělit i všechna čísla ci\,... ,cin-i, protože dělí jejich největšího společného dělitele, a proto ((cii,... ,an-i),an) | (ci\, ■ ■ ■, cin)- Dohromady dostáváme rovnost (6) a zcela analogicky se dokáže (7). Pomocí (6) a (7) snadno dokážeme existenci největšího společného dělitele i nejmenšího společného násobku libovolných n čísel indukcí vzhledem k n: pro n = 2 je jejich existence dána větami 2 a 4, jestliže pro některé n > 2 víme, že existuje největší společný dělitel i nejmenší společný násobek libovolných n — 1 čísel, podle (6) a (7) existuje i pro libovolných n čísel. « ►► < ► Page 8 of 21 Go Back Full Screen 1.4. Nesoudělnost. Definice. Čísla ci\, cii,..., a„ € Z se nazývají nesoudělná, jestliže platí (ci\,ci2, ■ 1. Čísla cii,ci2,..., ara G Z se nazývají po dvou nesoudělná, jestliže pro každé i, j takové, že 1 < i < j < n, platí (a*, a,-) = 1. • ,Cln) Close Quit Home Page Title Page Poznámka. V případě n = 2 oba pojmy splývají, pro n > 2 plyne z ne-soudě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. Příklad. Nalezněte největší společný dělitel čísel 263 — 1 a 291 Contents 1. Řešení. Užijeme Euklidův algoritmus. Platí 091 -i 028/063 i\ , 028 -,63 -,28 D 1 = 2^(2bd - 1) + 2' l = (235 + 27)(228-l) + 27-l, V* - 1 = (221 + 214 + 27 + 1)(27 - 1). Hledaný největší společný dělitel je tedy 27 — 1 = 127. VĚTA 5. Pro libovolná přirozená čísla a, b, c platí (1) (ac, bc) = (a, b) ■ c, (2) jestliže (a, b) = 1 a a \ bc, pak a \ c, (3) d = (a, b) právě tehdy, když existují qi,Q2 £ N tak, že a = dqx, b = dq2 a (qi,Q2) = 1- 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,bc). Podle věty 3 existují k,l E Z tak, že (a, b) = ka + lb. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo « ►► < ► Page 9 of 21 Go Back Full Screen Close Quit Home Page Title Page kac + lbe = (a, b) ■ c. Dokázali jsme, že (a, b) ■ c a (ac, bc) jsou dvě přirozená čísla, která dělí jedno druhé, proto se podle (4) rovnají. ad 2. Předpokládejme, že (a, b) = 1 a o | bc. Podle Bezoutovy věty (věta 3) existují k,l E Z tak, že ka + lb = 1, odkud plyne, že c = c(ka + lb) = kca + lbe. Protože a \ bc, plyne odsud, že i a \ c. ad 3. Nechť d = (a,b), pak existují q\,q2 E N tak, že a = dqi, b = dq2. Pak podle části (1) platí d = (a, b) = (dq±, dq2) = d-(q\, q2), a tedy (qi, q2) = 1. Naopak, je-li a = dqi, b = dq2 a (q\, q2) = 1, pak (a, b) = (dq\, dq2) = d(q\, q2) = d ■ 1 = d (opět užitím 1. části tohoto tvrzení). D Contents U ►► < ► Page 10 of 21 2. Prvočísla 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. Go Back Full Screen Close Quit Home Page Title Page 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, .... 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 230402457— 1 má pouze 9152 052 cifer). VĚTA 6. 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 E 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 \ b podle věty 5. „<=u 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 = - E N a platí p = ab, odkud 1 < a < p, 1 < b < p. Našli jsme tedy celá čísla a, b tak, že p \ ab a přitom p nedělí ani a, ani b. ' D PŘÍKLAD. Nalezněte všechna čísla k E N0, pro která je mezi deseti po sobě jdoucími čísly k + l,k + 2,... ,k + 10 nejvíce prvočísel. Řešení. Pro k = 1 je mezi našimi čísly pět prvočísel: 2, 3, 5, 7, 11. Pro k = 0 a k = 2 pouze čtyři prvočísla. Jestliže k > 3, není mezi zkoumanými čísly číslo 3. Mezi deseti po sobě jdoucími celými čísly pět sudých a pět lichých čísel, mezi kterými je zase aspoň jedno dělitelné třemi. Našli jsme tedy mezi čísly k + 1, Contents U ►► < ► Page Hof 21 Go Back Full Screen Close Quit Home Page Title Page k+ 2, ..., k + 10 aspoň šest složených, jsou tedy mezi nimi nejvýše čtyři prvočísla. Zadání proto vyhovuje jediné číslo k = 1. D 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 E {2,3,... ,n + 1} platí k \ (n + 1)!, a tedy k \ (n + 1)! + k, a proto (n + 1)! + k nemůže být prvočíslo. D Příklad. Dokažte, že pro libovolné prvočíslo p a libovolné k E N, k < p, je kombinační číslo (ľ) dělitelné p. Řešení. Podle definice kombinačního čísla 'p\ = p\ = p ■ {p - 1).....(p-k + 1) yk) k\{p-k)\ 1-2.....k a tedy k\ \ p ■ a, kde jsme označili a = (p — 1).....(p — k + 1). Protože k < p, není žádné z čísel 1,2,... ,k dělitelné prvočíslem p, a tedy podle věty 6 není ani k\ dělitelné prvočíslem p, odkud (k\,p) = 1. Podle věty 5 platí k\ \ a, a tedy b = |ý je celé číslo. Protože (ľ) = ^ = pb, je číslo (^) dělitelné číslem p. D Contents « ►► < ► Page 12 of 21 Go Back Full Screen Close Home Page Title Page VĚTA 7. Libovolné přirozené číslo n > 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 jako v 1.1 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 + \/—5) ■ (1 — \f—5); zkuste si rozmyslet, že všichni uvedení činitelé jsou skutečně v Z (a/—5) ireducibilní). 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. Contents « ►► < ► Page 13 of 21 Go Back Full Screen Close Quit Home Page Title Page Nyní dokážeme jednoznačnost. Předpokládejme, že platí rovnost součinů pí • P2.....Pm = Qi ■ Q2.....Qs, kde p\,... ,pm, q\,... ,qs jsou prvočísla a navíc platí P\ < P2 < • • • < Pm, 1, mělo by číslo p\ dělitele qx takového, že 1 < q\ < p\ (neboť g2 1), což není možné. Je tedy s = 1 a platí p\ = q\. Předpokládejme, že m > 2 a že tvrzení platí pro m— 1. Protože pí -p2.....pm = qi ■ q2.....qs, dělí pm součin q\.....qs, což je podle věty 6 možné jen tehdy, jestliže pm dělí nějaké $ pro vhodné i € {1,2,..., s}. Protože ^ je prvočíslo, plyne odtud pm = qi (neboť pm > 1). Zcela analogicky se dokáže, že qs = pj pro vhodné j E {1,2,..., m}. Odtud plyne qs = P j < P q% < qs takže Pm = qs- Vydělením dostaneme p\ ■ p2.....pm-\ = Q\ • Q2.....Qs-i, a tedy z indukčního předpokladu m — 1 = s — 1, p\ = q\,... ,pm-i = Qm-i- Celkem tedy m — s a pi = qi,,.. ,pm-i = Qm-i, Pm = Qm- Jednoznačnost, a proto i celá věta 7 je dokázána. D Contents U ►► < ► Page 14 of 21 Go Back Full Screen Close 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 Quit Home Page Title Page čí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/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). Že je problém rozkladu přirozeného čísla na prvočísla výpočetně složitý, o tom svědčí i výzva učiněná firmou RSA Security (viz http://www.rsasecurity.com/ rsalabs/node .asp?id=2093). Pokud se vám podaří rozložit čísla označená podle počtu cifer jako RSA-704, RSA-768, ..., RSA-2048, obdržíte 30 000, 50 000, resp. 200 000 dolarů (čísla RSA-576 a RSA-640 již byla rozložena v roce 2003, resp. 2005; byla-li vyplacena slíbená odměna, mi není známo). Contents « ►► < ► Page 15 of 21 Go Back DŮSLEDEK. (1) Jsou-lipi,... ,pk navzájem různá prvočísla a ri\. N0; je každý kladný dělitel čísla a = p™1.....p^k tvaru p™1..... nii, ■ ■ ■ ,rrik £ N0 a rrii < '^i, m-2 < '^2, ■ ■ ■, ink < nk-Číslo a má tedy právě mu Pk nk e , kde Full Screen Close r(a) = (ni + l)(n2 + l).....(nk + 1) Quit Home Page Title Page kladných dělitelů, jejichž součet je -i a-..... a (a) Pí ni,- Pk Pí- i- Pk- 1 (2) Jsou-li pí,... ,pk navzájem různá prvočísla a ri\, ..., rik, m\, ..., nik €= No a označíme-li r\ = mm{ní,m,i}, ti = max{ni,m,i} pro každé i = 1,2, k, platí (pT ■ ■ W ■ ■ pI\pT ■pI\pT pľk ■pT\ ) p? ň1 ■Pk ; Poznámka. 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 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 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ž: a je sudé dokonalé číslo, právě když je tvaru a = 29_1-(29—1); kde 2q — 1 je prvočíslo. 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" - obecně je pro velká čísla, u kterých se nedaří nalézt netriviálního Contents « ►► < ► Page 16 of 21 Go Back Full Screen Close Quit Home Page Title Page dělitele, obtížné prokázat, že jsou prvočísla. Pro Mersenneho prvočísla existuje poměrně jednoduchý a rychlý postup. 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). Na druhou stranu popsat lichá dokonalá čísla se dodnes nepodařilo, resp. dodnes se neví, jestli vůbec nějaké liché dokonalé číslo existuje PŘÍKLAD. Dokažte, že pro každé celé n > 2 existuje mezi čísly nan! alespoň jedno prvočíslo. Řešení. Označme p libovolné prvočíslo dělící číslo n\ — l (takové existuje podle věty 7, protože ni — 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. D 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 pi,P2, ■ ■ ■ ,Pn- Položme N = p\ ■ p2 .. .pn + 1. Toto číslo je buď samo prvočíslem nebo je dělitelné nějakým prvočíslem různým od pí,... ,pn (čísla pí,... ,pn totiž dělí číslo N — 1), což je spor. Contents « ►► < ► Page 17 of 21 Go Back Full Screen Close Quit Home Page Title Page (Kummer, 1878): Předpokládejme, že prvočísel je konečně mnoho a označme je pí < p2 < • • • < p«- Položme N = pí • p2 • • • p„ > 2. Číslo N — 1 je podle věty 7 dělitelné některým prvočíslem p», které dělí zároveň číslo N a tedy i N — (N — 1) = 1. Spor. (Fürstenberg, 1955): Contents « ►► 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 +OOJ. 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 a p 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. < ► Page 18 of 21 Go Back Full Screen Close D Home Page Title Page Příklad. Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3k keNo. 2, kde Contents Ř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 ■ P3.....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 3k+2, neboť v opačném případě by bylo N součinem prvočísel tvaru 3k + 1 (uvažte, že N není dělitelné třemi), a tedy podle příkladu na str. 3 by bylo i N tvaru 3k + 1, 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. D POZNÁMKA. Předchozí příklady je možné značně zobecnit. Platí totiž tvrzení: „Pro libovolné přirozené číslo n > 5 existují mezi čísly n a 2n alespoň dvě prvočísla", které zobecňuje Čebyševovu větu: „Pro každé číslo n > 3 existuje mezi čísly n a 2n — 2 alespoň jedno prvočíslo". Důkaz lze provést elementárními prostředky, je však poměrně dlouhý. Předchozí příklad zobecňuje Dirichletova věta o 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". 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. « ►► < ► Page 19 of 21 Go Back Full Screen Close Quit Home Page Title Page 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 p°p^ je nejvyšší mocninou prvočísla p, která dělí číslo n, nebo tím, že n = P«pW . m> kde m je ceié čí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(b) A a + b ^ 0 =^ vp(a + b) > vp(a) (9) Vp(a) < Vp(b) =^ Vp(a + b) = vp(a) (10) Vp(a)