Kongruensregning

Dette innlegget har allerede blitt vist 2003 ganger!

Selve kjernen i tallteori, ofte kalt klokkearitmetikk.

Definisjon: la a,b,m være heltall med m > 0. hvis m (a-b) så er a kongruent med b modulo m. Tallet m kalles modulus
Notasjon: a ≡ b (mod m). Dersom a ikke er kongruent med b modulo m setter vi en skrå strek over erliktegnet.

Teorem: a = b (mod m) ⇔ a mod m = b mod m

Dette fører til føløgende ekvivalenser

a ≡ b (mod m) ⇔ m(a-b)
⇔ m(r1 – r2)  ::Der r1, r2 er resten fra a/m og b/m
⇔ r1 – r2 = 0
⇔ r1 = r1
⇔ a mod m = b mod m

Regneregler:

  • a ≡ a (mod m)
  • Hvis a ≡ b (mod m) ⇒ b ≡ a (mod m)
  • Hvis a ≡ b (mod m) og b ≡ c (mod m) ⇒ a ≡ c (mod m)
  • Hvis a ≡ b (mod m) og c ≡ d (mod m) så er a + c ≡ b + d (mod m) og ac ≡ bd (mod m)