Jakoyhtälö

Kohteesta 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 < . 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 , 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.