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

<tex>a-xb = a-(-|a|)b = a+|a|b \geq a+|a| \geq 0</tex>

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

<tex>r-r' = q'b-qb = b(q'-q) </tex>

Tar vi absoluttverdien av begge sider, får vi

<tex>|r-r'| = |b(q'-q)|=b|q'-q|</tex>

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

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

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å

<tex>0 \leq |q'-q|<1 </tex>

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 eksisterer en annen kvotient og en annen rest med de samme egenskapene som tallene q og r vi fant i første del av beviset, ført til konklusjonen om at disse andre kvotientene og restene er akkurat de samme. Dette bevise entydigheten til q og r, og beviset er ferdig.