Primtall og Eratostenes' sil - Sideversjonshistorikk

MatteTor: /* Uendelig mange primtall */

2024-08-06T11:27:23Z

Uendelig mange primtall

← Eldre sideversjon		Sideversjonen fra 6. aug. 2024 kl. 11:27
Linje 17:		Linje 17:
	Så ser vi på følgende tall: <math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</math>, altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. <br>		Så ser vi på følgende tall: <math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</math>, altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. <br>

	Siden <math>a</math> er større enn alle primtallene, må <math>a</math> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</math> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</math> er faktorer i <math>a</math>. Men vi har at <math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</math> <br>		Siden <math>a</math> er større enn alle primtallene vi har antatt at eksisterer, må <math>a</math> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</math> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</math> er faktorer i <math>a</math>. Men vi har at <math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</math> <br>

	Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!		Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!

MatteTor: /* Uendelig mange primtall */

2024-08-06T11:24:20Z

Uendelig mange primtall

← Eldre sideversjon		Sideversjonen fra 6. aug. 2024 kl. 11:24
Linje 7:		Linje 7:
	===Uendelig mange primtall===		===Uendelig mange primtall===

	Det finnes uendelig mange primtall.		Påstand: Det finnes uendelig mange primtall.

	'''Bevis:'''		'''Bevis:'''

MatteTor: /* Uendelig mange primtall */

2024-08-06T11:23:50Z

Uendelig mange primtall

← Eldre sideversjon		Sideversjonen fra 6. aug. 2024 kl. 11:23
Linje 10:		Linje 10:

	'''Bevis:'''		'''Bevis:'''

	Strategi: Bevis ved motsigelse		Strategi: Bevis ved motsigelse

MatteTor: /* Primtallsmysteriet */

2024-08-06T11:23:24Z

Primtallsmysteriet

← Eldre sideversjon		Sideversjonen fra 6. aug. 2024 kl. 11:23
Linje 10:		Linje 10:

	'''Bevis:'''		'''Bevis:'''
			Strategi: Bevis ved motsigelse

	Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</math> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</math>. <br>		Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</math> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</math>. <br>

Vaktmester på 24. mai 2013 kl. 21:30

2013-05-24T21:30:44Z

← Eldre sideversjon		Sideversjonen fra 24. mai 2013 kl. 21:30
Linje 4:		Linje 4:
	Primtallene har forbløffet matematikere i tusener av år. De dukker opp på nærmest tilfeldige steder på tallinjen. Det er steder på tallinjen hvor man har to ''naboprimtall'' nesten ved siden av hverandre, mens det andre steder kan være flere tusen sammensatte tall mellom to primtall. Primtallgåten er i stor grad uløst, men det er gjort flere fremskritt når det gjelder forståelsen av primtallene. Et veldig viktig resultat er blant annet at det finnes uendelig mange primtall. Dette ble bevist av den greske matematikeren Euklid for over 2000 år siden.		Primtallene har forbløffet matematikere i tusener av år. De dukker opp på nærmest tilfeldige steder på tallinjen. Det er steder på tallinjen hvor man har to ''naboprimtall'' nesten ved siden av hverandre, mens det andre steder kan være flere tusen sammensatte tall mellom to primtall. Primtallgåten er i stor grad uløst, men det er gjort flere fremskritt når det gjelder forståelsen av primtallene. Et veldig viktig resultat er blant annet at det finnes uendelig mange primtall. Dette ble bevist av den greske matematikeren Euklid for over 2000 år siden.

	<~~blockquote~~ style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<div style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	===Uendelig mange primtall===		===Uendelig mange primtall===

Linje 19:		Linje 19:
	Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!		Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!

	</~~blockquote~~>		</div>

	Beviset ovenfor regnes av mange som et av de peneste bevisene i matematikken. Ved å bruke enkle egenskaper ved delelighet og om primtall kommer vi frem til noe veldig stort om primtallene -- at det finnes uendelig mange av dem. Vi vet ikke hvor primtallene befinner seg utover på tall-linjen, men vi kan likevel slå fast at det er uendelig mange av dem!		Beviset ovenfor regnes av mange som et av de peneste bevisene i matematikken. Ved å bruke enkle egenskaper ved delelighet og om primtall kommer vi frem til noe veldig stort om primtallene -- at det finnes uendelig mange av dem. Vi vet ikke hvor primtallene befinner seg utover på tall-linjen, men vi kan likevel slå fast at det er uendelig mange av dem!

