Kongruence

Kongruence je algebraický pojem označující ekvivalenci na algebře, která je slučitelná se všemi operacemi na této algebře (tedy například, pokud jsou tři páry prvků ekvivalentní a výsledky nějaké operace na těchto párech jsou také ekvivalentní, pak existuje pro tyto páry kongruence).

Formální definice

Předpokládejme, že (X, O_1, O_2, \ldots, O_n) \,\. je algebraická struktura s množinou prvků X \,\. +more a operacemi O_1, O_2, \ldots, O_n \,\. , operace O_i \,\. je m_i \,\. -ární.

Binární relaci R \,\! na X nazveme kongruence, pokud je to ekvivalence a pokud pro každou z vyjmenovaných operací a každé prvky a_1, a_2, \ldots, a_{m_i}, b_1, b_2, \ldots, b_{m_i} \in X platí : a_1 \sim_R b_1, a_2 \sim_R b_2, \ldots, a_{m_i} \sim_R b_{m_i} \implies O_i(a_1,a_2,\ldots,a_{m_i}) \sim_R O_i(b_1,b_2,\ldots,b_{m_i}) \,\!

Příklad

Chceme ověřit, zda na grupě celých čísel je relace "\scriptstyle x-y je násobkem deseti" kongruencí. Grupu je možné chápat jako strukturu s jednou operací nebo se třemi. +more Obě konvence jsou ekvivalentní, použijme tedy tu první: jedinou operací je sčítání (proto \scriptstyle n=1). \scriptstyle O_1(a,b) je jen jiný zápis pro a+b. Tato operace je binární (potřebuje dva "vstupy", takže \scriptstyle m_i = 2).

Zvolíme-li a1 = 3, a2 = 5, b1 = 13, b2 = 45, pak podle definice kongruence musí platit 3+5 ~ 13 + 45, což platí (8 a 58 se liší o násobek deseti).

Tím jsme ověřili jen konkrétní příklad; důkaz platný pro všechny hodnoty a_i a b_i lze provést takto: Pro obě i platí \scriptstyle a_i \sim_R b_i\,\. , čili existují celá čísla \scriptstyle k_1, k_2\,\. +more tak, že \scriptstyle b_i = a_i + 10. k_i. Potom platí: \scriptstyle O_1(a_1,a_2) - O_1(b_1,b_2) = a_1 + a_2 - (a_1 + 10. k_1) - (a_2 + 10. k_2) = -10. (k_1+k_2), což je násobek deseti, takže \scriptstyle O_1(a_1,a_2) \sim_R O_1(b_1,b_2).

Kongruence zbytkových tříd

Nejznámějším příkladem kongruence je rozklad množiny všech celých čísel na zbytkové třídy po dělení číslem n \geq 2 \,\. , tj. +more relace, která je zavedena vztahem:.

: a \equiv b \pmod n \Leftrightarrow n \mid (a-b) \,\!

Jinými slovy: dvě čísla jsou ekvivalentní (modulo n), pokud mají stejný zbytek po dělení číslem n \,\. . +more Pokud je z kontextu jasné, pro které n \,\. je kongruence zapsána (nebo na n \,\. nezáleží, protože zápis je platný pro jeho libovolnou hodnotu), vynechává se konec zápisu a píše se jednoduše a \equiv b \,\. . Celý zápis se čte „a je kongruentní s b modulo n“.

Vlastnosti kongruence modulo n

a \equiv b \land c \equiv d \implies a+c \equiv b+d \,\. , jinými slovy: relace \equiv \,\. +more je kongruence vzhledem ke sčítání * a \equiv b \land c \equiv d \implies a-c \equiv b-d \,\. , jinými slovy: relace \equiv \,\. je kongruence vzhledem k odčítání * a \equiv b \land c \equiv d \implies a*c \equiv b*d \,\. , jinými slovy: relace \equiv \,\. je kongruence vzhledem k násobení.

Je-li navíc n \,\! prvočíslo, pak navíc podle Malé Fermatovy věty: * a^n \equiv a \pmod n \,\!

Význam kongruence modulo n

Vlastnosti kongruence modulo n umožňují počítat pouze se zbytkovými třídami a výsledek pak zobecnit na všechna čísla - v takovýchto výpočtech zastupuje například číslo 3 v modulu 5 všechna čísla s ním kongruentní - 8,13,18,…, ale také -2,-7,… Kongruenci lze při výpočtech týkajících se dělitelnosti do jisté míry používat podobně jako rovnost při úpravách algebraických výrazů nebo při řešení rovnice.

