1.1 Definice a základní pojmy

Kapitola 1.

Teorie dělitelnosti

C. F. Gauss: „Matematika je královnou všech věd a teorie čísel je královna matematiky.“ Základním číselným oborem, se kterým budeme v této kapitole pracovat, jsou celá čísla a pouze v některých jasně definovaných případech se omezíme na jejich podobory, nejčastěji N, resp. N+. Víme již, že celá čísla tvoří algebraickou strukturu (označovanou jako eukleidovský obor integrity), která je uzavřená vzhledem k operaci sčítání, odčítání a násobení, tj. součet, rozdíl i součin libovolných dvou celých čísel je opět celé číslo. Vzhledem k operaci dělení však celá čísla tuto vlastnost obecně nemají. Obsahem této kapitoly budou právě vlastnosti celých čísel vzhledem k operaci dělení a hlavní výsledky, které se dotýkají problematiky dělitelnosti, prvočísel a kongruencí, mají zásadní význam, např. v oblasti výpočetní techniky, moderní teorie kódování, stochastického modelování apod.

1.1

Definice a základní pojmy

Definice 1.1.1 - dělitelnost Řekneme, že nenulové celé číslo b dělí a, píšeme b| a , jestliže existuje celé číslo q takové, že a  bq .

(1.1)

V opačném případě píšeme b | a a říkáme, že b nedělí a. Pokud b dělí a, říkáme také, že a je dělitelné b. V tomto případě číslo q nazýváme podílem, číslo a násobkem čísla b a číslo b dělitelem čísla a. Dělitele b nazveme vlastním dělitelem čísla a, jestliže

b  a  b  1 . Dělitele, který není vlastní nazýváme nevlastním dělitelem. Věta 1.1.1 Relace dělitelnosti | má následující vlastnosti: a) a  Z platí 1| a , b) a  Z  0 platí a | 0 , c) a  Z  0 platí a | a , d) a, b  Z platí a | b  b | a    a  b  a  b  , e) a, b, c  Z platí a | b  b | c    a | c ,  a | b  c , f) a, b, c  Z platí a | b 

g) a, b, c, d  Z platí

a  b  c  d | a  d | c    d | b .

Poznámka 1.1.1  Připomeňme, že vlastnost a) se nazývá reflexivita a c) tranzitivita relace dělitelnosti. Pokud bychom ve větě 1.1.1 nahradili číselný obor Z oborem přirozených čísel N, dostali bychom místo b) následující vlastnost: b*) a, b  N platí a | b  b | a    a  b , 5



která se nazývá antisymetrie. Je tedy zřejmé, že v oboru přirozených čísel je relace dělitelnosti (částečným) uspořádáním, které však není lineární (libovolná dvojice přirozených čísel a, b nemusí být v relaci, tj. nemusí platit a | b ani b | a). Vlastnost g) předcházející věty lze zobecnit následujícím způsobem: n

*

g ) Je-li známo, že číslo d dělí všechny členy rovnosti

a  b i 1



m

i

j 1

j

kromě jediného,

nutně dělí i zbývající člen. Jako zřejmý důsledek vlastnosti g*) dostáváme: Jestliže a | bi , i  1, , n , potom pro libovolná xi  Z , i  1,, n platí a | b1  x1    bn  xn  .

Příklad 1.1.1 Nalezněte všechna celočíselná řešení rovnice 21 x1  84 x2  35 x3  113 . Řešení. Předpokládejme, že existují celá čísla x1 , x 2 , x3 , která jsou řešením uvedené rovnice. Vzhledem k tomu, že 7|21, 7|84 a 7|(-35), nutně musí platit (dle výše uvedené poznámky) 7|113. Spor, tedy rovnice nemá v oboru celých čísel řešení. Příklad 1.1.2 Nechť x0 , y 0 jsou libovolná celá čísla taková, že 11| 5 x0  7 y 0  . Potom 11| 8 x0  20 y 0  . Řešení. Snadno nahlédneme, že existuje alespoň jedna dvojice x0 , y 0 s vlastností 11| 5 x0  7 y 0  , např. x0  20, y 0  3 .

Dále

zřejmě

platí

11|  2  11 x0  11 y 0 

a

vzhledem

k předpokladu

11| 6  5 x0  7 y 0 . Z poznámky 1.1.1 dostáváme 11|  2  11 x0  11 y0   6  5 x0  7 y0  a po

snadné úpravě 11| 8 x0  20 y 0  .

Pro další úvahy o dělitelnosti má zásadní význam následující tvrzení, označované jako věta o dělení se zbytkem. Věta 1.1.2 – Dělení se zbytkem Pro každé a  Z , b  N  existuje jediné q , r  Z takové, že platí a  b  q  r , kde 0  r  b .

Poznamenejme, že pro čísla a, b, q, r z věty 1.1.2 se běžně používá následující terminologie: a … dělenec, b … dělitel, q … neúplný podíl, r … zbytek. Příklad 1.1.3 Zřejmě platí: a = 128

b = 23

128 = 23·5 + 13, tj. q = 5, r = 13,

a = -128

b = 23

-128 = 23·(-6) + , tj. q = -6, r = 10,

a = 19

b = 54

19 = 54·0 + 19, tj. q = 0, r = 19,

a = -19

b = 54

-19 = 54·(-1) + 35, tj. q = 0, r = 35,

a=0

b = 29

0 = 29·0 + 0, tj. q = 0, r = 0. 6

(1.2)

Jak dokumentuje následující příklad, nachází věta o dělení se zbytkem využití při převodech z desítkové soustavy do ostatních číselných soustav. Připomeňme, že v soustavě o základu b (b přirozené větší než jedna), vyjadřujeme přirozená čísla ve tvaru (1.3) r0  r1  b  r2  b 2    rn  b n , kde ri  0,, b  1, n  N a používáme zkrácený zápis rn  r1r0 b . V případě dvojkové (binární) soustavy, kde b = 2, nazýváme jednotlivé cifry ri bity ( r0 nejméně významný bit, rn nejvýznamnější bit) a řetězec osmi bitů bytem. Příklad 1.1.4 Převeďte číslo 6862 do číselné soustavy o základu a) 2, b) 8, c) 16. Řešení. 6862 = (1101011001110)2 = (15316)8 = (1ACE)16 Poznámka 1.1.2 K vyjádření čísel v oblasti výpočetní techniky se používají různé číselné formáty, jejichž velikost bývá násobkem bytů, tj. osmi bitů. Například pomocí osmi bitů lze ve dvojkové soustavě vyjádřit přirozená čísla 0,…, 255, pomocí 16 bitů čísla 0,…, 65 535 a 32 bitů 0,…, 4 294 967 295. Snadno zjistíme, že pomocí n bitů lze ve dvojkové soustavě vyjádřit 2 n přirozených čísel 0, ,2 n  1, přičemž u čísel 0,,2 n 1  1 je nejvýznamnější bit nastaven na 0 a u zbývajících čísel, tj. 2 n1 ,,2 n  1 je nejvýznamnější bit nastaven na 1. Této skutečnosti se využívá k vyjádření

záporných čísel  1,,2 n1 ve tvaru tzv. dvojkových doplňků čísel 0,,2 n 1  1 tak, že u záporných čísel je nejvýznamnější bit nastaven na 1. V tomto případě se pomocí n bitů vyjadřují celá čísla z množiny  2 n1 ,,1, 0,1,, 2 n1  1. Například, využitím čtyř bitů lze zapsat čísla  8,,1, 0,1,, 7 . Jejich vyjádření je uvedeno v následující tabulce:

Nezáporné číslo

Vyjádření ve dvojkové soustavě

Vyjádření ve tvaru dvojkového doplňku

Záporné číslo

7

0111

…………

1000

-8

6

0110

…………

1001

-7

5

0101

…………

1010

-6

4

0100

…………

1011

-5

3

0011

…………

1100

-4

2

0010

…………

1101

-3

1

0001

…………

1110

-2

0

0000

…………

1111

-1

Formát záporného celého čísla k , kde  2 n  k  1 lze popsat následovně: 1) Vypočti přirozené číslo k  2 n  k .

7

2) Přirozené číslo k vyjádři pomocí n bitů ve dvojkové soustavě, tj. k  0 bn1 b1b0 2 . (Jelikož 0  k  2 n  1 je nejvýznamnější bit zřejmě nastaven na nulu, tj. bn  0 ). 3) Hledané vyjádření záporného celého čísla k pak dostáváme nastavením nej-významnějšího bitu na jedničku, tj. k  1bn 1 b1b0 .

1.2

Společný dělitel, společný násobek

Definice 1.2.1 – společný dělitel, společný násobek  Nenulové přirozené číslo d nazveme společným dělitelem celých čísel a, b, jestliže d | a  d | b , tj. d dělí obě čísla.  Nenulové přirozené číslo D nazveme společným násobkem nenulových celých čísel a, b, jestliže a | D  b | D , tj. D je dělitelné oběma čísly. Zdůrazněme skutečnost, že v souladu s výše uvedenou definicí 1.2.1 vyšetřujeme pouze kladné společné dělitele a kladné společné násobky. Příklad 1.2.1 Jediní společní dělitelé čísel a = 420, b = 36 jsou 1, 2, 3, 4, 6, 12. Čísla tvaru 1260  n , kde n  N , jsou všechny společné násobky čísel a, b. Pro libovolná a, b  Z  0 , označme d a ,b množinu všech společných dělitelů čísel a, b . Snadno

zjistíme, že d a ,b je shora omezená, neboť žádný z dělitelů nemůže být větší než min  a , b  , a tedy množina d a ,b má vzhledem k přirozenému uspořádání největší prvek. Stejně snadno zjistíme, že množina Da,b všech společných násobků nenulových čísel a, b je zdola omezená, neboť žádný společný násobek nemůže být menší než max  a , b  , a tedy množina Da,b má vzhledem k přirozenému uspořádání nejmenší prvek. Tyto skutečnosti nás opravňují k zavedení následujících pojmů. Definice 1.2.2 – největší společný dělitel, nejmenší společný násobek, nesoudělnost  Největším společným dělitelem celých čísel a, b , z nichž alespoň jedno je různé od nuly, nazveme takového jejich společného dělitele, který je ze všech společných dělitelů největší (existuje vždy a jediný).  Nejmenším společným násobkem nenulových celých čísel a, b nazveme takový jejich společný násobek, který je ze všech společných násobků nejmenší (existuje vždy jediný).  Řekneme, že celá čísla a, b jsou nesoudělná, jestliže jejich největší společný dělitel je roven jedné.

8

Pro největší společný dělitel čísel a, b se vžilo označení NSD a, b  , resp. a, b  a pro jejich nejmenší společný násobek NSN a, b  . Nesoudělnost čísel a, b vyjadřujeme obvykle zápisem NSD a, b   1 , resp. a, b   1 .

Nyní přirozeně vzniká otázka, jak největšího společného dělitele efektivně nalézt. Odpověď dává následující algoritmus, jehož základem je věta o dělení se zbytkem. Eukleidův algoritmus – určení NSN a, b  Nechť a, b  N  . Jestliže aplikujeme následující postupné dělení se zbytkem a  b  q0  r1 ,

0  r1  b ,

b  r1  q1  r2 ,

0  r2  r1 ,

r1  r2  q 2  r3 ,

0  r3  r2 ,

 ri  ri 1  qi 1  ri  2 ,

 0  ri  2  ri 1 ,

rn2

   rn1  q n1  rn , 0  rn  rn1 ,

rn1  rn  q n ,

potom největší společný dělitel čísel a, b je roven poslednímu od nuly různému zbytku ve výše uvedeném postupu, tj. NSDa, b   rn . Příklad 1.2.2 Určete: a) NSD 420 , 36  , b) NSD 8 n  3, 5 n  2 , kde n  N . Řešení. Aplikací Eukleidova algoritmu dostáváme: ad a) 420 = 36·11 + 24, 36 = 24·1 + 12, 24 = 12·2, ad b)

8 n  3  5 n  2   1  3 n  1 , 3 n  1  2 n  1  1  n ,

tedy NSD 420, 36   12 .

5 n  2  3 n  1  1  2 n  1 , 2 n  1  n  2  1,