Vaktmester: /* Uendelig mange primtall */

2013-05-24T21:29:19Z

Uendelig mange primtall

← Eldre sideversjon		Sideversjonen fra 24. mai 2013 kl. 21:29
Linje 11:		Linje 11:
	'''Bevis:'''		'''Bevis:'''

	Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</math> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</math>.		Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</math> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</math>. <br>

	Så ser vi på følgende tall: <math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</math>, altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1.		Så ser vi på følgende tall: <math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</math>, altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. <br>

	Siden <math>a</math> er større enn alle primtallene, må <math>a</math> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</math> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</math> er faktorer i <math>a</math>. Men vi har at <math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</math>		Siden <math>a</math> er større enn alle primtallene, må <math>a</math> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</math> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</math> er faktorer i <math>a</math>. Men vi har at <math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</math> <br>

	Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!		Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!
Linje 21:		Linje 21:
	</blockquote>		</blockquote>

	Beviset ovenfor regnes av mange som et av de peneste bevisene i matematikken. Ved å bruke enkle egenskaper ved delelighet og om primtall kommer vi frem til noe veldig stort om primtallene -- at det finnes uendelig mange av dem. Vi vet ikke hvor primtallene befinner seg utover på tall-linjen, men vi kan likevel slå fast at det er uendelig mange av dem!		Beviset ovenfor regnes av mange som et av de peneste bevisene i matematikken. Ved å bruke enkle egenskaper ved delelighet og om primtall kommer vi frem til noe veldig stort om primtallene -- at det finnes uendelig mange av dem. Vi vet ikke hvor primtallene befinner seg utover på tall-linjen, men vi kan likevel slå fast at det er uendelig mange av dem!

	== Primtallstesting og Eratostenes' sil ==		== Primtallstesting og Eratostenes' sil ==

Vaktmester på 24. mai 2013 kl. 21:27

2013-05-24T21:27:45Z

← Eldre sideversjon		Sideversjonen fra 24. mai 2013 kl. 21:27
Linje 5:		Linje 5:

	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	~~:'''~~Uendelig mange primtall~~'''~~		===Uendelig mange primtall===

	: Det finnes uendelig mange primtall.		Det finnes uendelig mange primtall.

			'''Bevis:'''

			Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</math> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</math>.

			Så ser vi på følgende tall: <math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</math>, altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1.

			Siden <math>a</math> er større enn alle primtallene, må <math>a</math> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</math> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</math> er faktorer i <math>a</math>. Men vi har at <math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</math>

			Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!

	~~:'''Bevis:'''~~
	~~: Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</math> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</math>. Så ser vi på følgende tall:~~
	~~::<math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</math>,~~
	: altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. Siden <math>a</math> er større enn alle primtallene, må <math>a</math> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</math> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</math> er faktorer i <math>a</math>. Men vi har at
	~~::<math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</math>~~
	: Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!
	</blockquote>		</blockquote>

