Jakoyhtälö

Kun x ja y ovat kokonaislukuja ja x > y, ne voidaan esittää yhtälönä x = a * y + r, missä a on luonnollinen luku ja 0 < r < $|y|$. Lukua a kutsutaan usein jakolaskun x/y osamääräksi ja lukua r jakojäännökseksi.

Jakoyhtälöä eli jakoalgoritmia käytetään esimerkiksi jakolaskussa ja Eukleideen algoritmissa. Lisäksi sen avulla määritellään erityinen kongruenssirelaatio. Kongruenssiyhtälöissä lasketaan jakojäännöksillä.

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.