Priemgetallen

[H@nk]

Weet iemand nog iets interressants over priemgetallen?
Wij zijn namelijk met een PO bezig en we kunnen geen onderwerpen meer vinden.

we hebben nu iets geschreven over:
-algemeen (wat zijn priemgetallen etc)
-bewijs dat aantal priem oneindig is
-paar formules die een aantal priemgetallen geven en formules die verbanden aangeven
-programma's geschreven voor rekenmachine en computer die kijken of een bepaald getal priem is
-verdeling van de priemgetallen (tweelingen, vierlingen, etc)
-zeef van ...(weet even niet hoe hij heet)


weet iemand misschien nog een paar goede punten voor ons PO?

alvast bedankt

[Tampert]

ieder getal (>1) is te schrijven als een product van priemgetallen + bewijs...?

[tý]

Tampert schreef op 06-06-2003 @ 20:32:
ieder getal (>1) is te schrijven als een product van priemgetallen + bewijs...?

een bewijs uit het ongerijmde (of zoiets) is dat toch ?

[Tampert]

tý schreef op 06-06-2003 @ 20:42:
een bewijs uit het ongerijmde (of zoiets) is dat toch ?

nee. Bewijs met volledige inductie.

dt houdt in:

bewijs het voor een bepaalde waarde.
bewijs dat als het voor een waarde geldt het ook geldt voor de daaropvolgende waarde.

Voorbeeld:

getal 2 is een priemgetal (product van één priemgetal)
getal 3 is een priemgetal (product van één priemgetal)
4 = 2*2 is een product van twee priemgetallen.

Stel je hebt een getal n. Je weet dat ieder getal kleiner dan n op te splitsen is in een product van priemgetallen.

Er zijn nu twee opties voor het getal n+1:

n+1 is een product van priemgetallen. Voor dit geval is de stelling bewezen
n+1 is een product van minstens één niet-priemgetal. Dat niet priemgetal is echter kleiner dan n. Aangezien we hebben aangenomen dat ieder getal kleiner dan n bestaat uit een product van priemgetallen moet de niet-priemdeler dus nog deelbaar zijn in een aantal priemgetallen.

zoiets?

[H@nk]

ja, bedankt, ik had op WisFAQ al een bewijs gevonden (http://www.wisfaq.nl/frame.htm?url=h...rd3.asp?id=329). Di hebben gaan we erin zetten en gaan we gelijk combineren met het algoritme van Euclides.

Iemand nog meer ideetjes?

Tampert schreef op 06-06-2003 @ 21:16:
nee. Bewijs met volledige inductie.

dt houdt in:

bewijs het voor een bepaalde waarde.
bewijs dat als het voor een waarde geldt het ook geldt voor de daaropvolgende waarde.

wij hebben het zo geleerd:
-bewijs dat het geld voor het getal 1
-neem nu aan dat het geld voor elk getal p
-bewijs dat het geld voor elk getal p+1

[GinnyPig]

Bewijs van een oneindig aantal priemgetallen:

Stel, Q is het grootste priemgetal.

Neem vervolgens het product van alle priemgetallen tot en met N:
2*3*5*7*...*Q

Dit levert een nieuw getal P.

Er geldt nu dat P+1 niet deelbaar is door een priemgetal kleiner of gelijk aan Q. Dus of P is een priemgetal, of er is een priemgetal R groter dan Q.

Conclusie, Q is niet het grootste priemgetal.

[H@nk]

GinnyPig schreef op 07-06-2003 @ 01:23:
Bewijs van een oneindig aantal priemgetallen:

Stel, Q is het grootste priemgetal.

Neem vervolgens het product van alle priemgetallen tot en met N:
2*3*5*7*...*Q

Dit levert een nieuw getal P.

Er geldt nu dat P+1 niet deelbaar is door een priemgetal kleiner of gelijk aan Q. Dus of P is een priemgetal, of er is een priemgetal R groter dan Q.

Conclusie, Q is niet het grootste priemgetal.

Dat is een bewijs dat het aantal priem oneindig is, niet dat ieder getal groter dan 1 op één manier te schrijven is als het product van priemgetallen.

iemand anders nog een andere suggestie?

[lucy48]

Ik dacht altijd dat een priemgetal een getal was dat alleen door zichzelf en 1 deelbaar was, zodat er nog een heel getal uitkomt

[mathfreak]

H@nk schreef op 07-06-2003 @ 08:17:
Dat is een bewijs dat het aantal priem oneindig is, niet dat ieder getal groter dan 1 op één manier te schrijven is als het product van priemgetallen.

iemand anders nog een andere suggestie?

Veronderstel dat n>1 op 2 manieren als een produkt van priemfactoren is te schrijven, namelijk n=p₁*p₂*...*p_k en n=q₁*q₂*...*q_l. Kies nu n zodanig dat k+l zo klein mogelijk is, dan zijn alle factoren p_i verschillend van de factoren q_j. Indien dat niet zo was zou er namelijk een getal zijn (zeg r), waarvoor k+l nog kleiner was, namelijk r=n/s, met s als gemeenschappelijke priemfactor. Omdat p₁ een factor is zou deze een deler moeten zijn van q₁ t/m q_l. Omdat verschillende priemgetallen geen deler van elkaar kunnen zijn geeft dit een tegenspraak wat het aantal mogelijke ontbindingen betreft, dus is een geheel getal n>1 slechts op 1 manier in priemfactoren te ontbinden, waarmee de hoofdstelling van de getaltheorie (zoals deze stelling heet) is bewezen.
Opmerking: wat betreft de zeefmethode voor het vinden van de priemgetallen neem ik aan dat je de zeef van Eratosthenes bedoelt.

@lucy48: Het is inderdaad zo dat een priemgetal p alleen 1 en p als deler heeft, maar het gaat er bij de hoofdstelling van de getaltheorie om dat ieder geheel getal n>1 slechts op 1 manier als een produkt van priemgetallen kan worden geschreven.

@FlorisvdB: Laat P(n) een uitspraak over de natuurlijke getallen n voorstellen, dan verloopt het bewijs van P(n) volgens het principe van volledige inductie als volgt:
1) Toon aan dat P(1) juist is
2) Laat k een willekeurig natuurlijk getal zijn en veronderstel dat P(k) juist is. Dit noemen we de inductiehypothese. Bewijs vervolgens:
P(k) => P(k+1). Dit bewijs noemen we de inductiestap.
3) Uit de juistheid van P(1) en P(k) => P(k+1) volgt nu de juistheid van
P(n) voor ieder natuurlijk getal n, waarmee het bewijs is geleverd.

