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
ja
kokonaislukuja ja
. Tällöin on olemassa sellaiset yksikäsitteiset kokonaisluvut
ja
, että
.
Todistus:
Olemassaolo:
Olkoon b > 0 ja joukko A = {a - nb,
}.
Hyvän järjestyksen periaatteen nojalla joukossa A on pienin positiivinen alkio
.
Nyt r < b, koska muuten
olisi vielä pienempi kokonaisluku.
Näin siis 
Jos b < 0, käytetään edellistä sijoittamalla b:n tilalle -b, jolloin
.
Yksikäsitteisyys:
Olkoon
ja
.
Tällöin qb + r = q'b + r' eli (q' - q)b = r - r'.
Tehdään vastaoletus:
.
Nyt
, koska q' ja q ovat kokonaislukuja.
Edelleen
.
Toisaalta


.
Näin olisi
, mikä on ristiriita.
Vastaoletus
on väärä, joten
.
Tällöin 0*b = r - r' eli r - r' = 0 eli r = r', mikä oli todistettava.

