Priemgetallen

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer

Priemgetallen

LS

Dankzij de Tweede Fase zit ik inmiddels aan een praktische opdracht wiskunde. Priemgetallen is mijn onderwerp.

Nu zit ik (tot nu toe) met één vraag en één vraagje.

De vraag gaat over het bewijs dat er oneindig veel priemgetallen zijn.

Euclides bewees dit met behulp van de hoofdstelling van de rekenkunde: elk natuurlijk getal is uniek te ontbinden in priemgetallen.

Het bewijs van Euclides kan ik inmiddels redelijk volgen (dat viel niet meteen mee... ik ben niet zo'n ster in wiskunde ;) ). Maar die hoofdstelling van de rekenkunde, is die op een (enigzins) begrijpelijke wijze uit te leggen?

En dan had ik nog een vraagje: mijn wiskundeleraar stelt eigen initiatief verplicht, m.a.w. je moet zelf iets bedenken dat aan je deelonderwerp gerelateerd is. Helaas staan GIMPS (het grote computer priemzoekproject), cryptografie en het schrijven van een programma al op de lijst. Hebben jullie nog een origineel (en uitvoerbaar :shock: ) idee?

Bij voorbaat veel dank!

Pieter

Gebruikersavatar
Berichten: 24.578

Re: Priemgetallen

Dit is redelijk goed te volgen:

http://www.math.hawaii.edu/~lee/courses/fu...fundamental.pdf

Het bewijs van een oneindig aantal priemgetallen is ook redelijk eenvoudig.

Onderstel dat er wél een eindig aantal bestaat, en noem de laatste P(laatste).

Stel dan Q = P(1)*P(2)*...*P(laatste) + 1

Dit getal geeft bij deling door een priemgetal altijd rest 1, dus het is óf zelf een priemgetal of het heeft een groter priemgetal als deler. In beide gevallen was P(L) niet het grootste priemgetal, dus er is geen eindig aantal priemgetallen.

Gebruikersavatar
Berichten: 238

Re: Priemgetallen

:shock: Als je eigen iniatief verplicht stelt is het geen eigen iniatief meer. Wij moesten aan het begin van dit jaar een programmaatje maken wat voor elk gegeven getal een priemgetal uitrekende wat groter was dan dat getal (dus oneindig veel priemgetallen).

Die hoofdstelling van de rekenkunde zegt gewoon dat elk getal te ontbinden is dus in priemgetallen.

Voorbeeld:

10: 2*5

80: 2*2*2*2*5

384: 2*2*2*2*2*2*2*3

99: 3*3*11

250: 2*5*5*5

Hoe doe je dit nou?

Je neemt het getal en kijkt of het deelbaar is door het laagste priemgetal, 2 dus. Is dit het geval, dan is de eerste factor 2, en anders kijk je door of het deelbaar door 3 is, dan is de eerste factor 3, enz. met 5, 7 etc. Dan kijk je of het resulterende getal deelbaar is door datzelfde priemgetal, zo ja ga je door, zo nee dan ga je weer een priemgetal hoger.

Voorbeeld:

250 is deelbaar door 2, dit is 125. 125 is niet deelbaar door 2 of 3, maar wel door 5, dit is 25. 25 is ook deelbaar door 5, dit maakt 5 en 5 is dus deelbaar door 5, dit maakt 1. 125 staat dus gelijk aan 2*5*5*5.
Peter van Gemert

2e jaars Luchtvaart- en Ruimtevaarttechniek, TU Delft

Re: Priemgetallen

Goede site! Ik neem aan dat BWOC = By Way Of Contradiction?

Het principe van de hoofdregel was me duidelijk, alleen het bewijs nog niet. Maar nu dus wel... 8)

Eigen initiatief is niet helemaal de juiste formulering. Ik bedoelde te zeggen: eigen inbreng. Je moet dus zelf nog iets extra's bedenken. Daar zit ik nog een beetje mee.

Tot zover al ontzettend bedankt, en als er iemand nog een leuk ideetje heeft: 't is zeer welkom!

Re: Priemgetallen

Ehm... ik heb toch nog een heel stel vragen... ;)

Het gaat over het gebruik van priemgetallen bij cryptografie. Het idee is dit: je neemt twee geheime (zeer grote) priemgetallen P en Q, die je met elkaar vermenigvuldigt. Het getal M dat je daaruit krijgt, gebruik je als modulus voor een modulair rekensysteem. Worteltrekken is in dit systeem zeer moeilijk, zelfs voor supercomputers, want als je in het systeem een getal stopt dat een kwadraat is 'modulo M' en je vraagt naar de wortel, dan kan het duizenden jaren duren voor de computer het antwoord weet.

Een 'kwadraat modulo M', wat moet ik me daarbij voorstellen?

Het gaat nog verder. Als je een geheim getal x neemt, van bijna net zoveel cijfers als M, en je kwadrateert dit 'modulo M', en het kwadraat X (=x^2) bekend maakt, ben jij de enige die een wortel van X weet.

Zover kan ik het volgen (op het onderstreepte stuk na). Maar nu:

Tenzij iemand de factorisatie van de modulus M kent (dus P en Q). Dan schijn je wel snel te kunnen worteltrekken.

Dat laatste snap ik dus helemaal niet. Hoe is het verband tussen M (en P en Q) en X (en x)? Waarom kun je met de factorisatie wel snel de wortel bepalen? Of stel ik nu veel te ingewikkelde vragen voor 5 VWO? :shock:

Reageer