Kongruence

Tento článek pojednává o matematickém pojmu ekvivalence na algebraické struktuře. Další významy jsou uvedeny v článku Kongruence (rozcestník).

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 \,\!$ 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 "x-y je násobkem deseti" kongruencí. Grupu je možné chápat jako strukturu s jednou operací nebo se třemi. Obě konvence jsou ekvivalentní, použijme tedy tu první: jedinou operací je sčítání (proto 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 a₁ = 3, a₂ = 5, b₁ = 13, b₂ = 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\,\!$ 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_2(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. relace, která je zavedena vztahem:

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

Jinými slovy: dvě čísla jsou ekvivalentní (modulo n), pokud mají stejný zbytek po dělení číslem $n \,\!$. 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 prostě $a \equiv b \,\!$. Celý zápis se čte „a je kongruentní s b modulo n“.

Vlastnosti kongruence modulo n

• $a \equiv b \and c \equiv d \implies a+c \equiv b+d \,\!$, jinými slovy: relace $\equiv \,\!$ je kongruence vzhledem ke sčítání
• $a \equiv b \and c \equiv d \implies a-c \equiv b-d \,\!$, jinými slovy: relace $\equiv \,\!$ je kongruence vzhledem k odčítání
• $a \equiv b \and 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í - 3,8,13,…, 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 . 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$. 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.) 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$. 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". 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