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
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.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 v waarvoor geldt a=v*d.
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.
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 = v * 11 en 341 = w * 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 v waarvoor geldt a=v*d.
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 d ook een deler van a-qm?