Jakoyhtälö

Wikipedia
Loikkaa: valikkoon, hakuun

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.