Linje 26:		Linje 30:

	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	: Dersom et tall <math>n</math> er sammensatt må minst én primfaktor være mindre eller lik <math>\sqrt n</math>.		Dersom et tall <math>n</math> er sammensatt må minst én primfaktor være mindre eller lik <math>\sqrt n</math>.


			'''Bevis'''


			Dette beviser vi ved å se på hva som skjer dersom ''alle'' primfaktorene var større enn <math>\sqrt n</math>. Vi kan skrive <math>n = ap</math>, der <math>p</math> er en av primfaktorene og <math>a</math> er produktet av de resterende primfaktorene. Vi ser nå på hva som skjer dersom både <math>p \geq \sqrt n</math> og <math>a \geq \sqrt n</math>. Da er

	:~~'''Bevis'''~~		:<math>ap \geq \sqrt n \cdot \sqrt n = n</math>

	: Dette beviser vi ved å se på hva som skjer dersom ''alle'' primfaktorene var større enn <math>\sqrt n</math>. Vi kan skrive <math>n = ap</math>, der <math>p</math> er en av primfaktorene og <math>a</math> er produktet av de resterende primfaktorene. Vi ser nå på hva som skjer dersom både <math>p \geq \sqrt n</math> og <math>a \geq \sqrt n</math>. Da er		altså blir også produktet av faktorene i <math>n</math> større enn <math>n</math> selv. Dette er umulig, og minst en av faktorene må altså være mindre enn <math>\sqrt n</math>.
	~~::<math>ap \geq \sqrt n \cdot \sqrt n = n</math>~~
	: altså blir også produktet av faktorene i <math>n</math> større enn <math>n</math> selv. Dette er umulig, og minst en av faktorene må altså være mindre enn <math>\sqrt n</math>.
	</blockquote>		</blockquote>

Linje 40:		Linje 48:

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

	:Skriv opp alle tall i fra 2 til <math>n</math>. Utfør så følgende steg, start med tallet <math>k=2</math>.		Skriv opp alle tall i fra 2 til <math>n</math>. Utfør så følgende steg, start med tallet <math>k=2</math>.
	:* Stryk ut alle tall som går opp i ~~<math>~~k~~</math>~~ utenom ~~<math>~~k~~</math>~~ selv.		* Stryk ut alle tall som går opp i $k$ utenom $k$ selv.
	:* Se på neste tall etter ~~<math>~~k~~</math>~~ som ikke er strøket ut. Dersom dette er større enn ~~<math>~~\sqrt n~~</math>~~ er vi ferdige. Hvis ikke, gjenta prosessen med dette tallet.		* Se på neste tall etter $k$ som ikke er strøket ut. Dersom dette er større enn $\sqrt n$ er vi ferdige. Hvis ikke, gjenta prosessen med dette tallet.

	: Når disse stegene er gjort vil de tallene som ikke er strøket ut være alle primtall som er mindre enn <math>n</math>.		Når disse stegene er gjort vil de tallene som ikke er strøket ut være alle primtall som er mindre enn <math>n</math>.
	</blockquote>		</blockquote>

Vaktmester: Teksterstatting – «» til «»

2013-02-05T20:59:06Z

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

Vaktmester: Teksterstatting – «» til « $»$

2013-02-05T20:57:50Z

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

← Eldre sideversjon		Sideversjonen fra 5. feb. 2013 kl. 20:57
Linje 10:		Linje 10:

	:'''Bevis:'''		:'''Bevis:'''
	: Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <~~tex~~>k</tex> stykker. Da har vi primtallene <~~tex~~>p_1, p_2, ..., p_k</tex>. Så ser vi på følgende tall:		: Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</tex> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</tex>. Så ser vi på følgende tall:
	::<~~tex~~>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</tex>,		::<math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</tex>,
	: altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. Siden <~~tex~~>a</tex> er større enn alle primtallene, må <~~tex~~>a</tex> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <~~tex~~>a</tex> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <~~tex~~>p_1, p_2, p_3, ..., p_k</tex> er faktorer i <~~tex~~>a</tex>. Men vi har at		: altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. Siden <math>a</tex> er større enn alle primtallene, må <math>a</tex> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</tex> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</tex> er faktorer i <math>a</tex>. Men vi har at
	::<~~tex~~>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</tex>		::<math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</tex>
	: Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <~~tex~~>p_i</tex> (der <~~tex~~>i</tex> er et tall mellom 1 og <~~tex~~>k</tex>) er en faktor i <~~tex~~>a</tex> og dette tallet også er en faktor i tallet <~~tex~~>p_1 \cdot p_2 \cdot p_3 \dots p_k</tex> så kan vi faktorisere ut tallet <~~tex~~>p_i</tex> på venstre side. Men hvis <~~tex~~>p_i</tex> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <~~tex~~>k</tex> forskjellige primtall er gal -- altså finne det uendelig mange primtall!		: Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</tex> (der <math>i</tex> er et tall mellom 1 og <math>k</tex>) er en faktor i <math>a</tex> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</tex> så kan vi faktorisere ut tallet <math>p_i</tex> på venstre side. Men hvis <math>p_i</tex> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</tex> forskjellige primtall er gal -- altså finne det uendelig mange primtall!
	</blockquote>		</blockquote>

