Største felles divisor og Euklids algoritme - Sideversjonshistorikk

Skf95: /* Største felles divisor / fra 32*2 til 223

2014-01-17T23:53:41Z

Største felles divisor: fra 3*2*2 til 2*2*3

← Eldre sideversjon		Sideversjonen fra 17. jan. 2014 kl. 23:53
Linje 1:		Linje 1:
	== Største felles divisor ==		== Største felles divisor ==

	Tallene 12 og 18 kan faktoriseres som <math>12 = 3 \cdot 2 \cdot 2</math> og <math>18 = 2 \cdot 3 \cdot 3</math>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <math>\text{gcd}(12,18) = 6</math>. <math>\text{gcd}</math> er en engelsk forkortelse for ''"greatest common divisor"''.		Tallene 12 og 18 kan faktoriseres som <math>12 = 2 \cdot 2 \cdot 3</math> og <math>18 = 2 \cdot 3 \cdot 3</math>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <math>\text{gcd}(12,18) = 6</math>. <math>\text{gcd}</math> er en engelsk forkortelse for ''"greatest common divisor"''.

	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">

Skf95: /* Største felles divisor */ Feil faktorisert.

2014-01-17T23:52:56Z

Største felles divisor: Feil faktorisert.

← Eldre sideversjon		Sideversjonen fra 17. jan. 2014 kl. 23:52
Linje 1:		Linje 1:
	== Største felles divisor ==		== Største felles divisor ==

	Tallene 12 og 18 kan faktoriseres som <math>12 = 2 \cdot 2 \cdot 2</math> og <math>18 = 2 \cdot 3 \cdot 3</math>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <math>\text{gcd}(12,18) = 6</math>. <math>\text{gcd}</math> er en engelsk forkortelse for ''"greatest common divisor"''.		Tallene 12 og 18 kan faktoriseres som <math>12 = 3 \cdot 2 \cdot 2</math> og <math>18 = 2 \cdot 3 \cdot 3</math>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <math>\text{gcd}(12,18) = 6</math>. <math>\text{gcd}</math> er en engelsk forkortelse for ''"greatest common divisor"''.

	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">

Vaktmester: Teksterstatting – «» til «»

2013-02-05T20:59:24Z

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

← Eldre sideversjon		Sideversjonen fra 5. feb. 2013 kl. 20:59
Linje 1:		Linje 1:
	== Største felles divisor ==		== Største felles divisor ==

	Tallene 12 og 18 kan faktoriseres som <math>12 = 2 \cdot 2 \cdot 2</~~tex~~> og <math>18 = 2 \cdot 3 \cdot 3</~~tex~~>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <math>\text{gcd}(12,18) = 6</~~tex~~>. <math>\text{gcd}</~~tex~~> er en engelsk forkortelse for ''"greatest common divisor"''.		Tallene 12 og 18 kan faktoriseres som <math>12 = 2 \cdot 2 \cdot 2</math> og <math>18 = 2 \cdot 3 \cdot 3</math>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <math>\text{gcd}(12,18) = 6</math>. <math>\text{gcd}</math> er en engelsk forkortelse for ''"greatest common divisor"''.

	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	:'''Største felles divisor'''		:'''Største felles divisor'''
	: Dersom vi har to heltall <math>a</~~tex~~> og <math>b</~~tex~~> og <math>n</~~tex~~> er det største tallet som er sånn at <math>n \| a</~~tex~~> og <math>n \| b</~~tex~~> så sier vi at <math>n</~~tex~~> er ''største felles divisor'' mellom <math>a</~~tex~~> og <math>b</~~tex~~>, og vi skriver		: Dersom vi har to heltall <math>a</math> og <math>b</math> og <math>n</math> er det største tallet som er sånn at <math>n \| a</math> og <math>n \| b</math> så sier vi at <math>n</math> er ''største felles divisor'' mellom <math>a</math> og <math>b</math>, og vi skriver

	::<math>\text{gcd}(a,b) = n</~~tex~~>		::<math>\text{gcd}(a,b) = n</math>

	: Noen norske bøker skriver i stedet <math>\text{sff}(a,b)</~~tex~~> der sff er en forkortelse for ''"største felles faktor"'', mens andre skriver <math>\text{sfd}(a,b)</~~tex~~> der sfd står for ''"største felles divisor"''.		: Noen norske bøker skriver i stedet <math>\text{sff}(a,b)</math> der sff er en forkortelse for ''"største felles faktor"'', mens andre skriver <math>\text{sfd}(a,b)</math> der sfd står for ''"største felles divisor"''.
	:		:
	</blockquote>		</blockquote>
