Kongruence, rozklad na zbytkové třídy Věta: Nechť a, b jsou celá čísla taková, že b ¹ 0. Potom existují celá čísla q, r splňující vztah: a = bq + r, 0 £ r < çb ç , přičemž toto vyjádření je jednoznačné. Poznámka: V předchozí větě a je dělenec, b je dělitel, q je neúplný podíl a r je zbytek. Je nutno si uvědomit, že zbytek r při dělení je vždy nezáporný, a to i v případě dělení záporným číslem. Např. a = - 26, b = - 8, q = 4, r = 6, protože - 26 = (- 8).4 + 6. Definice: Nechť a, bÎ C, mÎ N, m ³ 2. Pak řekneme, že číslo a je kongruentní s číslem b podle modulu m (píšeme a º b (mod m)), práve když obě čísla a, b dávají při dělení modulem m stejný zbytek. Příklad: 9 º 23 (mod 7), 19 º 51 (mod 8), - 26 º 22 (mod 8), ale 11 ≢ 19 (mod 5). Věta: Relace kongruence je pro libovolný modul m relací ekvivalence na množině C (je reflexivní, symetrická a tranzitivní). Definice: Nechť m je pevné přirozené číslo větší než jedna. Označme C[i][ ]= { x Î C; x dává po dělení číslem m zbytek i } , pro i = 0, 1, …, m - 1. Pak množina C[i] se nazývá zbytková třída podle modulu m. Symbolem C[m] pak označíme množinu všech zbytkových tříd podle modulu m , tj. C[m] = {C[0] , C[1] , …, C[m][-][1]} . Poznámka: Protože při dělení číslem m jsou možné zbytky 0, 1, …, m - 1, je počet zbytkových tříd podle modulu m roven číslu m . Každá zbytková třída podle modulu m obsahuje nekonečně mnoho celých čísel, která dávají při dělení modulem m týž zbytek (tzn. liší se o nějaký celočíselný násobek modulu m). Příklad: a) m = 4 C[0] = {… ,-8, -4, 0, 4, 8, … } C[1] = {… ,-7, -3, 1, 5, 9, … } C[2] = {… ,-6, -2, 2, 6, 10, …} C[3] = {… ,-5, -1, 3, 7, 11, …} b) m = 5 C[0] = {…,-10, -5, 0, 5, 10, …} C[1] = {… ,-9, -4, 1, 6, 11, … } C[2] = {… ,-8, -3, 2, 7, 12, …} C[3] = {… ,-7, -2, 3, 8, 13, …} C[4] = {… ,-6, -1, 4, 9, 14, …} Věta: Nechť m je pevné přirozené číslo větší než jedna. Pak množina C[m ]všech zbytkových tříd podle modulu m tvoří rozklad množiny C všech celých čísel. Poznámka: Nyní se budeme zabývat binárními operacemi sčítání a násobení definovanými na množině C[m ] pro různé moduly m. Obě operace na systému všech zbytkových tříd budeme chápat následujícím způsobem: Nechť např. m = 5. Zápis součtu C[3] + C[4] = C[2] znamená, že sečtením libovolného celého čísla dávajícího při dělení pěti zbytek 3 s libovolným celým číslem dávajícím při dělení pěti zbytek 4 dostaneme vždy celé číslo, které při dělené pěti dává zbytek 2. Analogicky zápis spoje násobení C[2] . C[4] = C[3] znamená, že vynásobením libovolného celého čísla dávajícího při dělení pěti zbytek 2 s libovolným celým číslem dávajícím při dělení pěti zbytek 4 dostaneme vždy celé číslo, které při dělené pěti dává zbytek 3. Populárně řečeno, výsledek sčítání či násobení zbytkových tříd podle modulu m získáme tak, že sečteme nebo vynásobíme indexy zbytkových tříd ze zadání úlohy, zjistíme zbytek součtu či součinu při dělení číslem m a tento zbytek je indexem zbytkové třídy hledaného součtu nebo součinu. Příklady: a) m = 4 : C[1] + C[3] = C[0], C[2] + C[3] = C[1], C[2] . C[3] = C[2], C[2] . C[2] = C[0.] a) m = 3 : C[1] + C[2] = C[0], C[2] + C[2] = C[1], C[2] . C[2] = C[1], C[0] . C[2] = C[0.] Poznámka: V následujících tvrzeních uvedeme typy algebraických struktur definovaných na množinách zbytkových tříd. Tvrzení nebudeme dokazovat, vždy uvedeme jen ilustraci dané struktury pomocí tabulky. Kvůli zjednodušení zápisů rovněž budeme místo C[m] uvádět pouze index m (zřejmě nebude moci dojít k nedorozumění). V předchozím příkladu a) tedy např. 1 + 3 = 0, 2 + 3 = 1, 2 . 3 = 2, 2 . 2 = 0. Věta: Nechť m je pevné přirozené číslo větší než jedna. Pak algebraická struktura (C[m] , +) je komutativní grupa s neutrálním prvkem C[0 ]. Ilustrace (C[4] , +): + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 Věta: Nechť m je pevné přirozené číslo větší než jedna. Pak algebraická struktura (C[m] , . ) je komutativní pologrupa s neutrálním prvkem C[1 ]a agresivním prvkem C[0]. Ilustrace (C[4] , .): . 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 Ilustrace (C[5] , .): . 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 Poznámka: Prohlédneme-li si pozorně obě tabulky v ilustraci předchozí věty, vidíme, že při operaci násobení zřejmě podstatně závisí na modulu. Odstraníme-li z obou těchto tabule první řádek a první sloupec, odpovídající třídě C[0], dostáváme následující tabulky struktur (C[4 ]- {C[0]} , .) a (C[5 ]- {C[0]} , .): Ilustrace (C[4 ]- {C[0]} , .): . 1 2 3 1 1 2 3 2 2 0 2 3 3 2 1 Ilustrace (C[5 ]- {C[0]} , .): . 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 Struktura (C[4 ]- {C[0]} , .) nyní již není ani grupoid, neboť obsahuje v tabulce prvek 0 , který již nepatří do nosné množiny (není v záhlaví tabulky). Oproti tomu, algebraická struktura (C[5 ]- {C[0]} , .) se ještě „zlepšila, nyní jde již o komutativní grupu. Který případ nastane, závisí na modulu. Věta: Nechť modul m je prvočíslo. Pak algebraická struktura (C[m ]- {C[0]} , .) je komutativní grupa. Je-li modul m číslo složené, pak (C[m ]- {C[0]} , .) není ani grupoidem. Důsledek: Nechť modul m je prvočíslo. Pak algebraická struktura se dvěma operacemi (C[m ]- {C[0]} ,+, .) je komutativní těleso. Poznámka: Podle předchozího tvrzení není (C[m ]- {C[0]} , .) pro složený modul ani grupoidem. Protože je však potřeba popsat i struktury zbytkových tříd se dvěma operacemi pro složený modul m, musíme nějak „popsat“ situaci nul vyskytujících se v tabulkách (např. (C[4 ]- {C[0]} , .)). Definice: Nechť modul m je složené číslo, nechť pro dvě zbytkové třídy C[u][ ], C[v] podle modulu m platí C[u][ ]¹ C[0 ], C[v][ ]¹ C[0 ]. Jestliže C[u][ ]. C[v] = C[0], pak obě třídy C[u][ ], C[v][ ]se nazývají vlastní dělitelé nulového prvku C[0] . Poznámka: Definice vlastních dělitelů nulového prvku (stručně jen dělitelů nuly) je samozřejmě obecnější. Struktury zbytkových tříd však poskytují užitečnou ilustraci tohoto pojmu. Současně ve shodě s obecnou teorií algebraických struktur se dvěma operacemi umožňuje existence dělitelů nuly popsat i struktury (C[m ]- {C[0]} ,+, .) pro složený modul m. Věta: Nechť modul m je složené číslo. Pak algebraická struktura se dvěma operacemi (C[m ],+, .) je komutativní okruh, který nikdy není oborem integrity (obsahuje dělitele nuly). Příklad: V okruhu (C[4 ],+, .) je dělitelem nuly C[2] ; v okruhu (C[6 ],+, .) jsou dělitelé nuly C[2][, ]C[3] ; v okruhu (C[8 ],+, .) jsou dělitelé nuly C[2][, ]C[4], C[6 ].