Linje 26:		Linje 26:

	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	: Dersom et tall <~~tex~~>n</tex> er sammensatt må minst én primfaktor være mindre eller lik <~~tex~~>\sqrt n</tex>.		: Dersom et tall <math>n</tex> er sammensatt må minst én primfaktor være mindre eller lik <math>\sqrt n</tex>.

	:'''Bevis'''		:'''Bevis'''

	: Dette beviser vi ved å se på hva som skjer dersom ''alle'' primfaktorene var større enn <~~tex~~>\sqrt n</tex>. Vi kan skrive <~~tex~~>n = ap</tex>, der <~~tex~~>p</tex> er en av primfaktorene og <~~tex~~>a</tex> er produktet av de resterende primfaktorene. Vi ser nå på hva som skjer dersom både <~~tex~~>p \geq \sqrt n</tex> og <~~tex~~>a \geq \sqrt n</tex>. Da er		: Dette beviser vi ved å se på hva som skjer dersom ''alle'' primfaktorene var større enn <math>\sqrt n</tex>. Vi kan skrive <math>n = ap</tex>, der <math>p</tex> er en av primfaktorene og <math>a</tex> er produktet av de resterende primfaktorene. Vi ser nå på hva som skjer dersom både <math>p \geq \sqrt n</tex> og <math>a \geq \sqrt n</tex>. Da er
	::<~~tex~~>ap \geq \sqrt n \cdot \sqrt n = n</tex>		::<math>ap \geq \sqrt n \cdot \sqrt n = n</tex>
	: altså blir også produktet av faktorene i <~~tex~~>n</tex> større enn <~~tex~~>n</tex> selv. Dette er umulig, og minst en av faktorene må altså være mindre enn <~~tex~~>\sqrt n</tex>.		: altså blir også produktet av faktorene i <math>n</tex> større enn <math>n</tex> selv. Dette er umulig, og minst en av faktorene må altså være mindre enn <math>\sqrt n</tex>.
	</blockquote>		</blockquote>

	Dette gjør det betraktelig enklere å bestemme om et tall er primtall eller ikke. Det ovenfor sier jo at hvis et tall er sammensatt, så '''må''' det være delelig på et primtall som er mindre enn kvadratorten av tallet. Det vil si at hvis vi deler et tall på alle primtallene som er mindre eller lik kvadratroten av tallet og ingen av divisjonene går opp (gir et helt tall) så kan ikke tallet være sammensatt -- det må være et primtall.		Dette gjør det betraktelig enklere å bestemme om et tall er primtall eller ikke. Det ovenfor sier jo at hvis et tall er sammensatt, så '''må''' det være delelig på et primtall som er mindre enn kvadratorten av tallet. Det vil si at hvis vi deler et tall på alle primtallene som er mindre eller lik kvadratroten av tallet og ingen av divisjonene går opp (gir et helt tall) så kan ikke tallet være sammensatt -- det må være et primtall.

	Å teste om et tall er primtall på den måten som er beskrevet ovenfor kan fort involvere å dele tallet på forskjellige primtall mange ganger. En annen metode som gir oss ''alle'' primtallene fra 2 og opp til et tall <~~tex~~>n</tex> kalles ''Eratostenes' sil'' (kalles også ''Eratostenes' såld''.) Denne metoden er oppkalt etter den greske matematikeren Eratostenes og stammer fra antikkens Hellas.		Å teste om et tall er primtall på den måten som er beskrevet ovenfor kan fort involvere å dele tallet på forskjellige primtall mange ganger. En annen metode som gir oss ''alle'' primtallene fra 2 og opp til et tall <math>n</tex> kalles ''Eratostenes' sil'' (kalles også ''Eratostenes' såld''.) Denne metoden er oppkalt etter den greske matematikeren Eratostenes og stammer fra antikkens Hellas.

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

	:Skriv opp alle tall i fra 2 til <~~tex~~>n</tex>. Utfør så følgende steg, start med tallet <~~tex~~>k=2</tex>.		:Skriv opp alle tall i fra 2 til <math>n</tex>. Utfør så følgende steg, start med tallet <math>k=2</tex>.
	:* Stryk ut alle tall som går opp i <~~tex~~>k</tex> utenom <~~tex~~>k</tex> selv.		:* Stryk ut alle tall som går opp i <math>k</tex> utenom <math>k</tex> selv.
	:* Se på neste tall etter <~~tex~~>k</tex> som ikke er strøket ut. Dersom dette er større enn <~~tex~~>\sqrt n</tex> er vi ferdige. Hvis ikke, gjenta prosessen med dette tallet.		:* Se på neste tall etter <math>k</tex> som ikke er strøket ut. Dersom dette er større enn <math>\sqrt n</tex> er vi ferdige. Hvis ikke, gjenta prosessen med dette tallet.

	: Når disse stegene er gjort vil de tallene som ikke er strøket ut være alle primtall som er mindre enn <~~tex~~>n</tex>.		: Når disse stegene er gjort vil de tallene som ikke er strøket ut være alle primtall som er mindre enn <math>n</tex>.
	</blockquote>		</blockquote>

