Kongruenca

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Za kongruenco v geometriji glej: Skladnost

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

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

Definicija[uredi | uredi kodo]

a,b\in \mathbb{Z}, m\in{N}, a\equiv b\mod(m)\Leftrightarrow m|a-b

Primer: 7\equiv 2 \mod(5)

Lastnosti kongruenc[uredi | uredi kodo]

Kongruenca je ekvivalenčna relacija, velja namreč:

a\equiv a \mod(m) - refleksivnost
a\equiv b\mod(m)\Longrightarrow b\equiv a \mod(m) - simetričnost
a\equiv b \mod(m)\and b\equiv c \mod(m)\Longrightarrow a\equiv c\mod(m) - tranzitivnost

Pravila pri računanju s kongruencami[uredi | uredi kodo]

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

Naj za vse primere velja:

a\equiv b\mod(m) \and c\equiv d\mod(m)

Seštevanje kongruenc[uredi | uredi kodo]

a+c\equiv b+d\mod(m)
a\equiv b\mod(m) \and c\equiv d\mod(m)\Longrightarrow a-b=km, c-d=lm

Zgoraj pridobljeni enačbi seštejemo:

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[uredi | uredi kodo]

a\cdot c\equiv b\cdot d\mod(m)
ac-bd=ac-ad+ad-bd=a(c-d)-d(a-b)=alm - dkm=m(al-dk)\Longrightarrow
ac-bd\equiv 0\mod(m) \Longrightarrow ac\equiv cd\mod(m)

Množenje kongruenc s celim številom[uredi | uredi kodo]

az\equiv bz\mod(m), z\in\mathbb{Z}
a-b=km |\cdot z
az-bz=kmz\Longrightarrow az-bz\equiv 0\mod(m)\Longrightarrow az\equiv bz\mod(m)

Potenciranje kongruenc[uredi | uredi kodo]

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[uredi | uredi kodo]

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[uredi | uredi kodo]

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

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

3 \equiv 3 \mod(m)

ali

3^1\equiv 3\mod(m)

in

3^2\equiv 9\mod(m)
3^3\equiv 7\mod(m)
3^4\equiv 1\mod(m)

Ker je 2005 = 4 * 501 + 1, velja

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

ali

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

pomnožimo obe strani s tri in to je rezultat

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

Zunanje povezave[uredi | uredi kodo]