12.1 Deler, priemdeler en priemfactor

Een geheel getal a is een deler van een geheel getal b als het getal a precies een geheel aantal keerin het getal past. Meer wiskundig: een geheel getal a is een deler van een geheel getal b als er eengeheel getal k is, zodanig dat er geldt a*k b

In de wiskunde is er een notatie voor "deler zijn van". Deze notatie is een verticale rechte streep: |. Wanneer je schrijft b, bedoel je dus dat een deler is van b.

Het getal is een priemdeler van b als a zelf een priemgetal is en als je door kunt delen. Voor het vervolg van de module is het belangrijk dat je jezelf er eerst van overtuigt dat je het begrippriemdeler goed beheerst. Op de sub-pagina staat een aantal opgaven over delers en priemdelersVoer deze eerst uit voor je verder gaat.

Priemdelers.docx

In de moderne cryptografie zijn priemgetallen erg belangrijk. Dit komt doordat het voor producten van twee heel grote priemgetallen van bijvoorbeeld elk 150 cijfers lang, heel erg moeilijk is de priemfactorontbinding te bepalen, anders gezegd is het nauwelijks mogelijk te ontdekken hoe het product van de vermenigvuldiging tot stand is gekomen. Van de priemgetallen die nodig zijn voor moderne cryptografie zijn er heel veel bekend. Zoveel zelfs dat je ze niet allemaal kunt gaan proberen om een ontbinding van m te vinden. Veel grotere priemgetallen vinden van bijvoorbeeld miljoenen cijfers lang, is niet eenvoudig. De grootste bekende priemgetallen zijn Mersenne-priemgetallen, genoemd naar de Franse wiskundige Marin Mersenne. Deze priemgetallen zijn van de vorm 2p-1, waarbij p een priemgetal is. Maar niet alle getallen van deze vorm zijn priemgetallen. Voor getallen van deze vorm bestaan testen om te onderzoeken of ze priem zijn.

Klik hier om naar de site te gaan.

 

Leesactiviteit

 

Lees de tekst op onderstaande site van Kennislink over priemgetallen van meer dan 10.000.000 cijfers en beantwoord daarna de vragen.

 

a) Wat zijn Mersenne-getallen?

b) Wat is GIMPS?

c) Wie was Edson Smith?

d) Is het voor de cryptografie van belang dat er een priemgetal is gevonden van meer dan 10.000.000 cijfers?

klik hier

 

Priemfactoren van een groot samengesteld getal vinden is erg moeilijk. Zo is bijvoorbeeld wel bekend dat het getal 216384+1 niet priem is, maar is er geen enkele priemfactor van bekend. Het is een getal van 5000 cijfers.
Voor de cryptografie zijn priemgetallen van een paar honderd cijfers van belang. We zullen daar in deze module niet mee hoeven rekenen, maar we willen wel proberen te begrijpen waarom priemgetallen de oplossing boden in een zoektocht naar asymmetrische sleutels.

Daarvoor moeten we het begrip grootste gemene deler kennen. Op de sub-pagina Grootste Gemene Deler wordt een tweetal opgaven aangeboden die je moet kunnen maken om het vervolg te kunnen begrijpen. Voer de opgaven onder het kopje Grootste Gemene Deler hieronder uit .

 

Grootste Gemene Deler

De grootste gemene deler van a en m is het grootste gehele getal dat deler is van zowel a als m. We noteren dit als ggd(a,m).
De volgende methode is goed te doen voor kleine getallen, maar voor grote getallen is de priemfactorontbinding erg moeilijk te vinden en kun je deze methode dus niet gebruiken. Het is wel van belang om grip te krijgen op de ggd.

Eerst een voorbeeld:
Daarbij hanteren we een paar eenvoudige wetmatigheden:
Een even getal is deelbaar door 2.
Als de som van de cijfers deelbaar is door 3, dan is het getal deelbaar door 3
Als het getal eindigt op een 5 of een 0 dan is het deelbaar door 5.
Hiermee vind je de ontbindingen van de meeste 'kleine' getallen wel, maar als je meer regeltjes wilt dan kun je die vinden op http://members.chello.nl/f.waanders1/deelbaar.htm
Bepaal de ggd(264, 2436)
We ontbinden 264 en 2436 zo ver mogelijk in priemfactoren. 
264=2*132=2*2*66=2*2*2*33=2*2*2*3*11
2436=2*1218=2*2*609=2*2*3*203=2*2*3*7*29
De gemeenschappelijke delers van 264 en 2436 zijn 2, 2 en 3.
De ggd(264,2436) is nu 2*2*3=12

Opgave 1

a) Geef de positieve delers van 120.
b) Geef de positieve delers van 112.
c) Wat zijn de gemeenschappelijke delers van 120 en 112?
d) Wat is grootste gemeenschappelijke deler van 120 en 112?

 


Nog een voorbeeld:
Bereken ggd(980, 504). 
980=2*2*5*7*7, 
504=2*2*2*3*3*7. 
In beide priemfactorontbindingen zit twee keer de priemfactor 2 en een keer de priemfactor 7, dus ggd(980,504)=2*2*7=28.

Opgave 2

a) Bereken ggd(252, 198).
b) Bereken ggd(6466, 5429).
c) Bereken ggd(47, 0).
d) Geef ggd(a, 0) a ≠ 0.
e) Geef ggd(0,0)

 

Ga nu verder met 12.2 Gemene delers