Divisjonsalgoritmen

Fra Matematikk.net
Sideversjon per 5. feb. 2013 kl. 20:58 av Vaktmester (diskusjon | bidrag) (Teksterstatting – «</tex>» til «</math>»)
Hopp til: navigasjon, søk

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

a=qr+bder0r<b

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 14=26+2.
  • Hvis dividenden er 35 og divisoren er 7, så er q = 5 og r = 0 siden 35=57+0. 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

S={axb|xZogaxb0}

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

axb=a(|a|)b=a+|a|ba+|a|0

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

a=qb+rderr0

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

a(q+1)b=(aqb)b=rb0rb

Antakelsen vår om at rb 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 rb, 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

a=qb+rder0r<b

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

rr=qbqb=b(qq)

Tar vi absoluttverdien av begge sider, får vi

|rr|=|b(qq)|=b|qq|

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

b+0<r+r<0+bb<rr<b|rr|<b

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å

0|qq|<1

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

|rr|=b0=0r=r

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.