SL
All
Articles
Dictionary
Quotes
Map

Wikiwand ❤️ Wikipedia

PrivacyTerms

Kongruenca

From Wikipedia, the free encyclopedia

Kongruenca
DefinicijaLastnosti kongruencPravila pri računanju s kongruencamiSeštevanje kongruencMnoženje kongruencMnoženje kongruenc s celim številomPotenciranje kongruencUporaba kongruencPrimer nalogeZunanje povezave

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

Za kongruenco v geometriji glej: Skladnost

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.

a , b ∈ Z {\displaystyle a,b\in \mathbb {Z} } {\displaystyle a,b\in \mathbb {Z} }, m ∈ N {\displaystyle m\in {N}} {\displaystyle m\in {N}}, a ≡ b mod ( m ) ⇔ m | a − b {\displaystyle a\equiv b\mod (m)\Leftrightarrow m|a-b} {\displaystyle a\equiv b\mod (m)\Leftrightarrow m|a-b}

Primer: 7 ≡ 2 mod ( 5 ) {\displaystyle 7\equiv 2\mod (5)} {\displaystyle 7\equiv 2\mod (5)}

Kongruenca je ekvivalenčna relacija, velja namreč:

a ≡ a mod ( m ) {\displaystyle a\equiv a\mod (m)} {\displaystyle a\equiv a\mod (m)} - refleksivnost
a ≡ b mod ( m ) ⟹ b ≡ a mod ( m ) {\displaystyle a\equiv b\mod (m)\Longrightarrow b\equiv a\mod (m)} {\displaystyle a\equiv b\mod (m)\Longrightarrow b\equiv a\mod (m)} - simetričnost
a ≡ b mod ( m ) ∧ b ≡ c mod ( m ) ⟹ a ≡ c mod ( m ) {\displaystyle a\equiv b\mod (m)\land b\equiv c\mod (m)\Longrightarrow a\equiv c\mod (m)} {\displaystyle a\equiv b\mod (m)\land b\equiv c\mod (m)\Longrightarrow a\equiv c\mod (m)} - tranzitivnost

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

Naj za vse primere velja:

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

Seštevanje kongruenc

a + c ≡ b + d mod ( m ) {\displaystyle a+c\equiv b+d\mod (m)} {\displaystyle a+c\equiv b+d\mod (m)}
a ≡ b mod ( m ) ∧ c ≡ d mod ( m ) ⟹ a − b = k m , c − d = l m {\displaystyle a\equiv b\mod (m)\land c\equiv d\mod (m)\Longrightarrow a-b=km,c-d=lm} {\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:

a − b + c − d = k m + l m = m ( l + k ) ⟹ a − b + c − d ≡ 0 mod ( m ) ⟹ a + c ≡ b + d mod ( m ) {\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)} {\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

a ⋅ c ≡ b ⋅ d mod ( m ) {\displaystyle a\cdot c\equiv b\cdot d\mod (m)} {\displaystyle a\cdot c\equiv b\cdot d\mod (m)}
a c − b d = a c − a d + a d − b d = a ( c − d ) + d ( a − b ) = a l m + d k m = m ( a l + d k ) ⟹ {\displaystyle ac-bd=ac-ad+ad-bd=a(c-d)+d(a-b)=alm+dkm=m(al+dk)\Longrightarrow } {\displaystyle ac-bd=ac-ad+ad-bd=a(c-d)+d(a-b)=alm+dkm=m(al+dk)\Longrightarrow }
a c − b d ≡ 0 mod ( m ) ⟹ a c ≡ b d mod ( m ) {\displaystyle ac-bd\equiv 0\mod (m)\Longrightarrow ac\equiv bd\mod (m)} {\displaystyle ac-bd\equiv 0\mod (m)\Longrightarrow ac\equiv bd\mod (m)}

Množenje kongruenc s celim številom

a z ≡ b z mod ( m ) , z ∈ Z {\displaystyle az\equiv bz\mod (m),z\in \mathbb {Z} } {\displaystyle az\equiv bz\mod (m),z\in \mathbb {Z} }
a − b = k m | ⋅ z {\displaystyle a-b=km|\cdot z} {\displaystyle a-b=km|\cdot z}
a z − b z = k m z ⟹ a z − b z ≡ 0 mod ( m ) ⟹ a z ≡ b z mod ( m ) {\displaystyle az-bz=kmz\Longrightarrow az-bz\equiv 0\mod (m)\Longrightarrow az\equiv bz\mod (m)} {\displaystyle az-bz=kmz\Longrightarrow az-bz\equiv 0\mod (m)\Longrightarrow az\equiv bz\mod (m)}

Potenciranje kongruenc

a ≡ b mod ( m ) ⟹ a n ≡ b n mod ( m ) , n ∈ N 0 {\displaystyle a\equiv b\mod (m)\Longrightarrow a^{n}\equiv b^{n}\mod (m),n\in \mathbb {N} _{0}} {\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.

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 3 2005 {\displaystyle 3^{2005}} {\displaystyle 3^{2005}}?

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

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

ali

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

in

3 2 ≡ 9 mod ( m ) {\displaystyle 3^{2}\equiv 9\mod (m)} {\displaystyle 3^{2}\equiv 9\mod (m)}
3 3 ≡ 7 mod ( m ) {\displaystyle 3^{3}\equiv 7\mod (m)} {\displaystyle 3^{3}\equiv 7\mod (m)}
3 4 ≡ 1 mod ( m ) {\displaystyle 3^{4}\equiv 1\mod (m)} {\displaystyle 3^{4}\equiv 1\mod (m)}

Ker je 2005 = 4 * 501 + 1, velja

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

ali

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

pomnožimo obe strani s tri in to je rezultat

3 2005 ≡ 3 mod ( m ) {\displaystyle 3^{2005}\equiv 3\mod (m)} {\displaystyle 3^{2005}\equiv 3\mod (m)}.
  • http://www2.arnes.si/~mmlaka10/Clanki/clanki.htm
Edit in WikipediaRevision historyRead in Wikipedia

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Chrome
Wikiwand for Chrome
Edge
Wikiwand for Edge
Firefox
Wikiwand for Firefox

Definicija

Lastnosti kongruenc

Pravila pri računanju s kongruencami

Uporaba kongruenc

Zunanje povezave