Zpracoval: hypspave@fel.cvut.cz 8.Dělitelnost celých čísel. Euklidův algoritmus pro nalezení největšího společného dělitele a jeho zobecnění.

Relace modulo n, zbytkové třídy a operace s nimi. Binární operace na množině, pologrupy, monoidy a grupy.

(A7B01MCS)

I. Dělitelnost celých čísel.

Definice. Řekneme, že přirozené číslo a dělí přirozené číslo b (tento fakt značíme a | b), pokud existuje přirozené

číslo n takové, že b = n · a. Řekneme, že celé číslo a dělí celé číslo b, (tento fakt též značíme a | b), pokud existuje

celé číslo n takové, že b = n · a.

Pokud a dělí číslo b (v oboru přirozených čísel nebo celých čísel), pak číslo a nazveme dělitelem čísla b.

Lemma. Množina všech prvočísel P je nekonečná množina.

Definice. Prvočíselným rozkladem přirozeného čísla x rozumíme rovnost

kde r ≥ 1 je přirozené číslo, p1 < p2 < … < pr jsou navzájem různá prvočísla a n1, n2, … , nr jsou kladná

přirozená čísla.

Věta (Základní veta elementární teorie čísel). Pro každé přirozené číslo x ˃ 2 existuje jednoznačný prvočíselný

rozklad.

Definice. Řekneme, že přirozené číslo d je největším společným dělitelem přirozených čísel a, b (značení

d = gcd(a, b)), pokud jsou splněny následující dvě podmínky:

1. Číslo d je společným dělitelem čísel a, b, tj. platí, d | a a současně d | b (v oboru přirozených čísel).

2. Číslo d je největším ze všech společných dělitelů čísel a, b, tj. platí následující: je-li c takové přirozené

číslo, pro které platí c | a a současně c | b, potom c | d.

Pokud gcd(a, b) = 1, řekneme, že přirozená čísla a, b jsou nesoudělná.

Tvrzení (Dělení se zbytkem v oboru celých čísel). Ať a, b jsou libovolná celá čísla, b 6= 0. Pak existují jednoznačné

určená celá čísla q a r taková, že jsou splněny následující dvě podmínky:

1. Platí rovnost a = q · b + r.

2. Číslo r splňuje nerovnost 0 ≤ r < |b|.

Tvrzení (Dělení se zbytkem v oboru celých čísel). Ať a, b jsou libovolná celá čísla, b ≠ 0. Pak existují jednoznačně

určená celá čísla q a r taková, že jsou splněny následující dvě podmínky:

1. Platí rovnost a = q · b + r.

2. Číslo r splňuje nerovnost 0 ≤ r < |b|.

Definice. Jednoznačně určené číslo r z předchozí věty nazveme zbytkem po dělení čísla a číslem b.

II. Euklidův algoritmus pro nalezení největšího společného dělitele a jeho zobecnění.

Příklad. Ukažme příklad běhu Euklidova algoritmu pro a = 427, b = 133.

Proto platí, že gcd(427, 133) = 7.

Důsledkem Euklidova algoritmu je následující tvrzení, které budeme v dalším potřebovat.

Důsledek (Bezoutova rovnost). Ať a a b jsou přirozená čísla. Potom existují celá čísla α, β tak, že platí rovnost

gcd(a, b) = α · a + β · b.

Rozšířený Euklidův algoritmus.

Vstup: přirozená čísla a, b, kde a ≥ b ≥ 0.

Výstup: d = gcd(a, b) a celá čísla α, β , splňující d = α · a + β · b.

1. Je-li b = 0, položte d := a, α := 1, β := 0 a skončete.

2. Položte α2 := 1, α1 := 0, β2 := 0, β1 := 1.

3. Dokud b > 0 dělejte následující:

3.1 Spočtete q a r tak, že a = q · b + r, 0 ≤ r < b.

3.2 Položte α := α2 − q · α1, β := β2 − q · β1.

3.3 Položte a := b, b := r.

3.4 Položte α2 := α1, α1 := α , β2 := β1, β1 := β.

4. Položte d := a, α := α2, β := β2 a skončete.

Rozšířený Euklidův algoritmus na nalezení gcd(427, 133). Naše výpočty uspořádáme do tabulky:

Proto tvrdíme, že gcd(427, 133) = 7 a že Bezoutova rovnost má tvar 7 = 5 · 427 + (−16) · 133.

Příklad. Rozšířený Euklidův alg. Může vypadat také takto:

gcd(54,150) = ?

a = 150, b = 54

150 = 2 · 54 + 42 42 = a – 2b

54 = 42 + 12 12 = b – (a – 2b) = -a + 3b

42 = 3 · 12 + 6 6 = (a – 2b) – 3(-a + 3b) = 4a – 11b

gcd(54,150) = 6 = 4a – 11b

III. Relace modulo m, zbytkové třídy a operace s nimi.

Kongruence modulo m.

Definice. Ať m > 1 je pevné přirozené číslo. Řekneme, že celá čísla a a b jsou kongruentní modulo m,

(značíme a b (mod m)), pokud existuje celé císlo k takové, že a − b = k · m.

Povšimneme si, že vztah a b (mod m) platí práve tehdy, když císla a a b mají stejný zbytek po dělení číslem m.

