Divisjonsalgoritmen - Sideversjonshistorikk

Vaktmester på 24. apr. 2013 kl. 12:08

2013-04-24T12:08:40Z

← Eldre sideversjon		Sideversjonen fra 24. apr. 2013 kl. 12:08
Linje 51:		Linje 51:
	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>		<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å

Administrator: /* Formelt utsagn */

2013-04-23T13:00:10Z

Formelt utsagn

← Eldre sideversjon		Sideversjonen fra 23. apr. 2013 kl. 13:00
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=qr+b \;\;\; \textrm{der} \;\;\; 0 \leq r < b</math>		<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''.

Vaktmester: Teksterstatting – «» til «»

2013-02-05T20:58:32Z

Teksterstatting – «</tex>» til «</math>»

Vaktmester: Teksterstatting – «» til « $»$

2013-02-05T20:56:55Z

Teksterstatting – «<tex>» til «<math>»

Svinepels: /* Entydighet */

2011-10-01T11:22:28Z

Entydighet

← Eldre sideversjon		Sideversjonen fra 1. okt. 2011 kl. 11:22
Linje 61:		Linje 61:
	<tex> \|r-r'\| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </tex>		<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.		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.

Svinepels: /* Entydighet */

2011-10-01T11:22:12Z

Entydighet

← Eldre sideversjon		Sideversjonen fra 1. okt. 2011 kl. 11:22
Linje 61:		Linje 61:
	<tex> \|r-r'\| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </tex>		<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.		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.

Svinepels: /* Eksistens */

2011-10-01T11:19:40Z

Eksistens

← Eldre sideversjon		Sideversjonen fra 1. okt. 2011 kl. 11:19
Linje 28:		Linje 28:
	<tex>a = qb+r \;\; \textrm{der} \;\; r \geq 0</tex>		<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		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>		<tex>a-(q+1)b=(a-qb)-b=r-b \geq 0 \;\; \Leftrightarrow \;\; r \geq b </tex>

Svinepels: Ny side: 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 divi...

2011-09-30T22:47:04Z

Ny side: 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 divi...

Ny side

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 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.

← Eldre sideversjon		Sideversjonen fra 5. feb. 2013 kl. 20:58
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=qr+b \;\;\; \textrm{der} \;\;\; 0 \leq r < b</~~tex~~>		<math>a=qr+b \;\;\; \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 <math>14=2 \cdot 6 + 2</~~tex~~>.		* 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</~~tex~~>. Når resten er 0, sier vi at ''b'' ''deler'' ''a''.		* 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 \}</~~tex~~>		<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</~~tex~~>		<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</~~tex~~>		<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 </~~tex~~>		<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</~~tex~~>		<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) </~~tex~~>		<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\|</~~tex~~>		<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 </~~tex~~>		<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 </~~tex~~>		<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 </~~tex~~>		<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.		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.

← Eldre sideversjon		Sideversjonen fra 5. feb. 2013 kl. 20:56
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

	<~~tex~~>a=qr+b \;\;\; \textrm{der} \;\;\; 0 \leq r < b</tex>		<math>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''.		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 <~~tex~~>14=2 \cdot 6 + 2</tex>.		* Hvis ''a'' = 14 og ''b'' = 6, da er kvotienten 2 og resten 2 siden <math>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''.		* Hvis dividenden er 35 og divisoren er 7, så er ''q'' = 5 og ''r'' = 0 siden <math>35 = 5 \cdot 7 + 0</tex>. 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

	<~~tex~~>S = \{ a-xb \, \| \, x \in \mathbb{Z} \: \textrm{og} \: a-xb \geq 0 \}</tex>		<math>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		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>		<math>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		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>		<math>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		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>		<math>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''.		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

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

	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

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

	Tar vi absoluttverdien av begge sider, får vi		Tar vi absoluttverdien av begge sider, får vi

	<~~tex~~>\|r-r'\| = \|b(q'-q)\|=b\|q'-q\|</tex>		<math>\|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		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>		<math> -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å		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>		<math>0 \leq \|q'-q\|<1 </tex>

	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å

	<~~tex~~> \|r-r'\| = b \cdot 0 = 0 \;\; \Rightarrow \;\; r'=r </tex>		<math> \|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 bekrefter entydigheten til ''q'' og ''r'', og beviset er ferdig.		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.