Sanna Ranto, LUKUTEORIA JA ALGEBRA
Versio 1, 1.11.2003 		LUKUTEORIA
 

Jäännösluokka

Kongruenssi modulo m hajottaa joukon Z ekvivalenssiluokkiin, jotka ovat muotoa:

[a] = {a + mk | k (- Z}.

Ekvivalenssiluokkaa [a] sanotaan luvun a jäännösluokaksi modulo m. Jäännösluokasta käytetään yleensä merkintää -- a tai a + mZ. Samassa jäännösluokassa olevat luvut antavat saman jakojäännöksen luvulla m jaettaessa. Kaikkien jäännösluokkien modulo m joukosta käytetään merkintää Zm. Jäännösluokan a- (- Zm edustajaksi voidaan valita mikä tahansa luku, joka on kongruentti luvun a kanssa modulo m. Näistä luvuista voidaan jakoalgoritmin mukaan valita yksikäsitteisesti luvun a pienin ei-negatiivinen jäännös modulo m. Tämä jäännös r toteuttaa ehdon 0 < r < m. Siis jokaisella luokalla -- a (- Zm on pienin ei-negatiivinen jäännös r modulo m, joka toteutaa saman ehdon. Toisaalta nämä jäännökset ovat selvästi parittain epäkongruentteja modulo m. Täten

---- ------ Zm = {0,1,...,m - 1}.

Esimerkki. Z3 = {-- 0,-- 1,-- 2}, missä

- 0= 3Z = {3k |k (- Z} = {...,- 9,- 6,- 3,0,3,6,9, ...}, 1=1 + 3Z = {1 + 3k |k (- Z} = {...,- 8,- 5,- 2,1,4,7,10, ...}, 2=2 + 3Z = {2 + 3k |k (- Z} = {...,- 7,- 4,- 1,2,5,8,11, ...}.

Joukko Z3 voidaan esittää myös esimerkiksi muodossa {--- -1,-- 0,-- 1} tai {-- 7,--- - 4,-- 6}.

Jos m = 1, niin kongruenssi modulo m on triviaali: a =_ b (mod 1) kaikilla a,b (- Z. Erityisesti siis Z1 = {- 0}, missä -- 0 = Z.

Lause. Jäännösluokkien summa a- + b = a-+-b ja tulo a- . b = ab- eivät ole riippuvia jäännösluokkien edustajien valinnasta. (Sanotaan, että jäännösluokkien summa ja tulo ovat hyvin määriteltyjä.)

Todistus. Olkoot -- a = -- a' ja - b = -- b'. Silloin a =_ a' (mod m) ja b =_ b' (mod m). Sivulla Kongruenssi olevan lauseen kohdan (i) mukaan on

' ' ' ' a + b =_ a + b ja ab =_ a b (mod m).

Täten - a+b = ------ a'+ b' ja --- ab = ---- a'b', mikä todistaa väitteen. []

Linkit:
Konruenssi
Ekvivalenssiluokka
Jakoalgoritmi
Diofantoksen yhtälö