n  1 n , tedy NSD 8 n  3, 5 n  2   1 a pro libovolné n  N jsou uvažovaná čísla nesoudělná. V praxi se osvědčilo zapisovat Eukleidův algoritmus pomocí následujícího schématu, kde čísla psaná kurzívou jsou podíly q i a čísla psaná tučně zbytky ri . Výpočet probíhá následovně:

24 24 0

36 24 12 2  r3

420 36 396 11 24  r1 1  q1  r2  q2

9

 q0

Věta 1.2.1 – základní vlastnosti NSD Pro největší společný dělitel dvou čísel platí: a) NSD a, b   NSD b, a  .

(1.4)

b) NSD k  a, k  b   k  NSD a, b  , kde k  N . 

(1.5)

 a b  NSDa, b  c) Jestliže d | a  d | b , potom NSD ,   . d d d  d) Jestliže NSD a, b   1 , potom NSD a  c, b   NSD c, b  .

(1.6) (1.7)

Jako užitečné důsledky věty 1.2.1 dostáváme:  d | a  d |b   d | NSDa, b  . 



(1.8)

NSDa, b   1  b | a  c   b | c .

(1.9)

  a b   1 , NSD ,  NSDa, b  NSDa, b   a tedy každá dvě nenulová přirozená čísla a, b lze vyjádřit ve tvaru

(1.10)

a  a1  NSD a, b , b  b1  NSD a, b  ,

(1.11)

kde NSD a1 , b1   1 . Tuto skutečnost budeme často využívat.

Kromě Eukleidova algoritmu existuje celá řada dalších způsobů výpočtu největšího společného dělitele. Např. z věty 1.2.1 lze snadno odvodit následující tzv. dvojkový NSD algoritmus (další způsob, který využívá prvočíselné rozklady je uveden v kapitole věnované problematice prvočísel). Dvojkový NSD algoritmus - určení NSN a, b  Největšího společného dělitele libovolných dvou nenulových celých čísel a, b lze nalézt opakovanou aplikací následujících pravidel (dokažte!): a b 1) Jsou-li a, b sudá, potom NSDa, b   2  NSD ,  .  2 2 a  2) Je-li a sudé, b liché, potom NSDa, b   NSD , b  . 2   ab  3) Jsou-li a, b lichá, potom NSDa, b   NSD , b  . 2   4) NSD a, b   NSD b, a  .

Algoritmus ukončíme v situaci, kdy a  b (zdůvodněte, že nastane!) a využijeme NSD a, a   a . Příklad 1.2.3 Pomocí dvojkového NSD algoritmu určete NSD 258,1728  . Řešení. Postupnou aplikací pravidel dvojkového NSD algoritmu dostáváme (použité pravidlo je uvedeno nad rovnítkem): 1)

2)

3)

3)

2)

NSD258,1728   2  NSD129, 864   2  NSD129, 27   2  NSD51, 27   2  NSD12, 27   2)

3), 4 )

2)

 2  NSD3, 27   2  NSD12, 3  2  NSD3, 3  2  3 ,

10

tj. NSD 258,1728   6 .

V celé řadě případů je velmi užitečná následující charakteristika největšího společného dělitele: Jsou-li a, b nenulová celá čísla, potom jejich největší společný dělitel je roven (dokažte!) nejmenšímu kladnému přirozenému číslu tvaru a  x1  b  x 2 , kde x i  Z .

(1.12)

Jak dokumentuje následující příklad, umožňuje Eukleidův algoritmus takové vyjádření efektivně nalézt. Příklad 1.2.4 Vyjádřete největšího společného dělitele následujících čísel 583 a 231 ve tvaru (1.12): Řešení. Nejprve aplikujeme Eukleidův algoritmus: 583  231  2  121  r1 , 231  121  1  110  r2 , 121  110  1  11  r3 ,

110  11 10 ,

tedy NSD583, 231  r3  11 .

Nyní největšího společného dělitele r3 ve tvaru (1.12) získáme postupným vyjádřením zbytků r1  121  583  231  2 ,

r2  110  231  121  1 ,

r3  11  121  110  1

a jejich zpětným dosazováním dostáváme 11  121  110  1  121  231  121  1  1  121  2  231   583  231  2   2  231  583  2  231   5 ,

tedy x1  2, x 2  5 a NSD 583, 231  583  2  231   5  11 . Přirozeným rozšířením pojmů společný dělitel a největší společný dělitel dvou čísel je následující definice. Definice 1.2.3 – společný dělitel, největší společný dělitel a1 ,, a n Společným dělitelem celých čísel a1 ,, a n , kde n  2 , nazveme každé nenulové přirozené číslo d,

které dělí beze zbytku všechna čísla a1 ,, a n , tj. i  1,, n d | ai . Největším společným

dělitelem celých čísel a1 ,, a n , z nichž alespoň jedno je různé od nuly, nazveme takového jejich společného dělitele, který je největší (existuje vždy a jediný). Poznámka 1.2.1  Úlohu na výpočet největšího společného dělitele více než dvou čísel a1 ,, a n , převádíme na opakovaný výpočet největšího společného dělitele dvou čísel dle schématu: d 2  NSD a1 , a 2  , d 3  NSDd 2 , a3  ,

d 4  NSDd 3 , a 4  ,

 d n  NSDd n1 , a n  , 11

kde NSDa1 ,, a n   d n . 

Největší společný dělitel nenulových celých čísel a1 , , a n , n  2 je roven nejmenšímu kladnému přirozenému číslu tvaru n

a i 1



i

 xi , kde x i  Z .

(1.13)

V případě více než dvou čísel se dále zavádějí pojmy nesoudělnost (někdy označovaná jako sdružená nesoudělnost) a nesoudělnost po dvou. Řekneme, že čísla a1 ,, a n jsou nesoudělná, jestliže NSDa1 ,, a n   1 a řekneme, že jsou nesoudělná po dvou, jestliže jsou nesoudělné všechny dvojice, tj. i  j

NSDai , a j   1 . Je zřejmé, že z nesoudělnosti po dvou vyplývá

nesoudělnost a jak dokládá následující ukázka, obrácené tvrzení neplatí. Například trojice čísel 14, 15, 121 je nesoudělná po dvou, neboť

NSD 14, 15   1 ,

NSD 14, 121  1, NSD 15, 121  1 a tedy i nesoudělná, tj. NSD 14, 15, 121  1 .

Trojice čísel 12, 15, 35 je nesoudělná, tj. NSD 12, 15, 35   1 , ovšem není nesoudělná po dvou, neboť NSD 12, 15   3, NSD 12, 35   1, NSD 15, 35   5 . Příklad 1.2.5 Nalezněte největšího společného dělitele čísel 1694, 3146, 858, 231 . Řešení. Strukturu výpočtu lze znázornit následovně (mezivýpočty jsou realizovány pomocí Eukliedova algoritmu): 1 694 d 2  NSD 1 694, 3 146  

3 146

858

231

242

d 3  NSDd 2 ,858  

22

d 4  NSDd 3 ,231 

11

Tedy NSD 1 694, 3146, 858, 231  d 4  11 . Analogickým postupem jako v příkladu 1.2.4 zjistíme hodnoty celočíselných koeficientů x i ze vztahu (1.13). Dostáváme x1  2, x2  1, x3  21, x4  77 , tedy

NSD 1 694, 3146, 858, 231  1694  2  3146   1  858   21  231  77  11 .

Nyní se krátce zastavme u společných násobků dvou nenulových přirozených čísel. Označme D libovolný společný násobek čísel a, b . Lze tedy psát D  a  q , kde q  N . Vzhledem k tomu, že čísla a, b lze vyjádřit ve tvaru a  a1  NSD a, b  , b  b1  NSD a, b  , kde NSD a1 , b1   1 , je číslo a q D  a1  n , kde  a1  q přirozené a navíc q je dělitelné (beze zbytku) b1 . Lze tak psát 1 b1 NSDa, b 

12

n  N a tedy a1  q  a1  b1  n . Několika snadnými úpravami získáme obecné vyjádření všech společných násobků čísel a, b ve tvaru a b D n, (1.14) NSDa, b  kde n  N . Navíc je zřejmé, že pro nejmenší společný násobek dvou čísel platí a b NSN a, b   . (1.15) NSDa, b  V případě, kdy čísla a, b jsou nesoudělná dostáváme NSN a, b   a  b . Příklad 1.2.6 Určete: a) nejmenší společný násobek čísel 420 a 36, b) nejmenší společný násobek D větší než 333 333. Řešení. ad a) Přímou aplikací vztahu 1.15 dostáváme NSN 420,36  

420  36 . Z příkladu NSD420,36 

1.2.2 část a) víme, že NSD 420, 36   12 , tedy NSN 420,36   1 260 .

ad b) Ze vztahu (1.14) vyplývá, že všechny společné násobky jsou tvaru 1 260  n, n  N a hledanému společnému násobku tak odpovídá n, které je nejmenším řešením (v oboru  333 333  přirozených čísel) nerovnice 1 260  n  333 333 . Odtud n     265 , tedy  1260  D  333 900 . Analogicky, jako v případě společného dělitele a nejmenšího společného dělitele, lze rozšířit pojmy společný násobek a nejmenší společný násobek na případ více než dvou čísel. Definice 1.2.4 – společný násobek, nejmenší společný násobek a1 ,, a n Společným násobkem nenulových celých čísel a1 ,, a n , kde n  2 , nazveme nenulové přirozené číslo D, které je dělitelné každým z čísel a1 ,, a n , tj. i  1,, n ai | D . Nejmenším společným násobkem nenulových celých čísel a1 ,, a n pak nazveme takový jejich společný násobek, který je nejmenší (existuje vždy a jediný). Poznámka 1.2.2  Úlohu na výpočet nejmenšího společného násobku více než dvou přirozených čísel a1 ,, a n , převádíme na opakovaný výpočet nejmenšího společného násobku dvou čísel dle schématu: D2  NSN a1 , a 2  , D3  NSN D2 , a3  , D4  NSN D3 , a4  ,

 Dn  NSN Dn1 , a n  ,

kde NSN a1 ,, a n   Dn .

13

POZOR! Nejmenší společný násobek více než dvou čísel nelze obecně počítat jako v případě dvou čísel, tj. jejich součin dělený jejich největším společným dělitelem. Jsou-li čísla a1 ,, a n po dvou nesoudělná, potom NSN a1 ,, a n   a1    a n .



POZOR! Předpoklad nesoudělnosti po dvou nelze pro n  2 nahradit předpokladem pouhé nesoudělnosti. Snadno zjistíme, že pro nejmenší společný násobek tří čísel platí a  b  c  NSDa, b, c  NSN a, b, c   . (1.16) NSDa, b   NSDa, c   NSDb, c 



Příklad 1.2.7 Vypočtěte nejmenší společný násobek čísel a) 420, 660, 1848, b) 1 694, 3 146, 858 a 231. ad a) Snadno zjistíme, že NSD 420, 660   60 , NSD 420,1848   84 , NSD 660,1848   132 a NSD 420,660,1848   12 . Aplikací vztahu (1.16) dostáváme

420  660  1848  NSD420,660,1848   9 240 . NSD420,660   NSD420,1848   NSD660,1848  ad b) Postup výpočtu nejmenšího společného násobku čtyř čísel lze znázornit následujícím schématem, jehož jednotlivé kroky spočívají ve výpočtu nejmenšího společného násobku dvou čísel a které realizujeme dle vztahu (1.15): NSN 420,660,1848  

1 694 D2  NSN 1 694, 3 146 

3 146

858

231

22 022

D3  NSN D2 ,858  

66 066

D4  NSN D3 ,231 

66 066

Tedy NSN 1 694, 3 146, 858, 231  D4  66 066 .

1.3

Prvočísla a prvočíselné rozklady

Zkoumáme-li počet dělitelů kladných přirozených čísel snadno zjistíme, že některá přirozená čísla větší než jedna mají pouze dva dělitele - číslo jedna a sebe sama (nevlastní dělitelé), kdežto ostatní mají i vlastní dělitele. Odtud následující definice pojmu prvočíslo. Definice 1.3.1 – prvočíslo, složené číslo Přirozené číslo p  1 nazveme prvočíslem, jestliže

