1

III. CELÁ ČÍSLA, DĚLITELNOST

1. Role celých čísel

Přestože přirozená čísla mají v matematice fundamentální význam, je toobor celých čísel, jehož základní roli (jak ve vývoji společnosti, tak pro roz-voj skutečné vědy) nelze docenit. Velmi známý je následující výrok slavnéhoněmeckého matematika Leopolda Kroneckera (1823–1891):

Celá čísla stvořil Bůh, vše ostatní je dílem lidského ducha.

Je však nutno připomenout výhrady Kroneckerova současníka Richarda De-dekinda (1831–1916), jehož pojetí přirozených čísel je v předchozí kapitole vy-jádřeno několika tvrzeními.

Obor celých čísel, který rozšiřuje obor přirozených čísel s jejich sčítáním, ná-sobením a uspořádáním, je základem výstavby všech dalších číselných oborů,celé algebry a moderní analýzy. Proto je velmi důležité porozumět jeho struk-tuře. A to je úkolem této kapitoly.

Pojem celého čísla prošel dlouhým vývojem, který zasahuje i do poměrně ne-dávného období, kdy ještě pojem čísla nezahrnoval ani nulu, ani čísla záporná.Ačkoliv se záporná čísla objevila již ve staré Číně krátce před počátkem našeholetopočtu a byla spolu s nulou nedělitelnou součástí indické matematiky, do Ev-ropy pomalu pronikala až v pozdním středověku zejména pod vlivem islámskématematiky.

Záporná čísla nebyla ještě plně pochopena ani v době Leonharda Eulera(1707–1783); připomeňme například, že i v 18. století se objevoval názor, žezáporná čísla jsou větší než nekonečno. Plné pochopení oboru celých čísel totižzahrnuje jednak hlubší porozumění úplnému uspořádání oboru celých čísel, jed-nak vnímání té skutečnosti, že můžeme odčítat jakákoli dvě celá čísla. Tentofakt budeme stručně vyjadřovat tímto výrokem: celá čísla tvoří aditivní grupu.Pojem grupy bude jedním z centrálních pojmů našeho studia. Následující vý-klad teorie dělitelnosti celých čísel bude cenným modelem pro studium abs-traktních grup.

Zápis celých čísel má rovněž bohatou historii. Počátky našeho současnéhozápisu celých čísel v desítkové soustavě pomocí tak zvaných arabských číslicspadají v Evropě do pozdního středověku. Tento zápis vedl po několik stoletíurputný boj se starším zápisem užívajícím tak zvané římské číslice. Byl to zápasmezi algoristy počítajícími již na cifrách, tj. písemně pomocí algoritmů vyjád-řených v desítkové soustavě, a abacisty, kteří ještě počítali na linách a výsledkypřípadně zapisovali, pokud bylo třeba, římskými číslicemi.

Kladům a záporům číselných systémů se budeme snažit porozumět, stejnětak i zápisům čísel v číselných soustavách o různých základech. Hlouběji seseznámíme s číselnou soustavou o základu 2 pro její význam v současné éře

2

počítačové techniky. Pro zajímavost uvádíme seznam prvních 25 prvočísel za-psaných v různých základech:

základ 10 základ 2 základ 3 základ 4 základ 5 základ 7 základ 12

−−−− −−−− −−−− −−−− −−−− −−−− −−−−2 10 2 2 2 2 23 11 10 3 3 3 35 101 12 11 10 5 57 111 21 13 12 10 711 1011 102 23 21 14 ♯13 1101 111 31 23 16 1117 10001 122 101 32 23 1519 10011 201 103 34 25 1723 10111 212 113 43 32 1♯29 11101 1002 131 104 41 2531 11111 1011 133 111 43 2737 100101 1101 221 131 52 3141 101001 1112 221 131 56 3543 101011 1121 223 133 61 3747 10111 1202 233 142 65 3♯53 110101 1222 311 203 104 4559 111011 2012 323 214 113 4♯61 111101 2021 331 221 115 5167 1000011 2111 1003 232 124 5771 1000111 2122 1013 241 131 5♯73 1001001 2201 1021 243 133 6179 1001111 2221 1033 304 142 6783 1010011 10002 1103 313 146 6♯89 1011001 10022 1121 324 155 7597 1100001 10121 1201 342 166 81

Poznamenejme, že pro vyjádření čísel v číselné soustavě o základu 12 po-třebujeme ještě symboly pro dvě nové číslice (vyjadřují deset, resp. jedenáctjednotek), ve výše uvedené tabulce jsme však využili jen jednu, kterou jsmeoznačili symbolem ♯.

