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.