Kongruenca

Kongruénca oziroma kongruénčna relácija je ekvivalenčna relacija.

Za kongruenco v geometriji glej: Skladnost

Celi števili ${\displaystyle a}$ in ${\displaystyle b}$ sta kongruentni po modulu ${\displaystyle m}$ (${\displaystyle m}$ je naravno število), če in samo če ${\displaystyle m}$ deli razliko števil ${\displaystyle a}$ in ${\displaystyle b}$.

Definicija

Naj bo ${\displaystyle m\in \mathbb {N} }$ in ${\displaystyle a,b\in \mathbb {Z} }$. Pravimo, da je ${\displaystyle a}$ kongruenten ${\displaystyle b}$ po modulu ${\displaystyle m}$ ter to zapišemo kot:

${\displaystyle a\equiv b\mod (m)}$.

Velja ${\displaystyle a\equiv b\mod (m)}$ natanko tedaj, ko velja ${\displaystyle m|(a-b)}$.

Na primer ${\displaystyle 55\equiv 61\mod (3)}$, saj velja ${\displaystyle 3|55-61}$.

Lastnosti kongruenc

Kongruenca je ekvivalenčna relacija, velja namreč:

${\displaystyle a\equiv a\mod (m)}$ – refleksivnost

${\displaystyle a\equiv b\mod (m)\Longrightarrow b\equiv a\mod (m)}$ – simetričnost

${\displaystyle (a\equiv b\mod (m))\land (b\equiv c\mod (m))\Longrightarrow (a\equiv c\mod (m))}$ – tranzitivnost

Pravila pri računanju s kongruencami

Iz definicije sledi da lahko kongruentna števila ali člene vedno zamenjujemo med seboj.

Naj za vse primere velja:

${\displaystyle a\equiv b\mod (m)\land c\equiv d\mod (m)}$

Seštevanje kongruenc

${\displaystyle a+c\equiv b+d\mod (m)}$

${\displaystyle a\equiv b\mod (m)\land c\equiv d\mod (m)\Longrightarrow a-b=km,c-d=lm}$

Zgoraj pridobljeni enačbi seštejemo:

${\displaystyle a-b+c-d=km+lm=m(l+k)\Longrightarrow a-b+c-d\equiv 0\mod (m)\Longrightarrow a+c\equiv b+d\mod (m)}$

Množenje kongruenc

${\displaystyle a\cdot c\equiv b\cdot d\mod (m)}$

${\displaystyle ac-bd=ac-ad+ad-bd=a(c-d)+d(a-b)=alm+dkm=m(al+dk)\Longrightarrow }$

${\displaystyle ac-bd\equiv 0\mod (m)\Longrightarrow ac\equiv bd\mod (m)}$

Množenje kongruenc s celim številom

${\displaystyle az\equiv bz\mod (m),z\in \mathbb {Z} }$

${\displaystyle a-b=km|\cdot z}$

${\displaystyle az-bz=kmz\Longrightarrow az-bz\equiv 0\mod (m)\Longrightarrow az\equiv bz\mod (m)}$

Potenciranje kongruenc

${\displaystyle a\equiv b\mod (m)\Longrightarrow a^{n}\equiv b^{n}\mod (m),n\in \mathbb {N} _{0}}$

Ta izrek je le posebni primer izreka o množenju kongruenc. Torej n-krat pomnožimo kongruenco samo s sabo in izrek je dokazan. Je pa ta izrek kot boste videli v nadaljevanju zelo pomemben.

Uporaba kongruenc

Kongruence so uporabne predvsem v nalogah, kjer nastopajo števila prevelika za računanje z njimi brez računalnika. Tipične naloge, ki se jih navadno lotimo s kongruencami so:

• dokazovanje ali spodbijanje deljivosti
• ugotavljanje zadnje števke
• ugotavljenje ostanka pri deljenju z nekim številom
• uporaba v diofantskih enačbah

Primer naloge

• S katero števko se konča ${\displaystyle 3^{2005}}$?

Ker iščemo zadnjo števko, gledamo število po modulu m=10. Velja seveda:

${\displaystyle 3\equiv 3\mod (m)}$

ali

${\displaystyle 3^{1}\equiv 3\mod (m)}$

in

${\displaystyle 3^{2}\equiv 9\mod (m)}$

${\displaystyle 3^{3}\equiv 7\mod (m)}$

${\displaystyle 3^{4}\equiv 1\mod (m)}$

Ker je 2005 = 4 * 501 + 1, velja

${\displaystyle 3^{4\cdot 501}\equiv 1\mod (m)}$

ali

${\displaystyle 3^{2004}\equiv 1\mod (m)}$

pomnožimo obe strani s tri in to je rezultat

${\displaystyle 3^{2005}\equiv 3\mod (m)}$.

Zunanje povezave

• http://www2.arnes.si/~mmlaka10/Clanki/clanki.htm