12.2 Gemene delers

De Griek Euclides van Alexandrië heeft een methode beschreven waarmee je de grootste gemene deler voor grote getallen kunt berekenen. Euclides is één van de belangrijkste wiskundigen van de afgelopen 2400 jaar.

 

Wie was Euclides

Euclides (ook Euclides van Alexandrië genoemd) was een Griekse wiskundige uit de 3e eeuw v. Chr. die werkzaam was in de bibliotheek van Alexandrië. Zijn bekendste werk is de Elementen, een boek waarin hij de eigenschappen van geometrische vormen en gehele getallen afleidt uit een verzameling axioma's. Hij wordt daarom wel beschouwd als een voorloper van de axiomatische methode in de moderne wiskunde. Veel van de resultaten in de Elementen zijn afkomstig van eerdere wiskundigen. Euclides' belangrijke prestatie was om ze allemaal in één samenhangend logisch kader te plaatsen. Zijn vijfde postulaat staat bekend als het parallellenpostulaat. Lang is geprobeerd dit axioma, dat ingewikkelder en minder vanzelfsprekend is dan de andere, uit de eerste vier axioma's te bewijzen. Maar in de 19e eeuw realiseerden Janos Bolyai, Nikolai Ivanovich Lobachevsky en waarschijnlijk ook Carl Friedrich Gauss zich dat het verwerpen van dit postulaat leidt tot volledig consistente niet-Euclidische meetkundes, die verder werden ontwikkeld door Bernhard Riemann. Naast meetkunde behandelt de Elementen ook elementaire getaltheorie, zoals de theorie van deelbaarheid, de grootste gemene deler en het algoritme van Euclides. Tot in de 20e eeuw werd de Elementen gebruikt als leerboek voor de meetkunde en was het zelfs samen met de Bijbel een van de meest gedrukte boeken. Toch schiet Euclides' methodologie tekort vergeleken met de huidige standaard van wiskundige precisie, omdat een aantal logische axioma's ontbreekt. De moderne axiomatische behandeling van de meetkunde gaat terug op David Hilbert in 1899.

Van de wiskunde die Euclides in 'De Elementen' beschreef, gebruiken we in de cryptografie niets. Het algoritme van Euclides dat we nu gaan bespreken is wel een belangrijke stelling in de cryptografie. Hoe je het algoritme op een snelle wijze kunt toepassen in een Excel-blad wordt na opgave 9 in 12.5 gedemonstreerd in een filmpje.

 

Opgave 1 

Het getal 11 is deler van 66 en 33.
a) Is het getal 11 ook deler van 66+33?
b) Is het getal 11 ook deler van 66-33?
c) Is het getal 11 ook deler van 33-66?

Uit opgave 1 ontstaat het vermoeden dat:
Als d een deler is van a en een deler is van b, dan is d ook een deler van a+b en a-b
Als we er goed over nadenken dan is dat ook wel logisch, immers
d is een deler van a, dus er is een geheel getal waarvoor geldt a=v*d
is een deler van b, dus er is een geheel getal w waarvoor geldt b=w*d.
We kunnen a+b dus schrijven als a+b=v*d+w*d=(v+w)*d
v+w is een heel getal, dus d is een deler van a+b.

 
Reflectie
Waarom moet ook een deler zijn van a-b?
klik hier

 

Opgave 2 

Het getal d = 11 is deler van de getallen a = 187 en m = 341.
a) Zoek getallen v en w waarvoor geldt dat 187 = 11 en 341 = 11.
b) Laat zien dat a + m = (v + w)*11 en a - m = (v - w)*11.

Opgave 3

Als a=6885 en m=2574 dan ggd(a,m) = 9, Deze noemen we d.
a) Leg uit dat d|(a-2*m).
b) Leg uit dat m en (a-2*m) geen grotere deler dan d gemeenschappelijk kunnen hebben 
en dat er dus geldt dat d=ggd(m,a-2*m).

Uit opgave 3 ontstaat het vermoeden dat:
Als d een deler is van a en een deler is van m, dan is d ook een deler van a+qm en a-qm
Als we er goed over nadenken dan is ook dat wel logisch, immers
d is een deler van a, dus er is een geheel getal waarvoor geldt a=v*d
is een deler van m, dus er is een geheel getal w waarvoor geldt m=w*d.
We kunnen a+qm dus schrijven als a+qm=v*d+qw*d=(v+qw)*d
v+qw is een geheel getal, dus d is een deler van a+qm.

 

Reflectie

Waarom is ook een deler van a-qm?

klik hier