Přeskočit na obsah

Kongruence

Z Wikipedie, otevřené encyklopedie
Tento článek je o matematickém pojmu ekvivalence na algebraické struktuře. Další významy jsou uvedeny na stránce 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).

Formální definice

[editovat | editovat zdroj]

Předpokládejme, že je algebraická struktura s množinou prvků a operacemi , operace je -ární.

Binární relaci na X nazveme kongruence, pokud je to ekvivalence a pokud pro každou z vyjmenovaných operací a každé prvky platí

Chceme ověřit, zda na grupě celých čísel je relace " 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 ). je jen jiný zápis pro a+b. Tato operace je binární (potřebuje dva "vstupy", takže ).

Zvolíme-li a1 = 3, a2 = 5, b1 = 13, b2 = 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 lze provést takto: Pro obě i platí , čili existují celá čísla tak, že . Potom platí: , což je násobek deseti, takže

Kongruence zbytkových tříd

[editovat | editovat zdroj]

Nejznámějším příkladem kongruence je rozklad množiny všech celých čísel na zbytkové třídy po dělení číslem , tj. relace, která je zavedena vztahem:


Jinými slovy: dvě čísla jsou ekvivalentní (modulo n), pokud mají stejný zbytek po dělení číslem . Pokud je z kontextu jasné, pro které je kongruence zapsána (nebo na nezáleží, protože zápis je platný pro jeho libovolnou hodnotu), vynechává se konec zápisu a píše se jednoduše . Celý zápis se čte „a je kongruentní s b modulo n“.

Vlastnosti kongruence modulo n

[editovat | editovat zdroj]
  • , jinými slovy: relace je kongruence vzhledem ke sčítání
  • , jinými slovy: relace je kongruence vzhledem k odčítání
  • , jinými slovy: relace je kongruence vzhledem k násobení

Je-li navíc prvočíslo, pak navíc podle Malé Fermatovy věty:

Význam kongruence modulo n

[editovat | editovat zdroj]

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

[editovat | editovat zdroj]

Je-li R kongruence, pak faktormnožině může být dána přirozená struktura takto (výsledek nezávisí na volbě reprezentantů):

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 ; v článku je však použito označení 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

[editovat | editovat zdroj]

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 , která se však obvykle značí , pokud nehrozí nedorozumění. Chceme zjistit např. výsledek operace "lichá čísla sudá čísla". Zvolíme tedy nějaké celé číslo tak, aby byla množina lichých čísel, tzv. reprezentanta množiny lichých čísel. Zvolme například . Pak výše uvedený vzorec říká:

Dosazením do pravé strany dostaneme:

Takže výsledek operace "lichá čísla sudá čísla" je množina lichých čísel.

Kdybychom vybrali jiné reprezentanty, např. , dospěli bychom k výsledku , což je množina totožná s množinou . 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ů

[editovat | editovat zdroj]

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

[editovat | editovat zdroj]