a  N a | p   a  1  a  p ,

tj. číslo p má pouze nevlastní dělitele. 14

Ostatní kladná přirozená čísla větší než jedna nazýváme čísla složená. Příklad 1.3.1 Čísla 2, 3, 5, 7 jsou prvočísla, neboť všechna mají pouze nevlastní dělitele. Naopak, čísla 4, 6, 189, 222 jsou čísla složená, neboť mají vlastní dělitele, např. 2 | 4, 3| 6, 7 |189, 37 | 222 . Ovšem

mnohem obtížnější je zjistit, že číslo 162 259 276 829 213 363 391 578 010 288 127 je prvočíslo, kdežto 340 282 366 920 938 463 463 374 607 431 768 211 457 je číslo složené. Věta 1.3.1 – Eukleides Existuje nekonečně mnoho prvočísel. Poznamenejme, že existuje celá řada dalších různě rafinovaných důkazů existence nekonečně mnoha prvočísel, které odkrývají mnohdy překvapivé souvislosti. Poznámka 1.3.1 

Nejmenší od jedničky různý dělitel složeného čísla n je prvočíslo, které je nejvýše rovno



Je-li p prvočíslo takové, že p | a  b , potom p| a nebo p| b . (Dokažte!)



 n .

Všechna prvočísla vyskytující se v množině 2, , n lze nalézt pomocí algoritmu (nazývaného Eratosthenovo síto), který lze formulovat následovně: 1. V posloupnosti 2,  , n označ první nevyškrtnuté a ještě neoznačené číslo. Toto číslo p je prvočíslo. Je-li p 

 n , jdi na krok 2., jinak ukonči algoritmus a nevyškrtnutá čísla jsou

právě všechna hledaná prvočísla. 2. Vyškrtni všechny násobky čísla p, počínaje p 2 . Po jejich vyškrtnutí jdi na krok 1. Výše popsaný algoritmus (Eratosthenes, 276 – 195 př. n. l.) je pravděpodobně historicky první metoda umožňující „generovat“ posloupnost prvočísel. Příklad 1.3.2 Pomocí Eratosthenova síta nalezněte všechna prvočísla, která jsou menší nebo rovna 50. Řešení. V tabulce obsahující čísla 2,, 50 aplikujeme výše popsaný algoritmus. Dostáváme tak následující tabulky, jejichž obsah postupně odpovídá jednotlivým krokům algoritmu: Vyškrtnutí násobků 2 (počínaje od 2 2 ) Vyškrtnutí násobků 3 (počínaje od 3 2 ) 3 5 7 5 7 2 2 3 9 11 13 15 11 13 17 19 21 17 19 23 25 27 29 23 25 29 31 33 35 31 35 37 39 41 43 37 41 43 45 47 49 47 49 Vyškrtnutí násobků 5 (počínaje od 5 2 ) 7 2 3 5 11 13

Vyškrtnutí násobků 7 (počínaje od 7 2 ) 2 3 5 7 11 13 15

17

19

17

23

29

23

31 37

19 29

31 41

43

37

41

43

47 49 47 Všechna prvočísla v řadě 2,, 50 jsou nalezena po vyškrtnutí násobků čísla 7 a jsou obsažena v poslední tabulce. V dalších úvahách hraje klíčovou roli následující věta, označovaná často jako Základní věta aritmetiky. Věta 1.3.2 Každé přirozené číslo větší než jedna lze rozložit na součin prvočísel, a to jednoznačně, nepřihlížíme-li k pořadí prvočísel. Jako zřejmý důsledek věty 1.3.2 dostáváme, že každé přirozené číslo a  1 lze jednoznačně vyjádřit ve tvaru (1.17) a  p11    pkk , kde

pi , i  1,, k jsou všechna navzájem různá prvočísla (seřazená vzestupně), která se

vyskytují v rozkladu čísla a,  i  N  , i  1,, k (tzv. násobnost prvočísla p i v rozkladu a). Výraz (1.17) se nazývá kanonický rozklad přirozeného čísla a. (Často budeme používat kratší označení „rozklad“ místo „kanonický rozklad“.) Věta 1.3.3 Nechť a  p11    pkk , b  q11    qll jsou kanonické rozklady. Potom platí: a) Každý dělitel d čísla a má kanonický rozklad d  p11    pkk ,

(1.18)

kde  i  N , 0   i   i , i  1,, k . b) Největší společný dělitel čísel a, b má kanonický rozklad NSDa, b  r11    rh h ,

(1.19)

kde r1 ,, rh jsou prvočísla společná kanonickým rozkladům čísel a, b,  i je minimum z exponentů, se kterým se prvočíslo ri vyskytuje v kanonických

rozkladech čísel a, b. c) Nejmenší společný násobek čísel a, b má kanonický rozklad NSNa, b  r11    rm m , kde r1 ,, rm jsou prvočísla vyskytující se v alespoň jednom kanonickém rozkladu,  i je maximum z exponentů, se kterým se prvočíslo ri vyskytuje v kanonických

rozkladech čísel a, b.

16

(1.20)

Příklad 1.3.3 Pomocí kanonických rozkladů čísel a  7 875, b  3 900, c  82 500 určete všechny dělitele čísla a, NSD a, b, c  , NSN a, b, c  .

Řešení. Nejprve je třeba nalézt kanonické rozklady uvedených čísel. Tyto rozklady určíme tak, že uvedená čísla zkoušíme dělit prvočísly (dělení zvoleným prvočíslem opakujeme, dokud je zbytek nulový). Dostáváme tak a  32  53  7, b  2 2  3  52  13, c  2 2  3  54  11 . Všechny dělitele čísla a jsou tvaru d  31  52  7 3 , kde 0  1  2, 0   2  3, 0  3  1 a jsou obsaženy v následující tabulce. 1 105

3 125

5 175

7 225

9 315

15 375

21 525

25 35 45 63 75 875 1125 1575 2625 7875

Z věty 1.3.3 víme, že kanonický rozklad NSD a, b, c  obsahuje pouze prvočísla společná oběma kanonickým rozkladům, tj. 3 a 5. Exponenty jsou rovny minimu z exponentů, se kterými se vyskytují v kanonických rozkladech čísel a, b, c. Odtud NSDa, b, c   3  5 2  75 . (Nalezněte všechny společné dělitele čísel a, b, c.) Dále víme (opět věta 1.3.3), že kanonický rozklad NSN a, b, c  obsahuje všechna prvočísla, která se vyskytují v kanonickém rozkladu alespoň jednoho z čísel a, b, c, tj. 2, 3, 5, 7, 11 a 13. V tomto případě se exponenty rovnají maximu z exponentů. Odtud NSN a, b, c   2 2  32  5 4  7  11  13  22 522 500 . Poznámka 1.3.2 Jedním z fundamentálních problémů teorie čísel je otázka rozložení prvočísel v množině všech přirozených čísel. Některé základní výsledky lze formulovat následovně (tabulka v příloze obsahuje prvních 840 prvočísel):  Existuje nekonečně mnoho libovolně dlouhých posloupností po sobě jdoucích složených čísel, tj. neobsahující žádné prvočíslo (dokažte!).  Pro libovolná nesoudělná přirozená čísla a, m existuje nekonečně mnoho prvočísel p, která při dělení číslem m dávají zbytek a, tedy jsou tvaru p  m  q  a , kde q  N (C. F. Gauss).  Označíme-li n  počet prvočísel menších nebo rovných přirozenému číslu n, platí n , (1.21) ln n kde symbol  chápeme jako přibližnou rovnost (přesněji, limita podílu obou stran je pro n   rovna 1). Hodnoty obou stran vztahu (1.21) jsou pro vybraná n obsaženy v následujících tabulkách: n  

n 10 20 30 40 50

n 

4 8 10 12 15

n

ln n 4 7 9 11 13

n 100 000 200 000 300 000 400 000 500 000 17

n 

9 592 17 984 25 997 33 860 41 538

n

ln n 8 686 16 385 23 788 31 010 38 103

60 70 80 90 100

17 19 22 24 25

15 16 18 20 22

600 000 700 000 800 000 900 000 1 000 000

49 098 56 543 63 951 71 274 78 498

45 097 52 010 58 857 65 645 72 382

Příklad 1.3.4 Dokažte speciální variantu obecného Gaussova tvrzení (poznámka 1.3.2), že existuje nekonečně mnoho prvočísel tvaru 4q  3 . Řešení. Důkaz provedeme analogicky k důkazu věty 1.3.1, tj. sporem. Nejprve si uvědomme, že každé prvočíslo větší než 2 dává při dělení číslem 4 zbytek 1, nebo 3. Nyní předpokládejme, že existuje pouze konečně prvočísel p1 , , p n uvažovaného tvaru 4q  3 (určitě taková existují, např. 3, 7, 11, 19, 23 apod.) a položme p  4 p1    p n  1 . Je zřejmé, že číslo p dává při dělení 4 zbytek 3, navíc není dělitelné žádným z prvočísel p1 , , p n (jinak by dané prvočíslo muselo dělit 1). Vzhledem k tomu, že součin čísel tvaru 4q  1 je opět číslo téhož tvaru (dokažte!), musí být číslo p dělitelné prvočíslem tvaru 4q  3 různým od p1 , , p n . Spor, existuje tedy nekonečně mnoho prvočísel tvaru 4q  3 . Velmi významnou roli v teorii čísel a v celé řadě aplikací, např. moderní teorie šifrování, testy superpočítačů apod. (podrobnosti přesahují rámec těchto skript, relevantní internetovské odkazy viz příloha), hraje problematika kanonických rozkladů velkých čísel, resp. testy jejich prvočíselnosti. V tomto kontextu se nejčastěji vyskytují čísla speciálních tvarů, např. Fermatova, Mersennova a Cunninghamova čísla. Definice 1.3.2 - Fermatova a Mersennova čísla n

Fermatovými čísly nazýváme čísla Fn  2 2  1 , kde n  N a Mersennovými čísly nazýváme čísla

M n  2 n  1 , kde n  N . Poznámka 1.3.3 - Fermatova a Mersennova prvočísla  Fermatova čísla F0  3, F1  5, F2  17, F3  257, F4  65 537 jsou prvočísla (tzv. Fermatova prvočísla). Tato skutečnost vedla vynikajícího francouzského matematika Pierre de Fermat (1601-1695) k vyslovení hypotézy, že všechna Fermatova čísla jsou prvočísla. Teprve později byla tato hypotéza vyvrácena Leonardem Eulerem, který ukázal, že číslo F 5 4 294 967 297 je složené. Nyní panuje obecné přesvědčení, že všechna Fermatova čísla Fn , n  5 jsou čísla složená. Ovšem ani v dnešní době výpočetní techniky není snadné prokázat, že pro některou konkrétní hodnotu n je Fn číslo složené. Například doposud nebylo zjištěno, zda F24 je skutečně číslo složené a u F12 (o kterém je prokázáno, že je složené) nebyl nalezen jeho 

kanonický rozklad. Historicky neméně zajímavá a z hlediska aplikací velmi významná jsou tzv. Mersennova prvočísla (Marin Mersenne, 1588-1648), tj. prvočísla tvaru 2 p  1 , kde p je prvočíslo (jde tedy o speciální Mersennova čísla). Lze ukázat, že pokud p není prvočíslo, nemůže být ani 2 p  1 18

prvočíslo. Obrácené tvrzení ovšem neplatí (je-li p prvočíslo, potom 2 p  1 být prvočíslem může, ale nemusí). V současné době se předpokládá (není ovšem dokázáno), že mezi všemi čísly tvaru 2 p  1 , kde p je prvočíslo, existuje nekonečně mnoho Mersennových prvočísel, ale i čísel složených. Například čísla M 2 , M 3 , M 5 , M 7 , M 13 , M 17 , M 19 , M 31 jsou Mersennova prvočísla, kdežto M 11 , M 67 , M 257 jsou čísla složená. Největší v současné době (rok 2001) známé Mersennovo prvočíslo je M 6 972 593  2 6 972 593  1 (to ovšem neznamená, že o všech číslech M p , kde p je prvočíslo menší než 6 972 593 je známo zda jsou prvočíslem). Vzhledem k tomu, že pro Mersennova čísla existují efektivní testy jejich prvočíselnosti (např. LucasLehmerův test), může jít opět o zajímavý námět pro studenty (viz internetovské odkazy v příloze). Pro zajímavost uveďme, že prvočíselnost M 1 257 787 byla prokázána na superpočítači Cray T-94, ovšem prvočíselnost M 6 972 593 již na pouhém PC Pentium 350MHz.