Linje 17:		Linje 17:
	<blockquote style="padding: 1em; border: 1px red; background-color: #EED5D2;">		<blockquote style="padding: 1em; border: 1px red; background-color: #EED5D2;">
	:'''Eksempel'''		:'''Eksempel'''
	: Finn <math>\text{gcd}(14,84)</~~tex~~>.		: Finn <math>\text{gcd}(14,84)</math>.

	: Vi starter med å faktorisere hvert tall. Vi får da:		: Vi starter med å faktorisere hvert tall. Vi får da:

	::<math>14 = 2 \cdot 7</~~tex~~>		::<math>14 = 2 \cdot 7</math>

	::<math>84 = 2 \cdot 42 = 2 \cdot 6 \cdot 7 = 2 \cdot 2 \cdot 3 \cdot 7</~~tex~~>		::<math>84 = 2 \cdot 42 = 2 \cdot 6 \cdot 7 = 2 \cdot 2 \cdot 3 \cdot 7</math>

	: Vi ser at 2 og 7 er faktorer i begge tallene. Da må <math>\text{gcd}(14,84) = 2 \cdot 7 = 14</~~tex~~>.		: Vi ser at 2 og 7 er faktorer i begge tallene. Da må <math>\text{gcd}(14,84) = 2 \cdot 7 = 14</math>.
	</blockquote>		</blockquote>

Linje 32:		Linje 32:
	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	:'''Største felles divisor'''		:'''Største felles divisor'''
	: Hvis <math>a > b</~~tex~~> og <math>r</~~tex~~> er resten vi får når vi deler <math>a</~~tex~~> på <math>b</~~tex~~> så er		: Hvis <math>a > b</math> og <math>r</math> er resten vi får når vi deler <math>a</math> på <math>b</math> så er

	::<math>\text{gcd}(a,b) = \text{gcd}(b,r)</~~tex~~>.		::<math>\text{gcd}(a,b) = \text{gcd}(b,r)</math>.

	:'''Bevis'''		:'''Bevis'''