Tvrzení. Ať m > 1 je pevné přirozené číslo. Potom platí:

1. Kongruence modulo m je reflexivní relace, tj. pro každé celé číslo a platí a a (mod m).

2. Kongruence modulo m je symetrická relace, tj. pro všechna celá čísla a, b platí:

jestliže platí a b (mod m), pak platí b a (mod m).

3. Kongruence modulo m je transitivní relace, tj. pro všechna celá čísla a, b, c platí:

jestliže platí a b (mod m) a současné b c (mod m), pak platí a c (mod m).

4. Kongruence modulo m respektuje operaci sčítání, tj. pro všechna celá císla a, b, a0, b0 platí:

jestliže platí a b (mod m) a současně a0 b0 (mod m), pak platí a + a0 b + b0 (mod m).

5. Kongruence modulo m respektuje operaci násobení, tj. pro všechna celá císla a, b, a0, b0 platí:

jestliže platí a b (mod m) a současně a b‘ (mod m), pak platí a · a‘ b · b‘ (mod m).

Definice. Ať m > 1 je pevné přirozené číslo. Pro libovolné celé číslo c definujeme [c]m jako množinu všech čísel

kongruentních s c modulo m. Přesněji:

[c]m = {a Z | c a (mod m)}.

Množinu [c]m nazýváme třidou kongruence(zbytkovou třídou) čísla c modulo m. Libovolný prvek množiny [c]m

nazveme representantem třídy [c]m.

Označme Zm = {[a]m | a Z}.

Množinu zbytkových tříd značíme ℤm={[a]m|a∈ℤ}, kde [a]m={b|b∈ℤ, b-a mod n = 0}.

Operace + je definována: [a]m+[b]m=[a+b]m.

Operace · je definována: [a]m·[ b]m=[a · b]m.

Příklad:

ℤ2 = {[0]2, [1]2} = {{…, -4, -2, 0, 2, 4, …}, {…, -3, -1, 1, 3, …}}.

ℤ3 = {[0]3, [1]3, [2]3} = {{…, -6, -3, 0, 3, 6, …}, {…, -5, -2, 1, 4, 7, …}, {…, -4, -1, 2, 5, 8, ...}}.

IV. Binární operace na množině, pologrupy, monoidy a grupy.

Definice. Binární operace na množině X je zobrazení ○: X × X −> X. Namísto ○ (x, y) budeme pro hodnotu ○ v (x, y)

používat obvyklý infix zápis x ○ y.

Dvojici ‹X, ○› budeme ríkat grupoid.

Příklady:

Na prázdné množině X = existuje jediná binární operace, totiž prázdné zobrazení : × −> . Proto ‹ , › je

příklad grupoidu.

Na množině X = {a, b, c} definujeme binární operaci ○ takto: x ○ y = x pro všechna x, y X. Protože X je konečná

množina, můžeme operaci ○ popsat následující tabulkou:

Je-li x v i-tém řádku a y v j-tém sloupci tabulky, pak v položce (i, j) je zapsán výsledek x ○ y. Dvojice ‹X, ○› je grupoid.

Definice. Ať ○ je binární operace na množině X.

1. Operace ○ je asociativní, pokud pro všechna x, y, z ∈ X platí rovnost x ○ (y ○ z) = (x ○ y) ○ z.

2. Operace ○ je komutativní, pokud pro všechna x, y ∈ X platí rovnost x ○ y = y ○ x.

3. Prvek el je levý neutrální prvek operace ○, pokud pro všechna x∈ X platí rovnost el ○ x = x.

4. Prvek er je pravý neutrální prvek operace ○, pokud pro všechna x ∈ X platí rovnost x ○ er = x.

5. Prvek e je neutrální prvek operace ○, pokud je pravým i levým neutrálním prvkem, tj. když pro všechna

x ∈ X platí rovnost e ○ x = x ○ e = x.

Definice. Ať ‹X, ○› je grupoid.

1. ‹X, ○› je pologrupa, je-li ○ asociativní operace.

2. Pologrupa ‹X, ○› říkáme monoid, jestliže operace ○ má neutrální prvek.

3. Monoidu ‹X, ○› s neutrálním prvkem e říkáme grupa, jestliže má každý prvek x inversi vzhledem k ○, tj.

jestliže platí: Pro každé x existuje právě jedno x−1 takové, že platí x−1 ○ x = e = x ○ x−1.

Samozřejmě, každá grupa je monoid, každý monoid je pologrupa a každá pologrupa je grupoid. Po dané struktuře

totiž požadujeme postupně víc a víc. Žádnou z těchto implikací však nelze obrátit.

Poznámka: ‹X, ○› nazýváme komutativní grupou, pokud operace ○ je navíc komutativní.

Príklad. Množina R s operací sčítání tvoří grupu. Skutečně platí asociativní zákon pro sčítání reálných čísel:

(x + y) + z = x + (y + z), dále existuje neutrální prvek 0, pro který 0 + x = x + 0 = 0 a konečně pro každé x ∈ R existuje

y = −x tak, že x+y = y+x = 0. Navíc se jedná o grupu komutativní, protože sčítání reálných čísel je komutativní.