Jakoyhtälö

Jakoyhtälö on yhtälö, joka osoittaa, miten kokonaisluku a voidaan esittää toisen kokonaisluvun b avulla yhdellä ja vain yhdellä tavalla muodossa a = q · b + r, missä q ja r ovat kokonaislukuja ja $0\leq r<|b|$. Lukua a sanotaan jaettavaksi, lukua b jakajaksi, q sanotaan (kokonaiseksi) osamääräksi ja lukua r jakojäännökseksi.

17 palloa on jaettu kolmelle täydelle pystyriville, joista jokaiseen tulee viisi palloa, ja kaksi palloa jäi yli. Jakoa osoittaa jakoyhtälö 17 = 3 · 5 + 2, missä jaettavana on 17 ja jakajana 3. Jako ei mene tasan, mutta (kokonaiseksi) osamääräksi saadaan 5 ja jakojäännökseksi 2.

Jakoyhtälö on oleellisesti sama asia kuin jakolasku käytettäessä ainoastaan kokonaislukuja. Koska murto- tai desimaaliluvut eivät ole käytössä, jako ei aina mene tasan, vaan tuloksena saadaan osamäärän ohella myös jakojäännös, joka tosin saattaa olla myös nolla. Siinä tapauksessa sanotaan, että x on jaollinen y:llä.

Jakoyhtälöä käytetään sellaisilla matematiikan aloilla, joissa käytetään vain kokonaislukuja. Siihen perustuu esimerkiksi Eukleideen algoritmi, jonka avulla voidaan löytää kahden kokonaisluvun suurin yhteinen tekijä. Lisäksi sen avulla määritellään erityinen kongruenssirelaatio. Kongruenssiyhtälöissä lasketaan jakojäännöksillä.

Vastaavalla tavalla kuin kokonaislukujen joukossa voidaan jakoyhtälö määritellä myös polynomeille sekä yleensäkin jokaisessa algebrallisessa renkaassa, joka ei ole kunta.

Olemassaolo ja yksikäsitteisyys

Lause:

Olkoot $a\$ ja $b\$ kokonaislukuja ja $b\neq 0,\ a>b\$. Tällöin on olemassa sellaiset yksikäsitteiset kokonaisluvut $q\$ ja $r\$, että

$a=qb+r,\ 0\leq r<|b|$.

Todistus

Olemassaolo

Olkoon b > 0 ja joukko A = {a - nb, $n\in \mathbb {N}$}.
Hyvän järjestyksen periaatteen nojalla joukossa A on pienin positiivinen alkio $r=a-qb,\ q\in \mathbb {N}$.
Nyt $r<b$, koska muuten $a-(q+1)b\$ olisi vielä pienempi kokonaisluku.
Näin siis $a=qb+r,\ 0\leq r<b=|b|$

Jos b < 0, käytetään edellistä sijoittamalla b:n tilalle -b, jolloin $a=q(-b)+r,\ 0\leq r<-b=|b|$.

Yksikäsitteisyys

Olkoon $a=qb+r,\ 0\leq r<|b|$ ja $a=q'b+r',\ 0\leq r'<|b|$. Tällöin qb + r = q'b + r' eli (q' - q)b = r - r'. Tehdään vastaoletus: $q'\neq q$. Nyt $|q'-q|\leq 1\$, koska q' ja q ovat kokonaislukuja.
Edelleen $|r-r'|=|q'-q||b|\leq 1*|b|=|b|$.

Toisaalta

$0\leq r,r'<|b|\$

$-|b|<r-r'<|b|\$

$0\leq |r-r'|<|b|\$.

Näin olisi $|b|\leq |r-r'|<|b|\$, mikä on ristiriita.
Vastaoletus $q'\neq q$ on väärä, joten $q'=q\$.
Tällöin 0*b = r - r' eli r - r' = 0 eli r = r', mikä oli todistettava.