Vlastnosti celých čísel
Pracujeme s množinou
N = {1,2,3,...}
všech přirozených čísel a s množinou
Z = {...,-2,-l,0,l,2,...}
všech celých čísel. Řekneme, že číslo a G Z dělí číslo b G Z, jestliže existuje číslo z G 7L takové, že b = a-z. Pak rovněž říkáme, že číslo a je dělitel čísla 6, a píšeme a \ b. Z této definice pro číslo 0 plyne, že a | 0 pro každé a G 7L a že 0 | b když a jen když b = 0. Základní vlastností je věta o dělení celých čísel se zbytkem:
Věta. Nechť a G Z, 6 G N. Pak existují g, r G Z splňující a = b-q + r,  0 < r < b.
Přitom čísla g, r jsou určena jednoznačně.
Poznámka. Číslo g se potom nazývá podíl a číslo r zbytek po dělení čísla a číslem b.
Důkaz. Dokážeme existenci čísel g, r. Uvažme množinu
M = {x G Z| b-x < a}.
Pak M ^ 0, poněvadž 0 G M pokud a > 0 a, a £ M pokud a < 0. Dále množina M je zřejmě shora omezená, takže obsahuje největší prvek, který označíme q. Dále položíme r = a — b-q. Pak ovšem a = b-q + r a ukážeme, že platí také 0 < r < 6. Nerovnost 0 < r plyne z toho, že b-q < a. Dále z definice čísla q plyne, že b-(q + 1) > a, takže b > a — b-q, čili b > r.
Dokážeme jednoznačnost čísel g, r. Nechť g, g', r, r' G Z jsou čísla splňující a = b-q + r, 0 < r < 6, a = b-q' + r', 0 < r' < b.
1
Předpokládejme napříkld, že r < r'. Pak odečtením uvedených rovností dostáváme 0 = b-(q — q') + r — r', čili r' — r = b-(q — q'), kde ovšem 0 < r' — r < b. Odtud plyne, že nutně q — q' = 0, a tedy také r' — r = 0. Takže q = q' a r = r', čímž je ověřena jednoznačnost g, r.
Číslo c G Z se nazývá společný dělitel čísel a, 6 G Z, jestliže c | a a také c | 6. Číslo cř G Z, které je společným dělitelem čísel a, b a které je přitom největším číslem s touto vlastností, se nazývá největší společný dělitel čísel a, b. Je-li a ^ 0 nebo 6^0, pak tento největší společný dělitel d čísel a, b existuje, přitom d G N, a značí se (a, b). Je-li a = 6 = 0, pak největší společný dělitel čísel a, 6 podle dané definice neexistuje.
Je známa metoda pro nalezení největšího společného dělitele (a, b) dvou čísel a, b G N, nazývaná Euklidův algoritmus. Provádí se postupně následující dělení se zbytkem podle předchozí věty. To znamená, že se hledají čísla qo, qi,..., qn, qn+\ G N U {0} a 7"o, 7"i,..., rn G N taková, že platí:
a = b-q0 + r0, 0 < r0 < 6,
^ = nrgi + n, 0 < n < r0,
?"o = rvq2 + r2, 0 < r2 < n,
n = r2-g3 + ^3, 0 < r3 < r2,
= rn_rqn + rn,  0 < rn < r„_i,
Poslední dělení je tedy vlastně tvaru rn_i = rn-qn+\ + rn_|_i, kde ale rn+i = 0. Poněvadž b > ro > r\ > r2 > ..., musí tato posloupnost dělení opravdu skončit tímto způsobem, což znamená, že buďto již ro = 0 pokud b \ a, anebo skutečně existuje n G N U {0} takové, že rn+i = 0. Jestliže ovšem ro = 0, položme n = — 1 a označme ještě r_i = b. Pak máme následující fakt:
2
Věta. Nechť a,b EN. Pak při označení z předchozího textu platí (a, b) = rn.
Důkaz. Postupujeme-li v předchozím schématu zdola nahoru, postupně krok za krokem odtud plyne rn\rn-i, rn\rn-2,. ■ ■, ^n|^2j ^nl^li '"nl^Oi Tn\ 6, Tn\ Gt, takže Tn je společným dělitelem čísel a, b. Nechť naopak c G Z je společným dělitelem čísel a, b. Postupuj eme-li v předchozím schématu naopak shora dolů, pak z toho, že c | a, c\b, podobným způsobem postupně dostáváme c|r0, c\ri, c\r2, ..., c|rn_2, c|r„_i, c|r„. Takže rn = c-z pro jisté z G Z. Poněvadž rn > 0, plyne odtud rn > c. To znamená, že rn je nej větším společným dělitelem čísel a, b.
Důsledkem této věty je následující Bezoutova rovnost:
Věta. Pro libovolná a, b G Z taková, že a ^ 0 nebo 6^0, existují u,v G Z taková, že (a, 6) = a-w + b-v.
Důkaz. Je-li a = 0 pak 6^0, (a, 6) = |6| a tvrzení je zřejmé. Je-li 6 = 0 pak podobně a ^ 0, (a,b) = \a\ a tvrzení je rovněž zřejmé. Poněvadž dále platí (a, b) = (|a|, stačí tvrzení dokázat už jen pro a, b G N. Je-li zde b | a, pak ovšem (a, b) = b a tvrzení je opět zřejmé. Předpokládejme tedy dále navíc, že b J(a, a přepišme všechny rovnosti v předchozím schématu Euklidova algoritmu vyjma poslední následovně:
r0 = a - b-q0, n = b- r0-gi,
f"2 = n) - n-92,
r3 = n - r2.g35
í"n = ^n-2 - rn-i-qn.
Poněvadž b J(a, máme zde přinejmenším první uvedenou rovnost. Označme ještě r_i = b a r_2 = a. Zpětnou indukcí pro každé
3
i = n—l, n—2,..., 1, O, —1 ukážeme, že existují Uí,Ví G Z taková, že r n = Ti-yUi + ry v,. Pro i = n — 1 to ihned plyne z poslední z výše uvedených rovností. Nechť nyní i G {n — 2,.. .,1, 0,-1}. Pak rovnost pro r,+i v předchozím systému má tvar r,+i = rj_i — ryť/,+i. Podle indukčního předpokladu pro i + 1 máme rn = ryiíj+i + rj+i-i;,-!-! pro jistá ií,+i, Vj+i G Z. Dosazením z předchozí rovnosti odtud dostáváme rn = ryií,+i + (r,_i — ryť7,+i)-i;j+i = r,_i-i;i+i + ry(ií,+i — qfj+i-Vj+i). Tím je proveden indukční krok a důkaz indukcí je hotov. Pro i = — 1 odtud plyne dokazované tvrzení, poněvadž r_2 = a, r_i = 6 a rn = (a, 6).
Důsledek. Nechť a, 6 G Z, a ^ 0 nebo 6^0. Pak číslo d G N je největším společným dělitelem čísel a, b, právě když d\a, d\b a je splněna podmínka, že pro každé číslo e G N s vlastností, že e | a, e | b, platí e | d.
Poznámka. Uvedené požadavky lze chápat jako alternativní definici pojmu největšího společného dělitele čísel a, b, která pro a ^ 0 nebo b ^ 0 splývá s definicí předchozí. Navíc tyto podmínky se nezmění, zaměníme-li v nich množinu N množinou NU{0}. V tom případě ale obdržíme definici, která určuje největšího společného dělitele i pro a = b = 0, a to takovým způsobem, že (0,0) = 0.
Důkaz. Nechť d G N je největší společný dělitel čísel a, b a nechť e G N je nějakým společným dělitelem čísel a, b. Pak podle předchozí věty existují u, v G 7L taková že d = a-u + b-v. Dále e | a, e\b, takže existují x,y G Z taková, že a = e-x, 6 = e-7/. Odtud vyplývá, že d = e-x-w + e-7/-v, což ukazuje, že e | cř.
Nechť naopak d G N je společný dělitel čísel a, b takový, že pro každý společný dělitel e G N těchto čísel platí e | d. Pak rovněž pro každý společný dělitel / G Z těchto čísel platí / | d, čili existuje g G 7L takové, že d = f-g. Odtud ovšem plyne, že / < d, což ukazuje, že d je největším společným dělitelem čísel a,b.
4
Řekneme, že čísla a, 6 G Z jsou nesoudělná, jestliže (a, b) = 1.
Důsledek. Jestliže pro čísla a, 6, c G Z platí a \ b-c a současně (a, b) = 1, pak odtud plyne a | c.
Důkaz. Jestliže (a, b) = 1, pak podle předchozí věty existují u,v G 7L taková, že 1 = a-u + b-v. Odtud vynásobením číslem c dostáváme c = a-c-w + b-c-v. Jestliže tedy a | b-c, plyne odtud, že a | c.
Přirozené číslo p > 2 se nazývá prvočíslo, jestliže přirozenými čísly, která jsou jeho děliteli, jsou pouze čísla lap.
Věta. Pro každé přirozené číslo a > 2 platí, že buďto a je prvočíslo, anebo a je možno rozložit na součin prvočísel, přičemž tento rozklad je jediný až na pořadí činitelů.
Důkaz. Fakt, že každé přirozené číslo a > 2 buď je prvočíslem nebo ho lze rozložit na součin prvočísel, dokážeme indukcí vzhledem k velikosti čísla a. Číslo a = 2 je prvočíslo. Nechť tedy a > 2. Je-li a prvočíslo, není co dokazovat. Není-li a prvočíslo, pak má přirozeného dělitele b takového, že 1 < b < a. Tedy lze psát a = b-c pro jisté přirozené číslo c takové, že 1 < c < a. Podle indukčního předpokladu pak pro každé z čísel b, c platí, že jde buď o prvočíslo nebo o číslo, které lze rozložit na součin prvočísel. Pak ovšem také číslo a = b-c lze rozložit na součin prvočísel.
Dokážeme jednoznačnost tohoto rozkladu. Předpokládejme, že a = pr ... -pn = qr ... -qk, kde p1,... ,pn, q1,..., qk jsou prvočísla. Dokážeme, že v rovnosti p\ -... -pn = q\ -... -qk stojí na obou stranách stejní činitelé, případně v odlišném pořadí. Postupujeme indukcí vzhledem k počtu n činitelů v prvním součinu. Je-li n = 1, je tam jedno prvočíslo, což znamená, že také qv ■ ■ ■ -qk je prvočíslo, takže k = 1 a p\ = q\. Nechť tedy n > 1. Pak z uvedené rovnosti plyne, že P\\q\- ■ ■ ■ -qk- Vícenásobným
5
použitím předchozího důsledku odtud odvodíme, že pi|g« platí alespoň pro jeden index i G {1,..., k}. Skutečně, pokud pi|gi, jsme hotovi. Pokud ovšem k > 1 a pi/fgi, pak (pi,gi) = 1, neboť pi je prvočíslo. Pak ale z předchozího důsledku plyne, že pi|g2" • • • 'Qk- Nyní pokud pi|(/2, jsme opět hotovi. Pokud ale k > 2 a pi/f(/2, pak (pi,g2) = 1 a opět z předchozího důsledku plyne, že pi\qs-... Postupujeme-li takto dále, pak buďto jednou narazíme na i G {1,..., k — 1} takové, že pi|(/j, anebo v posledním kroku zjistíme, že pi\qt- Existuje tedy i G {1,..., k} takové, že pi|g«. Poněvadž qi je prvočíslo, znamená to, že pi = qi-Vydělíme-li nyní shora vedenou rovnost tímto prvočíslem, dostaneme rovnost p<i- ■ ■ ■ -pn — Qv ■ ■ ■ 'Qi-vqi+v ■ ■ ■ mqk- Nyní podle indukčního předpokladu oba tyto součiny obsahují stejné činitele, možná v nestejném pořadí. To potvrzuje dokazovanou jednoznačnost.
Důsledek. Existuje nekonečně mnoho prvočísel.
Důkaz. Připusťme, že existuje pouze konečně mnoho prvočísel pi,P2, • • • ,Pn- Uvažme číslo a = p\-p2-... -pn + 1. Podle předchozí věty číslo a je možno rozložit na součin prvočísel. Odtud zejména plyne, že existuje prvočíslo q takové, že q \ a. Ovšem pro každé i = 1, 2,..., n máme PiJ(a, neboť v opačném případě bychom měli pi \ 1, což není možné. To znamená, že q je prvočíslo takové, ze q ^ pi pro všechna i = 1, 2,..., n, což dává spor.
6