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 $(X,O_1,O_2,\dots ,O_n)$ je algebrická štruktúra s množinou prvkov $X$ a operáciami $O_1,O_2,\dots ,O_n$, operácia $O_i$ je $m_i$ - árna. Predpokladajme ďalej, že $R$ je relácia ekvivalencie na množine $X$. $R$ je kongruencia na $X$, ak pre každú z vymenovaných operácií platí:
$a_1{\sim }_R{b}_1,a_2{\sim }_R{b}_2,\dots ,a_{m_i}{\sim }_R{b}_{m_i}⟹O_i(a_1,a_2,\dots ,a_{m_i}){\sim }_R{O}_i(b_1,b_2,\dots ,b_{m_i})$

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 $a,b\in \mathbb{Z}$ sú kongruentné, ak ich rozdiel je deliteľný číslom $m$, ktoré nazývame modulo. Formálne

$a\equiv b(\mathrm{mod}m)$

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

$a-b=k\cdot m$
$a=k\cdot m+b$

Príklad

Z predchádzajúceho vidno, že číslo $a$ dáva po delení modulom zvyšok $b$. 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í

$4\equiv 4+3k(\mathrm{mod}3)$

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ť

$a\equiv a(\mathrm{mod}m)$

Dôkaz spočíva v použití definície kongruencie. Teda má platiť $m|(a-a)$, čo je zrejme pravda, pretože $m|0$.$◼$
2. symetria

$a\equiv b(\mathrm{mod}m)\Rightarrow b\equiv a(\mathrm{mod}m)$

Aj táto vlastnosť je jednoducho dokázateľná priamo z definície. Čiže $m|(a-b)\Rightarrow m|(b-a)$, čo sa dá prepísať $(a-b=k\cdot m)\Rightarrow (b-a=k\cdot m)$, po úprave $(a=k\cdot m+b)\Rightarrow (a=-k\cdot m+b)$.$◼$
3. tranzitívnosť

$(a\equiv b(\mathrm{mod}m)\wedge b\equiv c(\mathrm{mod}m))\Rightarrow (a\equiv c(\mathrm{mod}m))$

Dôkaz:
$\begin{array}{c}a-b=k_1\cdot m\\ b-c=k_2\cdot m\end{array}$
Súčtom oboch rovností vznikne nová rovnica
$\begin{array}{ccc}a-c& =& k_1\cdot m+k_2\cdot m\\ a-c& =& (k_1+k_2)\cdot m\\ a& \equiv & c(\mathrm{mod}m)◼\end{array}$

Príklad

Názorný príklad ukazuje, že číslo $29^{21}+1$ je deliteľné desiatimi. Ak si zápis prepíšeme do formy kongruencie, potom
$\begin{array}{ccc}29^{21}+1& \equiv & 0(\mathrm{mod}10)\\ 29^{21}& \equiv & -1\\ 29\cdot 29\cdots 29& \equiv & -1\\ 9\cdot 9\cdots 9& \equiv & -1\\ 9^{21}& \equiv & -1\\ 9^{20}\cdot 9& \equiv & -1\\ 81^{10}\cdot 9& \equiv & -1\\ 9& \equiv & -1\end{array}$