Porozumění celým číslům, jak jsme již naznačili, tkví především v hlubšímporozumění jejich dělitelnosti. Zdůrazníme, že základem je tak zvané eukleidov-ské dělení a s ním úzce související eukleidovský algoritmus. K porozumění rolieukleidovského dělení, tj. jednoznačného dělení se zbytkem, nám může pomocinásledující hádanka, kterou před lety zaslal James Joseph Sylvester (1814–1897) do časopisu Educational Times:

Vlastním velké množství známek, ale pouze v hodnotách 5 pencí a 17 pencí.Jaké je největší poštovné, které nemohu frankovat kombinací známek těchtodvou hodnot?

3

Předně si uvědomme, že Sylvester prozradil, že takové největší poštovnéexistuje, ač to není a priori vůbec jasné. Zřejmé se to však stane, a hádankuihned zodpovíme s využitím obrázku 1. Vrátíme se k němu později v sekci II.B.Nyní jen poznamenejme, že z tabulky ihned vidíme, že poštovné

103 p lze dosáhnout jednoznačně (9 · 5 p+ 4 · 17 p),203 p dvěma způsoby (10 · 5 p+ 9 · 17 p = 27 · 5 p+ 4 · 17 p),303 p třemi (13 · 5 p+ 14 · 17 p = 30 · 5 p+ 9 · 17 p = 47 · 5 p+ 4 · 17 p)

atd. Na druhé straně těch 32 hodnot uvedených vně rámování dosáhnout nelze;největší takové poštovné je 63 p.

Obrázek

Poněkud náročněji, ale přesvědčivěji, vysvětlí podobný obrázek následujícíhistorku:

Karel Zpěvák prodával své poslední CD ve dvou vydáních. Základní vy-dání za 299,− Kč a luxusní vydání s příslušnou literaturou za 472,− Kč. Jehoagent mu po měsíčním prodeji přinesl utržených 140.407,− Kč s omluvou, ženemůže nalézt záznam, kolik kterého vydání prodal. Nu, při téhle sumě to ne-vadí. Je pouze jediná možnost kolik kterých vydání jste prodal. A skutečně semůžete přesvědčit, že agent musel prodat 277 základních a 122 luxusních vy-dání. A Karel Zpěvák ještě dodal: To byste nevěřil, co vše se dá při takovémprodeji zjistit. Vím například, že jste nemohl utržit 100.000,− Kč, a rovněžvím, že jste mohl utržit jakoukoliv sumu větší než 140.357,− Kč. Kdybystenapříklad utržil 200.000,− Kč, musel byste prodat 440 základních a 145 lu-xusních CD. Tak jednoznačnou odpověd Vám však už nemohu dát v případě,kdybyste utržil 300.000,− Kč. Je vše, co Karel Zpěvák říkal, pravda?

4

Podaří se nám vnést do následující tabulky nějaký pořádek a porozumět jí?

Počet PočetTRŽBA základních luxusních

vydání vydání

140.400,−Kč 408 39140.401,−Kč 187 179140.402,−Kč 438 20140.403,−Kč 217 160140.404,−Kč 468 1140.405,−Kč 247 141140.406,−Kč 26 281140.407,−Kč 277 122140.408,−Kč 56 262140.409,−Kč 307 103140.410,−Kč 86 243

141.000,−Kč 440 20150.000,−Kč 448 34200.000,−Kč 440 145

300.000,−Kč 896 68424 367

500.000,−Kč 1336 213864 512392 811

1.000.000,−Kč 3144 1272672 4262200 7251728 10241256 1323784 1622312 1921

Při tom není možné utržit prodejem těchto dvou vydání CD ani 100.000.− Kč,ani 50.000.− Kč.

Tato jednoduchá úloha nás přivede k teorii (celočíselných) diofantickýchúloh, k teorii kongruencí, k porozumění prvočíslům, eukleidovskému dělení,ke klasifikaci cyklických grup, ke konstrukcím konečných těles a stručnému na-hlédnutí do kryptografie.

5

2. Dělitelnost

Na množině celých čísel

Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . . }

máme dány dvě algebraické operace, sčítání a násobení, které rozšiřují odpoví-dající operace na množině přirozených čísel N. Obě tyto operace jsou komuta-tivní a asociativní. Ve srovnání s množinou N je množina Z vzhledem ke sčítáníabelovskou grupou, kterou značíme Z(+). To znamená, že kromě asociativitya komutativity sčítání existuje v množině Z nulový prvek 0 splňující rovnost0 + a = a pro každé a ∈ Z a že pro každé a ∈ Z existuje opačný prvek −a ∈ Z,tj. takový prvek, pro který je a+ (−a) = 0.

