## 12.3 De grootste gemene deler

Opgave 4

Gegeven de getallen a, m en d = ggd(a , m),
Het getal q is een geheel getal.
We weten nu dat d|(a - q * m).
Leg uit dat m en (a - q * m) geen grotere deler dan d gemeenschappelijk kunnen hebben en dat er dus geldt dat
d = ggd(m ,a - q * m).

We hebben nu gezien dat we de grootste gemene deler van een paar getallen kunnen vinden, zonder eerst alle delers op te moeten schrijven. We trekken telkens het kleinste getal een aantal keer van het grootste getal af. Zoiets deden we eerder in opgave 2 van les 10. Omdat we graag met zo klein mogelijke getallen rekenen, berekenen we liever de ggd van a - m en m dan van a en m. Het beste kunnen we het kleinste getal zo vaak mogelijk van het grootste getal aftrekken, maar wel zo dat de uitkomst positief blijft.

Voorbeeld:
Bereken de ggd(252, 198)
Berkening: 252 - 198 = 54, dus ggd(252, 198) = ggd(198, 54)
198 - 3 * 54 = 36, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36)
54 - 36 = 18, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36) = ggd(36, 18)
36 - 2 * 18 = 0, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36) = ggd(36, 18) = ggd(18, 0) = 18.
Merk op dat weer geldt als ieder getal een deler is van 0, behalve 0 zelf. Zie opgave 2 op de sub-pagina Grootste Gemene Delers.

Opgave 5

Bereken op bovenstaande manier:
a) ggd(6466,5429)
b) ggd(5346,897)
c) ggd(47,0)

In het voorbeeld boven opgave 5 zagen we, dat als we de ggd(252,198) willen bereken we 252reduceren door het getal 198 daar zovaak als mogelijk is van af te trekken (in dit geval één keer) zodat het resultaat nog net positief is. Bij de berekening maken we intuïtief gebruik van de geheeltallige deling en de REST-functie, of modulo-berekening.
We geven nu een paar formele definities. Op de sub-pagina (a div m) en (a mod m) worden deze verder toegelicht en kun je het modulo-rekenen oefenen met een paar opgaven.

Definitie a div b:
Voor gehele getallen a en positieve gehele getallen m is a div m het grootste gehele getal k dat voldoet aan k*m a.
Voorbeeld: 17 div 5 = 3 en -17 div 5 =-4

Definitie a mod m:
Voor gehele getallen a en positieve gehele getallen m is a mod m = a - m*(a div m),

Samengevat:
Voor gehele getallen a en positieve gehele getallen m geldt
(1) a = m*(a div m) + (a mod m)
(2) 0 a mod m < m.

Als je met het bovenstaande geen moeite hebt kun je rustig verder.
Zo niet kijk dan eerst naar de voorbeelden en verdere uitleg onder het kopje 12.3A (a div m) en (a mod m)

Opgave 6

Gegeven zijn de positieve gehele getallen a=2164, m=153 en q=2164 div 153,
met a > m dan is q het grootste getal waarvoor geldt dat a-q*m0.
Er geldt dus 2164-2164*153=2164(mod 153).
a) Leg uit dat ggd(2164,153)=ggd(153,2164(mod 153)).
b) Onderzoek of ggd(153,2164)=ggd(2164,153(mod 2164)).

Opgave 7

Gegeven zijn de positieve gehele getallen a, m en q=a div m, met a>m en q is het grootste getal is waarvoor geldt dat a-q*m>=0.
Er geldt dus a-q*m=a(mod m).
a) Leg uit dat ggd(a,m)=ggd(m,a(modm)).
b) Onderzoek of ggd(m,a)=ggd(a,m(mod a)) ook geldt als m>a.

De methode om een grootste gemene deler snel te berekenen die we in de bovenstaande opgaven ontdekt hebben, heet het "Algoritme van Euclides".