Linje 40:		Linje 40:
	: Vi har fra divisjonsalgoritmen at		: Vi har fra divisjonsalgoritmen at

	:: <math>a = bn + r</~~tex~~>, der <math>n</~~tex~~> er et naturlig tall.		:: <math>a = bn + r</math>, der <math>n</math> er et naturlig tall.

	: La <math>d = \text{gcd}(a,b)</~~tex~~>. Da er <math>d \| a</~~tex~~> og <math>d \| b</~~tex~~>, eller med andre ord kan vi finne to hele tall <math>s</~~tex~~> og <math>t</~~tex~~> slik at <math>a = sd</~~tex~~> og <math>b = td</~~tex~~>. Men da har vi at		: La <math>d = \text{gcd}(a,b)</math>. Da er <math>d \| a</math> og <math>d \| b</math>, eller med andre ord kan vi finne to hele tall <math>s</math> og <math>t</math> slik at <math>a = sd</math> og <math>b = td</math>. Men da har vi at
	:: <math>sd = tdn + r \ \Leftrightarrow \ r = (s-nt)d</~~tex~~>,		:: <math>sd = tdn + r \ \Leftrightarrow \ r = (s-nt)d</math>,
	: altså er <math>d</~~tex~~> også en faktor i <math>r</~~tex~~>. Da må <math>d \| \text{gcd}(b,r)</~~tex~~>. Nå gjenstår det å vise at <math>d</~~tex~~> er den ''største'' felles faktoren mellom <math>b</~~tex~~> og <math>r</~~tex~~>. Vi kan gjøre det med et motsigelsesbevis. Anta at <math>\text{gcd}(b,r) = dd^\prime</~~tex~~>, der <math>d^\prime > 1</~~tex~~>. Vi antar altså at i tillegg til <math>d</~~tex~~> har <math>b</~~tex~~> og <math>r</~~tex~~> også en faktor <math>d^\prime</~~tex~~> felles. Nå ser vi hva det vil føre til. Vi har at		: altså er <math>d</math> også en faktor i <math>r</math>. Da må <math>d \| \text{gcd}(b,r)</math>. Nå gjenstår det å vise at <math>d</math> er den ''største'' felles faktoren mellom <math>b</math> og <math>r</math>. Vi kan gjøre det med et motsigelsesbevis. Anta at <math>\text{gcd}(b,r) = dd^\prime</math>, der <math>d^\prime > 1</math>. Vi antar altså at i tillegg til <math>d</math> har <math>b</math> og <math>r</math> også en faktor <math>d^\prime</math> felles. Nå ser vi hva det vil føre til. Vi har at
	:: <math>a = bn + r = s^\prime dd^\prime + t^\prime dd^\prime = (s^\prime + t^\prime)dd^\prime</~~tex~~>.		:: <math>a = bn + r = s^\prime dd^\prime + t^\prime dd^\prime = (s^\prime + t^\prime)dd^\prime</math>.
	: Dette er umulig, for da må <math>d d^\prime \| a</~~tex~~>, slik at <math>\text{gcd}(a,b) = d d^\prime</~~tex~~>. Det strider i mot vårt valg av at <math>d = \text{gcd}(a,b)</~~tex~~>.		: Dette er umulig, for da må <math>d d^\prime \| a</math>, slik at <math>\text{gcd}(a,b) = d d^\prime</math>. Det strider i mot vårt valg av at <math>d = \text{gcd}(a,b)</math>.
	: Resultatet blir at <math>d</~~tex~~> er største felles faktor mellom <math>b</~~tex~~> og <math>r</~~tex~~>, eller sagt med andre ord:		: Resultatet blir at <math>d</math> er største felles faktor mellom <math>b</math> og <math>r</math>, eller sagt med andre ord:
	:: <math>d = \text{gcd}(a,b) = \text{gcd}(b,r)</~~tex~~>.		:: <math>d = \text{gcd}(a,b) = \text{gcd}(b,r)</math>.
	</blockquote>		</blockquote>

	Nå kan vi bruke Euklids algoritme til å finne største felles faktor mellom to tall.		Nå kan vi bruke Euklids algoritme til å finne største felles faktor mellom to tall.

Vaktmester: Teksterstatting – «» til « $»$

2013-02-05T20:58:01Z

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

← Eldre sideversjon		Sideversjonen fra 5. feb. 2013 kl. 20:58
Linje 1:		Linje 1:
	== Største felles divisor ==		== Største felles divisor ==

	Tallene 12 og 18 kan faktoriseres som <~~tex~~>12 = 2 \cdot 2 \cdot 2</tex> og <~~tex~~>18 = 2 \cdot 3 \cdot 3</tex>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <~~tex~~>\text{gcd}(12,18) = 6</tex>. <~~tex~~>\text{gcd}</tex> er en engelsk forkortelse for ''"greatest common divisor"''.		Tallene 12 og 18 kan faktoriseres som <math>12 = 2 \cdot 2 \cdot 2</tex> og <math>18 = 2 \cdot 3 \cdot 3</tex>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <math>\text{gcd}(12,18) = 6</tex>. <math>\text{gcd}</tex> er en engelsk forkortelse for ''"greatest common divisor"''.

	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	:'''Største felles divisor'''		:'''Største felles divisor'''
	: Dersom vi har to heltall <~~tex~~>a</tex> og <~~tex~~>b</tex> og <~~tex~~>n</tex> er det største tallet som er sånn at <~~tex~~>n \| a</tex> og <~~tex~~>n \| b</tex> så sier vi at <~~tex~~>n</tex> er ''største felles divisor'' mellom <~~tex~~>a</tex> og <~~tex~~>b</tex>, og vi skriver		: Dersom vi har to heltall <math>a</tex> og <math>b</tex> og <math>n</tex> er det største tallet som er sånn at <math>n \| a</tex> og <math>n \| b</tex> så sier vi at <math>n</tex> er ''største felles divisor'' mellom <math>a</tex> og <math>b</tex>, og vi skriver

	::<~~tex~~>\text{gcd}(a,b) = n</tex>		::<math>\text{gcd}(a,b) = n</tex>

	: Noen norske bøker skriver i stedet <~~tex~~>\text{sff}(a,b)</tex> der sff er en forkortelse for ''"største felles faktor"'', mens andre skriver <~~tex~~>\text{sfd}(a,b)</tex> der sfd står for ''"største felles divisor"''.		: Noen norske bøker skriver i stedet <math>\text{sff}(a,b)</tex> der sff er en forkortelse for ''"største felles faktor"'', mens andre skriver <math>\text{sfd}(a,b)</tex> der sfd står for ''"største felles divisor"''.
	:		:
	</blockquote>		</blockquote>
