Kongruence

Z Wikipedie, otevřené encyklopedie

Skočit na: Navigace, Hledání
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).

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 vyskytující se na stejné pozici v argumentu operace 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 \geq 2 \,\! , tj. relace, která je zavedena vztahem:
a \equiv b \pmod n \Leftrightarrow n | (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“.

[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] Související články

Související články obsahuje
Portál Matematika
Citováno z „http://cs.wikipedia.org/wiki/Kongruence“