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
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
. - Hvis dividenden er 35 og divisoren er 7, så er q = 5 og r = 0 siden
. 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
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
Nå gjenstår det å vise at r < b. La oss anta det motsatte, nemlig at r ≥ b. Betrakt så tallet
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
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å
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 bekrefter entydigheten til q og r, og beviset er ferdig.