Linje 17:		Linje 17:
	<blockquote style="padding: 1em; border: 1px red; background-color: #EED5D2;">		<blockquote style="padding: 1em; border: 1px red; background-color: #EED5D2;">
	:'''Eksempel'''		:'''Eksempel'''
	: Finn <~~tex~~>\text{gcd}(14,84)</tex>.		: Finn <math>\text{gcd}(14,84)</tex>.

	: Vi starter med å faktorisere hvert tall. Vi får da:		: Vi starter med å faktorisere hvert tall. Vi får da:

	::<~~tex~~>14 = 2 \cdot 7</tex>		::<math>14 = 2 \cdot 7</tex>

	::<~~tex~~>84 = 2 \cdot 42 = 2 \cdot 6 \cdot 7 = 2 \cdot 2 \cdot 3 \cdot 7</tex>		::<math>84 = 2 \cdot 42 = 2 \cdot 6 \cdot 7 = 2 \cdot 2 \cdot 3 \cdot 7</tex>

	: Vi ser at 2 og 7 er faktorer i begge tallene. Da må <~~tex~~>\text{gcd}(14,84) = 2 \cdot 7 = 14</tex>.		: Vi ser at 2 og 7 er faktorer i begge tallene. Da må <math>\text{gcd}(14,84) = 2 \cdot 7 = 14</tex>.
	</blockquote>		</blockquote>

Linje 32:		Linje 32:
	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	:'''Største felles divisor'''		:'''Største felles divisor'''
	: Hvis <~~tex~~>a > b</tex> og <~~tex~~>r</tex> er resten vi får når vi deler <~~tex~~>a</tex> på <~~tex~~>b</tex> så er		: Hvis <math>a > b</tex> og <math>r</tex> er resten vi får når vi deler <math>a</tex> på <math>b</tex> så er

	::<~~tex~~>\text{gcd}(a,b) = \text{gcd}(b,r)</tex>.		::<math>\text{gcd}(a,b) = \text{gcd}(b,r)</tex>.

	:'''Bevis'''		:'''Bevis'''