1.4

Základní aritmetické funkce

V teorii čísel a v jejich aplikacích hrají významnou roli funkce, jejichž definiční obory tvoří kladná přirozená čísla N  . Pro takové funkce se vžilo označení aritmetické funkce. Definice 1.4.1 – multiplikativní funkce Řekneme, že aritmetická funkce f je multiplikativní, jestliže: 

n  N  takové, že f n   0 ,



m, n  N  platí NSDm, n   1   f m  n   f m  f n  .

(1.22)

Základní vlastnosti multiplikativních funkcí popisuje následující věta. Věta 1.4.1 a) Je-li f multiplikativní funkce, potom f 1  1 . b) Součin multiplikativních funkcí je multiplikativní funkce. c) Je-li f multiplikativní, n  p11    pkk kanonický rozklad, potom

 f d   1  f  p   f  p     f  p    1  f  p   f  p     f  p . 1

2 1

1 1

k

k k

2 k

d |n

(Součet na levé straně se provádí přes všechny dělitele d čísla n.) Poznámka 1.4.1 – počet dělitelů, součet dělitelů Aritmetická funkce f r n  n r , n  N  je multiplikativní (dokažte!) a dle vztahu (1.23) platí

d

r









 1  p1r  p12 r    p11r    1  p kr  p k2 r    p k k r .

d |n

Odtud volbou r  0 dostáváme vztah pro počet dělitelů čísla n

n   1  1    1    1    1 ,     d |n 1 1

tj. 19

 k 1

(1.23)

n   1  1     k  1 .

Volbou r  1 dostáváme vztah pro součet dělitelů čísla n







(1.24)



S n    d  1  p1  p12    p11    1  p k  p k2    p k k , d |n

tj.

 p  k 1  1   p 1 1  1       k S n    1   p 1  .  p1  1   k 

(1.25)

Příklad 1.4.1 Určete počet a součet všech dělitelů čísla 15 120. Řešení. Snadno zjistíme, že kanonický rozklad daného čísla je 15 120  2 4  33  5  7 . Pro počet dělitelů tak dostáváme

15 120   4  1  3  1  1  1  1  1  80

a součet dělitelů

 2 41  1   331  1   511  1   711  1             59 520 . ¶ S 15 120     2 1   3 1   5 1   7 1  Definice 1.4.2 - Möbiova funkce Aritmetickou funkci n  definovanou vztahy 

1  1 ,



n  

0 , pokud existuje přirozené číslo d  1 takové, že d 2 | n ,

 1k , v ostatních případech, kde k je počet prvočísel vyskytujících se v kanonickém rozkladu n, nazýváme Möbiovou funkcí. Z definice je patrné, že hodnoty n  snadno určíme z kanonického rozkladu čísla n  p11    pkk . Jsou-li totiž všechna  i  1 , potom n   1k a pokud alespoň jedno  i  2 je n   0 . Věta 1.4.2 Möbiova funkce je multiplikativní a pro n  1 platí

 d   0 . d |n

Definice 1.4.3 - Eulerova funkce Aritmetickou funkci n  definovanou vztahy 

1  1 ,



n   k , kde k je počet čísel v řadě 1, , n , která jsou nesoudělná s n,

nazýváme Eulerovou funkcí. Z definice snadno zjistíme, že pro libovolné prvočíslo p platí  p   p  1 (zdůvodněte!). V případě složených čísel je výpočet hodnoty Eulerovy funkce obtížnější.

20

Věta 1.4.3 a) Je-li n  p11    pkk kanonický rozklad, potom









n  p11  p11 1    pkk  pkk 1 .

(1.26)

b) Eulerova funkce je multiplikativní. c) Platí

 d   n .

(1.27)

d |n

Příklad 1.4.2 Určete hodnotu Möbiovy a Eulerovy funkce v bodech 13 799 247 a 24 538 437. Řešení. Prvním krokem je určení kanonických rozkladů. Platí 24 538 437  33  7  112  29  37 . 13 799 247  3  7  11  31  41  47 , Přímo z definice Möbiovy funkce dostáváme 6 13 799 247    1  1 , neboť v kanonickém rozkladu se vyskytuje 6 prvočísel a každé s exponentem 1, dále 24 538 437   0 ,

neboť v kanonickém rozkladu se vyskytuje alespoň jedno prvočíslo s exponentem větším než 1 (prvočísla 3 a 11). Hodnotu Eulerovy funkce určíme ze vztahu (1.26). Dostáváme tak 13 799 247   3  1  7  1  11  1  31  1  41  1  47  1  6 624 000 a









24 538 437   33  32  7  1  112  11  29  1  37  1  11 975 040 . ¶

Poznamenejme, že v příloze lze nalézt tabulky s hodnotami Möbiovy a Eulerovy funkce pro hodnoty n  830 , které lze spolu s multiplikativitou vhodně využít k výpočtům. Například 35 100   351  100  ,

neboť NSD 351,100   1. V tabulkách snadno nalezneme 351  216 a 100   40 , tedy 35 100   8 640 .

Kromě aritmetických funkcí hrají v diskrétní matematice významnou roli také funkce nazývané dolní celá část, horní celá část a lomená část. Jsou definovány následovně:  Funkce dolní celá část x, kde x  R , je definována jako největší celé číslo menší nebo rovné x. Tuto funkci budeme označovat symbolem x  a lze ji definovat následujícími vlastnostmi: 



x  R x   Z , x  R x   x  x   1 .

Funkce horní celá část x, kde x  R , je definována jako nejmenší celé číslo větší nebo rovné x. Tuto funkci budeme označovat symbolem x  a lze ji definovat vlastnostmi: -

x  R x   Z ,

-

x  R x   1  x  x  .

Funkci lomená část x, kde x  R , budeme označovat symbolem x . Tato funkce je definována vztahem x  x  x  . 21

Příklad 1.4.3 5  5

 5  5  5  5  4,75  5  4,75  4  6,01  7  6,01  6 5,2  3,1  9  5,2  3,1  10 4,8  3,4  9  4,8  3,4 . ¶

5  5 4,75  4 4,75  5 6,01  6 6,01  7 5,2  3,1  8  5,2  3,1 4,8  3,4  8  4,8  3,4  7

Poznámka 1.4.2  Některé často využívané vlastnosti funkcí dolní a horní celá část jsou (dokažte!): x  1  x   x  x   x  1,

 x   x , x  n  x  n, n  N ,

 x   x , x  n  x  n, n  N ,

n  n   x i    x i  ,  i 1  i 1

n  n   x i    x i  .  i 1  i 1

Pro názornost následují grafy funkcí dolní celá část, horní celá část a lomená část.

-3

-2

-1

x 3 

3

2

2

1

1

0

1

2 x 3

-3

-1

0 -1

-2

-2

-3

-3

2

-2

-1

x

1 -3

-2

-1

0

1 -1 -2

22

2 x 3

x 

1

2 x 3

1.5

Řetězové zlomky

Je všeobecně známé, že při numerických výpočtech vždy pracujeme s racionálními čísly, resp. s jejich jistou podmnožinou. V tomto kontextu hraje důležitou roli problematika tzv. diofantické aproximace, která, zjednodušeně řečeno, zkoumá, jak přesně lze dané číslo (nejčastěji iracionální) aproximovat pomocí racionálních čísel určitých vlastností. K této problematice má úzký vztah i tato podkapitola týkající se řetězových zlomků. Snadno totiž zjistíme, že každé číslo   R  Z (v případě celých čísel je situace triviální), lze vyjádřit jediným způsobem ve tvaru 1 ,   q0  1 kde q0    Z (největší celé číslo menší nebo rovné  ) a 1   1 . Pokud  1 není přirozené číslo, lze postupovat analogicky i v tomto případě, tj. psát 1 , 1  q1  2 kde q1  1  a 1   2 . Odtud   q0 

1 1 q1  2

.

Naznačený postup lze samozřejmě opakovat, dokud v některém kroku (např. i v prvním) nedostaneme  n  N  (jak uvidíme později, tato situace nemusí nastat). Tím se již dostáváme k pojmu rozvoj čísla  v řetězový zlomek. Definice 1.5.1 Řetězovým zlomkem nazveme (konečný nebo nekonečný) výraz tvaru 1 , q0  1 q1  q2 

(1.28)

 1



qn 

1 

kde q0  Z , qi  N  . Čísla q i se nazývají členy rozvoje (v řetězový zlomek) a výrazy  0  q 0 , 1  q 0 

1 , … ,  n  q0  q1

1 q1 

,…

1 q2   

23

1 qn

(1.29)

se nazývají přibližnými zlomky†. Pro zjednodušení budeme častěji využívat zápis ve tvaru  0  q0  , 1  q0 , q1  , … ,  n  q0 , q1 ,, q n  , … Dále řekneme, že číslo  má konečný (ukončený) rozvoj v řetězový zlomek, jestliže existuje n takové, že při postupu popsaném v úvodu je  n celé číslo (tj.  n i  0 pro  i  N  ). V tomto případě zřejmě platí   q0 , q1 ,, q n  , tj.   q 0 

1 q1 

.

1 q2   

1 qn

Věta 1.5.1 Reálné číslo  má konečný rozvoj v řetězový zlomek právě tehdy, je-li racionální. Obecný postup jak sestrojovat řetězové zlomky je popsán v úvodu. Následující poznámka ukazuje na souvislost s již dobře známým Eukleidovým algoritmem. Poznámka 1.5.1 – Řetězové zlomky a Eukleidův algoritmus a Je-li racionální číslo, potom užitím Eukleidova algoritmu dostáváme následující: b a 1 b 1. krok tj.  q 0  , kde 1   1. a  b  q0  r1 , 0  r1  b , b 1 r1 2. krok

b  r1  q1  r2 , 0  r2  r1 ,

tedy

3. krok

a  q0  b

1 1 q1  2

a  q0  b

1 q1 

r b 1 , kde  2  1  1 ,  q1  r2 r1 2

tj.

r1 r 1  q2  , kde  3  2  1 , r2 3 r3

.

r1  r2  q 2  r3 , 0  r3  r2 ,

tedy

tj.

.

1 q2 

1 3

Vzhledem k tomu, že zbytky tvoří klesající posloupnost přirozených čísel, je zaručena konečnost uvedeného postupu a musí nastat situace, kdy jisté rn je poslední nenulový zbytek n. krok

†

rn2  rn1  q n1  rn , 0  rn  rn1 ,

tj.

rn  2 r 1  q n 1  , kde  n  n 1  1 , rn 1 n rn

Každý přibližný zlomek lze vyjádřit ve tvaru zlomku s právě jednou zlomkovou čarou, tj.  i 

24

Pi Qi

, i  1,  , n

tedy

a  q0  b

1 q1 

.

1 q2   1



q n 1 

n  1. krok

rn1  rn  q n ,

rn 1  qn , rn

tj.

1 n

a  q0  b

1 q1 

.

1 q2   

Vidíme tedy, že jednotlivé členy rozvoje racionálního čísla

1 qn

a v řetězový zlomek tvoří právě b

neúplné podíly z Eukleidova algoritmu. Věta 1.5.2 – základní vlastnosti přibližných zlomků a) Mezi čitateli P i a jmenovateli Qi přibližných zlomků platí Pi  qi  Pi 1  Pi 2 , kde P1  1, P0  q1 ,

(1.30)

Qi  qi  Qi 1  Qi 2 , kde Q1  0, Q0  1 .

(1.31)

b) Pro libovolné dva sousední přibližné zlomky  i ,  i 1 platí  i   i 1 

 1i 1 Qi  Qi 1

.

(1.32)

