Literatura [1] J. Herman, R. Kučera a J. Simša. Metody řešení 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. 1 Algebra 2 — Teorie čísel Michal Bulant katedra matematiky, přírodovědecká fakulta, kova univerzita, janáčkovo nám. 2A, 662 95 brno E-mail address: bulant@math.muni.cz 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 nejjed-nodušší 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 nej-zná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 větu (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, ?? tutoriál - 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. Literatura 1. Základní pojmy 2. Prvočísla 3. Kongruence Obsah 1 6 12 19 5 6 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: a | b A b | c ==> a \ c (1) a | b A a \ c ==> a\b + cř\a\b — c (2) c 0 ==> (a | b <í=> ac \ bc) (3) a\b A b>0 ==> a 2, a tedy z n + 1 | 2 plyne n + 1 = 2, 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 + r', tedy a = —q'm — r'. Je-li r' = 0, položíme r = 0, g = —g'; je-li r > 0, položíme r = m — r', q = —q' — 1. V obou případech a = q ■ m + r, a tedy čísla g, r s požadovanými vlastnostmi existují pro každé a G Z, m G N. 7 Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla q±,q2 G Z; Ti,r2 G {0,1,. .. ,m — 1} platí a = q\m + r\ = q2in + r2. Úpravou dostaneme r\ — r2 = (g2 — qi)m, a tedy m \ r\ — r2. Ovšem z 0 < r-y < m, 0 < r2 < m plyne — m < r\ — r2 < m, odkud podle (4) platí r-y — r2 = 0. Pak ale i (q2 — qi)m = 0, a proto qi = g2, r\ = r2. Čísla q, r jsou tedy určena jednoznačně. Tím je důkaz ukončen. □ Čí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 a r 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 G Z číslem m G N jedna, je jedna i zbytek po dělení čísla ab číslem m. Řešení. Podle věty 1 existují s, ŕ G 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, kde q = stm + s + ŕ, r = 1, které je podle věty 1 jednoznačné, a tedy zbytek po dělení čísla ab číslem m je jedna. □ 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: ? divrem(1234567890,321) '/.2 = [3846005, 285] ~ nebo i jinak: ? 1234567890X321 '/.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 m takové, že m | ai, m | a2 (resp. a! m, a2 m) se nazývá společný dělitel (resp. společný násobek) čísel ai,a2. Společný dělitel (resp. násobek) m > 0 čísel ai,a2, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel ai,a2, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel ai,a2 a značí se (ai, a2) (resp. [ai, a2]). Poznámka. Přímo z definice plyne, že pro libovolné a, 6 G Z platí (a, 6) = (6, a), [a, 6] = [6, 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 £ Z čísla (a, b) a 8 [a, b] vůbec existují. Pokud však existují, jsou určena jednoznačně: Pro každá dvě čísla mi,m2 E No totiž podle (4) platí, že pokud m\ \ m2 a zároveň m2 | mi, je nutně m\ = 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ť ai,a2 jsou přirozená čísla. Pro každé n > 3, pro které an-\ 7^ 0, označme an zbytek po děleni čísla an_2 číslem an_\. Pak po konečném počtu kroků dostaneme ak = 0 a platí (2fc_i = (01,02)- DŮKAZ. Podle věty 1 platí a2 > > a4 > .... 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 = 0, přičemž ak_i 7^ 0. Z definice čísel an plyne, že existují celá čísla ql5 q2, ■ ■ ■, Qk-2 tak, že ai = qi ■ a2 + a3, a-2 = s = s±ai + s2a2, kde r±, r2, s±, s2 E Z, můžeme tak vyjádřit i r + s = {r x + si)ai + (r2 + s2)a2 a také c • r = (c • ri)ai + (c • r2)a2 pro libovolné c G Z. Protože ai = 1 • ai + 0 • a2, a2 = 0 • ai + 1 • a2, plyne z (5), že takto můžeme vyjádřit i a% = a± — q±a2, a^ = a2 — q2a%, ..., ak-i = ak-3 - 0 čísel ai, a2,..., 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 ai, a2,. .., an a značí se (oi, 02, ..., an) (resp. [ai, a2,. .., an\). Snadno se přesvědčíme, že platí (oi,. .., an_i, an) = ((oi,.. ., an_i), an), (6) [ai,.. ., a„_i, an] = [[ai,. .., a„_i], an\. (7) Největší společný dělitel (oi,..., an) totiž dělí všechna čísla ai,... ,an, a tedy je společným dělitelem čísel oi, ..., a„_i, a proto dělí i největšího společného dělitele (oi,. .., a„_i), tj. (oi,. .., an) \ ((oi, .. ., a„_i), an). Naopak největší společný dělitel čísel (oi,..., a„_i), an musí kromě čísla an dělit i všechna čísla oi,.. ., a„_i, protože dělí jejich největšího společného dělitele, a proto (((21, ..., (2ra-i), an) \ (ai,.. ., an). 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 72 čísel indukcí vzhledem k 72: pro 72 = 2 je jejich existence dána větami 2 a 4, jestliže pro některé 72 > 2 víme, že existuje největší společný dělitel i nejmenší společný násobek libovolných 72 — 1 čísel, podle (6) a (7) existuje i pro libovolných 72 čísel. 11 1.4. Nesoudělnost. Definice. Čísla a\, a2,..., an G Z se nazývají nesoudělná, jestliže platí (ai, a2, ■ ■ ■, an) = 1. Čísla 0,1,0,2,... ,an G Z se nazývají po dvou nesoudělná, jestliže pro každé í, j takové, že 1 < í < j < n, platí (aj, Oj) = 1. poznámka. v případě n = 2 oba pojmy splývají, pro n > 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, nebot 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í 291-l = 228(263 -l) + 228 -l, 263 _ 1 = (235 + 27)(228 -l) + 27-l, 22S_1 = (22i + 214 + 27 + l)(27-l). 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 G N tak, že a = dqi, b = dq2 a (gi, g2) = 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 G Z tak, že (a, b) = ka + Ib. Protože (ac, bc) je společný dělitel čísel ac, bc, dělí i číslo 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 a | bc. Podle Bezoutovy věty (věta 3) existují k, l G Z tak, že ka + Ib = 1, odkud plyne, že c = c(ka + Ib) = kca + lbe. Protože a \ bc, plyne odsud, že i a \ c. ad 3. Necht d = (a, b), pak existují gi,g2 G N tak, že a = dqi, b = dq2. Pak podle části (1) platí d = (a, b) = (dqi, dq2) = d ■ (gi, q2), a tedy (gi,g2) = 1. Naopak, je-li a = dqi, b = dq2 a (gi,g2) = 1, pak (a,b) = (dqi,dq2) = d(qi,q2) = d ■ 1 = d (opět užitím 1. části tohoto tvrzení). □