De grootste gemene deler

GGD : Grootste Gemeenschappelijke Deler

Laat twee natuurlijke niet-nul gehele getallen a en b. Elk van deze twee nummers heeft een aantal verdelers. a en b hebben minstens 1 als gemeenschappelijke deler (omdat 1 alle gehele getallen verdeelt). De grootste deler die hoort bij a en b wordt genoteerd GGD (a; b).

Neem een voorbeeld

Laten we kijken naar de grootste gemene deler tussen 24 en 56. Er zijn verschillende methoden om de GGD te vinden :

Methode 1:

We vermelden de delers van de twee getallen en we zoeken naar het grootste aantal voor beide lijsten :

24 = 1x24 = 2x12 = 3x8 = 4x6 = 6x4 = 8x3 = 12x2
Ofwel de delers van 24 zijn D(24) = {1;2;3;4;6;8;12;24}
56 = 1x56 = 2x28 = 4x14 = 7x8 = 8x7
Ofwel de delers van 56 zijnD(56)={1;2;4;7;8;14;28;56}

Dus GGD(24;56) = 8
Deze methode is lang en vervelend.

Methode 2 :

Laten we de aftrekmethode gebruiken. Het is een eenvoudige methode.

56-24 = 32
32-24 = 8
24-8 = 16
16-8 = 8
8-8 = 0

Dus GGD(24;56) = 8

Methode 3 :

IEr is ook nog een andere eenvoudige methode genaamd de Euclidische divisiemethode. Deze methode is gebaseerd op het algoritme van Euclid :

Laat a en b twee gehele getallen zijn, zodanig dat a > b,
en laat de rest van de Euclidische divisie van a door b.
GGD (a ; b) = GGD (b ; r)

In ons voorbeeld geeft dit :
56 = 24x2 + 8
24 = 8x3 + 0

Dus GGD(24;56) = 8

Methode 4 :

We gebruiken de priemfactoren. We schrijven de ontbinding van de primaire factoren van de twee getallen. De GGD is dan gelijk aan het product van de priemgetallen die de twee decomposities gemeen hebben, waarbij aan elk daarvan de kleinste exponent wordt toegewezen.

24 = 23x3
56 = 23x7

Dus GGD (24;56) = 23 = 8 (2 is de enige gemeenschappelijke eerste factor in ons geval).