c) Přibližné zlomky jsou v základním tvaru, tj. NSDPi , Qi   1 . Je zřejmé, že neúplné podíly qi , i  0,1, , n a rekurentní vztahy (1.30), (1.31) s počátečními podmínkami umožňují efektivní výpočet přibližných zlomků. Tento výpočet se často realizuje pomocí tzv. tabulky přibližných zlomků, jejíž schéma následuje: i -1 0 1 2 … n q1 q2 qi q0 qn --… Pi q0 Pn P1 P2 1 … Q1 Q2 Qi Qn 0 1 …

Příklad 1.5.1 781 Číslo rozviňte v řetězový zlomek a sestavte tabulku přibližných zlomků. 654 Řešení. Pomocí Eukleidova algoritmu zjistíme potřebné neúplné podíly: 654  127  5q1   19 , 127  19  6q 2   13 , 781  654  1q0   127 , 25

19  13  1q3   6 ,

13  6  2q 4   1 ,

Odtud hledaný rozvoj v řetězový zlomek 781  1 654

6  1  6q5  , 1 1

5

1

6 1

1 2

1 6

a tabulka přibližných zlomků: i -1 0 1 2 3 4 5 qi --1 5 6 1 2 6 Pi 1 1 6 37 43 123 781 Qi 0 1 5 31 36 103 654 Nyní lze snadno ověřit, základní vlastnosti přibližných zlomků uvedené ve větě 1.5.2. Poznámka 1.5.2  Lze ukázat (dokažte), že mezi všemi racionálními čísly, jejichž jmenovatel je nejvýše roven Qi , je právě přibližný zlomek  i nejlepší aproximací rozvíjeného čísla. Přesněji, platí: Je-li  i 

Pi a přibližný zlomek rozvoje reálného čísla  v řetězový zlomek,   libovolné Qi b

racionální číslo takové, že 0  b  Qi ,  i   , potom    i     . 

Pro zajímavost jsou v následující tabulce uvedeny (nekonečné) řetězové zlomky některých vybraných iracionálních čísel. Číslo

Řetězový zlomek

e

[2,1,2,1,1,4,1,1,6,1,1,8,1,1,10, …]



[3,7,15,1,292,1,1,1,2,1,3,1,14, …]

2

[1,2,2,2, …]

5

[2,4,4,4, …]

10

[3,6,6,6, …]

17

[4,8,8,8, …]

Jako důsledek dostáváme, že následující racionální čísla nejlépe aproximují (ve smyslu první odrážky této poznámky) číslo  . Pi 3 22 333 355 103 993 Qi 1 7 106 113 33 102 i 1,42E-01 1,26E-03 8,32E-05 2,67E-07 5,78E-10 Poslední řádek obsahuje horní hranici „chyby“ aproximace, tj.  

26

Pi  i . Qi

1.6

Kongruence

Z věty o dělení se zbytkem víme, že celá čísla dávají při dělení přirozeným číslem m  2 zbytky pouze z množiny 0,1, , m  1 . Z pohledu dělitelnosti, lze proto čísla dávající stejný zbytek považovat za „totožná“. Odtud následující definice. Definice 1.6.1 Řekneme, že celá čísla a, b jsou kongruentní modulo m, kde m  N  0,1 , jestliže obě čísla mají při dělení číslem m stejný zbytek. Skutečnost, že čísla a, b jsou kongruentní modulo m vyjadříme některým z následujících zápisů: a  b mod m  , a  b m  , resp. a  m b . V opačném případě (a, b nemají při dělení číslem m stejný zbytek), píšeme a  b mod m  a říkáme, že uvedená čísla nejsou kongruentní modulo m. Dále budeme používat zápis a  b mod m  , kterým vyjádříme skutečnost, že číslo a je rovno zbytku při dělení čísla b číslem m. Například 7  28 mod 3 , 1  28 mod 3 . Poznámka 1.6.1 Přes svou jednoduchost nachází výše zavedený pojem kongruence velmi široké využití v celé řadě oblastí. Vzhledem k rozsahu skript se stručně zmíníme pouze o generování náhodných (přesněji řečeno pseudonáhodných) čísel a některých způsobech šifrování.  Efektivní metodou generování posloupnosti pseudonáhodných čísel x1 , x 2 , jsou lineární kongruence. Jednotlivé členy posloupnosti jsou počítány rekurentně ze vztahu xn1  a  xn  c  mod m , (1.34) kde m, a, c, x0 jsou vhodná přirozená čísla taková, že 2  a  m, 0  c  m, 0  x0  m (m … modul, a … multiplikační koeficient, c … inkrement, x 0 … počáteční hodnota).



Většina standardních počítačů dnes využívá pro generování pseudonáhodných čísel modul m  2 31  1 , multiplikační koeficient a  7 5 a navíc speciální variantu vztahu (1.34), tzv. ryze multiplikativní generátor, kde c  0 . (V případě, kdy požadujeme pseudonáhodná čísla x z intervalu 0,1 , použijeme posloupnost i , i  1, 2, ) m Jedním z nejstarších způsobů šifrování je tzv. Caesarovo šifrování, které spočívalo v „cyklickém posunutí“ celé abecedy o tři znaky vpřed  A  D, B  E , , Z  C  . Z pohledu kongruencí lze toto šifrování popsat vztahem y   x  3 mod 26  , (1.35) kde x je pořadové číslo šifrovaného znaku (v rámci anglické abecedy, počet znaků 26), y je pořadové číslo zašifrovaného znaku a 3 je posunutí. Dešifrování se pak provádí „zpětným“ posunutím, tj. dle vztahu x   y  3 mod 26  , resp. x   y  23 mod 26  (1.36) kde x je původní znak a y zašifrovaný znak. Poznamenejme, že výše popsaný způsob šifrování není příliš bezpečný, proto se dnes používají sofistikovanější metody (viz poznámka 1.7.3).

27

Věta 1.6.1 Následující tvrzení jsou ekvivalentní: a) a  b mod m  , b) m | a  b  , c) a  b  m  t , kde t  Z . Příklad 1.6.1 Zřejmě platí 760  23 mod 3

… obě čísla dávají při dělení číslem 3 zbytek 1, tedy ekvivalentně platí 3 | 760   23 , 760   23  3  261 .

760  23 mod 7 

… při dělení číslem 7 dává 760 zbytek 4 a –23 zbytek 5, tedy

31  435 mod 101

… obě čísla dávají při dělení číslem 101 zbytek 31, tedy ekvivalentně

ekvivalentně 7 | 760   23 , 760   23  7  t pro každé t  Z . platí 101| 31  435 , 31  435  101   4  .

Jak dokládá následující věta, jsou početní pravidla pro kongruence mající stejný modul podobná početním pravidlům pro rovnice. Věta 1.6.2 – stejný modul Jestliže a1  b1 mod m  , a 2  b2 mod m  , potom platí: a) a1  a 2  b1  b2 mod m  .

(1.37)

b) a1  a 2  b1  b2 mod m  .

c) Jestliže d | a1 , d | b1 , NSD d , m   1 , potom

(1.38)

a1 b1  mod m . d d

(1.39)

Jako snadný důsledek pak dostáváme:  K oběma stranám kongruence lze přičíst, resp. od nich odečíst libovolné celé číslo.  Obě strany kongruence lze vynásobit libovolným číslem.  Členy z jedné strany kongruence lze převést na druhou, pokud u nich změníme znaménko.  Obě strany kongruence lze umocnit na n-tou, kde n  N . Jak dokládá následující ukázka, je ve větě 1.6.2 část c) předpoklad NSD d , m   1 podstatný, neboť 144  78 mod 33 , ovšem

144 78 mod 33 .  6 6

Věta 1.6.3 – změna modulu a) Jestliže a  b mod m  , potom a  k  b  k mod m  k  , kde k  N  . m  b) Jestliže a  b mod m , d | m , potom a  b  mod  . d  a b m c) Jestliže a  b mod m , d | NSD a, b, m  , potom   mod  . d d  d d) Jestliže a  b mod m1 , a  b mod m2  , potom a  b mod NSN m1 , m 2  .

28

Příklad 1.6.2 Pro určení dne v týdnu (pondělí – neděle), který připadne na dané datum, lze využít tzv. Zellerovy kongruence

  r  s  x    d  2,6m  0,2  r     2s     mod 7  , (1.40) 4 4   kde x … je identifikace dne v týdnu dle tabulky 0 1 2 3 4 5 6 NE PO ÚT ST ČT PÁ SO d … je den v měsíci, m … je identifikace měsíce dle tabulky 1 2 3 4 5 6 7 8 9 10 11 12 březen duben květen červen červenec srpen září říjen listopad prosinec leden únor s … je století příslušné N, kde N je pro leden a únor předcházející rok zjišťovaného data a v ostatních případech jde o aktuální rok, r… jsou jednotky a desítky let (bez století) příslušné N. Snadno například zjistíme, že dne: 1.11.1111 byla středa N  1111, d  1, m  9, r  11, s  11, x  7 3 , 2.2. 2222 bude sobota N  2221, d  2, m  12, r  21, s  22, x  7 6 .

Pro další úvahy je podstatné, že vztah „býti kongruentní modulo m“ tvoří binární relaci na Z s vlastnostmi a  Z a  a mod m  ,  (reflexivita) 

a, b  Z



a, b, c  Z

a  b mod m   b  a mod m , a  b mod m  b  c mod m   a  c mod m .

(symetrie) (tranzitivita)

Jde tedy o relaci ekvivalence, která indukuje rozklad Z mající m následujících tříd ekvivalence

0  ,  2m,  m, 0, m, 2m,  k  m k  Z , 1  ,1  2m,1 m,1,1  m,1  2m,  1  k  m k  Z , 2  ,2  2m,2  m, 2, 2  m,2  2m,  2  k  m k  Z ,

 m  1  ,  m  1,1, m  1, 2m  1, 3m  1,  m  1  k  m k  Z , nazývané zbytkové třídy modulo m, resp. třídy zbytků modulo m. Každá třída zbytků obsahuje právě všechny navzájem modulo m kongruentní celá čísla (tj. čísla mající při dělení m stejný zbytek). Pro množinu všech takto vzniklých zbytkových tříd modulo m se vžilo označení Z m , tj. Z m  0, 1,, m  1 . Poznamenejme, že v dalších částech skript, kde by již nemělo dojít

k nedorozumění, budeme běžně používat zjednodušený zápis a místo a  a Z m  0,1,, m  1. Nyní na množině Z m definujme operaci sčítání

a   b  a  b

a násobení

a   b  a  b. 29

a1   a 2 , b1   b2 ,

(Dokažte, že obě operace jsou definovány korektně, tj. pokud

a1   b1   a 2   b2  a a1   b1   a 2   b2  .)

potom

Kromě obvyklých vlastností obou operací (asociativita, komutativita, distributivita, existence nulového, opačného a jednotkového prvku) platí:  V Z m lze dělit právě tehdy, je-li m prvočíslo, tj. a  Z m  0 b  Z m

a b  1 právě tehdy, je-li m prvočíslo. (V tomto případě používáme označení a1 místo b  a mluvíme o inverzním prvku.)



V Z m existují vlastní dělitelé nuly právě tehdy, je-li m číslo složené, tj. a, b  Z m  0 a   b  0 právě tehdy, je-li m číslo složené.

Příklad 1.6.3 Algebraická struktura Z 5 obsahuje následujících pět zbytkových tříd (a tvoří rozklad Z):

0  ,  10,  5, 0, 5,10,  5k k  Z  … čísla dělitelná pěti, tj. dávající zbytek 0, 1  ,  9,  4,1, 6,11,  5k  1 k  Z  … čísla dávající při dělení pěti zbytek 1, 2  ,  8,  3, 2, 7,12,  5k  2 k  Z  … čísla dávající při dělení pěti zbytek 2, 3  ,  7,  2, 3, 8,13,  5k  3 k  Z  … čísla dávající při dělení pěti zbytek 3, 4  ,  6,  1, 4, 9,14,  5k  4 k  Z  … čísla dávající při dělení pěti zbytek 4,

kde operace sčítání a násobení jsou definovány následujícími tabulkami: +

[0]

[1]

[2]

[3]

[4]

·

[0]

[1]

[2]

[3]

[4]

[0] [1]

[0] [1]

[1] [2]

[2] [3]

[3] [4]

[4] [0]

[0] [1]

[0] [0]

[0] [1]

[0] [2]

[0] [3]

[0] [4]

[2] [3] [4]