Vektormannen på 31. aug. 2012 kl. 13:33

2012-08-31T13:33:30Z

← Eldre sideversjon		Sideversjonen fra 31. aug. 2012 kl. 13:33
Linje 25:		Linje 25:
	For å teste om et tall er primtall kan vi benytte aritmetikkens fundamentalteorem. Det sier oss at dersom tallet ''ikke'' er et primtall, må det være et sammensatt tall med en unik primtallsfaktorisering, der hver primfaktor i alle fall er mindre enn tallet selv. Med andre ord kan vi teste om et tall er primtall ved å dele det på forskjellige primtall mellom 2 og tallet selv. Hvis vi får et helt tall når vi deler på et av primtallene, må dette primtallet være et faktor i tallet vårt, og da er ikke tallet vårt et primtall. Men dersom vi fortsetter å dele på primtall og vi ikke får et heltall noen av gangene, må tallet være et primtall. Men kan vi gjøre dette enda enklere?		For å teste om et tall er primtall kan vi benytte aritmetikkens fundamentalteorem. Det sier oss at dersom tallet ''ikke'' er et primtall, må det være et sammensatt tall med en unik primtallsfaktorisering, der hver primfaktor i alle fall er mindre enn tallet selv. Med andre ord kan vi teste om et tall er primtall ved å dele det på forskjellige primtall mellom 2 og tallet selv. Hvis vi får et helt tall når vi deler på et av primtallene, må dette primtallet være et faktor i tallet vårt, og da er ikke tallet vårt et primtall. Men dersom vi fortsetter å dele på primtall og vi ikke får et heltall noen av gangene, må tallet være et primtall. Men kan vi gjøre dette enda enklere?

	<blockquote style="padding: 1em; border: ~~3px dotted~~ blue;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	: Dersom et tall <tex>n</tex> er sammensatt må minst én primfaktor være mindre eller lik <tex>\sqrt n</tex>.		: Dersom et tall <tex>n</tex> er sammensatt må minst én primfaktor være mindre eller lik <tex>\sqrt n</tex>.

Linje 39:		Linje 39:
	Å teste om et tall er primtall på den måten som er beskrevet ovenfor kan fort involvere å dele tallet på forskjellige primtall mange ganger. En annen metode som gir oss ''alle'' primtallene fra 2 og opp til et tall <tex>n</tex> kalles ''Eratostenes' sil'' (kalles også ''Eratostenes' såld''.) Denne metoden er oppkalt etter den greske matematikeren Eratostenes og stammer fra antikkens Hellas.		Å teste om et tall er primtall på den måten som er beskrevet ovenfor kan fort involvere å dele tallet på forskjellige primtall mange ganger. En annen metode som gir oss ''alle'' primtallene fra 2 og opp til et tall <tex>n</tex> kalles ''Eratostenes' sil'' (kalles også ''Eratostenes' såld''.) Denne metoden er oppkalt etter den greske matematikeren Eratostenes og stammer fra antikkens Hellas.

	<blockquote style="padding: 1em; border: ~~3px dotted~~ blue;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	:'''Eratostenes' sil'''		:'''Eratostenes' sil'''