Můžeme tedy definovat operaci odčítání: rozdílem a− b prvků a, b (v tomtopořadí) rozumíme prvek a+ (−b).

Pro žádné celé číslo s výjimkou ±1 neexistuje v Z inverzní prvek, tj. Z(·)není multiplikativní grupou. Je však multiplikativní pologrupou s jednotkovýmprvkem (neboli monoidem), neboť číslo 1 splňuje pro každé a ∈ Z identitu1 · a = a.

Operace sčítání a násobení jsou (stejně jako v množině N) svázány distribu-tivním zákonem: pro každé a, b, c ∈ Z je

a(b+ c) = ab+ ac.

Všechny výše uvedené vlastnosti celých čísel lze stručně vyjádřit takto:Z(+, ·) je komutativní okruh. To znamená, že vzhledem ke sčítání je Z ko-mutativní grupa, násobení je asociativní a komutativní a operace + a · jsousvázány distributivním zákonem.

Operace násobení v okruhu Z(+, ·) má ještě navíc tzv. vlastnost krácení:jestliže a 6= 0 a ab = ac, potom b = c.

Jiným způsobem lze tuto podmínku vyjádřit takto:

jestliže ab = 0, potom je buď a = 0 nebo b = 0.

Komutativní okruhy s jednotkovým prvkem, které mají tuto vlastnost, se nazý-vají obory integrity. Množina Z(+, ·) všech celých čísel se sčítáním a násobenímje tedy oborem integrity.

Na množině Z máme rovněž přirozené rozšíření lineárního uspořádání mno-žiny N:

· · · < −m < · · · < −2 < −1 < 0 < 1 < 2 < · · · < n < . . .

6

pro m,n ∈ N. Celá čísla a, pro něž 0 < a, se nazývají kladná (jsou to právěvšechna přirozená čísla) a čísla a, pro něž a < 0, se nazývají záporná.

Připomeňte, že a < b platí právě tehdy, když je 0 < b − a. Z toho vyplývá,že pro a < b je a + c < b + c pro libovolné číslo c ∈ Z, zatímco pro a < b jeac < bc pro libovolné číslo c > 0 a ac > bc pro libovolné číslo c < 0.

Celá čísla tedy můžeme znázornit na číselné ose:

.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................• • • • • •• ◦−2 −1 1 20 ······ 3

Lineární uspořádání ztratilo vlastnost dobrého uspořádání přirozených čísel.Skutečně, například množina všech sudých čísel nemá nejmenší prvek.

Definice. Řekneme, že celé číslo a je násobkem celého čísla b, jestliže exis-tuje celé číslo c tak, že a = bc.

Definice. Řekneme, že celé číslo b dělí celé číslo a, resp. že je dělitelemčísla a, jestliže existuje celé číslo c tak, že a = bc. Tuto vlastnost budeme značitsymbolem b | a.Věta. Vlastnosti relace dělitelnosti v oboru celých čísel Z.

(i) b | a právě tehdy, když −b | a, a to je právě tehdy, když b | −a.(ii) Je-li b | a a a 6= 0, potom |b| ≤ |a|.(iii) Je-li a | b a b | a, pak a = b nebo a = −b.(iv) Je-li a | b a b | c, pak a | c.(v) Je-li a | b a a | c, pak a | bu + cv pro libovolná celá čísla u, v.Speciálně a | b+ c a a | b − c.

(vi) Je-li a | b, pak ac | bc pro libovolné celé číslo c.

Tvrzení (iv) a (v) lze formulovat obecněji ve tvaru

(iv’) Je-li at | at+1 pro 1 ≤ t ≤ k − 1, pak a1 | ak.(v’) Je-li a | bt pro 1 ≤ t ≤ k, pak a |

∑kt=1 ctbt pro libovolná celá čísla ct.

Tvrzení (i) nám umožňuje omezit se při studiu dělitelnosti celých čísel na kladná(tj. přirozená) čísla (a na jejich dělitele a násobky). To budeme v budoucnu,pokud neřekneme jinak, vždy předpokládat.

Zaveďme ještě jedno užitečné označení pro množinu všech dělitelů danýchčísel a a b:

D(a) = {d ∈ N | d | a} a D(a, b) = {d ∈ N | d | a, d | b}. (1)

Cvičení. Dokažte tvrzení (i) až (vi). Omezte se na a, b, c ∈ N a přepištetvrzení (iii) až (vi) s využitím značení (1).

7

