Divisjonsalgoritmen: Forskjell mellom sideversjoner
Ingen redigeringsforklaring |
|||
| (4 mellomliggende versjoner av 3 brukere er ikke vist) | |||
| Linje 4: | Linje 4: | ||
Divisjonsalgoritmen sier at for to heltall ''a'' og ''b'' > 0, så eksisterer det unike heltall ''q'' og ''r'' slik at | Divisjonsalgoritmen sier at for to heltall ''a'' og ''b'' > 0, så eksisterer det unike heltall ''q'' og ''r'' slik at | ||
< | <math>a=qb+r \;\;\; \textrm{der} \;\;\; 0 \leq r < b</math> | ||
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''. | 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== | ==Eksempler== | ||
* Hvis ''a'' = 14 og ''b'' = 6, da er kvotienten 2 og resten 2 siden < | * Hvis ''a'' = 14 og ''b'' = 6, da er kvotienten 2 og resten 2 siden <math>14=2 \cdot 6 + 2</math>. | ||
* Hvis dividenden er 35 og divisoren er 7, så er ''q'' = 5 og ''r'' = 0 siden < | * Hvis dividenden er 35 og divisoren er 7, så er ''q'' = 5 og ''r'' = 0 siden <math>35 = 5 \cdot 7 + 0</math>. Når resten er 0, sier vi at ''b'' ''deler'' ''a''. | ||
==Bevis== | ==Bevis== | ||
| Linje 18: | Linje 18: | ||
La ''a'' og ''b'' > 0 være vilkårlige heltall. Betrakt mengden | La ''a'' og ''b'' > 0 være vilkårlige heltall. Betrakt mengden | ||
< | <math>S = \{ a-xb \, | \, x \in \mathbb{Z} \: \textrm{og} \: a-xb \geq 0 \}</math> | ||
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 | 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 | ||
< | <math>a-xb = a-(-|a|)b = a+|a|b \geq a+|a| \geq 0</math> | ||
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 | 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 | ||
< | <math>a = qb+r \;\; \textrm{der} \;\; r \geq 0</math> | ||
Nå gjenstår det å vise at ''r'' < ''b''. La oss anta det motsatte, nemlig at ''r'' ≥ ''b''. Betrakt så tallet | Nå gjenstår det å vise at ''r'' < ''b''. La oss anta det motsatte, nemlig at ''r'' ≥ ''b''. Betrakt så tallet | ||
< | <math>a-(q+1)b=(a-qb)-b=r-b \geq 0 \;\; \Leftrightarrow \;\; r \geq b </math> | ||
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''. | 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''. | ||
| Linje 36: | Linje 36: | ||
Vi har altså at for to vilkårlige heltall ''a'' og ''b'' > 0, så eksisterer det heltall ''q'' og ''r'' slik at | Vi har altså at for to vilkårlige heltall ''a'' og ''b'' > 0, så eksisterer det heltall ''q'' og ''r'' slik at | ||
< | <math>a=qb+r \;\; \textrm{der} \;\; 0 \leq r < b</math> | ||
Nå gjenstår det å vise at ''q'' og ''r'' er unike. | Nå gjenstår det å vise at ''q'' og ''r'' er unike. | ||
| Linje 43: | Linje 43: | ||
Anta at ''a'' har to representasjoner: ''a'' = ''qb'' + ''r'' = ''q'b'' + ''r' '', hvor 0 ≤ ''r'' < ''b'' og 0 ≤ ''r' '' < ''b''. Dette gir | Anta at ''a'' har to representasjoner: ''a'' = ''qb'' + ''r'' = ''q'b'' + ''r' '', hvor 0 ≤ ''r'' < ''b'' og 0 ≤ ''r' '' < ''b''. Dette gir | ||
< | <math>r-r' = q'b-qb = b(q'-q) </math> | ||
Tar vi absoluttverdien av begge sider, får vi | Tar vi absoluttverdien av begge sider, får vi | ||
< | <math>|r-r'| = |b(q'-q)|=b|q'-q|</math> | ||
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 | 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 | ||
< | <math> -b+0 < -r'+ r < 0 + b \;\; \Rightarrow \;\; -b < r'-r < b \;\; \Rightarrow \;\; |r'-r|< b </math> | ||
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å | 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å | ||
< | <math>0 \leq |q'-q|<1 </math> | ||
Altså er eneste mulighet at |''q' '' - ''q''| = 0, som gir ''q' '' = ''q''. Men da må | Altså er eneste mulighet at |''q' '' - ''q''| = 0, som gir ''q' '' = ''q''. Men da må | ||
< | <math> |r-r'| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </math> | ||
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 | 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. | ||
Siste sideversjon per 24. apr. 2013 kl. 12:08
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
<math>a=qb+r \;\;\; \textrm{der} \;\;\; 0 \leq r < b</math>
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 <math>14=2 \cdot 6 + 2</math>.
- Hvis dividenden er 35 og divisoren er 7, så er q = 5 og r = 0 siden <math>35 = 5 \cdot 7 + 0</math>. 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
<math>S = \{ a-xb \, | \, x \in \mathbb{Z} \: \textrm{og} \: a-xb \geq 0 \}</math>
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
<math>a-xb = a-(-|a|)b = a+|a|b \geq a+|a| \geq 0</math>
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
<math>a = qb+r \;\; \textrm{der} \;\; r \geq 0</math>
Nå gjenstår det å vise at r < b. La oss anta det motsatte, nemlig at r ≥ b. Betrakt så tallet
<math>a-(q+1)b=(a-qb)-b=r-b \geq 0 \;\; \Leftrightarrow \;\; r \geq b </math>
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
<math>a=qb+r \;\; \textrm{der} \;\; 0 \leq r < b</math>
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
<math>r-r' = q'b-qb = b(q'-q) </math>
Tar vi absoluttverdien av begge sider, får vi
<math>|r-r'| = |b(q'-q)|=b|q'-q|</math>
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
<math> -b+0 < -r'+ r < 0 + b \;\; \Rightarrow \;\; -b < r'-r < b \;\; \Rightarrow \;\; |r'-r|< b </math>
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å
<math>0 \leq |q'-q|<1 </math>
Altså er eneste mulighet at |q' - q| = 0, som gir q' = q. Men da må
<math> |r-r'| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </math>
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.