← Eldre sideversjon		Sideversjonen fra 5. feb. 2013 kl. 20:59
Linje 10:		Linje 10:

	:'''Bevis:'''		:'''Bevis:'''
	: Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</~~tex~~> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</~~tex~~>. Så ser vi på følgende tall:		: Anta at det kun finnes et endelig antall primtall. Vi kan si at det er <math>k</math> stykker. Da har vi primtallene <math>p_1, p_2, ..., p_k</math>. Så ser vi på følgende tall:
	::<math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</~~tex~~>,		::<math>a = p_1 \cdot p_2 \cdot p_3 \dots p_k + 1</math>,
	: altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. Siden <math>a</~~tex~~> er større enn alle primtallene, må <math>a</~~tex~~> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</~~tex~~> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</~~tex~~> er faktorer i <math>a</~~tex~~>. Men vi har at		: altså tallet vi får når vi ganger sammen alle primtallene vi har og plusser på 1. Siden <math>a</math> er større enn alle primtallene, må <math>a</math> være et sammensatt tall. Da gir aritmetikkens fundamentalsetning at <math>a</math> har en unik primtallsfaktorisering. Det betyr at minst to av primtallene <math>p_1, p_2, p_3, ..., p_k</math> er faktorer i <math>a</math>. Men vi har at
	::<math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</~~tex~~>		::<math>a - p_1 \cdot p_2 \cdot p_3 \dots p_k = 1</math>
	: Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</~~tex~~> (der <math>i</~~tex~~> er et tall mellom 1 og <math>k</~~tex~~>) er en faktor i <math>a</~~tex~~> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</~~tex~~> så kan vi faktorisere ut tallet <math>p_i</~~tex~~> på venstre side. Men hvis <math>p_i</~~tex~~> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</~~tex~~> forskjellige primtall er gal -- altså finne det uendelig mange primtall!		: Nå ser vi at siden i alle fall et av primtallene, la oss kalle det <math>p_i</math> (der <math>i</math> er et tall mellom 1 og <math>k</math>) er en faktor i <math>a</math> og dette tallet også er en faktor i tallet <math>p_1 \cdot p_2 \cdot p_3 \dots p_k</math> så kan vi faktorisere ut tallet <math>p_i</math> på venstre side. Men hvis <math>p_i</math> er en faktor på venstre side så må det også være en faktor i høyre side, altså tallet 1. Det er umulig. Siden vi kun har gjort gyldige steg helt i fra antagelsen om at det kun er et endelig antall primtall, må det være denne antagelsen som gjorde at vi kom frem til denne umuligheten. Antagelsen om at det er bare <math>k</math> forskjellige primtall er gal -- altså finne det uendelig mange primtall!
	</blockquote>		</blockquote>

