Home Page Literatura [1] J. Herman, R. Kučera a J. Simša. Metody řešeni matematických úloh I MU Brno, druhé vydání, 2001. [2] K. Ireland a M. Rosen. A Classical Introduction to Modem Number Theory. Číslo 84 v Graduate Texts in Mathematics. Springer, druhé vydání, 1998. [3] I. M. Vinogradov. Základy theorie čísel. Nakladatelství ČSAV, 1953. Title Page Contents ► ► Page 1 of 51 Go Back Full Screen Close Quit Home Page Title Page Contents « ►► < ► Page 2 of 51 Go Back Full Screen Close Quit Home Page Algebra 2 — Teorie čísel Title Page Michal Bulant Contents KATEDRA MATEMATIKY, PŘÍRODOVĚDECKÁ FAKULTA, MASARYKOVA UNIVERZITA, Janáčkovo nám. 2a, 662 95 Brno « I ►► E-mail address: bulant@math.muni.cz " < | ► Page 3 of 51 Go Back Full Screen Close Quit Home Page Abstrakt. Na této přednášce se budeme zabývat úlohami o celých číslech. Převážně v nich půjde o dělitelnost celých čísel, popřípadě 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í. 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), 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 vetu (rozhodnout, zda existují přirozená čísla n, x, y, z tak, že n > 2 a platí xn + yn = zn). Tento text výrazně čerpá z knih [1] a [3], pro zájemce o bližší seznámení s nkterými tématy doporučujeme knihu [2], dostupnou v knihovně PřF MU. V mnoha problémech je výhodné vyzkoušet chování algoritmů na reálných příkladech. K tomu lze využít SW nainstalovaný na počítačích sekce matematika. Doporučujeme zejména: • PARI-GP : specializovaný SW na teorii čísel, při výpočtech s většími čísly obvykle výrazně efektivnější než obecně orientované balíky. Spouští se příkazem gp. Nejdůležitější příkazy: \q - ukončení, ? - help, ?? - kompletní uživatelský manuál, ?? tutorial - tutoriál pro úvodní seznámení. Viz také pari.math.u-bordeaux.fr. • Maple: vhodný zejména kvůli existenci mnoha výukových pracovních listů (worksheets, i pro teorii čísel), např. na www.mapleapps.com. Title Page Contents « ►► < ► Page 4 of 51 Go Back Full Screen Close Quit Obsah Literatura 1. Základní pojmy 1.1. Dělitelnost 1.2. Největší společný dělitel a nejmenší společný násobek 1.3. Dělitelé a násobky mnoha čísel 1.4. Nesoudělnost 2. Prvočísla 3. Kongruence 3.1. Základní vlastnosti kongruencí 3.2. Aritmetické funkce 3.3. Eulerova funkce ip 3.4. Malá Fermatova věta, Eulerova věta Home Page Title Page Contents « ►► < ► Page 5 of 51 1 6 6 9 14 15 18 31------------- 32 38 Go Back 41 44 Full Screen Close Quit Home Page Title Page 1. Základní pojmy Contents 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 6 of 51 n a I b A b I c =>- a \ c a | b A a \ c =^- a \ b + c A a \ b — c c^ 0 =^- (a | b <í=^ ac \ be) a\b A b > 0 =^ a < b PŘÍKLAD. Zjistěte, pro která přirozená čísla n je číslo n2 -1. (1) (2) (3) (4) 1 dělitelné číslem Go Back ŘEŠENÍ. Platí n2 - 1 = (n + í) (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 + Full Screen Close Quit Home Page Title Page 2, D 1) — (n2 — 1) = 2. Protože n E N, platí n + 1 > 2, a tedy z n+1 \ 2 plyne n + 1 proto n = 1. Uvedenou vlastnost má tedy jediné přirozené číslo 1. 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 G No 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', r' 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' = qm + 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'm + r1, tedy a = —q'm — r1. Je-li r' = 0, položíme r = 0, q = —q'; Contents je-li r > 0, 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 G N. Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla qi,q2 E Z; °T\,r2 E {0,1,... ,m — 1} platí a = q\m + V\ = q2vn + r2. Úpravou dostaneme r\ — r2 = ((?2 — Qi)m, a tedy m\r\ — r2. Ovšem z 0 < r\ < m, 0 < r2 < m plyne u ►► < ► Page 7 of 51 Go Back Full Screen Close Quit Home Page Title Page —m < T\ — ľ2 < m, odkud podle (4) platí r\ — r 2 = 0. Pak ale i (q2 — q\)m = 0, a proto q\ = q2, r\ = ľ2- čísla q, 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 Contents Q přitom 0 < — < 1. m a m 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 + t)m + 1 = qm + r, 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 POUŽITÍ v Pari-GP. Vydělením čísla 1234567890 číslem 321 se zbytkem dostáváme 3846005, zbytek 285 - jak vidíme v PARI: « ►► < ► Page 8 of 51 Go Back Full Screen Close Quit Home Page Title Page ? divrem(1234567890,321) °/„2 = [3846005, 285] ~ nebo i jinak: ? 1234567890\321 °/„3 = 3846005 ? 12345678907.321 °/„4 = 285 1.2. Největší společný dělitel a nejmenší společný násobek. Definice. Mějme celá čísla ai,a2- Libovolné celé číslo 777 takové, že 777 | a\, 777 I a2 (resp. cl\ \ m, a2 I "7) se nazývá společný dělitel (resp. společný násobek) čísel ai,ß2- Společný dělitel (resp. násobek) 777 > 0 čísel 0,1,0,2, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel a\, 02, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel a\,02 a značí se (01,02) (resp. [01,02]). Poznámka. Přímo z definice plyne, že pro libovolné a, b G Z platí (a, 6) = (b, a), [a,b] = [b,a], (a, 1) = 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 7771,7772 G N0 totiž podle (4) platí, že pokud 7771 | 7772 a zároveň 7772 | 7771, je nutně 7771 = 7772. Důkaz existence Contents « ►► < ► Page 9 of 51 Go Back Full Screen Close Quit Home Page Title Page čí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_\. Pak po konečném počtu kroků dostaneme o^Oa platí ak-\ = («i, a2). DŮKAZ. Podle věty 1 platí a2 > a3 > «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 au = 0, přičemž ak-i ^ 0. Z definice čísel an plyne, že existují celá čísla qi, q2,. ■ ■, qk-2 tak, že Contents « ►► < ► Page 10 of 51 üi = qi ■ a2 + aa, a2 = q2 ■ a3 + a4, öfc-3 = qk-3 ■ O-k-2 + öfc-l ßfc-2 = Qk-2 • ßfc-1- (5) Z poslední rovnosti plyne, že afc-i | ßfc-2, z předposlední, že afc-i | ßfc-3, atd., až nakonec ze druhé ük-i \ a2 a z první dostaneme ük-i \ a\. Je tedy ßfc_i společný dělitel čísel a\, a2. Naopak jejich libovolný společný dělitel dělí i číslo a3 = a\ — qia2, Go Back Full Screen Close Quit Home Page Title Page proto i CI4 = ü2 — 02.03, ■ ■ ■, a proto i Ok-i cik-i je největší dělitel čísel 0\,02- ßfc-3 — Qk-adk-2- Dokázali jsme, že D POZNÁMKA. Z poznámky za definicí, z věty 2 a z toho, že pro libovolná a, b E Z platí (a, 6) = (a, —6) = (—a, 6) = (—a, —b) plyne, že existuje největší společný dělitel libovolných dvou celých čísel. VĚTA 3. (Bezoutova) Pro libovolná celá čísla 0,1,0,2 existuje jejich největší společný dělitel (01,02), přitom existují celá čísla k\,k.2 tak, že (01,02) = k\0\ + /ř2«2- DŮKAZ. Jistě stačí větu dokázat pro a\,02 E N. Všimněme si, že jestliže je možné nějaká čísla r, s E Z vyjádřit ve tvaru r = r\0\ + r2a2, s = s\d\ + s2ß2, kde fi, ?*2> Si,s2 E Z, můžeme tak vyjádřit i r + s = (r i + si)oi + (r2 + s2)o2 a také c- r = (c- rx)ai + (c- r2)a2 pro libovolné c E Z. Protože o\ = 1 ■ o\ + 0 ■ 02, 02 = 0 ■ o\ + 1 ■ 02, plyne z (5), že takto můžeme vyjádřit i 03 = 0\ — q\02, «4 = O2 — O2O?,, ... , Ok-i = Ok-3 — qk-30k-2, což je ovšem (o\, 02). □ POUŽITÍ v Pari-GP. 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ě Contents « ►► < ► Page Hof 51 Go Back Full Screen Close Quit Home Page Title Page 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=nextprime(5*10~100); ? q=nextprime(3*10"100); ? r=nextprime(10~100); ? A=p*q; ? B=q*r; ? # timer = 1 (on) ? gcd(A,B) t ime = 0 ms. °/„19 = 300000000000000000000000000000000000000000X oooooooooooooooooooooooooooooooooooooooooooooooox 00000000223 ? bezout(A,B) t ime = 0 ms. °/„20 = [284455128205128205128205128205128205128205\ 1282051282051282051282051282051282051282051282051\ 282051358, -1422275641025641025641025641025641025\ 6410256410256410256410256410256410256410256410256\ Contents « ►► < ► Page 12 of 51 Go Back Full Screen Close Home Page Title Page 410256410256435, 30000000000000000000000000000000\ ooooooooooooooooooooooooooooooooooooooooooooooooox 00000000000000000223] Poznámka. Euklidův algoritmus a Bezoutova věta jsou jedny z nejdůležitějších výsledků elementární teorie čísel a tvoří jeden ze základních 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 B. Willis a Samuel Jackson ve filmu Smrtonosná past 3, kde mají za úkol zlikvidovat bombu pomocí 4 galonu vody, přičemž k dispozici mají pouze nádoby na 3, resp. 5 galonu. Zde stačí s využitím Euklidova algoritmu najít celá čísla k, l tak, že bude platit 3k + bl = 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, což podrobně rozebereme v části o diofantických rovnicích. VĚTA 4. Pro libovolná celá čísla ai,ci2 existuje jejich nejmenší společný násobek [01,02] a platí (ai, 02) • [01, 02] = ]oi • a 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 14 of 51 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 15 of 51 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 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 Contents « ►► < ► Page 16 of 51 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, contents 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 € Z tak, že ka + lb = 1, odkud plyne, že c = c(ka + /&) = kca + /6c. « |__►►_ Protože a \ bc, plyne odsud, že i a \ c. ad 3. Nechť d = (a,b), pak existují q\,q2 £ N tak, že a = dqi, b = dq2- Pak podle části (1) platí d = (a, b) = (dqi, dq2) = d-(q\, q2), a tedy (q\, q2) = 1. Naopak, ^ I__^_ 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 Page 17 of 51 Go Back Full Screen Close Quit Home Page Title Page 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. 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. „=>u 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. Contents « ►► < ► Page 18 of 51 Go Back Full Screen Close Quit Home Page Title Page „<=" 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. ' -■ n Příklad. Nalezněte všechna čísla fc e No, 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, 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. Contents U ►► < ► Page 19 of 51 Go Back Full Screen Close Quit Home Page Title Page Ř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 ■ u, 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 = Jr je celé číslo. Protože (^) = ff = pb, je číslo (^) dělitelné číslem p. D 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 + i/—5) • (1 — \f—5); zkuste si rozmyslet, že všichni uvedení činitelé jsou skutečně v rLiy\f—5) ireducibilní). DŮKAZ. Nejprve dokážeme indukcí, že každé n > 2 je možné vyjádřit jako součin prvočísel. Contents « ►► < ► Page 20 of 51 Go Back Full Screen Close Quit Home Page Title Page 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ů p\ ■ p2.....pm = Qi ■ Q_2.....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ť q2q3 ■ ■ ■ qs > 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 = qx ■ q2.....qs, dělí pm součin qx.....qs, což je podle věty 6 možné jen tehdy, jestliže pm dělí nějaké $ pro vhodné i E {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 Contents « ►► i ► Page 21 of 51 Go Back Full Screen Close qs = P j < P- Qi < qs, Quit Home Page Title Page takže pm = qs. Vydělením dostaneme pí ■ P2.....pm-i — Qi ' Q2.....Qs-i, a tedy z indukčního předpokladu m — 1 = s — 1, p\ = q\,... ,pm-i = qm-\- 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 « ►► 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/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). < ► Page 22 of 51 Go Back Full Screen Close Quit Home Page Title Page DŮSLEDEK. (1) Jsou-lipi,... ,pk navzájem různá prvočísla a ri\, No, je každý kladný dělitel čísla a = p™1.....p^k tvaru p™1..... ni\, ■ ■ ■ ,rrik £ No a ni\ < ri\, rri2 < ri2, ■ ■ ■, nik < nečíslo a má tedy právě T(a) = (m + l)(na + l).....{nk + 1) kladných dělitelů, jejichž součet je rai + l _ -, rifc+l _ i „(r,\ Pl_____t Pk_____i- ffw =--------r~ • • •--------r~ ■ pí - i Pk - i (2) Jsou-li pí,... ,pk navzájem různá prvočísla ari\, ..., rik, ni\, . mi, Pk , kde mk e N0 a označíme-li r. 1,2,... ,k, platí (P?..... m.m{ni,nii}, ti = maxjii^TOj} pro každé i nk mi Pk iPl [pT.....p!\pT ,«ifc\ Pk ■pT\ ■p? pí1 *■*■ ■Pk > p{k. 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). Contents « ►► < ► Page 23 of 51 Go Back Full Screen Close Quit Home Page Title Page 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 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 n a n\ alespoň jedno prvočíslo. Řešení. Označme p libovolné prvočíslo dělící číslo nl — 1 (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 nl — 1. Je tedy n < p. Protože p | (n! — 1), platí p < ni — 1, tedy p < ni. 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. Contents « ►► < ► Page 24 of 51 Go Back Full Screen Close Quit Home Page Title Page DŮKAZ. (Eukleides) Předpokládejme, že prvočísel je konečně mnoho a označme je pi,P2, • • • ,Pra- Položme N = p\ -p? .. .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. (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 +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í Contents « ►► < ► Page 25 of 51 Go Back Full Screen Close Quit Home Page Title Page 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 3k k E No. D 2, kde Řešení. Předpokládejme naopak, že existuje pouze konečně mnoho prvočísel tohoto tvaru a označme je p\ — 2, pi — 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. 8 by bylo i N tvaru 3k + 1, což neplatí. 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. D Předchozí příklady je možné značně zobecnit. Platí totiž tvrzení, které bývá nazýváno Bertrandovým postulátem nebo Čebyševovou větou: VĚTA 9. (Čebyševova) (1) libovolné přirozené číslo n > 5 existují mezi čísly n a 2n alespoň dvě prvočísla. Contents « ►► < ► Page 26 of 51 Go Back Full Screen Close Quit Home Page Title Page (2) Pro každé číslo n > 3 existuje mezi čí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. Viz např. http://matholymp.com/TUTORIALS/Bertrand. pdf D 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": VĚTA 10. (o hustotě prvočísel) Nechť ir(x) udává počet prvočísel menších nebo rovných číslu i6l. Pak %{x) ~ -—, mír tj. podíl funkcí tt(x) a x/lux se pro x —► oo limitně blíží k nule. 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 1 £ Přitom např. p prvočíslo raGN P OO. 7T T' Contents a ►► < ► Page 27 of 51 Go Back Full Screen Close Quit Home Page Title Page což znamená, že prvočísla jsou v N rozmístěna „hustěji" než druhé mozniny. POUŽITÍ v Pari-GP. O tom, jak odpovídá asymptotický odhad ir(x) ~ x/ln(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. ? ¥=[100,1000,10000,100000,500000]; ? f or (k=l, 5, print (v [k] , „k", primepi (v [k]), ,,&" , \ v[k]/log(v[k]),M&",\ (primepi(v[k])-v[k]/log(v[k]))/primepi(v[k]))) x n (x) x/ In (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 Contents « ►► < ► Page 28 of 51 Go Back Full Screen Poslední příklad (o nekonečnosti počtu prvočísel tvaru 3k richletova věta o aritmetické posloupnosti: 2) zobecňuje Di- VĚTA 11. (Dirichletova) 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. Close Quit Home Page Title Page 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ř. [2, kap. ???] D Contents « ►► 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 = pvp(n) . 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) 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í. < ► Page 29 of 51 Go Back Full Screen Close Quit Home Page Title Page Příklad. Dokažte, že pro libovolná přirozená čísla a, b, c platí Contents ([a,b],[a,c],[b,c]) = [(a,b),(a,c),(b,c)] Řešení. Podle věty 7 budeme hotovi, ukážeme-li, že vp(L) = vp(P) pro libo- « I ►► volné 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(d), vp((b, c)) = vp(b), odkud vp(L) = vp(b) = vp(P), což jsme měli dokázat. D Page 30 of 51 Go Back Full Screen Close Quit Home Page Title Page 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 m), 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 E Z, m E N jsou následující podmínky ekvivalentní: (1) a = b (mod m), (2) a = b + mt pro vhodné t E Z, (3) m | a — b. DŮKAZ. „(1)=^(3)" Jestliže a = q\m + r, b = q^m + r, pak a — b= (q\ — q2)m. „(3)=>-(2)" Jestliže m \ a — b, pak existuje t E Z tak, že m ■ t = a — b, tj. a = b + mt. Contents U ►► < ► Page 31 of 51 Go Back Full Screen Close Quit Home Page Title Page „(2)=>(1)" Jestliže a = b+mt, pak z vyjádření b ■ tedy a i b mají při dělení číslem m týž zbytek r, tj. = rnq+r plyne a ■ a = b (mod m). m(q+t)+r, D 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 E Z), symetrická (tj. pro každé a,b E Z z a = b (mod m) plyne b = a (mod m)) a tranzitivní (tj. pro každé a,b,c E Zz a = b (mod m) a b = c (mod m) plyne a = c (mod m)) relace, jde tedy o ekvivalenci. Dokážeme nyní další vlastnosti: VĚTA 12. (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. Na libovolnou stranu kongruence můžeme přičíst jakýkoliv násobek modulu. DŮKAZ. Je-li a\ = b\ (mod m) a «2 = 62 (mod m), existují podle lemmatu í1;í2 £ ^ tak, že a\ = b\ + mti, a2 = b2 + mr2- Pak ovšem ai + a2 = bi + b2 + m(ti + t2) a opět podle lemmatu a\ + a2 = b\ + b2 (mod m). Sečteme-li kongruencí a+b = c (mod m) s kongruencí —6 = —b (mod m), která zřejmě platí, dostaneme a = c — b (mod m). Sečteme-li kongruencí a = b (mod m) s kongruencí mfc = 0 (mod m), jejíž platnost je zřejmá, dostaneme a + mk = b (mod m). D Contents U ►► < ► Page 32 oř 51 Go Back Full Screen Close Quit Home Page Title Page (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 ax t\,t2 £ Z tak, že a,\ - = b\ (mod to) a a2 = &2 (mod to), existují podle b\ + míi, «2 = &2 + wÍ2- Pak ovšem aia2 = (&i + mti)(b2 + mí2) = &1&2 + m(tib2 + M2 + mtit2), odkud podle dostáváme aiß2 = b\b2 (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 ara = 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 ara+1 = 6ra+1 (mod m,), což je tvrzení pro n + 1. Důkaz indukcí je hotov. Jestliže vynásobíme kongruenci a = b (mod to) a kongruenci c = c (mod m), dostaneme ac = be (mod to). D (3) 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 (to, d) = 1. Podle lemmatu je rozdíl a — 6 = (ai — 61) • d dělitelný číslem Contents U ►► < ► Page 33 of 51 Go Back Full Screen Close Quit Home Page Title Page m. Protože (m, d) = 1, je podle věty 5 číslo a\ — b\ také dělitelné číslem m, odtud podle lemmatu plyne a\ = b\ (mod m). D (4) Obě struny 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 = be (mod mc). D (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 = b\ ■ d, m = mi ■ d, kde d E N. Podle lemmatu existuje t E Z tak, že a = b + mt, tj. a\-d = bi-d + rriidt, odkud ax = bi+rriit, což podle lemmatu znamená, že a\ = bi (mod mi). D (6) Jestliže kongruence a = b platí podle různých modulů mi,..., mfc; platí i podle modulu, kterým je nejmenší společný násobek [mi,..., mk] těchto čísel. DŮKAZ. Jestliže a = b (mod mi), a = b (mod m2),... ,a = b (mod rrik), podle lemmatu je rozdíl a — b společný násobek čísel mi,m2,..., m^ a Contents « ►► < ► Page 34 of 51 Go Back Full Screen Close Quit Home Page Title Page tedy je dělitelný jejich nejmenším společným násobkem [mi, 7712, ■ ■ ■, nik], odkud plyne a = b (mod [mi,..., m*]). D (7) Jestliže kongruence platí podle modulu ra, platí podle libovolného modulu d, který je dělitelem čísla ra. DŮKAZ. Jestliže a = b (mod m), je a — b dělitelné m, a proto také dělitelem d čísla m, odkud a = b (mod d). 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, m = raid. Pak podle lemmatu existuje t E Z tak, že a = b + rat = b\d + ra\dt = (bi + ra\ť)d, a tedy d \ a. D Poznámka. Některé vlastnosti kongruencí jsme již používali, aniž bychom si toho povšimli - například příklad ze strany 8 lze přeformulovat do tvaru „jestliže a = 1 (mod m), 6 = 1 (mod m), pak také ab = 1 (mod m)", což je speciální případ tvrzení věty 12 (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 Contents « ►► < ► Page 35 of 51 Go Back Full Screen Close Quit Home Page Title Page 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 12 (2) -20 (-1) 10 (mod 26), a tedy zbytek po dělení čísla 5 číslem 26 je jedna. Příklad. Dokažte, že pro libovolné n e N je 37ra+2 sedmi. 16 ra+l D 23ra dělitelné ŘEŠENÍ. Platí 37 = 16 = 23 = 2 (mod 7), a tedy podle 12 (2) a (1) platí 37n+2 + 16n+l + 23n _ 2n+2 + T+l + T = 2^(4+2+1) = T ■ 7 = 0 (mod 7), což jsme chtěli dokázat. D Příklad. Dokažte, že číslo n = (8355 + 6)18 - 1 je dělitelné číslem 112. Ř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 12 n = (25 + 6)18 - 1 = 3818 - 1 = 318 - 1 = 276 - 1 = (-1)6 - 0 (mod 7), Contents u ►► < ► Page 36 of 51 Go Back Full Screen Close Quit Home Page Title Page proto 7 I n. Podobně 835 = 3 (mod 16), a tedy n = (35 + 6) 18 (3 • 81 + 6) 18 9 18 (3-1 + 6) . =819-] 18 0 (mod 16), proto 16 | n. Celkem tedy 112 | n, což jsme měli dokázat. D Příklad. Dokažte, že pro libovolné prvočíslo p a libovolná a, b E Z, platí ap + bp = (a + b)p (modp). Řešení. Podle binomické věty platí (a + bf = ap P\nP~l a'' *b py,P-2h2 )ar 2b2 p,)abp-1 p—u W. Podle příkladu za větou 6 pro libovolné k E {1,... ,p— 1} platí (|) odkud plyne tvrzení. Následující tvrzení je další užitečnou vlastností kongruencí: 0 (mod p), D Lemma. Dokažte, že pro libovolné přirozené číslo m a libovolná a, b E Z taková, že a = b (mod mn), kde n eN, platí, že am = bm (mod mn+l). DŮKAZ. Platí bm = (a-b){am-l + -ra—2r ab m-2 + bm~L) (12) Contents a ►► < ► Page 37 of 51 Go Back Full Screen Close Quit Home Page Title Page a protože m \ mn, tak podle 12 (7) platí i a = b (mod m). Jsou tedy všechny sčítance ve druhé závorce v (12) kongruentní s am~l modulo m, a tedy ..m—\ -,m—1 am~2b ~,m-2 i + abm~2 + bm~l abm-2 + bm-l m ■ a m—l 0 (mod m), proto je a"1 i + a"1 z + • • • + ab"1 z + bm i dělitelné m. Z a = b (mod m11) plyne, že mn dělí a — b, a tedy mn+l dělí jejich součin, což vzhledem k (12) vede k závěru, ze a bm (mod mn+1). D 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 ß(n) definujeme rovnu 0, pokud pro některé i platí olí > 1 a rovnu (—l)fc v opačném případě. Dále definujeme ß(l) = 1. Příklad. ß{A) = ß(22) = 0,/x(6) = p{2 ■ 3) = (-l)2,/i(2) = ^(3) = -1. Dokážeme nyní několik důležitých vlastností Möbiovy funkce, zejména tzv. Möbiovu inverzní formuli. Lemma. Pro n e N \ {1} platí d\n ß(d) = 0. Contents u ►► < ► Page 38 of 51 Go Back Full Screen Close Quit Home Page Title Page DŮKAZ. Zapíšeme-li n ve tvaru n = p"1 ■ ■ ■ p%k, pak všechny dělitele d čísla n jsou tvaru d = pf1 ■ • -pffc, kde 0 < ßi < cti pro všechna iE {!,..., k}. Proto ^2n(d) E ^■■■pík) d\n (ßi,...,ßk)e(Nu{o})k 0 1, resp. I (n) = 1 pro všechna n E N. Pak pro každou aritmetickou funkci / platí: foI = Iof = f Contents « ►► < ► Page 40 of 51 (Iof)(n) = (foI)(n) = Y,f(d). d\n Dále platí Ioß = ßoI = I, neboť (/o/x)(n) = £l(d)M?) = £/(i)M<0 = d\n d\n = y y/i( 1 (i|ra podle lemmatu za definicí Möbiovy funkce (pro n = 1 je tvrzení zřejmé). Go Back Full Screen Close Quit Home Page Title Page VĚTA 13. (Möbiova inverzní formule) Nechť je aritmetická funkce F definovaná pomocí aritmetické funkce f předpisem F(n) = J2d\nf(d). Pak lze funkci f vyjádřit ve tvaru f(n) = J2KBd)-nd). d\n DŮKAZ. Vztah F(n) = J2din f(d) lze jiným způsobem zapsat jako F = f o L Proto Foß = (yfoI)oß = fo(yIoß) = fol = f7 což je tvrzení věty. D DEFINICE. Multiplikativní funkcí přirozených čísel rozumíme takovou aritmetickou funkci, která splňuje, že pro všechny dvojice nesoudělných čísel a, b E N platí f (a -b) = f (a) -f (b). Příklad. Multiplikativními funkcemi jsou např. funkce f(n) = o~(n), f(n) = r(n), či f(n) = ß(n) nebo, jak brzy dokážeme i tzv. Eulerova funkce f(n) = (f(n). 3.3. Eulerova funkce ip. Definice. Nechť n£N. Definujme Eulerovu funkci ip předpisem - (n, a) = 1 A (n, b) = 1. Spolu se snadno odvoditelným výsledkem ^(p«) =pa- pa~l = (p - 1) • pa~l (14) pak lze odvodit vztah (13) již třetím způsobem. Příklad. Vypočtěte 1 nalezněte zbytek po dělení čísla 2 2 Příklad. Určete řád čísla 2 modulo 7. ŘEŠENÍ. 21 = 2 ^ 1 (mod 7) 22 = 4 ^ 1 (mod 7) 23 = 8 = 1 (mod 7) Contents a ►► < ► Page 48 of 51 Go Back Full Screen Close Řád čísla 2 modulo 7 je tedy roven 3. D Quit Home Page Title Page Uveďme nyní několik zásadních tvrzení udávajících možné hodnoty řádu čísla modulo m: Lemma. Nechť m E N, a, b E Z, (a, m) = (b, m) = 1. Jestliže a = b (mod m), pak obě čísla a, b mají stejný řád modulo m. DŮKAZ. Umocněním kongruence a = b (mod m) na n-tou dostaneme an = bn (mod m), tedy an = 1 (mod m) -<=>- bn = 1 (mod m). D Lemma. Nechť m E N, a E Z, (a, m) = 1. Je-li řád čísla a modulo m roven r ■ s, (kde r, s E N), pak řád čísla aľ modulo m je roven s. DŮKAZ. Protože žádné z čísel a, a2, a3,..., ars~l není kongruentní s 1 modulo m, není ani žádné z čísel of, a2r, a3r,..., a^s~^r kongruentní s 1. Platí ale (ar)s = 1 (mod m), proto je řád ď modulo m roven s. D Poznámka. Opak obecně neplatí - z toho, že řád čísla ď modulo m je roven s ještě neplyne, že řád čísla a modulo m je r • s. Pi: m = 13 a = 3, a2 = 9 (mod 13), a3 = 27 = 1 (mod 13) =^> 3 má řád 3 mod 13. b = -4, b2 = 16 ^ 1 (mod 13), b3 = -64 = 1 (mod 13) => -4 má řád 3 modulo 13. Přitom (—4)2 = 16 = 3 (mod 13) má stejný řád 3 jako číslo 3, ale číslo —4 nemá řád 2 • 3. Přesný popis závislosti řádu na exponentu dávají následující 2 věty: Contents « ►► < ► Page 49 of 51 Go Back Full Screen Close Quit Home Page Title Page VĚTA 17. Nechť m G N, a G Z, (a, m) Pak pro libovolná ŕ, s G N U {0} platí a!' = as (mod m) <= 1. Označme r řád čísla a modulo m. t = s (mod r). DŮKAZ. Bez újmy na obecnosti lze předpokládat, že t > s. Vydélíme-li číslo t — s číslem r se zbytkem, dostaneme t — s = q ■ r + z, kde q, z G No, 0 < z < r. Protože t = s (mod r), máme z = 0, a tedy a í-s gr (ar)q lq (mod m). Vynásobením obou stran kongruence číslem as dostaneme tvrzení. Z a* (mod m) plyne as • a' qr+z (mod m). Protože je ar (mod m), je rovněž a' qr+z (mod m). Celkem po vydělení obou stran kon- gruence číslem as (které je nesoudělné s modulem), dostáváme oř = 1 (mod m). Protože z < r, plyne z definice řádu, že z = 0, a tedy r | ŕ — s. D Zřejmým důsledkem předchozí věty a Eulerovy věty je následující tvrzení (jehož druhá část je přeformulováním Lagrangeovy věty z Algebry pro naši situaci): DŮSLEDEK. Nechť m G N, a G Z, (a, m) = 1. Označme r řád čísla a modulo m. (1) Pro libovolné n G N U {0} platí an = 1 (mod m) (2) r |