Jakoyhtälö

Wikipedia

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.