Gegeven zijn 2 natuurlijke getallen
en
. Het grootste natuurlijk getal dat zowel een deler is van
als van
heet de grootste gemene deler van
en
. Notatie : ggd[a,b). Het kleinste getal dat zowel een veelvoud is van
als van
, heet het kleinste gemene veelvoud van
en
. Notatie : kgv(a,b).
Men kan de grootste gemene deler en het kleinste gemene veelvoud van 2 getallen bepalen door beide getallen te ontbinden in priemfactoren. Vooral bij grotere getallen kan dit een omvangrijk werk zijn. Er is een veel snellere methode. Deze berust op de eigenschap dat als
, dan geldt er dat ggd (a,b) = ggd(a,r). Elke deler van
en
is immers ook een deler van
en omgekeerd elke deler van
en
is ook een deler van
. Deze werkwijze noemt men het algoritme van Euclides.
We berekenen de ggd van 1970 en 1066 op twee manieren:
- 1970 = 2.5.197 en 1066 = 2.13.41, dus is ggd(1970,1066)=2
- 1970 = 1.1066 + 904 ; 1066=1.904+162 ; 904=5.162+94 ; 162=1.94+68 ; 94=1.68+26 ; 68=2.26+16 ; 26=1.16+10 ; 16=1.10+6 ; 10=1.6+4 ; 6=1.4+2 ; 4=2.2. Dus is ggd(1970,1066)=ggd(1066,904)=ggd(904,162)=ggd(162,94)=ggd(94,68) = ggd(68,26)=ggd(26,16)=ggd(16,10)=ggd(10,6)=ggd(6,4)=ggd(4,2)=2
Via dit algoritme kan men ( zoals hieronder in de stelling van Bezout vermeld wordt) de grootste gemene deler van 2 getallen schrijven als een lineaire combinatie van die twee getallen.
ggd(1970,1066)= 2= 6 – 4 = 6 – (10 – 6) = 2.6 – 10 = 2.(16 – 10) – 10 = 2.16 – 3.10 =
= 377.1066 – 204.1970.
Enkele eigenschappen
- Elke gemeenschappelijke deler van
en
is ook een deler van ggd(a,b)
- Elk gemeenschappelijk veelvoud van
en
is ook een veelvoud van kgv(a,b).
- ggd(a,b).kgv(a,b)=a.b
- Als
een deler is van
en als ggd(n,a) = 1 dan moet
een deler zijn van
.
- Als ggd(a,b)=d dan geldt : ggd(
)=1
- ggd(a,b) = ggd(b,a – qb)
- De grootste gemene deler van 2 getallen is een lineaire combinatie van die twee getallen ( stelling van Bezout ).