Relácia kongruencie (algebra)

Relácia kongruencie alebo kongruencia je ekvivalencia na algebre, ktorá je zlučiteľná so všetkými operáciami na tejto algebre (teda napríklad, ak sú tri páry prvkov ekvivalentné a výsledky nejakej operácie na týchto pároch sú tiež ekvivalentné, potom existuje pre tieto páry zhodnosť).

Definícia 
Predpokladajme, že  je algebrická štruktúra s množinou prvkov  a operáciami , operácia  je  - árna. Predpokladajme ďalej, že  je relácia ekvivalencie na množine .  je kongruencia na , ak pre každú z vymenovaných operácií platí:

Táto oficiálna definícia hovorí v podstate to isté, čo úvodné priblíženie - ak sú operandy na rovnakom mieste po dvoch ekvivalentné, potom musia aj výsledky operácie byť ekvivalentné.

Príklad - zhodnosť zvyškových tried 
Kongruencia čísel je úzko spätá s ich deliteľnosťou a so zvyškovými triedami. Jednoducho povedané, dve čísla sú kongruentné, ak ich rozdiel je deliteľný modulom, teda po delení modulom dávajú rovnaký zvyšok. Spomínaná ekvivalencia je v tom, že obe čísla dávajú rovnaký zvyšok po delení modulom, t. j. patria do tej istej zvyškovej triedy.

Hovoríme, že dve čísla  sú kongruentné, ak ich rozdiel je deliteľný číslom , ktoré nazývame modulo. Formálne

Predchádzajúci zápis sa môže ekvivalentne prepísať na tvar

Príklad 

Z predchádzajúceho vidno, že číslo  dáva po delení modulom zvyšok . Pomocou axióm modulárnej aritmetiky je možné ľahko dokázať deliteľnosť veľkých čísel určitým modulom. Je zrejmé, že číslo 4 dáva po delení číslom (modulom) 3 zvyšok 1. Ale aj čísla 7,10,13,16 ... dávajú ten istý zvyšok a teda platí

Odtiaľ vyplýva, že podľa relácie kongruencie sú čísla 4, 7, 10,... ekvivalentné, lebo dávajú rovnaký zvyšok po delení modulom 3.

Vlastnosti kongruencií 
Relácia kongruencie je reláciou ekvivalencie a teda je reflexívna, symetrická a tranzitívna.
1. reflexívnosť

Dôkaz spočíva v použití definície kongruencie. Teda má platiť , čo je zrejme pravda, pretože .
2. symetria

Aj táto vlastnosť je jednoducho dokázateľná priamo z definície. Čiže , čo sa dá prepísať , po úprave .
3. tranzitívnosť

Dôkaz:

Súčtom oboch rovností vznikne nová rovnica

Príklad 
Názorný príklad ukazuje, že číslo  je deliteľné desiatimi. Ak si zápis prepíšeme do formy kongruencie, potom

Referencie 

Modulárna aritmetika