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 \ne 0, \ a > b \$. Tällöin on olemassa sellaiset yksikäsitteiset kokonaisluvut $q \$ ja $r \$, että

$a = qb + r, \ 0 \le 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 \le r < b = |b|$

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

Yksikäsitteisyys:

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

Toisaalta

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

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

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

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