2.1 Kongruenssi
Teoria ja esimerkit
Mitä yhteistä on:
- kellonajoilla 10.20, 11.20, 12.20, …
- luvuilla 6, 11, 16, 21, …
Sanotaan, että luvut ovat kongruentteja modulo 5. (Erotus jaollinen viidellä / jos jaetaan viidellä, niin jakojäännös sama: 6 = 1 ⋅ 5 + 1 ja 11 = 2 ⋅ 5 + 1).
Määritelmä: Jos lukujen a ja b erotus on jaollinen luvulla n eli n | (a – b), niin luvut a ja b
ovat kongruentteja modulo n. Merkitään a ≡ b (mod n).
- Siis: a ≡ b (mod n) <=> n | (a – b)
- a ≡ b (mod n) <=> a = pn + r ja b = qn + r
ESIM 1. Osoita, että
a) 45 ≡ 3 (mod 7)
***
b) 19 ≡ –37 (mod 8)
***
c) 376 ≡ 0 (mod 8).
***
ESIM 2. Onko 45 ≡ 5 (mod 7)?
***
Kongruenssin perusominaisuuksia
- a ≡ a (mod n)
- Jos a ≡ b (mod n), niin b ≡ a (mod n)
- Jos a ≡ b (mod n) ja b ≡ c (mod n), niin a ≡ c (mod n)