Literatura
[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:
a | b A b | c   =>-    a \ c                                                   (1)
a | b A a \ c   =>-    a\b + cAa\b — c                      (2)
c^ 0    =>-    (a | b <í=^ ac \ bc)                           (3)
a | b A b > 0   =^   a<b                                         (4)
Příklad. Zjistěte, pro která přirozená čísla n je číslo n2 + 1 dělitelné číslem n + 1.
Ř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 + 1) — (n2 — 1) = 2. Protože nel, 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í.
i
2
Předpokládejme nyní, že a > maž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' = o'to + r' a přitom r' G {0,1,... ,m — 1}. Zvolíme-li g = q' + l, r = r', platí a = a' + m = (q' + ľ)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, q = —q'; 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 E Z, m EN.
Nyní dokážeme jednoznačnost. Předpokládejme, že pro některá čísla qi,q2 E Z; ri,r2 G {0,1,... ,m - 1} platí a = q\m + r\ = q2m + r2. Úpravou dostaneme ri — r2 = (q2 — qi)iTi, a tedy m \ r\ — 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 (q2 — qi)m = 0, a proto q\ = q2, 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
a             r        v.          n ^  r
— = q H-----,     pritom    U < — < 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,
kde q = stm + s +1, 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 a\,a2. Libovolné celé číslo m takové, že m | a\, m \ a2 (resp. a\ \ m, a2 \ m) se nazývá společný dělitel (resp. společný násobek) čísel a\,a2. Společný dělitel (resp. násobek) m > 0 čísel a\,a2, který je dělitelný libovolným společným dělitelem (resp. dělí libovolný společný násobek) čísel a\,a2, se nazývá největší společný dělitel (resp. nejmenší společný násobek) čísel a\,a2 a značí se (a\,a2) (resp. [01,02])-
Poznámka. Přímo z definice plyne, že pro libovolné a, b E Z, platí
(a, b) = (b, a), [a, b] = [b,a], (a, 1) = 1, [a, 1] = \a\, (a, 0) = \a\, [a, 0] =
3
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,rri2 E No totiž podle (4) platí, že pokud rri\ \ rri2 a zároveň m2 | mi, je nutně rri\ = rri2- 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-i ^ 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í ük-i = (01,02).
DŮKAZ. Podle věty 1 platí 02 > 03 > 04 > .... 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 o^ = 0, přičemž ßfc-i 7^ 0. Z definice čísel an plyne, že existují celá čísla Oi, q2,..., qk-2 tak, že
Oi = »i • a2 + 03, 02 = 02 • 03 + 04,
!                                                                   (5)
Ofc-3 = Ofc_3 • Ofc-2 + Ofc-1 Ofc-2 = Ofc-2 - Ofc-1-
Z poslední rovnosti plyne, že au-i \ Ofc-2, z předposlední, že Ofc_i | Ofc_3, atd., až nakonec ze druhé au-i \ a2 a z první dostaneme Ofc_i | oi. Je tedy Ofc-i společný dělitel čísel 01,02- Naopak jejich libovolný společný dělitel dělí i číslo 03 = 01 — 01O2, proto i 04 = 02 — 02O3,..., a proto i Ofc-i = Ofc-3 —Ofc-30fc_2- Dokázali jsme, že Ofc_i je největší dělitel čísel 01, a,2-                                                                                         □
POZNÁMKA. Z poznámky za definicí, z věty 2 a z toho, že pro libovolná a, b E Z platí (o, b) = (o, —b) = (—0, b) = (—0, —b) plyne, že existuje největší společný dělitel libovolných dvou celých čísel.
VĚTA 3. (Bezoutova) Pro libovolná celá čísla 01,02 existuje jejich největší společný dělitel (01,02), přitom existují celá čísla fci,/^ tak, že (01,02) = fciOi + fc2o2.
DŮKAZ. Jistě stačí větu dokázat pro 01,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 = riOi + f202, s = s\a\ + S2O2, kde r\, f2, s\, S2 E Z, můžeme tak vyjádřit i
r + s = (r i + Si)oi + (r2 + s2)a2
a také
c- r = (c- ri)oi + (c- r2)a2
4
pro libovolné c E Z. Protože cl\ = 1 • cl\ + 0 • a2, ci2 = 0 • a\ + 1 • a2, plyne z (5), že takto můžeme vyjádřit i a3 = a\ — q\a2, «4 = a2 — q2a3, ..., ak-i = ak-3 - qk-idk-2, což je ovšem (ai, a2).                             □
VĚTA 4. Pro libovolná celá čísla a\,a2 existuje jejich nejmenší společný násobek [01,02] a platí (ai,a2) • [ai,a2] = l^i ' d2\.
DŮKAZ. Věta jistě platí, je-li některé z čísel a\,a2 rovno nule. Můžeme navíc předpokládat, že obě nenulová čísla a\, a2 jsou kladná, neboť jejich znaménka se v dokazovaném vzorci neprojeví. Budeme hotovi, ukážeme-li, že q = a\ ■ a2/(a\,a2) je nejmenší společný násobek čísel a\,a2. Protože (a\,a2) je společný dělitel čísel a\,a2, jsou a\/(ai,a2) i a2/(a\,a2) celá čísla, a proto
ülü2                  Cl\                             Cl2
q = 7-------r = 7-------r • a2 =--------- • üi
{ai,a2)      {ai,a2)            {ai,a2)
je společný násobek čísel a\,a2. Podle věty 3 existují k\,k2 E Z tak, že (a\,a2) = k\a\ + k2a2. Předpokládejme, že n E Z je libovolný společný násobek čísel 0,1, a2 a ukážeme, že je dělitelný číslem q. Je tedy n/ai, n/a2 G Z, a proto je i celé číslo
n            n            n(k\a\ + k2a2)      n(a\,a2)      n
a2           d\                    a\a2                 a\a2         q
To ovšem znamená, že q \ n, což jsme chtěli dokázat.                        D
1.3.  Dělitelé a násobky mnoha čísel.
Definice. Největší společný dělitel a nejmenší společný násobek n čísel a\,a2,... ,an E Z definujeme analogicky jako v 1.2. Libovolné m E Z takové, že m \ ci\, m \ a2, ..., m \ an (resp. a\ \ m, a2 \ m, ..., an \ m) se nazývá společný dělitel (resp. společný násobek) čísel ci\, a2,..., an. Společný dělitel (resp. násobek) m > 0 čísel a\, 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 a\, a2,..., an a značí se (cii, a2,..., an) (resp. [ai,a2,. • • ,an]).
Snadno se přesvědčíme, že platí
(ai,..., a„_i, an) = ((ai,..., ara-i), an),                    (6)
[ai,... ,an-i,an] = [[a1}... ,an-i],an].                      (7)
Největší společný dělitel (a\,..., an) totiž dělí všechna čísla ci\,..., an, a tedy je společným dělitelem čísel ci\, ..., a„_i, a proto dělí i největšího společného dělitele (a\,..., an-\), tj. (a\,..., an) \ ((a\,..., an-\), an). Naopak největší společný dělitel čísel (a\,..., an-\), an musí kromě čísla an dělit i všechna čísla a\,..., a„_i, protože dělí jejich největšího společného dělitele, a proto ((ai,..., ara_i), an) \ (cii,..., an). Dohromady dostáváme rovnost (6) a zcela analogicky se dokáže (7).
5
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.
1.4.  Nesoudělnost.
Definice. Čísla a\,ci2,... ,an E Z se nazývají nesoudělná, jestliže platí (a\, ci2, ■ ■ ■, an) = 1. Čísla ci\, ci2, ■ ■ ■, an E Z se nazývají po dvou nesoudělná, jestliže pro každé i, j takové, že 1 < i < j < n, platí (ai,aj) = 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, 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í 291-l = 228(263-l) + 228-l, 263-l = (235 + 27)(228-l) + 27-l, 228-l = (221 + 214 + 27 + l)(27-l). Hledaný největší společný dělitel je tedy 27 — 1 = 127.                      D
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 EN tak, že a = dq\, 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 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 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 = dq\, b = dq2- Pak podle části (1) platí d = (a, b) = (dq\,dq2) = d ■ (q\,q2), a tedy (51,52) = 1- Naopak, je-li a = dq\, b = dq2 a (51,52) = 1, pak (a,b) = (dq\,dq2) = ^(51,52) = d ■ 1 = d (opět užitím 1. části tohoto tvrzení).                                                                                            D
6
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 9 152 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.
„<=" 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 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.
7
Řešení. Podle definice kombinačního čísla
íp\ =        p\        = p • (p - 1).....(p-k + 1)
\k)      k\{p-k)\                    1-2.....fc
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 6 = -| je celé číslo. Protože (^) = ff = iA Je číslo (k) 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.
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 ■ q2.....qs, kde 'pí, ■ ■ ■ ,pm, qi,...,qs
jsou prvočísla a navíc platí p\ < p2 < • • • < pm, Qi < Q2 < • • • < Qs a 1  < m < s. Indukcí vzhledem k m dokážeme, že m = s, p\ =
yl) • • • i Pm        Qm-
Je-li m = 1, je pí = qi.....qs prvočíslo. Kdyby s > 1, mělo by číslo
P\ dělitele q\ takového, že 1 < q\ < p\ (neboť q2q?>... 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
Pi-p2.....pm = q\-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 qi je prvočíslo, plyne odtud pm = qi (neboť pm > 1). Zcela analogicky se dokáže, že qs = p j pro vhodné j E {1,2,..., m}. Odtud
8
iS)
plyne
Qs = P j <Pm = Qi<q.
takže pm = qs. Vydělením dostaneme p\-p2.....pm-\ = Qi • 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 px = qi,...,pm-i = qm-i, pm = q,, Jednoznačnost, a proto i celá věta 7 je dokázána.                                 D
m-
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 (Agra-wal, 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).
DŮSLEDEK.          (1) Jsou-li pí,... ,pk navzájem různá prvočísla a
ni,... ,rik E No, je každý kladný dělitel čísla a = p™1.....p%k
tvaru p™1.....p™k, kde mi,..., nik E No ani\ < ri\, rri2 < ri2,
..., mk < nk.
Číslo a má tedy právě
r(a) = (n1 + l)(n2 + l).....(nk + 1)
kladných dělitelů, jejichž součet je
pT+1-i    p7+1-i
a{a) —
P\ - 1            Pk - 1
(2) Jsou-li pí,... ,Pk navzájem různá prvočísla a ri\, ..., nk, m\, ..., nik G No a označíme-li r\ = mm{ni, nii}, ti = imoí{ni, nii} pro každé i = 1, 2,..., k, platí
(pT.....pI\pT.....Pľk)=p?.....Pk,
[pT.....pI\pT.....Pľk]=p\1.....PÍ-
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".
9
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. Mer-senneho prvočísly. Platí totiž: a je sudé dokonalé číslo, právě když je tvaru a = 2q~l ■ {2q — 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 n\ — 1 (takové existuje podle věty 7, protože n\ — 1 > 1). Kdyby p < n, muselo by p dělit číslo n\ a nedělilo by n\ — 1. Je tedy n < p. Protože p \ (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 Pi,... ,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 = px ■ 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 +00J. 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í
10
komplement 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.
D
Příklad. Dokažte, že existuje nekonečně mnoho prvočísel tvaru 3k + 2, kde k E N0.
Ř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 ■ p?>.....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. 2 by bylo i N tvaru 3k + l, 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
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 Gebyš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.
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 pvp(n) je nejvyšší mocninou prvočísla p, která dělí číslo n, nebo tím, že n = pvp(n'> ■ m, kde m je celé číslo, které není dělitelné číslem p. Odtud snadno plyne, že pro libovolná nenulová celá čísla a, b
11
platí
Vp(ab) = Vp(a) + vp(b)                                    (8)
vp(a) < Vp(b)  A a + b ^ O   =>-   wp(a + b) > vp(a)           (9)
^p(a) < Vp(b)   =>-   Vp(a + b) = vp(a)                    (10)
^p(a) < Vp(b)   =>   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í.
Příklad. Dokažte, že pro libovolná přirozená čísla a, b, c platí ([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 libovolné 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(a), vp((b,c)) = vp(b), odkud vp(L) = Vp(b) = vp(P), což jsme měli dokázat.                                                D