[H@nk]

mathfreak schreef op 07-06-2003 @ 12:03:
Opmerking: wat betreft de zeefmethode voor het vinden van de priemgetallen neem ik aan dat je de zeef van Eratosthenes bedoelt.

ja, die bedoelde ik (ik heb dat stuk niet geschreven).

Maar. heeft er iemand nog een goed idee voor onze PO?

[H@nk]

mathfreak schreef op 07-06-2003 @ 13:56:
Na even in mijn Encyclopedic Dictionary of Mathematics te hebben gesnuffeld kwam ik de volgende dingen tegen die je voor je PO zou kunnen gebruiken:
- een bewijs voor het vermoeden van Bertrand dat er tussen n en 2*n minstens 1 priemgetal ligt
- een bewijs voor de stelling van Dirichlet dat de rij a, a+b, a+2*b,... een oneidig aantal priemgetallen bevat als a en b relatief priem zijn. Relatief priem houdt in dat de grootste gemeenschappelijke deler van a en b 1 is.

Hmm, hoe bewijs je dat, ik kan op sites als Google geen Nederlandstalige sites vinden met een bewijs, wel engelstalige maar daar snap ik niet veel van.

[mathfreak]

H@nk schreef op 07-06-2003 @ 14:11:
Hmm, hoe bewijs je dat, ik kan op sites als Google geen Nederlandstalige sites vinden met een bewijs, wel engelstalige maar daar snap ik niet veel van.

Ik heb mijn vorige reply, waar jouw quote betrekking op had, maar verwijderd omdat de bewijzen die ik daar noemde een beroep doen op onderwerpen uit de analyse en de getaltheorie die pas op universiteitsniveau aan de orde komen, dus laat dat verder maar zitten. Misschien is dit wel interessant: http://www.utm.edu/research/primes/mersenne/index.html

[Da King]

bewijs dat het aantal priemen van de form 3 mod 4 oneindig is kun je ook doen

[- DeJa - Vu -]

GinnyPig schreef op 07-06-2003 @ 01:23:
Bewijs van een oneindig aantal priemgetallen:

Stel, Q is het grootste priemgetal.

Neem vervolgens het product van alle priemgetallen tot en met N:
2*3*5*7*...*Q

Dit levert een nieuw getal P.

Er geldt nu dat P+1 niet deelbaar is door een priemgetal kleiner of gelijk aan Q. Dus of P is een priemgetal, of er is een priemgetal R groter dan Q.

Conclusie, Q is niet het grootste priemgetal.

Ja idd, zo heb ik het ongeveer ook beschreven op:
http://www.natutech.nl/forumDiscussi...702FC3C97519F5

[Just Johan]