Linje 40:		Linje 40:
	: Vi har fra divisjonsalgoritmen at		: Vi har fra divisjonsalgoritmen at

	:: <~~tex~~>a = bn + r</tex>, der <~~tex~~>n</tex> er et naturlig tall.		:: <math>a = bn + r</tex>, der <math>n</tex> er et naturlig tall.

	: La <~~tex~~>d = \text{gcd}(a,b)</tex>. Da er <~~tex~~>d \| a</tex> og <~~tex~~>d \| b</tex>, eller med andre ord kan vi finne to hele tall <~~tex~~>s</tex> og <~~tex~~>t</tex> slik at <~~tex~~>a = sd</tex> og <~~tex~~>b = td</tex>. Men da har vi at		: La <math>d = \text{gcd}(a,b)</tex>. Da er <math>d \| a</tex> og <math>d \| b</tex>, eller med andre ord kan vi finne to hele tall <math>s</tex> og <math>t</tex> slik at <math>a = sd</tex> og <math>b = td</tex>. Men da har vi at
	:: <~~tex~~>sd = tdn + r \ \Leftrightarrow \ r = (s-nt)d</tex>,		:: <math>sd = tdn + r \ \Leftrightarrow \ r = (s-nt)d</tex>,
	: altså er <~~tex~~>d</tex> også en faktor i <~~tex~~>r</tex>. Da må <~~tex~~>d \| \text{gcd}(b,r)</tex>. Nå gjenstår det å vise at <~~tex~~>d</tex> er den ''største'' felles faktoren mellom <~~tex~~>b</tex> og <~~tex~~>r</tex>. Vi kan gjøre det med et motsigelsesbevis. Anta at <~~tex~~>\text{gcd}(b,r) = dd^\prime</tex>, der <~~tex~~>d^\prime > 1</tex>. Vi antar altså at i tillegg til <~~tex~~>d</tex> har <~~tex~~>b</tex> og <~~tex~~>r</tex> også en faktor <~~tex~~>d^\prime</tex> felles. Nå ser vi hva det vil føre til. Vi har at		: altså er <math>d</tex> også en faktor i <math>r</tex>. Da må <math>d \| \text{gcd}(b,r)</tex>. Nå gjenstår det å vise at <math>d</tex> er den ''største'' felles faktoren mellom <math>b</tex> og <math>r</tex>. Vi kan gjøre det med et motsigelsesbevis. Anta at <math>\text{gcd}(b,r) = dd^\prime</tex>, der <math>d^\prime > 1</tex>. Vi antar altså at i tillegg til <math>d</tex> har <math>b</tex> og <math>r</tex> også en faktor <math>d^\prime</tex> felles. Nå ser vi hva det vil føre til. Vi har at
	:: <~~tex~~>a = bn + r = s^\prime dd^\prime + t^\prime dd^\prime = (s^\prime + t^\prime)dd^\prime</tex>.		:: <math>a = bn + r = s^\prime dd^\prime + t^\prime dd^\prime = (s^\prime + t^\prime)dd^\prime</tex>.
	: Dette er umulig, for da må <~~tex~~>d d^\prime \| a</tex>, slik at <~~tex~~>\text{gcd}(a,b) = d d^\prime</tex>. Det strider i mot vårt valg av at <~~tex~~>d = \text{gcd}(a,b)</tex>.		: Dette er umulig, for da må <math>d d^\prime \| a</tex>, slik at <math>\text{gcd}(a,b) = d d^\prime</tex>. Det strider i mot vårt valg av at <math>d = \text{gcd}(a,b)</tex>.
	: Resultatet blir at <~~tex~~>d</tex> er største felles faktor mellom <~~tex~~>b</tex> og <~~tex~~>r</tex>, eller sagt med andre ord:		: Resultatet blir at <math>d</tex> er største felles faktor mellom <math>b</tex> og <math>r</tex>, eller sagt med andre ord:
	:: <~~tex~~>d = \text{gcd}(a,b) = \text{gcd}(b,r)</tex>.		:: <math>d = \text{gcd}(a,b) = \text{gcd}(b,r)</tex>.
	</blockquote>		</blockquote>

	Nå kan vi bruke Euklids algoritme til å finne største felles faktor mellom to tall.		Nå kan vi bruke Euklids algoritme til å finne største felles faktor mellom to tall.

Vektormannen på 12. nov. 2012 kl. 14:14

2012-11-12T14:14:48Z

← Eldre sideversjon		Sideversjonen fra 12. nov. 2012 kl. 14:14
Linje 3:		Linje 3:
	Tallene 12 og 18 kan faktoriseres som <tex>12 = 2 \cdot 2 \cdot 2</tex> og <tex>18 = 2 \cdot 3 \cdot 3</tex>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <tex>\text{gcd}(12,18) = 6</tex>. <tex>\text{gcd}</tex> er en engelsk forkortelse for ''"greatest common divisor"''.		Tallene 12 og 18 kan faktoriseres som <tex>12 = 2 \cdot 2 \cdot 2</tex> og <tex>18 = 2 \cdot 3 \cdot 3</tex>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <tex>\text{gcd}(12,18) = 6</tex>. <tex>\text{gcd}</tex> er en engelsk forkortelse for ''"greatest common divisor"''.

	<blockquote style="padding: 1em; border: ~~3px dotted~~ blue;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	:'''Største felles divisor'''		:'''Største felles divisor'''
	: Dersom vi har to heltall <tex>a</tex> og <tex>b</tex> og <tex>n</tex> er det største tallet som er sånn at <tex>n \| a</tex> og <tex>n \| b</tex> så sier vi at <tex>n</tex> er ''største felles divisor'' mellom <tex>a</tex> og <tex>b</tex>, og vi skriver		: Dersom vi har to heltall <tex>a</tex> og <tex>b</tex> og <tex>n</tex> er det største tallet som er sånn at <tex>n \| a</tex> og <tex>n \| b</tex> så sier vi at <tex>n</tex> er ''største felles divisor'' mellom <tex>a</tex> og <tex>b</tex>, og vi skriver
