Relácia kongruencie (algebra)

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

Predpokladajme, že  (X, O_1, O_2, \ldots, O_n) \,\! je algebraická štruktúra s množinou prvkov  X \,\! a operáciami  O_1, O_2, \ldots, 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, \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}) \,\!

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[upraviť | upraviť zdroj]

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\pmod{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[upraviť | upraviť zdroj]

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\pmod{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í[upraviť | upraviť zdroj]

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

a\equiv a\pmod{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.\blacksquare
2. symetria

a\equiv b\pmod{m}\;\Rightarrow\; b\equiv a\pmod{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).\blacksquare
3. tranzitívnosť

(a\equiv b\pmod{m}\wedge b\equiv c\pmod{m})\Rightarrow(a\equiv c\pmod{m})

Dôkaz:
\begin{array}{l}a-b=k_1\cdot m\\b-c=k_2\cdot m\end{array}
Súčtom oboch rovností vznikne nová rovnica
\begin{array}{rcl}a-c&=&k_1\cdot m+k_2\cdot m\\ a-c&=&(k_1+k_2)\cdot m\\ a&\equiv& c\pmod{m}\blacksquare\end{array}

Príklad[upraviť | upraviť zdroj]

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}{rcl}29^{21}+1&\equiv&0\pmod{10}\\29^{21}&\equiv&-1\\ 29\cdot29\cdots29&\equiv&-1\\9\cdot9\cdots9&\equiv&-1\\9^{21}&\equiv&-1\\9^{20}\cdot9&\equiv&-1\\81^{10}\cdot9&\equiv&-1\\9&\equiv&-1\end{array}