[2] [3] [4]

[3] [4] [0]

[4] [0] [1]

[0] [1] [2]

[1] [2] [3]

[2] [3] [4]

[0] [0] [0]

[2] [3] [4]

[4] [1] [3]

[1] [4] [2]

[3] [2] [1]

Nyní snadno ověříme, že v Z 5 je možné provádět „stejné“ výpočty jako v Q, resp. R, neboť lze „dělit“ pomocí násobení inverzním prvkem

11  1, 21  3, 31  2, 41  4 ,

navíc platí Například, pokud máme následovně: Odtud

3  2  x  4  3  1,

lze postupovat

… využíváme 21  3

x  4  3 .

Dále tedy

a b  0   a  0  b  0 . určit zbytkovou třídu x  takovou, aby 2  x   4  1 ,

x  2 .

x  4  4  3  4 , 30

… využíváme 41  4

Algebraická struktura Z 6 obsahuje následujících šest zbytkových tříd:

0  ,  12,  6, 0, 6,12,  6k k  Z  … čísla dělitelná šesti, tj. dávající zbytek 0, 1  ,  11,  5,1, 7,13,  6k  1 k  Z  … čísla dávající při dělení šesti zbytek 1, 2  ,  10,  4, 2, 8,14,  6k  2 k  Z  … čísla dávající při dělení šesti zbytek 2, 3  ,  9,  3, 3, 9,15,  6k  3 k  Z  … čísla dávající při dělení šesti zbytek 3, 4  ,  8,  2, 4,10,16,  6k  4 k  Z  … čísla dávající při dělení šesti zbytek 4, 5  ,  7,  1, 5,11,17,  6k  5 k  Z  … čísla dávající při dělení šesti zbytek 5,

kde operace sčítání a násobení jsou definovány následujícími tabulkami: +

[0]

[1]

[2]

[3]

[4]

[5]

·

[0]

[1]

[2]

[3]

[4]

[5]

[0] [1] [2] [3] [4]

[0] [1] [2] [3] [4]

[1] [2] [3] [4] [5]

[2] [3] [4] [5] [0]

[3] [4] [5] [0] [1]

[4] [5] [0] [1] [2]

[5] [0] [1] [2] [3]

[0] [1] [2] [3] [4]

[0] [0] [0] [0] [0]

[0] [1] [2] [3] [4]

[0] [2] [4] [0] [2]

[0] [3] [0] [3] [0]

[0] [4] [2] [0] [4]

[0] [5] [4] [3] [2]

[5]

[5]

[0]

[1]

[2]

[3]

[4]

[5]

[0]

[5]

[4]

[3]

[2]

[1]

V Z 6 neexistuje 21 , 31 , 41 a navíc může platit a   b  0 přesto, že a   0 i b   0 (např.

2  3  3  4  0 ).

Odtud již motivace pro následující definici úplné a redukované soustavy zbytků. Definice 1.6.2 – úplná a redukované soustava zbytků  Úplnou soustavou zbytků modulo m nazveme každou množinu obsahující m modulo m nekongruentních celých čísel.  Redukovanou soustavou zbytků modulo m nazveme takovou podmnožinu úplné soustavy zbytků modulo m, která obsahuje právě všechny zbytky nesoudělné s modulem m. Poznámka 1.6.2  Z definice Eulerovy funkce vyplývá, že počet prvků redukované soustavy zbytků modulo m je roven m  . 

Pro daný modul m  2 existuje nekonečně mnoho úplných (i redukovaných) soustav zbytků, neboť každá zbytková třída je v úplné soustavě zastoupena libovolným svým prvkem (tzv. reprezentant zbytkové třídy). Nejpoužívanější je však úplná soustava nejmenších nezáporných zbytků modulo m, tj.: 0,1, , m  1, resp. úplná soustava absolutně nejmenších zbytků modulo m tj.: m  1 1  m , ,1, 0,1, ,   pro m liché, 2   2 m  2 m  m 2  m , ,1, 0,1, ,  pro m sudé.  , ,1, 0,1, ,  , resp.  2  2  2  2

31

Příklad 1.6.4 Příklady úplných a redukovaných soustav zbytků modulo 5: 0, 1, 2, 3, 4 … úplná soustava nejmenších nezáporných zbytků modulo 5,

 2,  1, 0, 1, 2 … úplná soustava absolutně nejmenších zbytků modulo 5, 7, 8, 9, 10, 11   21,20,19,18,17 … další příklady úplných soustav zbytků modulo 5.  4, 10, 16, 22, 28   51,  23,  10,16, 38  Jelikož 5  4 , má každá redukovaná soustava zbytků modulo 5 právě 4 prvky. 1, 2, 3, 4   2,  1, 1, 2  … příklady redukovaných soustav zbytků modulo 5. 4, 16, 22, 28   51,  23, 16, 38 Příklady úplných a redukovaných soustav zbytků modulo 6: 0, 1, 2, 3, 4, 5 … úplná soustava nejmenších nezáporných zbytků modulo 6,

 3,  2,  1, 0, 1, 2 … úplné soustava absolutně nejmenších zbytků modulo 6,  2,  1, 0, 1, 2, 3  11, 12,13,14,15,16    10,9,8,7,6,5   … další příklady úplných soustav zbytků modulo 6. 7, 14, 21, 28, 35, 42   73,  62,  28,  12,19, 45 Jelikož 6  2 , má každá redukovaná soustava zbytků modulo 6 právě 2 prvky. 1, 5   1, 1  … příklady redukovaných soustav zbytků modulo 6. 11, 13  19,  73 Věta 1.6.4 Nechť a, b, m  Z , kde m  2, NSD a, m   1 . Potom platí: a) Je-li x1 , , x m  úplná soustava zbytků modulo m, potom a  x1  b,, a  xm  b tvoří také úplnou soustavu zbytků modulo m. b) Je-li x1 ,, xm   redukovaná soustava zbytků modulo m, potom a  x1 ,, a  xm   tvoří také redukovanou soustavu zbytků modulo m. Věta 1.6.5 - Eulerova věta Pro libovolné a, m  Z , m  2 , kde NSD a, m   1 platí a m   1 mod m .

Jako snadný důsledek Eulerovy věty dostáváme následující tzv. malou Fermatovu větu. 32

(1.41)

Věta 1.6.6 – Malá Fermatova věta Je-li p prvočíslo, a přirozené číslo takové, že p | a , potom platí a p 1  1 mod p  . Jako cvičení zdůvodněte, že pro libovolné prvočíslo p a libovolné přirozené číslo a platí

(1.42)

a p  a mod p  .

Příklad 1.6.5 Určete zbytek při dělení čísla 32882 číslem 97. Řešení. Pro hledaný zbytek, který označíme x 0 , platí

x0  32882 mod 97  .

Z Eulerovy věty  NSD 3, 97   1, 97   96  víme, že

396  1 mod 97 

a jelikož 2882  30  96  2 dává číslo 32882 při dělení 97 stejný zbytek jako 3 2 . Odtud hledaný zbytek x0  9 . Poznámka 1.6.3 Staří čínští matematici se chybně domnívali, že číslo p je prvočíslo právě tehdy, jestliže platí 2 p 1  1 mod p  .

()

Z malé Fermatovy věty vyplývá, že pro všechna prvočísla větší než dvě vztah () skutečně platí a jelikož jim nebylo známé žádné složené číslo, které by mělo stejnou vlastnost, učinili již zmíněný chybný závěr (ostatně obdobného omylu se dopustil i Fermat v případě tzv. Fermatových čísel). V dnešní době výpočetní techniky lze snadno zjistit, že nejmenší složené číslo pro které platí () je

341  11  31 , tj. 2 340  1 mod 341 . Lze dokonce ukázat, že takových složených čísel (nazývaných pseudoprvočísla) existuje nekonečně mnoho. Na druhé straně lze ukázat, že jejich výskyt je v porovnání s prvočísly řídký, tzn. je relativně velká pravděpodobnost, že číslo s vlastností () bude opravdu prvočíslo. Této skutečnosti využívají tzv. pravděpodobnostní testy prvočíselnosti a číslo, které tímto testem úspěšně projde je s vysokou pravděpodobností (tj. nikoliv nutně) prvočíslo.

1.7

Řešení kongruencí 1. stupně a jejich soustav

V tomto odstavci se budeme zabývat úlohou, která má v oblasti diskrétní matematiky široké využití, totiž řešením kongruencí. Pro tyto účely budeme pod pojmem kongruence rozumět výraz f  x   0 mod m  , (1.43) kde

m  Z , m  2 je modul a

f x   an x n    a1 x  a0 je nenulový polynom s celočíselnými koeficienty, pro který

m | a n (číslo n nazýváme stupněm kongruence).

Hlavním cílem bude nalézt všechna celá čísla, pro která platí (1.43). V tomto kontextu je důležité si uvědomit (dokažte!), že platí (1.44) f x0   0 mod m   t  Z f x0  m  t   0 mod m 33

a tedy pokud kongruenci (1.43) vyhovuje jisté číslo x 0 , vyhovují jí také všechna celá čísla, která jsou s x 0 kongruentní modulo m, tj. x  x0 mod m  . Z těchto důvodů je rozumné (a dále tak činíme), považovat za jedno řešení celou zbytkovou třídu

x0   x0  m  t

t  Z . Zřejmým

důsledkem pak je skutečnost, že kongruence (1.43) má nejvýše m řešení (řádně zdůvodněte!), která lze nalézt metodou „hrubé síly“, tj. postupným dosazováním čísel 0,1,, m  1. Na druhé straně je celá řada relevantních důvodů, pro které je vhodné nalézt efektivnější způsoby řešení (1.43). Vzhledem k rozsahu skript se dále omezíme na metody řešení kongruencí 1. stupně, tj. a  x  b mod m  (1.45) a jejich speciálních soustav. Věta 1.7.1 Nechť NSD m, a   1, m  2 . Potom kongruence (1.45) má pro libovolné b  Z právě jedno řešení. Toto řešení je tvaru

x   1  Pn 1  b mod m  , n

(1.46)

kde Pn 1 je čitatel předposledního přibližného zlomku rozvoje

m v řetězový zlomek. a

Příklad 1.7.1 Nalezněte řešení kongruence 269 x  11 mod 379  . Řešení. Jelikož NSD m, a   NSD 379, 269   1 , má uvedená kongruence právě jedno řešení, které určíme ze vztahu (1.46). Aplikací Eukleidova algoritmu dostáváme (hodnoty q i jsou neúplné podíly v Eukleidově algoritmu a Pi počítáme rekurentně dle vztahu (1.30)). i qi Pi

-1 --1

0 1 1

1 2 3

2 2 7

3 4 31

4 12 379

Odtud n  4, Pn1  P3  31, b  11 a hledané řešení je x  341 mod 379  . Jak vyplyne z následující poznámky, má věta 1.7.1 základní význam i pro řešení obecných kongruencí 1. stupně, kde NSD m, a   1 . Poznámka 1.7.1 – řešení obecných kongruencí 1. stupně Uvažujme nyní obecnou kongruenci (1.45) a označme d  NSD m, a  . V situaci, kdy d  1 postupujeme dle věty (1.71), proto předpokládejme, že d  2 . V tomto případě platí: a) Jestliže d | b , potom kongruence (1.45) nemá řešení (řádně zdůvodněte!). b) Jestliže d | b , potom kongruence (1.45) má právě d následujících řešení x  x0 ; x0  m1 ; ; x0  d  1  m1

mod m ,

kde x 0 je jediné řešení kongruence a1  x  b1 mod m1  , a1  34

a b m , b1  , m1  . d d d

(1.47)

(Zdůvodněte! Využijte pravidlo, že obě strany kongruence i modul lze vydělit jejich společným dělitelem, čímž dostaneme kongruenci a1  x  b1 mod m1  , kde NSD m1 , a1   1 . Dle věty 1.7.1 má tato kongruence řešení x  x0 mod m1  , které vyjádříme pomocí zbytků modulo m.) Příklad 1.7.2 Nalezněte všechna řešení kongruence: a) 210 x  57 mod 385  , b) 116 x  60 mod 148  . Řešení. ad a) Pomocí Eukleidova algoritmu zjistíme, že NSD m, a   NSD 385, 210   35 . Jelikož 35 | 57 , nemá dle poznámky 1.7.1 část a) uvedená kongruence řešení.

