Priemgetallen
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 |
ieder getal (>1) is te schrijven als een product van priemgetallen + bewijs...?
|
Citaat:
|
Citaat:
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? |
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? |
Citaat:
-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 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. |
Citaat:
iemand anders nog een andere suggestie? |
Ik dacht altijd dat een priemgetal een getal was dat alleen door zichzelf en 1 deelbaar was, zodat er nog een heel getal uitkomt
|
Citaat:
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. |
Citaat:
Maar. heeft er iemand nog een goed idee voor onze PO? |
Citaat:
|
Citaat:
|
bewijs dat het aantal priemen van de form 3 mod 4 oneindig is kun je ook doen
|
Citaat:
http://www.natutech.nl/forumDiscussi...702FC3C97519F5 |
|
Citaat:
past alleen niet echt mooi in onze PO. |
|
RSA encryptie, stelling van Fermat,...
volgens mij heb ik die nog niet zien staan |
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. |
Citaat:
Je zou een lijst kunnen maken met alle priemgetallen... dat is natuurlijk nooit volledig. |
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' :p).
In ieder geval alle even getallen eruit filteren (na een check of het 2 is) zoals OOOOOOOO zegt. |
Citaat:
-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. |
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. |
Citaat:
dus ik een eenvoudig lusje programmeren tem wortel N |
Alle tijden zijn GMT +1. Het is nu 22:30. |
Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.