Poznamenejme, že množina D(a) vždy obsahuje přirozená čísla 1, a, množinaD(a, b) vždy obsahuje číslo 1.

Definice. Číslo p nazveme prvočíslem, jestliže je D(p) = {1, p}. Řekneme,že čísla a, b jsou nesoudělná, jestliže je D(a, b) = {1}.Definice. Řekneme, že přirozené číslo n je společným násobkem celých čísel

a1, a2, . . . , ak, jestliže at | n pro všechna 1 ≤ t ≤ k. Množinu všech společnýchnásobků čísel a1, a2, . . . , ak označme symbolem N(a1, a2, . . . , ak).

Definice. Řekneme, že přirozené číslo d je společným dělitelem celých čísela1, a2, . . . , ak, jestliže d | at pro všechna 1 ≤ t ≤ k. Označme množinu všechspolečných dělitelů čísel a1, a2, . . . , ak symbolem D(a1, a2, . . . , ak).

Dobré uspořádání přirozených čísel zaručuje v množině N(a1, a2, . . . , ak)existenci nejmenšího čísla n = n(a1, a2, . . . , ak), které nazýváme nejmenšímspolečným násobkem čísel a1, a2, . . . , ak.

Jelikož je množina D(a1, a2, . . . , ak) omezená, existuje v ní největší pr-vek d = d(a1, a2, . . . , ak); číslo d nazveme největším společným dělitelem čísela1, a2, . . . , ak.

Snadno se přesvědčíme, že

n(303, 1 500, 1 515) = 151 500 a d(303, 1 500, 1 515) = 3.

Zdůrazněme, že

n(−15, 25) = n(15, 25) = 75 a d(−15, 25) = d(15, 25) = 5.

Poznamenejme ještě, že je-li at = 0 pro některé 1 ≤ t ≤ k, potom je

N(a1, a2, . . . , ak) = {0}

aD(a1, a2, . . . , ak) = D(a1, a2, . . . , at−1, at+1, . . . , ak).

Je tedy např. D(a, 0) = D(a).

Popsat množinu všech společných dělitelů daných čísel je v jednoduchýchsituacích velmi snadné. Například pro Dk = D(16k + 3, 20k + 2), kde k ∈ N, jebuď Dk = {1} nebo Dk = {1, 7}. Druhý případ nastane právě tehdy, když jek = 7t+ 2 pro t = 0, 1, 2, . . . Je-li totiž d | b = 16k + 3 a d | c = 20k + 2 pronějaké k, pak podle tvrzení (v) je d | 5b − 4c = 7, a vše je jasné.Bude nás zajímat struktura množin N(a) (která je stejná, tj. izomorfní,

s množinou N(1) = N), D(a), N(a, b) a D(a, b) pro daná přirozená čísla a a b,a především charakterizace čísel n(a, b) a d(a, b), jejich vztah a otázka, jak tytodvě hodnoty v obecném případě nalézt. To vše nám v příští sekci odhalí takzvané eukleidovské dělení (tj. celočíselné dělení se zbytkem).

Zatím si připomeňme, že jsme v minulé kapitole definovali na množině všechpřirozených čísel nové (částečné) uspořádání ≺ takto:

8

a ≺ b právě tehdy, když a | b.

V tomto uspořádání je 1 nejmenším prvkem. Každému přirozenému číslu a ∈ Nmůžeme přiřadit speciální hvězdicovitý distributivní svaz množiny D(a) (někdyse mu říká Hasseho diagram).

Pro a = 360 (či 6174) máme:

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•............................................................................................................................................................................................................................................................................................................................................................................ ........

............................................................................................................................................................................................................................................................................................................................................................................ ........

............................................................................................................................................................................................................................................................................................................................................................................ ........

............................................................................................................................................................................................................................................................................................................................................................................ ........

............................................................................................................................................................................................................................................................................................................................................................................ ........

............................................................................................................................................................................................................................................................................................................................................................................ ........

............................................................................................................................................................................................................................................................................................................................................................................ ........

............................................................................................................................................................................................................................................................................................................................................................................ ........

............................................................................................................................................................................................................................................................................................................................................................................ .............

....................................................................................................................................................................................................................................................................................................................................................................... ..................

.................................................................................................................................................................................................................................................................................................................................................................. ....................

................................................................................................................................................................................................................................................................................................................................................................ ........

...................................................

...................................................

...................................................

...................................................

...................................................

...................................................

........................................................................................................................

........................................................................................................................

........................................................................................................................

........................................................................................................................

........................................................................................................................

........................................................................................................................

........................................................................................................................

........................................................................................................................

