Als a en b twee positieve gehele getallen zijn met
en waarvoor ggd(a,b) = 7, bepaal dan a+b.
.
- Dus
en
.
- Bijgevolg is
.
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:
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