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 ${\displaystyle (X,O_{1},O_{2},\ldots ,O_{n})\,\!}$ je algebraická struktura s množinou prvků ${\displaystyle X\,\!}$ a operacemi ${\displaystyle O_{1},O_{2},\ldots ,O_{n}\,\!}$, operace ${\displaystyle O_{i}\,\!}$ je ${\displaystyle m_{i}\,\!}$-ární.

Binární relaci ${\displaystyle R\,\!}$ na X nazveme kongruence, pokud je to ekvivalence a pokud pro každou z vyjmenovaných operací a každé prvky ${\displaystyle a_{1},a_{2},\ldots ,a_{m_{i}},b_{1},b_{2},\ldots ,b_{m_{i}}\in X}$ platí

${\displaystyle 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 "${\textstyle \scriptstyle 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 ${\displaystyle \scriptstyle n=1}$). ${\displaystyle \scriptstyle O_{1}(a,b)}$ je jen jiný zápis pro a+b. Tato operace je binární (potřebuje dva "vstupy", takže ${\displaystyle \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 ${\displaystyle a_{i}}$ a ${\displaystyle b_{i}}$ lze provést takto: Pro obě i platí ${\displaystyle \scriptstyle a_{i}\sim _{R}b_{i}\,\!}$, čili existují celá čísla ${\displaystyle \scriptstyle k_{1},k_{2}\,\!}$ tak, že ${\displaystyle \scriptstyle b_{i}=a_{i}+10.k_{i}}$. Potom platí: ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle n\geq 2\,\!}$, tj. relace, která je zavedena vztahem:

${\displaystyle 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 ${\displaystyle n\,\!}$. Pokud je z kontextu jasné, pro které ${\displaystyle n\,\!}$ je kongruence zapsána (nebo na ${\displaystyle 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 ${\displaystyle a\equiv b\,\!}$. Celý zápis se čte „a je kongruentní s b modulo n“.

Vlastnosti kongruence modulo n

• ${\displaystyle a\equiv b\land c\equiv d\implies a+c\equiv b+d\,\!}$, jinými slovy: relace ${\displaystyle \equiv \,\!}$ je kongruence vzhledem ke sčítání
• ${\displaystyle a\equiv b\land c\equiv d\implies a-c\equiv b-d\,\!}$, jinými slovy: relace ${\displaystyle \equiv \,\!}$ je kongruence vzhledem k odčítání
• ${\displaystyle a\equiv b\land c\equiv d\implies a*c\equiv b*d\,\!}$, jinými slovy: relace ${\displaystyle \equiv \,\!}$ je kongruence vzhledem k násobení

Je-li navíc ${\displaystyle n\,\!}$ prvočíslo, pak navíc podle Malé Fermatovy věty:

• ${\displaystyle 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ě ${\displaystyle X/R}$ může být dána přirozená struktura takto (výsledek nezávisí na volbě reprezentantů):

${\displaystyle {\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 ${\displaystyle O_{i}\,\!}$; v článku je však použito označení ${\displaystyle {\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 ${\displaystyle \scriptstyle {\hat {+}}}$, která se však obvykle značí ${\displaystyle \scriptstyle +}$, pokud nehrozí nedorozumění. Chceme zjistit např. výsledek operace "lichá čísla ${\displaystyle \scriptstyle {\hat {+}}}$ sudá čísla". Zvolíme tedy nějaké celé číslo ${\displaystyle \scriptstyle [x_{1}]}$ tak, aby ${\displaystyle \scriptstyle [x_{1}]_{R}}$ byla množina lichých čísel, tzv. reprezentanta množiny lichých čísel. Zvolme například ${\displaystyle \scriptstyle x_{1}=11,x_{2}=8}$ . Pak výše uvedený vzorec říká: ${\displaystyle \scriptstyle [x_{1}]_{R}{\hat {+}}[x_{2}]_{R}=[x_{1}+x_{2}]_{R}}$

Dosazením do pravé strany dostaneme: ${\displaystyle \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 ${\displaystyle \scriptstyle {\hat {+}}}$ sudá čísla" je množina lichých čísel.

Kdybychom vybrali jiné reprezentanty, např. ${\displaystyle \scriptstyle x_{1}=41,x_{2}=42}$, dospěli bychom k výsledku ${\displaystyle \scriptstyle [83]_{R}}$, což je množina totožná s množinou ${\displaystyle \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í ${\displaystyle 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í ${\displaystyle 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