36(441)

12(147)

4(44)

18(63)

6(21)

2(7)

9(9)

3(3)

1(1)

180(882)

60(294) 90(126)

20(98) 30(42) 45(18)

10(14) 15(6)

5(2))

360(6174)

120(2058)

40(686)

8(343)

24(1029)

72(3087)

Poznamenejme, že úplné uspořádání ≤ na množině Z je rozšířením částeč-ného uspořádání ≺ na množině N, tj. a ≺ b implikuje a ≤ b. Každé nenulovécelé číslo má tedy jen konečný počet dělitelů.

3. Eukleidovské (celočíselné) dělení se zbytkem

Nejprve zformulujme samotnou podstatu eukleidovského dělení.

Věta („Vymezeníÿ čísla a pomocí násobků čísla b). Nechť b je přirozenéčíslo. Potom pro každé celé číslo a existuje právě jedno celé číslo q tak, že

bq ≤ a < b(q + 1).

Důkaz. Nechť a je přirozené číslo. Tvrzení je triviální pro 0 ≤ a < b (položímeq = 0) a rovněž pro a = b (položíme q = 1).

Nechť tedy a > b. Označme nyní A podmnožinu množiny N definovanounásledujícím způsobem:

A = {t ∈ N | b(t+ 1) > a}.

9

Množina A je zřejmě neprázdná, neboť b(a + 1) = ba + b ≥ a + b > a, a tedya ∈ A. Z principu dobrého uspořádání vyplývá, že existuje nejmenší číslo q ∈ A,a tedy bq ≤ a < b(q + 1).Jestliže a < 0, pak −a ∈ N, a proto existuje číslo q1 takové, že bq1 ≤ −a <

b(q1 + 1). Odtud 0 < b(q1 + 1) + a. Proto existuje právě jedno celé číslo q2takové, že bq2 ≤ b(q1+1)+ a < b(q2+1). Položíme-li nyní q = q2− q1− 1, pakje bq ≤ a < b(q + 1), čímž je věta dokázána.

Jiný důkaz. Množina celých čísel se rozpadne na tyto disjunktní podmnožiny:

. . . ,{−b, . . . ,−1

},

{0, . . . , b−1

},

{b, . . . , 2b−1

}, . . . ,

{qb, . . . , (q+1)b−1

}, . . .

Číslo a musí ležet v některé z uvedených podmnožin.

Důsledek (Eukleidovské neboli celočíselné dělení se zbytkem). Nechť b jepřirozené číslo. Potom pro každé celé číslo a existuje právě jedna dvojice (q, r)celých čísel (tzv. celočíselný podíl q a zbytek r), pro kterou je

a = bq + r a 0 ≤ r < b. (2)

Přitom je zjevně D(a, b) = D(b, r). Speciálně, je-li r = 0, je D(a, b) =D(b, 0) = D(b).

Připomeňme rozdíl mezi dělením kladných a záporných čísel. Například proa = ±78 a b = 32 máme

78 = 32 · 2 + 14 a − 78 = 32 · (−3) + 18.

Poznamenejme už nyní, že se pro dané číslo b obor všech celých čísel Z (kterémuříkáme obor integrity) rozpadl na b disjunktních podmnožin. V každé z nichjsou všechna čísla se stejným zbytkem r. Významný je případ, kdy r = 0, tj.kdy b ∈ D(a). Pro b = 2 to vyjadřuje velmi dobře známý poznatek, že celá číslase dělí na sudá (r = 0) a lichá (r = 1). Rozkladu Z na b podmnožin (tzv. třídmodulo b) charakterizovaných zbytky r = 0, 1, . . . , r − 1, využijeme předevšímv příští sekci C týkající se zápisu čísel a v sekci II.A, věnované kongruencím.

Uveďme několik jednoduchých užití eukleidovského dělení.

Cvičení.

1. Ukažme, že číslo n = k(k + 1)(2k + 1) je dělitelné šesti pro každé k.

Především je jeden z prvních dvou činitelů vždy sudý, tj. dělitelný dvěma.Jde tedy třeba ukázat, že číslo n je dělitelné třemi. Eukleidovské dělení třeminám zaručuje, že číslo k má tvar k = 3t, nebo k = 3t+1, nebo k = 3t+2. Prok = 3t je n = 3t·(3t+1)·(6t+1), pro k = 3t+1 je n = (3t+1)·(3t+2)·3(2t+1)a pro k = 3t+ 2 je n = (3t+ 2) · 3(t+ 1) · (6t+ 5).

10