ad b) Aplikací Eukleidova algoritmu zjistíme, že NSD m, a   NSD 148,116   4 a jelikož 4 | 60 , má dle poznámky 1.7.1 část b) uvedená kongruence právě čtyři řešení tvaru (1.47).

Nyní převedeme řešení původní kongruence na řešení ekvivalentní kongruence, kterou dostaneme vydělením obou stran i modulu čtyřmi. Dostáváme tak 29 x  15 mod 37  , () kde NSD 37, 29   1 a kterou řešíme dle věty 1.7.1. i qi Pi

-1 --1

0 1 1

1 3 4

2 1 5

3 1 9

4 1 14

5 2 37

Jako řešení kongruence () tak dostáváme x0  12 mod 37  a konečně ze vztahu (1.47) pak dostáváme hledaná čtyři řešení původní kongruence x  12; 49; 86; 123 mod 148  . Na závěr tohoto odstavce se ještě zmíníme o řešení soustavy kongruencí x  b1 mod m1 , , x  bn mod mn  , kde NSDmi , m j   1 pro všechna i  j .

(1.48)

Tyto soustavy nachází využití například při provádění rychlých výpočtů s velkými čísly (viz následující poznámka 1.7.2) nebo při jednom z nejbezpečnějších způsobů šifrování tzv. RSA metodě (viz poznámka 1.7.3). Věta 1.7.2 Soustava (1.48) má pro libovolné hodnoty b1 ,, bn jediné řešení. Toto řešení je tvaru x  x0

kde

mod M  ,

x0  M 1  x1  b1    M n  xn  bn

(1.49) M  m1    mn , Mi 

M , i  1, , n a mi

x i je (libovolné) číslo vyhovující kongruenci M i  xi  1 mod mi  .

35

Příklad 1.7.3 Nalezněte řešení soustavy x  2 mod 5, x  3 mod 8, x  6 mod 11, x  4 mod 9  . Řešení. Dle věty

1.7.2

vypočteme

M  3960, M 1  792, M 2  495, M 3  360, M 4  440 .

xi , i  1,,4 určíme z následujících kongruencí 792 x1  1 mod 5 , tedy x1  3 ,

Čísla

495 x 2  1 mod 8 , tedy x 2  7 , 440 x 4  1 mod 9  , tedy x 4  8 .

360 x3  1 mod 11 , tedy x3  7 ,

Ze vztahu (1.49) dostáváme x0  792  3  2  495  7  3  360  7  6  440  8  4  44 348 a odtud hledané řešení (v soustavě nejmenších nezáporných zbytků) x  787 mod 3 960  .

Poznámka 1.7.2 – aritmetika velkých čísel Procesory jsou schopny provádět „rychlé“ aritmetické operace s čísly, které lze uložit do paměti určité velikosti (např. 64 bitů). Výpočty s velkými čísly se proto realizují pomocí tzv. modulární aritmetiky, která je založena na větě 1.7.2. Z této věty vyplývá, že pokud máme dány moduly k

m1 ,, mn (po dvou nesoudělné, pochopitelně nejčastěji tvaru 2 i  1 ), lze každé číslo a z množiny

0,1, , M  1,

kde M  m1    mn , jednoznačně reprezentovat n-ticí

a1 ,, an  ,

kde a i je

nejmenší nezáporný zbytek modulo mi , tj. ai  0,1,, mi  1. Tuto n-tici nazýváme modulární

reprezentací čísla a. Nyní lze provádět výpočty v modulární reprezentaci a to po složkách (vzhledem k jejich velikosti velmi rychle) následovně: Označme a1 , , a n  modulární reprezentaci čísla a, b1 , , bn  modulární reprezentaci čísla b, potom modulární reprezentace a  b je rovna a1  b1  mod m1 ,, an  bn  mod mn  a modulární reprezentace a  b je rovna a1  b1 mod m1 ,, an  bn mod mn  . Na závěr poznamenejme, že převody mezi „standardní“ a modulární reprezentací se provádí pouze na začátku a konci výpočtu, navíc tyto převody jsou vzhledem k obvyklé volbě modulů rychlé. Příklad 1.7.4 Pomocí modulární aritmetiky využívající moduly m1  211  1  2 047, m2  213  1  8 191 a m3  215  1  32 767 , vypočtěte

3b  2d c  a  ,

kde

a  454 545, b  313 131, c  888 888,

d  171 717 .

Řešení. Nejprve nalezneme odpovídající modulární reprezentace čísel, s kterými budeme provádět výpočty. Dostáváme a  a mod m1 , a mod m2 , a mod m3   111, 4040, 28574  , b  b mod m1 , b mod m2 , b mod m3   1987 , 1873, 18228  ,

c  c mod m1 , c mod m2 , c mod m3   624, 2350, 26845  ,

d  d mod m1 , d mod m2 , d mod m3   1816, 7897 , 7882  .

Nyní snadno provedeme po složkách příslušné modulární výpočty. 36

První složka: Druhá složka:

3  1987  2  1816   624  111  1376 mod 2047  . 3  1873  2  7897   2350  4040   2841 mod 8191 . 3  18228  2  7882   26845  28574   10738 mod 32767  .

Třetí složka: Jako modulární reprezentaci výsledku tak dostáváme 3b  2d c  a   1376, 2841, 10738  .

Posledním krokem je převedení výsledku z jeho modulární reprezentace do „standardní“. Tu nalezneme jako řešení soustavy x  1376 mod 2047 , x  2841 mod 8191, x  10738 mod 32767  . Aplikací věty 1.7.2 tak dostáváme výsledek 3b  2d c  a   252 830 838 078 . ¶ Poznámka 1.7.3 (metoda RSA - šifrování s veřejným klíčem) Metoda RSA (Rivest, Shamir, Adleman – jména autorů metody) je moderní a velmi bezpečný způsob šifrování, který je vyvíjen od poloviny sedmdesátých let 20. století. Na rozdíl od klasického šifrování, kde odesilatel i příjemce je schopen zprávy jak šifrovat, tak i dešifrovat, je v případě RSA metody situace zásadně odlišná. Každý zájemce má k dispozici tzv. veřejný klíč, tj. dvojici čísel n, e  , která mu umožňuje zprávy jednoduše šifrovat, nikoliv však dešifrovat. K dešifrování je totiž potřeba znát kanonický rozklad čísla n, které je záměrně konstruováno jako součin dvou velkých prvočísel majících obvykle stovky dekadických míst. Velmi vysoká bezpečnost tohoto způsobu šifrování je pak založena na skutečnosti, že doposud není znám žádný dostatečně efektivní algoritmus umožňující nalézt kanonický rozklad extrémně velkých čísel (viz poznámka 1.3.3 týkající se Fermatových a Mersennových prvočísel) a prakticky jediná možnost jak rozklad čísla n nalézt, je postupně testovat jeho dělitelnost přirozenými čísly 

 n . Snadno se přesvědčíme (číslo

n mívá kolem 400 dekadických míst), že tento postup je mimo možnosti jakékoliv současné výpočetní techniky. Nyní podrobněji k RSA metodě. 

RSA šifrování. Pro šifrování máme k dispozici již zmíněný veřejný klíč, tj. dvojici čísel n, e  . Nejprve šifrovanou právu převedeme do podoby čísla B (např. každému znaku přiřadíme jeho pořadí v rámci abecedy), které pak rozdělíme na bloky B1 , , Bl (blok je například tvořen čtyřmi ciframi). Nyní jednotlivé bloky zašifrujeme dle vztahu K i  Bie mod n, i  1,, l .

(1.50)

Původní zprávě pak odpovídá zašifrovaný text skládající se z bloků K1 ,, K l . 

RSA dešifrování. Pro dešifrování máme k dispozici trojici čísel  p, q, e  , kde NSD e,  p  1  q  1  1 , n  p  q a samozřejmě zprávu K1 ,, K l zašifrovanou dle (1.50). K dešifrování použijeme vztah Bi  K id mod n, i  1,, l ,

(1.51)

kde d je nejmenší nezáporný zbytek vyhovující kongruenci d  e  1 mod  p  1  q  1 .

(1.52)

Z podmínky NSD e,  p  1  q  1  1 vyplývá (viz věta 1.7.1), že číslo d existuje a je určeno jednoznačně. Odtud dostáváme 37

 

K id  Bie

d

 Bi1t  p 1q 1 .

(Připomeňme, že 1.52 lze přepsat na de  1  t   p  1  q  1 pro jisté t  Z .) Z malé Fermatovy věty dostáváme (vzhledem k volbě prvočísel p a q) Bip1  1 mod p , Biq1  1 mod q  , tedy



K id  Bi  Bip 1



t  q 1

 Bi mod p  ,



K id  Bi  Biq 1



t  p 1

 Bi mod q  .

Z věty 1.6.3 část d) vyplývá, že K  Bi mod p  q  a tedy uvedený postup skutečně vede d i

k dešifrování. Příklad 1.7.5 Pomocí RSA metody: a) zašifrujte slovo KRALOVKA, použijte veřejný klíč n, e   3337 , 9 , b) dešifrujte slovo 3149

2883 2177 , máte-li klíč  p, q, e   67, 83, 13 .

Řešení. Poznamenejme, že jde pouze o prezentaci principu RSA metody, proto je hodnota veřejného klíče n (tedy i prvočísel p, q) malá. Skutečně používané hodnoty mívají stovky cifer. ad a) Nejprve slovo KRALOVKA převedeme do posloupnosti čísel, které vyjadřují pořadí jednotlivých znaků v rámci (anglické) abecedy. Dostáváme tak 11, 18, 01, 12, 15, 22, 11, 01 . Tato čísla seskupíme do bloků (například po dvou číslech) 1118 0112 1522 1101 a tyto bloky nyní zašifrujeme (vyjádříme v soustavě nejmenších nezáporných zbytků modulo n) dle vztahu (1.50), tj. K i  Bi9 mod 3337  . Dostáváme tak

2550  1118 9 mod 3337  , 2508  0112 9 mod 3337  ,

0816  1522 9 mod 3337  , 2504  11019 mod 3337 .

Slovu KRALOVKA proto odpovídá šifrový text 2550 2508 0816 2504 . ad b) Nejprve z klíče  p, q, e   67, 83, 13 vypočteme dešifrovcí klíč d. Poznamenejme, že čísla p, q zná pouze příjemce zprávy a tedy pouze on je schopen určit dešifrovací klíč (odesilatelé znají veřejný klíč, tj. hodnotu součinu n  p  q a číslo e, což jim umožňuje zprávy šifrovat, nikoliv dešifrovat). V souladu s poznámkou 1.7.3 určíme dešifrovací klíč d jako řešení (nejmenší nezáporný zbytek) nám již dobře známého typu kongruence d  e  1 mod  p  1  q  1 , tj. 13d  1 mod 5412  . Aplikací věty 1.7.1 dostáváme

d  1249 . Nyní provedeme vlastní dešifrování dle vztahu (1.51), tj. Bi  K i1249 mod 5561 . Dostáváme tak 1005  3149 1249 mod 5561 , 1920  28831249 mod 5561 , 0504  2177 1249 mod 5561

a tedy pořadová čísla jednotlivých znaků původní zprávy jsou 10, 05, 19, 20, 05, 04 . Nyní již snadno zjistíme, že nezašifrované slovo bylo JESTED. ¶ 38

Platí (zobecněná čínská věta o zbytku) Soustava kongruencí má řešení právě tehdy, jestliže právě jedno řešení modulo Toto řešení je tvaru

. V tomto případě má daná soustava . ,

kde

jsou přirozená čísla taková, že

,

jsou přirozená čísla taková, že ,

a

Literatura K. H. Rosen: Handbook of Discrete and Combinatorial Mathematics. CRC Press, 2000. K. H. Rosen: Elementary Number Theory and Its Applications. Addison-Wesley, 1999. K. H. Rosen: Discrete Mathematics and Its Applications. McGraw-Hill, 1999. N. R. Scott: Computer Number Systems and Arithmetic. Prentice Hall, 1985. I. M. Vinogradov: Základy theorie čísel. ČSAV, Praha 1953 (překlad z ruštiny).

