Jakoalgoritmi

Mistä tiedetään onko annettu (suuri) luku N alkuluku? Entä jos luku ei ole alkuluku, miten löydetään sen tekijät? Alkeellinen menetelmä sen ratkaisemiseksi onko luku a jaollinen luvulla b on jakoalgoritmi eli jaon suorittaminen jakokulmassa. Seuraava lause koskee jaon tulosta.

Lause. (Jakoalgoritmi) Jos a,b ja b0, niin on olemassa sellaiset yksikäsitteiset kokonaisluvut q ja r, että

Todistus. Jos b > 0, valitaan joukosta {a - nb | n } pienin ei-negatiivinen kokonaisluku r = a - qb. Silloin r < b, sillä muuten a - (q + 1)b olisi vielä pienempi ei-negatiivinen kokonaisluku.

Tapaus b < 0 palautetaan edelliseen korvaamalla b luvulla -b:

Todistetaan vielä, että luvut q ja r ovat yksikäsitteiset. Oletetaan, että q' ja r' olisivat toiset sellaiset luvut, joille

Silloin a = q'b + r' = qb + r, josta saadaan r - r' = (q'- q)b. Koska 0 < r,r' < |b|, niin -|b| < r - r' < |b|. Siis 0 <|r - r'| < |b| ja toisaalta |r - r'| = |q'- q||b|, joten välttämättä |r - r'| = 0, toisin sanoen r = r' ja täten myös q = q'.

Esimerkki. 30 = 4 ^. 7 + 2, 17 = (-2)(-7) + 3, -11 = (-3) ^. 5 + 4.

Linkit:
Jaollisuus ja alkuluvut