Linje 15:		Linje 15:
	Når vi skal finne største felles divisor mellom to tall gjør vi slik som innledningsvis ovenfor. Vi faktoriserer hvert tall og ser hvilke faktorer som er felles mellom de to tallene. Produktet av alle faktorene som er felles vil da være største felles divisor.		Når vi skal finne største felles divisor mellom to tall gjør vi slik som innledningsvis ovenfor. Vi faktoriserer hvert tall og ser hvilke faktorer som er felles mellom de to tallene. Produktet av alle faktorene som er felles vil da være største felles divisor.

	<blockquote style="padding: 1em; border: ~~3px dotted~~ red;">		<blockquote style="padding: 1em; border: 1px red; background-color: #EED5D2;">
	:'''Eksempel'''		:'''Eksempel'''
	: Finn <tex>\text{gcd}(14,84)</tex>.		: Finn <tex>\text{gcd}(14,84)</tex>.
Linje 28:		Linje 28:
	</blockquote>		</blockquote>

	For å regne ut største felles divisor trenger vi altså å faktorisere hvert tall. Dersom man skal finne største felles divisor til to ganske store tall, kan dette fort bli en utfordring. Under skal vi se på en ''algoritme'' som gjør det ganske enkelt for oss å finne største felles divisor uten å faktorisere. Først skal vi se på ~~noen egenskaper~~ ved største felles divisor som gjør oss i stand til å forstå hvorfor algoritmen fungerer.		For å regne ut største felles divisor trenger vi altså å faktorisere hvert tall. Dersom man skal finne største felles divisor til to ganske store tall, kan dette fort bli en utfordring. Under skal vi se på en ''algoritme'' som gjør det ganske enkelt for oss å finne største felles divisor uten å faktorisere. Først skal vi se på en viktig egenskap ved største felles divisor som gjør oss i stand til å forstå hvorfor algoritmen fungerer.

	== ~~Egenskaper ved~~ største felles ~~divisor~~ ==		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
			:'''Største felles divisor'''
			: Hvis <tex>a > b</tex> og <tex>r</tex> er resten vi får når vi deler <tex>a</tex> på <tex>b</tex> så er

			::<tex>\text{gcd}(a,b) = \text{gcd}(b,r)</tex>.

			:'''Bevis'''

			: Vi har fra divisjonsalgoritmen at

			:: <tex>a = bn + r</tex>, der <tex>n</tex> er et naturlig tall.

			: La <tex>d = \text{gcd}(a,b)</tex>. Da er <tex>d \| a</tex> og <tex>d \| b</tex>, eller med andre ord kan vi finne to hele tall <tex>s</tex> og <tex>t</tex> slik at <tex>a = sd</tex> og <tex>b = td</tex>. Men da har vi at
			:: <tex>sd = tdn + r \ \Leftrightarrow \ r = (s-nt)d</tex>,
			: altså er <tex>d</tex> også en faktor i <tex>r</tex>. Da må <tex>d \| \text{gcd}(b,r)</tex>. Nå gjenstår det å vise at <tex>d</tex> er den ''største'' felles faktoren mellom <tex>b</tex> og <tex>r</tex>. Vi kan gjøre det med et motsigelsesbevis. Anta at <tex>\text{gcd}(b,r) = dd^\prime</tex>, der <tex>d^\prime > 1</tex>. Vi antar altså at i tillegg til <tex>d</tex> har <tex>b</tex> og <tex>r</tex> også en faktor <tex>d^\prime</tex> felles. Nå ser vi hva det vil føre til. Vi har at
			:: <tex>a = bn + r = s^\prime dd^\prime + t^\prime dd^\prime = (s^\prime + t^\prime)dd^\prime</tex>.
			: Dette er umulig, for da må <tex>d d^\prime \| a</tex>, slik at <tex>\text{gcd}(a,b) = d d^\prime</tex>. Det strider i mot vårt valg av at <tex>d = \text{gcd}(a,b)</tex>.
			: Resultatet blir at <tex>d</tex> er største felles faktor mellom <tex>b</tex> og <tex>r</tex>, eller sagt med andre ord:
			:: <tex>d = \text{gcd}(a,b) = \text{gcd}(b,r)</tex>.
			</blockquote>

			Nå kan vi bruke Euklids algoritme til å finne største felles faktor mellom to tall.

Vektormannen: /* Største felles divisor */

2011-12-06T19:57:58Z

Største felles divisor