39

.

Použité značení Logika

   

… logická spojka „a“ (konjunkce), … logická spojka „nebo“ (disjunkce), … implikace (jestliže), … ekvivalence (právě když).

Množiny

N N

… množina přirozených čísel (včetně nuly), … množina kladných přirozených čísel, … množina celých čísel, … množina racionálních čísel,

Z Q R

C a1 ,, an 

a V  a 

… množina reálných čísel, … množina komplexních čísel, … množina skládající se z prvků a1 ,, a n , … množina prvků s vlastností V,

A B A B A B A B P  A

… průnik množin A, B, … sjednocení množin A, B, … rozdíl množin A – B, … kartézský součin množin A, B,

A

… počet prvků (mohutnost, kardinalita) množiny A.

… potenční množina,

Dělitelnost

a| b a | b

… a dělí b (tj. beze zbytku), … a nedělí b,

NSD a, b 

… největší společný dělitel čísel a, b,

NSN a, b 

… nejmenší společný násobek čísel a, b,

a  b  mod m 

… a je kongruentní s b modulo m,

a  b  mod m 

… a není kongruentní s b modulo m,

a  b mod m 

… a je zbytek při dělení b číslem m,

 an an1

… vyjádření čísla v soustavě o základu b.

a0 b

Funkce

f a

… hodnota funkce f v bodě a,

an n0

… číselná posloupnost,

 x 

… horní celá část čísla x,

 x  a 

… dolní celá část čísla x,



… hodnota Eulerovy funkce v bodě a.

40

Tabulka prvočísel (prvních 840) 2 31 73 127 179 233 283 353 419 467 547 607 661 739 811 877 947 1019 1087 1153 1229 1297 1381 1453 1523 1597 1663 1741 1823 1901 1993 2063 2131 2221 2293 2371 2437 2539 2621 2689 2749 2833 2909 3001

3 37 79 131 181 239 293 359 421 479 557 613 673 743 821 881 953 1021 1091 1163 1231 1301 1399 1459 1531 1601 1667 1747 1831 1907 1997 2069 2137 2237 2297 2377 2441 2543 2633 2693 2753 2837 2917 3011

5 41 83 137 191 241 307 367 431 487 563 617 677 751 823 883 967 1031 1093 1171 1237 1303 1409 1471 1543 1607 1669 1753 1847 1913 1999 2081 2141 2239 2309 2381 2447 2549 2647 2699 2767 2843 2927 3019

7 43 89 139 193 251 311 373 433 491 569 619 683 757 827 887 971 1033 1097 1181 1249 1307 1423 1481 1549 1609 1693 1759 1861 1931 2003 2083 2143 2243 2311 2383 2459 2551 2657 2707 2777 2851 2939 3023

11 47 97 149 197 257 313 379 439 499 571 631 691 761 829 907 977 1039 1103 1187 1259 1319 1427 1483 1553 1613 1697 1777 1867 1933 2011 2087 2153 2251 2333 2389 2467 2557 2659 2711 2789 2857 2953 3037

13 53 101 151 199 263 317 383 443 503 577 641 701 769 839 911 983 1049 1109 1193 1277 1321 1429 1487 1559 1619 1699 1783 1871 1949 2017 2089 2161 2267 2339 2393 2473 2579 2663 2713 2791 2861 2957 3041

41

17 59 103 157 211 269 331 389 449 509 587 643 709 773 853 919 991 1051 1117 1201 1279 1327 1433 1489 1567 1621 1709 1787 1873 1951 2027 2099 2179 2269 2341 2399 2477 2591 2671 2719 2797 2879 2963 3049

19 61 107 163 223 271 337 397 457 521 593 647 719 787 857 929 997 1061 1123 1213 1283 1361 1439 1493 1571 1627 1721 1789 1877 1973 2029 2111 2203 2273 2347 2411 2503 2593 2677 2729 2801 2887 2969 3061

23 67 109 167 227 277 347 401 461 523 599 653 727 797 859 937 1009 1063 1129 1217 1289 1367 1447 1499 1579 1637 1723 1801 1879 1979 2039 2113 2207 2281 2351 2417 2521 2609 2683 2731 2803 2897 2971 3067

29 71 113 173 229 281 349 409 463 541 601 659 733 809 863 941 1013 1069 1151 1223 1291 1373 1451 1511 1583 1657 1733 1811 1889 1987 2053 2129 2213 2287 2357 2423 2531 2617 2687 2741 2819 2903 2999 3079

3083 3187 3259 3343 3433 3517 3581 3659 3733 3823 3911 4001 4073 4153 4241 4327 4421 4507 4591 4663 4759 4861 4943 5009 5099 5189 5281 5393 5449 5527 5641 5701 5801 5861 5953 6067 6143 6229 6311 6373

3089 3191 3271 3347 3449 3527 3583 3671 3739 3833 3917 4003 4079 4157 4243 4337 4423 4513 4597 4673 4783 4871 4951 5011 5101 5197 5297 5399 5471 5531 5647 5711 5807 5867 5981 6073 6151 6247 6317 6379

3109 3203 3299 3359 3457 3529 3593 3673 3761 3847 3919 4007 4091 4159 4253 4339 4441 4517 4603 4679 4787 4877 4957 5021 5107 5209 5303 5407 5477 5557 5651 5717 5813 5869 5987 6079 6163 6257 6323 6389

3119 3209 3301 3361 3461 3533 3607 3677 3767 3851 3923 4013 4093 4177 4259 4349 4447 4519 4621 4691 4789 4889 4967 5023 5113 5227 5309 5413 5479 5563 5653 5737 5821 5879 6007 6089 6173 6263 6329 6397

3121 3217 3307 3371 3463 3539 3613 3691 3769 3853 3929 4019 4099 4201 4261 4357 4451 4523 4637 4703 4793 4903 4969 5039 5119 5231 5323 5417 5483 5569 5657 5741 5827 5881 6011 6091 6197 6269 6337 6421

3137 3221 3313 3373 3467 3541 3617 3697 3779 3863 3931 4021 4111 4211 4271 4363 4457 4547 4639 4721 4799 4909 4973 5051 5147 5233 5333 5419 5501 5573 5659 5743 5839 5897 6029 6101 6199 6271 6343 6427

42

3163 3229 3319 3389 3469 3547 3623 3701 3793 3877 3943 4027 4127 4217 4273 4373 4463 4549 4643 4723 4801 4919 4987 5059 5153 5237 5347 5431 5503 5581 5669 5749 5843 5903 6037 6113 6203 6277 6353 6449

3167 3251 3323 3391 3491 3557 3631 3709 3797 3881 3947 4049 4129 4219 4283 4391 4481 4561 4649 4729 4813 4931 4993 5077 5167 5261 5351 5437 5507 5591 5683 5779 5849 5923 6043 6121 6211 6287 6359 6451

3169 3253 3329 3407 3499 3559 3637 3719 3803 3889 3967 4051 4133 4229 4289 4397 4483 4567 4651 4733 4817 4933 4999 5081 5171 5273 5381 5441 5519 5623 5689 5783 5851 5927 6047 6131 6217 6299 6361 6469

3181 3257 3331 3413 3511 3571 3643 3727 3821 3907 3989 4057 4139 4231 4297 4409 4493 4583 4657 4751 4831 4937 5003 5087 5179 5279 5387 5443 5521 5639 5693 5791 5857 5939 6053 6133 6221 6301 6367 6473

Tabulka hodnot Eulerovy funkce 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

1 1 10 12 30 40 32 60 70 54 72 100 72 110 130 92 150 132 108 180 190 132 210 192 120 240 250 168 270 280 192 252 310 212 330 300 216 342 312 252 352 400 272 420

2 1 4 10 16 12 24 30 24 40 44 32 48 60 40 70 72 54 84 72 64 100 104 72 112 110 72 130 128 92 144 150 96 132 164 108 160 180 120 190 168 132 204 210

3 2 12 22 20 42 52 36 72 82 60 102 112 80 108 120 96 162 172 120 192 168 140 222 232 162 220 262 144 282 292 200 312 288 216 294 352 220 372 382 260 360 348 276

4 2 6 8 16 20 18 32 36 24 46 48 36 60 66 48 60 80 56 88 96 64 106 96 72 120 126 80 136 140 84 144 156 108 166 168 116 144 160 128 196 200 132 208

5 4 8 20 24 24 40 48 40 64 72 48 88 100 72 112 120 80 120 144 96 160 168 120 184 168 128 208 200 144 232 240 144 240 264 176 280 288 200 240 312 216 328 320

43

6 2 8 12 12 22 24 20 36 42 32 52 56 36 64 72 48 82 80 60 84 102 72 112 116 80 128 108 88 120 144 96 156 162 96 172 176 120 184 192 120 168 192 140

7 6 16 18 36 46 36 66 60 56 96 106 72 126 136 84 156 166 116 160 196 132 180 226 156 216 256 176 276 240 180 306 316 216 336 346 192 366 336 252 396 360 276 360

8 4 6 12 18 16 28 32 24 40 42 36 58 64 44 72 78 48 88 92 60 96 108 72 96 120 84 132 138 96 148 120 104 160 156 112 178 176 108 192 198 128 180 212

9 6 18 28 24 42 58 44 78 88 60 108 96 84 138 148 104 156 178 108 198 180 144 228 238 164 216 268 180 272 264 204 280 276 224 348 358 240 378 388 216 408 418 240

10 4 8 8 16 20 16 24 32 24 40 40 32 48 48 40 64 64 48 72 80 48 80 88 64 100 96 72 96 112 80 120 128 80 128 120 96 144 144 96 160 160 96 168

43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

430 252 400 460 312 432 490 332 432 520 348 540 504 320 570 492 392 600 552 396 630 640 360 660 600 452 690 700 468 612 672 432 750 760 512 700 672 528 810 820

144 192 224 120 232 240 160 250 256 168 216 270 176 280 240 192 288 252 192 310 312 212 324 330 192 300 344 216 352 342 240 312 368 252 384 352 240 400 336 272

432 442 300 462 420 264 448 502 324 522 480 360 468 562 380 520 592 396 612 528 420 642 652 384 672 682 360 648 660 480 732 742 500 648 772 504 720 720 540 822

180 144 226 224 156 220 216 144 256 260 176 256 276 184 240 288 180 300 306 192 316 264 216 328 336 216 346 320 192 360 366 240 336 380 252 336 396 264 360 408

224 352 288 240 360 384 240 400 408 240 424 432 288 448 440 288 384 440 320 500 504 336 520 432 360 544 552 368 480 560 336 592 600 384 600 624 416 528 648 400

44

216 222 144 232 192 162 240 220 168 262 264 144 276 282 192 292 296 200 240 312 208 288 320 216 312 294 224 352 356 220 352 372 216 382 384 260 396 360 256 348

396 296 456 466 312 486 420 312 460 480 356 546 556 324 576 586 396 606 616 360 504 646 432 616 676 456 640 600 476 726 660 492 756 696 432 786 796 536 756 826

144 192 228 144 238 240 164 252 216 160 268 272 180 280 272 168 264 288 204 312 280 216 276 332 224 336 348 232 358 288 240 320 378 256 388 392 216 400 408 264

438 448 288 396 478 324 498 508 344 506 420 360 504 568 384 540 598 336 618 576 420 580 658 444 576 624 464 708 718 486 738 636 440 768 720 524 736 808 432 828

160 120 176 184 128 168 200 128 192 208 144 200 192 144 224 232 160 240 240 144 256 240 160 264 256 176 240 280 192 288 288 200 288 240 192 312 320 216 320 328

Literatura D. E. Knuth: The Art of Computer Programming. Volume 1: Fundamental Algorithms, K. H. Rosen: Handbook of Discrete and Combinatorial Mathematics. CRC Press, 2000. K. H. Rosen: Elementary Number Theory and Its Applications. Addison-Wesley, 1999. K. H. Rosen: Discrete Mathematics and Its Applications. McGraw-Hill, 1999. N. R. Scott: Computer Number Systems and Arithmetic. Prentice Hall, 1985. I. M. Vinogradov: Základy theorie čísel. ČSAV, Praha 1953 (překlad z ruštiny).

45