http://forum.scholieren.com/showthre...hreadid=452344

[H@nk]

Just Johan schreef op 08-06-2003 @ 12:16:
http://forum.scholieren.com/showthre...hreadid=452344

mooi geschreven
past alleen niet echt mooi in onze PO.

[Flærynn]

Nog een leuke site vol priemgetallen (wel in Engels)

http://primes.utm.edu/curios/index.php

[Fade of Light]

RSA encryptie, stelling van Fermat,...

volgens mij heb ik die nog niet zien staan

[bulbanos]

srry voor het oprakelen van een oude topic
maar men zegt altijd: zoekfunctie gebruiken!

ik moet een programma schrijven in java dat controleert of een getal priem is of niet.
Ik vraag me af of er een efficienter algoritme bestaat dan gewoon alle getallen afgaan tem sqrt(N ) en telkens te controleren.

bulbanos schreef op 05-11-2004 @ 21:38 :
srry voor het oprakelen van een oude topic
maar men zegt altijd: zoekfunctie gebruiken!

ik moet een programma schrijven in java dat controleert of een getal priem is of niet.
Ik vraag me af of er een efficienter algoritme bestaat dan gewoon alle getallen afgaan tem sqrt(N ) en telkens te controleren.

Ik zou eerst kijken of het getal even is, als dat niet zo is alleen de oneven getallen kleiner dan de wortel proberen.

Je zou een lijst kunnen maken met alle priemgetallen... dat is natuurlijk nooit volledig.

[Fade of Light]

Ik geloof dat je nooit snel kunt kijken of iets een priem is, vandaar dat het gebruikt wordt in encryptie methoden. (maar pin me daar maar niet op vast, misschien dat sommige beveiligers zich nu 'omdraaien in hun graf' ).

In ieder geval alle even getallen eruit filteren (na een check of het 2 is) zoals OOOOOOOO zegt.

[Young Grow Old]

FlorisvdB schreef op 06-06-2003 @ 23:13 :
wij hebben het zo geleerd:
-bewijs dat het geld voor het getal 1
-neem nu aan dat het geld voor elk getal p
-bewijs dat het geld voor elk getal p+1

-bewijs dat het geldt voor het getal 1
-neem nu aan dat het geldt voor een willekeurig getal p
-bewijs dat hieruit volgt dat het geldt voor het getal p+1
-concludeer hieruit dat het voor alle natuurlijke getallen geldt
Dit is inderdaad hoe een bewijs met volledige inductie eruit ziet. Tampert maakte echter gebruik van het sterke principe van volledige inductie, waar je aanneemt dat het voor alle getallen kleiner dan een zekere p geldt en daaruit laat volgen dat het ook voor p moet gelden. Ook moet je het voor 1 bewijzen natuurlijk.

[saganou]

o maar er zijn verschillende snelle en goede priemtesten. De meeste algoritmes geven echter niet 100 % zekerheid, maar worden in vele computerprogramma's wel gebruikt als 'officieele priemtest'.

Eentje die vaak wordt gebruikt is de Rabin-test. Ik heb zelf niet echt gekeken, maar het bewijs is vast wel te vinden op internet..

Echter, de methode van alle delers onder sqrt( N ) proberen is dan wel de langzaamste, maar wel eentje die nog redelijk makkelijk te programmeren is. Wil je de Rabin-test gaan inprogrammeren, dan moet je daarbij een aantal trucjes erin verwerken die die test gebruikt wil hij redelijk snel zijn, zoals machtsverheffen modulo N.. dus behalve als je een heel energiek geinteresseerd persoon bent, zou ik je dit afraden en gewoon bij het 'oude' algoritme blijven.

[bulbanos]

saganou schreef op 06-11-2004 @ 19:47 :
o maar er zijn verschillende snelle en goede priemtesten. De meeste algoritmes geven echter niet 100 % zekerheid, maar worden in vele computerprogramma's wel gebruikt als 'officieele priemtest'.

Eentje die vaak wordt gebruikt is de Rabin-test. Ik heb zelf niet echt gekeken, maar het bewijs is vast wel te vinden op internet..

Echter, de methode van alle delers onder sqrt( N ) proberen is dan wel de langzaamste, maar wel eentje die nog redelijk makkelijk te programmeren is. Wil je de Rabin-test gaan inprogrammeren, dan moet je daarbij een aantal trucjes erin verwerken die die test gebruikt wil hij redelijk snel zijn, zoals machtsverheffen modulo N.. dus behalve als je een heel energiek geinteresseerd persoon bent, zou ik je dit afraden en gewoon bij het 'oude' algoritme blijven.

thx!
dus ik een eenvoudig lusje programmeren tem wortel N