Divisjonsalgoritmen

I aritmetikk og tallteori er divisjonsalgoritmen et fundamentalt teorem knyttet til divisjon blant heltallene. Det finnes flere metoder for å finne kvotienten og resten i en divisjon, men begrepet divisjonsalgoritmen refererer til det formelle utsagnet som understreker eksistensen og entydigheten til disse to tallene, til tross for at ordet algoritme inngår i navnet. Teoremet opptrer som en ingrediens i mange andre resultater i tallteori, for eksempel i den euklidske algoritmen, som brukes til å finne største felles divisor mellom to heltall.

Formelt utsagn

Divisjonsalgoritmen sier at for to heltall a og b > 0, så eksisterer det unike heltall q og r slik at

<tex>a=qr+b \;\;\; \textrm{der} \;\;\; 0 \leq r < b</tex>

Tallet a kalles for dividenden, b kalles for divisoren, q kalles for kvotienten og r kalles for resten. Det er vanlig å betegne kvotienten med q = a div b og resten med r = a mod b.

Eksempler

Hvis a = 14 og b = 6, da er kvotienten 2 og resten 2 siden <tex>14=2 \cdot 6 + 2</tex>.
Hvis dividenden er 35 og divisoren er 7, så er q = 5 og r = 0 siden <tex>35 = 5 \cdot 7 + 0</tex>. Når resten er 0, sier vi at b deler a.

Bevis

Beviset for divisjonsalgoritmen er basert på velordningsprinsippet, som sier at dersom en ikke-tom mengde inneholder kun ikke-negative heltall, ja da må mengden inneholde et minste element. Vi deler beviset inn i to deler: Bevis for at q og r eksisterer, og bevis for at de er unike.

Eksistens

La a og b > 0 være vilkårlige heltall. Betrakt mengden

<tex>S = \{ a-xb \, | \, x \in \mathbb{Z} \: \textrm{og} \: a-xb \geq 0 \}</tex>

Vi skal først vise at S ikke er tom, uansett hvilke heltall a og b måtte være. Da må vi demonstrere en heltallsverdi for x slik at a - xb ≥ 0. Observer at siden b > 0, altså b ≥ 1, må |a|b ≥ |a| og a + |a|b ≥ a + |a|. Lar vi da x = -|a|, får vi at

Altså ligger a - xb i S hvis x = -|a|. Dermed er mengden ikke-tom og inneholder kun ikke-negative heltall. Ifølge velordningsprinsippet følger det at S må inneholde et minste element, som vi kaller r. Siden r er i S, må det etter definisjonen av S finnes et heltall q som tilfredsstiller r = a - qb, der r ≥ 0. Flytter vi qb over likhetstegnet, får vi

<tex>a = qb+r \;\; \textrm{der} \;\; r \geq 0</tex>

Nå gjenstår det å vise at r < b. La oss anta det motsatte, nemlig at 'r ≥ b. Betrakt så tallet

<tex>a-(q+1)b=(a-qb)-b=r-b \geq 0 \;\; \Leftrightarrow \;\; r \geq b </tex>

Antakelsen vår om at r ≥ b impliserer altså at det finnes et heltall a - (q + 1)b ≥ 0. Se på formen til tallet, det må per definisjon være med i S. Men a - (q + 1)b = r - b < r, noe som er umulig siden vi har valgt r til å være det minste elementet i S. Vi må derfor forkaste antakelsen vår om at r ≥ b, og følgelig er r < b.

Vi har altså at for to vilkårlige heltall a og b > 0, så eksisterer det heltall q og r slik at

<tex>a=qb+r \;\; \textrm{der} \;\; 0 \leq r < b</tex>

Nå gjenstår det å vise at q og r er unike.

Entydighet

Anta at a har to representasjoner: a = qb + r = q'b + r' , hvor 0 ≤ r < b og 0 ≤ r' < b. Dette gir

Tar vi absoluttverdien av begge sider, får vi

Legg merke til at vi kunne fjerne absoluttverditegnene rundt b, siden vi har antatt at b > 0. Vi vet at 0 ≤ r' < b, som gir -b < -r' ≤ 0. Legger vi denne ulikheten sammen med 0 ≤ r < b, får vi

Ser vi nå på de tidligere uttrykkene våre, får vi |r' - r| = b|q - q' | < b. Vi kan i siste ulikhet dele med b på begge sider. Siden b > 0, slipper vi å bekymre oss for å måtte snu ulikheten. Siden absoluttverdien av et uttrykk alltid er ikke-negativ, får vi nå

Altså er eneste mulighet at |q' - q| = 0, som gir q' = q. Men da må

<tex> |r-r'| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </tex>

Altså har antakelsen vår om at det eksistere en annen kvotient og en annen rest med de samme egenskapene som vår allerede eksisterende kvotient og rest, ført til konklusjonen om at disse kvotientene og restene er akkurat de samme. Dette bevise entydigheten til q og r, og beviset er ferdig.