Faktoralgebra

Je-li R kongruence, pak faktormnožině X / R může být dána přirozená struktura takto (výsledek nezávisí na volbě reprezentantů): : \hat{O_i}([x_1]_R, [x_2]_R, \ldots, [x_{m_i}]_R) = [O_i(x_1, x_2, \ldots, x_{m_i})]_R

Faktormnožina s těmito operacemi se nazývá faktoralgebra a její operace se obvykle značí stejně, jako operace původní algebry (v tomto případě tedy O_i \,\!; v článku je však použito označení \hat{O_i} pro zdůraznění, že se nejedná o tutéž operaci).

Toto je nejběžnější způsob, jak formálně definovat okruh modulo n.

Příklad faktoralgebry

Na okruhu celých čísel uvažujme kongruenci "x-y je sudé číslo". Faktormnožina bude mít dva prvky: množina sudých celých čísel a množina lichých celých čísel . +more Na této faktormnožině lze přirozeně zavést operaci \scriptstyle \hat{+}, která se však obvykle značí \scriptstyle +, pokud nehrozí nedorozumění. Chceme zjistit např. výsledek operace "lichá čísla \scriptstyle \hat{+} sudá čísla". Zvolíme tedy nějaké celé číslo \scriptstyle [x_1] tak, aby \scriptstyle [x_1]_R byla množina lichých čísel, tzv. reprezentanta množiny lichých čísel. Zvolme například \scriptstyle x_1 = 11, x_2 = 8 . Pak výše uvedený vzorec říká: \scriptstyle [x_1]_R \hat{+} [x_2]_R = [x_1 + x_2]_R.

Dosazením do pravé strany dostaneme: \scriptstyle [x_1]_R \hat{+} [x_2]_R = [x_1 + x_2]_R = [11 + 8]_R = [19]_R

Takže výsledek operace "lichá čísla \scriptstyle \hat{+} sudá čísla" je množina lichých čísel.

Kdybychom vybrali jiné reprezentanty, např. \scriptstyle x_1 = 41, x_2 = 42, dospěli bychom k výsledku \scriptstyle [83]_R, což je množina totožná s množinou \scriptstyle [19]_R. +more To je ilustrací (nikoli však důkazem), že výsledek je nezávislý na volbě reprezentantů. Kdyby nezávislý nebyl, pak by definice byla nekorektní.

Vztah kongruence a homomorfismů

Binární relace na A je kongruencí právě tehdy, pokud je jádrem nějakého homomorfismu z A do nějaké struktury B.

Pro každý homomorfismus f z A do B platí, že jádro homomorfismu Ker f je kongruence na A. (Pojem jádro homomorfismu je někdy chápán jako podstruktura A, ale zde se držíme obecnější definice, že jde o relaci na A. +more) Proto každý homomorfismus definuje faktoralgebru. Podle první věty o izomorfismu je tato faktoralgebra izomorfní s oborem hodnot f.

Platí i opačný vztah: Každá kongruence R je jádrem nějakého homomorfismu. Příkladem takového homomorfismu je zobrazení f(x): A \to A / R, f(x) = [x]_R . +more V příkladě níže toto zobrazení jakémukoli lichému číslu (např. 3) přiřadí množinu všech lichých čísel a sudému číslu množinu všech sudých čísel. Nejedná se o izomorfismus, neboť zobrazení není prosté .

Příklad: Zobrazení f: Z \to Z, f(n) = (-1)^n přiřadí každému sudému číslu hodnotu 1 a lichému číslu -1. Jádrem tohoto zobrazení je právě výše zmíněná relace "x-y je sudé číslo". +more Faktoralgebra i obor hodnot jsou dvouprvkové množiny. Izomorfismus mezi nimi přiřadí množině všech sudých čísel hodnotu 1 a množině všech lichých čísel -1. Tento izomorfismus není totožný se zobrazením f, neboť jeho argumentem jsou množiny čísel, zatímco argumentem f jsou čísla.

Související články

Dělitelnost * Malá Fermatova věta * Velká Fermatova věta

Kategorie:Algebra Kategorie:Teorie čísel