2. Nechť a, b jsou celá čísla taková, že 3 | a2 + b2. Potom 3 | a a 3 | b. Nechťa = 3q1 + r1 a b = 3q2 + r2, kde r1 a r2 jsou čísla 0, 1 či 2. Potom je a2 + b2 =3(3q21 + 2q1r1 + 3q

22 + 2q2r2) + r

21 + r

22. Proto 3 | r21 + r22. Jelikož r21 + r22 ∈

{0, 1, 2, 4, 5, 8}, je nutně r21 = r22 = 0, tj. 3 dělí a i b.

3. Stejným způsobem ukažte, že z 3 | a4 + b4 plyne 3 | a a 3 | b.

Následující úlohu rozřešíme dvojím způsobem.

4. Dokažte, že pro všechna n je číslo P (n) = 5n3 + n dělitelné šesti.

Pišme P (n) = n(5n2 + 1). První řešení je založeno na tom, že každé číslo jetvaru 6q+ r, kde r ∈ {0, 1, 2, 3, 4, 5}. Pro n = 6q je n dělitelné šesti, pro 6q+2,resp. 6q+4 je číslo n sudé a číslo 5n2+1 dělitelné třemi. Pro n = 6q+1, resp.6q+5 je 5n2+1 dělitelné šesti a pro n = 6q+3 je číslo n dělitelné třemi a číslo5n2 + 1 je číslo sudé.

Důkaz faktu, že je číslo P (n) dělitelné šesti, poskytne snadno matematickáindukce. Jednak je P (1) = 6, jednak je P (n+1) = P (n)+15n(n+1)+6. ČísloP (n) je tedy dělitelné šesti pro každé n.

4. Zápis celých čísel

To, že v našem běžném životě zapisujeme čísla v desítkové soustavě, je výtvorlidský. Nebylo tomu tak vždy. Zápis čísel prošel bohatou historií, v ní dominujeasyrsko-babylonský zápis v soustavě o základu 60 užívaný až do středověkui v Evropě. Připomeňme též zápis užitím římských číslic. Dekadická (desítková)soustava, která dnes dominuje, je v současném věku digitalizace doprovázenabinární soustavou.

Jádrem zápisu celého čísla a v soustvě o základu b je opakované užití euk-leidovského dělení.

Věta (číselná soustava o základu b). Nechť b ≥ 2 je přirozené číslo. Potompro každé přirozené číslo a existují přirozené číslo n a celá nezáporná číslaα0 < b, . . . , αn < b, taková, že αn 6= 0 a

a = αnbn + αn−1b

n−1 + · · ·+ α2b2 + α1b+ α0. (∗)

Takovéto vyjádření čísla a je jednoznačné.

Důkaz. Myšlenka je následující. Abychom získali vyjádření čísla a v číselnésoustavě o základu b, budeme uvažovat následující posloupnost celočíselnýchdělení:

a = bq1 + α0, 0 ≤ α0 < b,

q1 = bq2 + α1, 0 ≤ α1 < b,

q2 = bq3 + α2, 0 ≤ α2 < b,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

qn−1 = bqn + αn−1, 0 ≤ αn−1 < b,

kde a > q1 > q2 > · · · > qn−1 > b > qn = αn. Je-li a < b, pak q1 = 0a α0 = a.

Pro větší názornost je možno postupně dosazovat:

a = bq1 + α0 = b2q2 + bα1 + α0 = b3q3 + b2α2 + bα1 + α0 = . . .

Z jednoznačnosti eukleidovského dělení plyne jednoznačnost zápisu (∗). Větaje dokázána.

Vyjádření (∗) čísla a budeme zapisovat následujícím způsobem:

a = (a)b = (qnαn−1αn−2 . . . α2α1)b.

Příklad. Číslo 2282 = (2282)10 (zapsané v našem dekadickém systému) mánásledující vyjádření:

(100011101010)2 v binárním systému (číselná soustava o základu 2),

(10010112)3 v terciárním (3-adickém) systému,

(4352)8 v 8-adickém systému,

(13α2)12 v 12-adickém systému (číslice této číselné soustavy značíme 1, 2, . . . ,8, 9, α, β).

Explicitně: 2282 = 12 ·190+2, 190 = 12 ·15+10, 15 = 12 ·1+3, 1 = 12 ·0+1,a tedy (2282)10 = (13α2)12.

Vraťme se nyní na skok k úvodu této kapitoly a přesvědčeme se o správnostivyjádření prvočísel v soustavách o různých základech.

Příklad („Antickéÿ schéma násobení). Nechť a, b jsou přirozená čísla. V bi-nárním systému je

a = αn2n + αn−12

