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

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

[editovat] Podívejte se také na

Související články obsahuje:
 Portál Matematika