Linje 26:		Linje 26:

	<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">		<blockquote style="padding: 1em; border: 1px blue; background-color: #B2DFEE;">
	: Dersom et tall <math>n</~~tex~~> er sammensatt må minst én primfaktor være mindre eller lik <math>\sqrt n</~~tex~~>.		: Dersom et tall <math>n</math> er sammensatt må minst én primfaktor være mindre eller lik <math>\sqrt n</math>.

	:'''Bevis'''		:'''Bevis'''

	: Dette beviser vi ved å se på hva som skjer dersom ''alle'' primfaktorene var større enn <math>\sqrt n</~~tex~~>. Vi kan skrive <math>n = ap</~~tex~~>, der <math>p</~~tex~~> er en av primfaktorene og <math>a</~~tex~~> er produktet av de resterende primfaktorene. Vi ser nå på hva som skjer dersom både <math>p \geq \sqrt n</~~tex~~> og <math>a \geq \sqrt n</~~tex~~>. Da er		: Dette beviser vi ved å se på hva som skjer dersom ''alle'' primfaktorene var større enn <math>\sqrt n</math>. Vi kan skrive <math>n = ap</math>, der <math>p</math> er en av primfaktorene og <math>a</math> er produktet av de resterende primfaktorene. Vi ser nå på hva som skjer dersom både <math>p \geq \sqrt n</math> og <math>a \geq \sqrt n</math>. Da er
	::<math>ap \geq \sqrt n \cdot \sqrt n = n</~~tex~~>		::<math>ap \geq \sqrt n \cdot \sqrt n = n</math>
	: altså blir også produktet av faktorene i <math>n</~~tex~~> større enn <math>n</~~tex~~> selv. Dette er umulig, og minst en av faktorene må altså være mindre enn <math>\sqrt n</~~tex~~>.		: altså blir også produktet av faktorene i <math>n</math> større enn <math>n</math> selv. Dette er umulig, og minst en av faktorene må altså være mindre enn <math>\sqrt n</math>.
	</blockquote>		</blockquote>

	Dette gjør det betraktelig enklere å bestemme om et tall er primtall eller ikke. Det ovenfor sier jo at hvis et tall er sammensatt, så '''må''' det være delelig på et primtall som er mindre enn kvadratorten av tallet. Det vil si at hvis vi deler et tall på alle primtallene som er mindre eller lik kvadratroten av tallet og ingen av divisjonene går opp (gir et helt tall) så kan ikke tallet være sammensatt -- det må være et primtall.		Dette gjør det betraktelig enklere å bestemme om et tall er primtall eller ikke. Det ovenfor sier jo at hvis et tall er sammensatt, så '''må''' det være delelig på et primtall som er mindre enn kvadratorten av tallet. Det vil si at hvis vi deler et tall på alle primtallene som er mindre eller lik kvadratroten av tallet og ingen av divisjonene går opp (gir et helt tall) så kan ikke tallet være sammensatt -- det må være et primtall.

	Å teste om et tall er primtall på den måten som er beskrevet ovenfor kan fort involvere å dele tallet på forskjellige primtall mange ganger. En annen metode som gir oss ''alle'' primtallene fra 2 og opp til et tall <math>n</~~tex~~> kalles ''Eratostenes' sil'' (kalles også ''Eratostenes' såld''.) Denne metoden er oppkalt etter den greske matematikeren Eratostenes og stammer fra antikkens Hellas.		Å teste om et tall er primtall på den måten som er beskrevet ovenfor kan fort involvere å dele tallet på forskjellige primtall mange ganger. En annen metode som gir oss ''alle'' primtallene fra 2 og opp til et tall <math>n</math> kalles ''Eratostenes' sil'' (kalles også ''Eratostenes' såld''.) Denne metoden er oppkalt etter den greske matematikeren Eratostenes og stammer fra antikkens Hellas.

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

	:Skriv opp alle tall i fra 2 til <math>n</~~tex~~>. Utfør så følgende steg, start med tallet <math>k=2</~~tex~~>.		:Skriv opp alle tall i fra 2 til <math>n</math>. Utfør så følgende steg, start med tallet <math>k=2</math>.
	:* Stryk ut alle tall som går opp i <math>k</~~tex~~> utenom <math>k</~~tex~~> selv.		:* Stryk ut alle tall som går opp i <math>k</math> utenom <math>k</math> selv.
	:* Se på neste tall etter <math>k</~~tex~~> som ikke er strøket ut. Dersom dette er større enn <math>\sqrt n</~~tex~~> er vi ferdige. Hvis ikke, gjenta prosessen med dette tallet.		:* Se på neste tall etter <math>k</math> som ikke er strøket ut. Dersom dette er større enn <math>\sqrt n</math> er vi ferdige. Hvis ikke, gjenta prosessen med dette tallet.

	: Når disse stegene er gjort vil de tallene som ikke er strøket ut være alle primtall som er mindre enn <math>n</~~tex~~>.		: Når disse stegene er gjort vil de tallene som ikke er strøket ut være alle primtall som er mindre enn <math>n</math>.
	</blockquote>		</blockquote>