n−1 + · · ·+ α222 + α12 + α0.

Uvědomte si, že αt = 0 nebo αt = 1 pro každé 0 ≤ t ≤ n, tedy αn = 1. Protomůže být vypočítán součin a · b „zdvojovánímÿ a „půlenímÿ. Neboť

a · b = αn(2nb) + αn−1(2n−1b) + · · ·+ α2(22b) + α1(2b) + α0b =∑

t=1,...,nαt=1

2tb.

Proces zdvojování a půlení (eukleidovské dělení dvěma) můžeme schematickyzapsat takto.

12

b a = 2q1 + α0 α0 = 1 ⇐⇒ a = q0 je liché2b q1 = 2q2 + α1 α1 = 1 ⇐⇒ q1 je liché22b q2 = 2q3 + α2 α2 = 1 ⇐⇒ q2 je liché23b q3 = 2q4 + α3 α3 = 1 ⇐⇒ q3 je liché

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2tb qt = 2qt+1 + αt αt = 1 ⇐⇒ qt je liché

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2n−1b qn−1 = 2qn + αn−1 αn−1 = 1 ⇐⇒ qn−1 je liché2nb qn = αn = 1 αn = 1

Proto jea · b =

∑

t=0,...,nqt je liché

2tb.

Takovéto násobení bylo výhodné v římském zápisu čísel, neboť nebylo nutnéznát žádnou násobilku. Domníváme se, že to bylo jedním z důvodů, proč byl bojmezi abacisty a algoristy tak zdlouhavý. Připomeňme, že na Karlově univerzitěse na jejím počátku v rámci studia hudby kromě sčítání a odčítání učilo právězdvojování a půlení.

Ilustrace. Vezměme a = 163, b = 289. Potom

289 163 α0 = 1 •578 (= 2 · 289) 81 (= 12 · 163) α1 = 1 •1 156 (= 2 · 578) 40 (= 12 · 81)2 312 (= 2 · 1156) 20 (= 12 · 40)4 624 (= 2 · 2 312) 10 (= 12 · 20)9 248 (= 2 · 4 624) 5 (= 12 · 10) α5 = 1 •18 496 (= 2 · 9 248) 2 (= 12 · 5)36 992 (= 2 · 18 496) 1 (= 12 · 2) α7 = 1 •

Proto je a · b rovno 289 + 578 + 9 248 + 36 992 = 47 107.

Ilustrace (násobení římských čísel).

Vezměme a = XXXVIII = 38, b = XVII = 17.

XVII XXXVIIIXXXIIII XVIIII •LXVIII VIIII •CXXXVI IIIICCLXXII IIDXXXXIIII I •

13

Tedy

38 · 17 = XXXVIII ·XVII == XXXIIII + LXVIII + DXXXXIIII = DCXXXXVI = 646.

Úloha. Zkonstruujte podobné schéma násobení tak, že užijete vyjádřeníčísla a v soustavě o základu 3. Připomeňme, že v tomto případě je při euklei-dovském dělení zbytek buď 0, 1 nebo 2.

5. Eukleidův algoritmus

Následující věta je pilířem elementární aritmetiky.

Věta (Eukleidův algoritmus). Nechť a > b jsou přirozená čísla. Potom ná-sledující posloupnost celočíselných dělení

a = bq0 + r0, 0 ≤ r0 < b ,

b = r0q1 + r1, 0 ≤ r1 < r0 (jestliže r0 6= 0),

r0 = r1q2 + r2, 0 ≤ r2 < r1 (jestliže r1 6= 0),. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

rt−1 = rtqt+1 + rt+1, 0 ≤ rt+1 < rt (jestliže rt 6= 0),. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

je konečná: končí v okamžiku, kdy je některý zbytek roven nule, tj. takto:

rk−2 = rk−1qk + rk, 0 < rk < rk−1,

rk−1 = rkqk+1.

Poslední nenulový zbytek rk je největším společným dělitelem čísel a, b. Jestližeje již r0 = 0, potom je d(a, b) = b.

Důkaz. Algoritmus dělení musí po konečném počtu kroků skončit, neboťposloupnost přirozených čísel b > r0 > r1 > · · · > rt > · · · ≥ 0 je klesající azdola omezená.

Vzhledem k uvedeným vztahům v posloupnosti celočíselných dělení se zbyt-kem je

D(a, b) = D(b, r0) = D(r0, r1) = · · · =

= D(rk−2, rk−1) = D(rk−1, rk) = D(rk, 0) = D(rk).