← Eldre sideversjon		Sideversjonen fra 6. des. 2011 kl. 19:57
Linje 8:		Linje 8:

	::<tex>\text{gcd}(a,b) = n</tex>		::<tex>\text{gcd}(a,b) = n</tex>

			: Noen norske bøker skriver i stedet <tex>\text{sff}(a,b)</tex> der sff er en forkortelse for ''"største felles faktor"'', mens andre skriver <tex>\text{sfd}(a,b)</tex> der sfd står for ''"største felles divisor"''.
			:
	</blockquote>		</blockquote>

Vektormannen: Ny side: == Største felles divisor == Tallene 12 og 18 kan faktoriseres som 12 = 2 \cdot 2 \cdot 2 og 18 = 2 \cdot 3 \cdot 3. Vi ser at begge tallene har 2 og 3 som faktorer....

2011-09-24T14:42:34Z

Ny side: == Største felles divisor == Tallene 12 og 18 kan faktoriseres som <tex>12 = 2 \cdot 2 \cdot 2</tex> og <tex>18 = 2 \cdot 3 \cdot 3</tex>. Vi ser at begge tallene har 2 og 3 som faktorer....

Ny side

== Største felles divisor ==

Tallene 12 og 18 kan faktoriseres som <tex>12 = 2 \cdot 2 \cdot 2</tex> og <tex>18 = 2 \cdot 3 \cdot 3</tex>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den ''største'' faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er ''største felles divisor'' mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <tex>\text{gcd}(12,18) = 6</tex>. <tex>\text{gcd}</tex> er en engelsk forkortelse for ''"greatest common divisor"''.

<blockquote style="padding: 1em; border: 3px dotted blue;">
:'''Største felles divisor'''
: Dersom vi har to heltall <tex>a</tex> og <tex>b</tex> og <tex>n</tex> er det største tallet som er sånn at <tex>n | a</tex> og <tex>n | b</tex> så sier vi at <tex>n</tex> er ''største felles divisor'' mellom <tex>a</tex> og <tex>b</tex>, og vi skriver

::<tex>\text{gcd}(a,b) = n</tex>
</blockquote>

Når vi skal finne største felles divisor mellom to tall gjør vi slik som innledningsvis ovenfor. Vi faktoriserer hvert tall og ser hvilke faktorer som er felles mellom de to tallene. Produktet av alle faktorene som er felles vil da være største felles divisor.

<blockquote style="padding: 1em; border: 3px dotted red;">
:'''Eksempel'''
: Finn <tex>\text{gcd}(14,84)</tex>.

: Vi starter med å faktorisere hvert tall. Vi får da:

::<tex>14 = 2 \cdot 7</tex>

::<tex>84 = 2 \cdot 42 = 2 \cdot 6 \cdot 7 = 2 \cdot 2 \cdot 3 \cdot 7</tex>

: Vi ser at 2 og 7 er faktorer i begge tallene. Da må <tex>\text{gcd}(14,84) = 2 \cdot 7 = 14</tex>.
</blockquote>

For å regne ut største felles divisor trenger vi altså å faktorisere hvert tall. Dersom man skal finne største felles divisor til to ganske store tall, kan dette fort bli en utfordring. Under skal vi se på en ''algoritme'' som gjør det ganske enkelt for oss å finne største felles divisor uten å faktorisere. Først skal vi se på noen egenskaper ved største felles divisor som gjør oss i stand til å forstå hvorfor algoritmen fungerer.

== Egenskaper ved største felles divisor ==

Største felles divisor og Euklids algoritme - Sideversjonshistorikk

Skf95: /* Største felles divisor */ fra 3*2*2 til 2*2*3

Skf95: /* Største felles divisor */ Feil faktorisert.

Vaktmester: Teksterstatting – «» til «»

Vaktmester: Teksterstatting – «» til «»

Vektormannen på 12. nov. 2012 kl. 14:14

Vektormannen: /* Største felles divisor */

Vektormannen: Ny side: == Største felles divisor == Tallene 12 og 18 kan faktoriseres som 12 = 2 \cdot 2 \cdot 2 og 18 = 2 \cdot 3 \cdot 3. Vi ser at begge tallene har 2 og 3 som faktorer....

Skf95: /* Største felles divisor / fra 32*2 til 223

Vaktmester: Teksterstatting – «» til « $»$