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,\dots <!--\; \dots \; -->,O_n)$ je algebraická struktura s množinou prvků $X$ a operacemi $O_1,O_2,\dots <!--\; \dots \; -->,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,\dots <!--\; \dots \; -->,a_{m_i},b_1,b_2,\dots <!--\; \dots \; -->,b_{m_i}\in <!--\; \in \; -->X$ platí

$a_1{\sim <!--\; \sim \; -->}_R{b}_1,a_2{\sim <!--\; \sim \; -->}_R{b}_2,\dots <!--\; \dots \; -->,a_{m_i}{\sim <!--\; \sim \; -->}_R{b}_{m_i}⟹<!--\; ⟹\; -->O_i(a_1,a_2,\dots <!--\; \dots \; -->,a_{m_i}){\sim <!--\; \sim \; -->}_R{O}_i(b_1,b_2,\dots <!--\; \dots \; -->,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$). $O_1(a,b)$ je jen jiný zápis pro a+b. Tato operace je binární (potřebuje dva "vstupy", takže $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í $a_i{\sim <!--\; \sim \; -->}_R{b}_i$, čili existují celá čísla $k_1,k_2$ tak, že $b_i=a_i+10.k_i$. Potom platí: $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 $O_1(a_1,a_2){\sim <!--\; \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\ge <!--\; \ge \; -->2$, tj. relace, která je zavedena vztahem:

$a\equiv <!--\; \equiv \; -->b\left(\mathrm{mod}n\right)\iff <!--\; \iff \; -->n\mid <!--\; \mid \; -->(a-<!--\; -\; -->b)$

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 jednoduše $a\equiv <!--\; \equiv \; -->b$. Celý zápis se čte „a je kongruentní s b modulo n“.

Vlastnosti kongruence modulo n

• $a\equiv <!--\; \equiv \; -->b\wedge <!--\; \wedge \; -->c\equiv <!--\; \equiv \; -->d⟹<!--\; ⟹\; -->a+c\equiv <!--\; \equiv \; -->b+d$, jinými slovy: relace $\equiv <!--\; \equiv \; -->$ je kongruence vzhledem ke sčítání
• $a\equiv <!--\; \equiv \; -->b\wedge <!--\; \wedge \; -->c\equiv <!--\; \equiv \; -->d⟹<!--\; ⟹\; -->a-<!--\; -\; -->c\equiv <!--\; \equiv \; -->b-<!--\; -\; -->d$, jinými slovy: relace $\equiv <!--\; \equiv \; -->$ je kongruence vzhledem k odčítání
• $a\equiv <!--\; \equiv \; -->b\wedge <!--\; \wedge \; -->c\equiv <!--\; \equiv \; -->d⟹<!--\; ⟹\; -->a\ast <!--\; \ast \; -->c\equiv <!--\; \equiv \; -->b\ast <!--\; \ast \; -->d$, jinými slovy: relace $\equiv <!--\; \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 <!--\; \equiv \; -->a\left(\mathrm{mod}n\right)$

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ů):

$\stackrel{^<!--\; ^\; -->}{O_i}\left(\right[x_1{]}_R,[x_2{]}_R,\dots <!--\; \dots \; -->,[x_{m_i}{]}_R)=[O_i(x_1,x_2,\dots <!--\; \dots \; -->,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í $\stackrel{^<!--\; ^\; -->}{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 $\stackrel{^<!--\; ^\; -->}{+}$, která se však obvykle značí $+$, pokud nehrozí nedorozumění. Chceme zjistit např. výsledek operace "lichá čísla $\stackrel{^<!--\; ^\; -->}{+}$ sudá čísla". Zvolíme tedy nějaké celé číslo $\left[x_1\right]$ tak, aby $[x_1{]}_R$ byla množina lichých čísel, tzv. reprezentanta množiny lichých čísel. Zvolme například $x_1=11,x_2=8$ . Pak výše uvedený vzorec říká: $\left[x_1{]}_R\stackrel{^<!--\; ^\; -->}{+}\right[x_2{]}_R=[x_1+x_2{]}_R$

Dosazením do pravé strany dostaneme: $\left[x_1{]}_R\stackrel{^<!--\; ^\; -->}{+}\right[x_2{]}_R=[x_1+x_2{]}_R=[11+8{]}_R=[19{]}_R$

Takže výsledek operace "lichá čísla $\stackrel{^<!--\; ^\; -->}{+}$ sudá čísla" je množina lichých čísel.

Kdybychom vybrali jiné reprezentanty, např. $x_1=41,x_2=42$, dospěli bychom k výsledku $[83{]}_R$, což je množina totožná s množinou $[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\left(x\right):A\to <!--\; \to \; -->A/R,f\left(x\right)=[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 <!--\; \to \; -->Z,f\left(n\right)=(-<!--\; -\; -->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

Autoritní data	PSH: 7179