Je tedy jednak rk dělitelem čísel a, b, jednak je každý dělitel čísel a, b dělitelemčísel rk. Proto je rk = d(a, b).

14

Ve výše uvedené definici byl největší společný dělitel d(a, b) dvou čísel D(a, b)největším prvkem množiny všech společných dělitelů čísel a a b. Eukleidovskýalgoritmus však popisuje strukturu množiny D(a, b) přesněji a podává v násle-dujícím tvrzení ekvivalentní definici největšího společného dělitele d(a, b).

Důsledek. Nechť a, b jsou přirozená čísla. Potom

D(a, b) = D(d(a, b)),

tj. každý společný dělitel čísel a a b je dělitelem jejich největšího společnéhodělitele d(a, b). Největší společný dělitel d = d(a, b) je tedy číslo definovanénásledujícími dvěma vlastnostmi:

1. d | a, d | b;2. d′ | a, d′ | b implikuje d′ | d.Píšeme-li tedy a = da′ a b = db′, je d(a′, b′) = 1, tj. čísla a′ a b′ jsou

nesoudělná. Odtud se snadno odvodí následující duální tvrzení (dokažte je!):

Nejmenší společný násobek n = n(a, b) čísel a a b má tvar abd(a,b) a je cha-

rakterizován následujícími dvěma (duálními) vlastnostmi:

1. a | n, b | n;2. a | n′, b | n′ implikuje n | n′.Toto vše vysvětluje tvar předchozího distributivního svazu všech dělitelů čí-

sel 360 (či 6174). Částečné uspořádání ≤ množiny N přirozených čísel předsta-vuje nekonečný distributivní svaz s nejmenším prvkem (svazově nulovým) 1.Zopakujme, že svazem zde rozumíme množinu se dvěma operacemi spojení∨ a průsek ∧ (v našem případě představené nejmenším společným násobkema největším společným dělitelem), které jsou komutativní, asociativní a splňujípodmínku absorpce, tj. rovnost

a ∧ (a ∨ b) = a ∨ (a ∧ b) = a.

Svaz dělitelů D(a) čísla a je navíc distributivní, tj. splňuje rovnost

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c).

Skutečnost, že v D(a) platí rovnost

d(a, n(b, c)

)= n

(d(a, b), d(a, c)

)

a řada dalších obdobných rovností, dokážeme v příští kapitole. Jako ilustraciuvádíme ještě svaz D(2160) a malý segment svazu přirozených čísel, který jeurčený částečným uspořádáním definovaným dělitelností.

15

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

....................................................................................................................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

........................................................................................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

..............................

2160

432 720 1080

144 240 216 360 540

48 80 72 120 108 180 270

16 24 40 36 60 54 90 135

8 12 20 18 30 27 45

4 6 10 9 15

2 3 5

1

Obr. 2

16

2 3 5 7 11 13 17 192329 31 37 41 43 47 53 59 61 67 71 73 ···

4 6 9 10 14 15 21 22 25 26 33 34 35 383946 49 51 55 57 58 62 65 69 ···

8 12 18 20 27 28 30 4244

45 50 52 63 66 68 70 ···

16 24 36 40 54 56 60 ···

32 48 72 ···

64···

1

........................................................................................................................................................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................................................................................................

...................................................................................................................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................

...........................................................................................................................................................................................................................................................................

.......................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................

........................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

........................................................................................................................................................................................................................

......................................................................................................................................................................................................................................

.......................................................................................................................................................................................................................................................

...........................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................

...................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

........................................................................................................................................................................................................................

...........................................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................................................................................................

....................................................................................................................................................................................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

........................................................................................................................................................................................................................

......................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................

....................................................................................................................................................................................................................................................................................................................................................................................................................................

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.......................................................................................................................................................................................................................................................

...................................................................................................................................................................................................................................................................................................................................................

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.........................................................................................................................................................................................................................................................................................................................

....................................................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.......................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................

........................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

.......................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

...................................................................................................................................................................................................................

......................................................................................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

....

..............................................................................................................................................................................................................................................

....................................................................................................................................................................................................................................................................................................................................................................................................................................

.......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

..

......................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

......................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..............................................................................................................................................................................................................................................

...................................................................................................................................................................................................................................................................................................................................................

.......................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................

.................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................................................................................................

..........................................................................................................................................................................................................................................................................................................................................................................................

...........................................................................................................................................................................................................................................................................................................................................................................................................

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

.....

...

..............................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................

...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

........................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................

.............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.................................................................................................................................................................................................................................................................

..............................................................................................................................................................................................................................................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................................................................................

..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

..........................................................................................................................................................................................................................................................................................................................................................................................

..................................