Kongruence

Z Wikipedie, otevřené encyklopedie

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).

Obsah

1 Definice
2 Příklad - kongruence zbytkových tříd
- 2.1 Vlastnosti kongruence modulo n
- 2.2 Význam kongruence modulo n
3 Podívejte se také na

[editovat] 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í. Předpokládejme dále, že $R \,\!$ je relace ekvivalence na množině $X \,\!$ . Řekneme, že $R \,\!$ je kongruence na $X \,\!$ , pokud pro každou z vyjmenovaných operací 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}) \,\!$

kde zápis $a_{m_i} \sim_R b_{m_i}$ značí binární relaci (ekvivalenci) $R \,\!$ prvků $a_{m_i}, b_{m_i}$ na množině $X \,\!$ .

Odpudivost této formální definice nemění nic na tom, že říká v podstatě totéž, co úvodní přiblížení - jsou-li operandy na stejném místě po dvou ekvivalentní, pak musí i výsledky operace být ekvivalentní.

[editovat] Příklad - 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 > 2 \,\!$ , tj. relace, která je zavedena vztahem:
$a \equiv b \pmod n \Leftrightarrow (a-b) | n \,\!$
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“.

[editovat] 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$

[editovat] 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.