het kleinste gemeenschappelijke veelvoud (kgv) van een verzameling positieve gehele getallen is per definitie het kleinste getal dat deelbaar is door al deze getallen. Om dat getal te vinden is het héél handig om de priemfactorisatie van die getallen te kennen.
Voorbeeld: stel je zoekt de kgv van 60 en 72. Vind dan eerst de priemfactorisaties van 60 en 72
60=22×31×51
72=23×32×50
Het kgv(60, 72) is een veelvoud van 60, en is dus
deelbaar door 60, en is dus deelbaar door
22, door
31 en door
51. Het heeft dus minstens 2 factoren 2, 1 factor 3 en 1 factor 5.
Het is evenzo
deelbaar door 72, en dus deelbaar door
23 en door
32. Het heeft dus minstens 3 factoren 2 en 2 factoren 3.
Een getal met al deze eisen heeft 3 factoren 2, 2 factoren 3 en 1 factor 5, en het kleinste heeft verder geen priemfactoren. Dat getal bedraagt dus:
23×32×51=360
Inderdaad is 360 deelbaar door 60 en 72:
360/60=6 en
360/72=5. De quotiënten hebben geen gemeenschappelijke delers (waarom?)
Dit werkt ook zo voor de kgv van méér dan 2 getallen. Voorbeeld: kgv(80, 84, 90)
80=24×30×51×70
84=22×31×50×71
90=21×32×51×70
iets wat deelbaar is door
24 door
22 en door
21 is deelbaar door
2max
Dus je neemt voor elke exponent de hoogste van alle die voorkomen:
2^4 \times 3^2 \times 5^1 \times 7^1 = 5040
Dus dat is het algoritme:
neem van alle priemfactoren in alle getallen, de hoogst voorkomende exponent.
Dan kgv(1, 2, ..., n). Ter voorbeeld kgv(1, 2, ..., 16):
1 = 2^0 \times 3^0 \times \cdots
2 = 2^1 \times 3^0 \times \cdots
3 = 2^0 \times 3^1 \times \cdots
4 = 2^2 \times 3^0 \times \cdots
5 = 2^0 \times 3^0 \times \cdots
6 = 2^1 \times 3^1 \times \cdots
7 = 2^0 \times 3^0 \times \cdots
8 = 2^3 \times 3^0 \times \cdots
9 = 2^0 \times 3^2 \times \cdots
10 = 2^1 \times 3^0 \times \cdots
11 = 2^0 \times 3^0 \times \cdots
12 = 2^2 \times 3^1 \times \cdots
13 = 2^0 \times 3^0 \times \cdots
14 = 2^1 \times 3^0 \times \cdots
15 = 2^0 \times 3^1 \times \cdots
16 = 2^4 \times 3^0 \times \cdots
De reden dat ik het zo uitschrijf is dat je dan de regelmaat ziet in de exponenten.
Wat is de hoogste exponent van priemfactor 2 die voorkomt in 1 .. 16? Dat is 4, want
2^4 <= 16 en
2^5 > 16.
Wat is de hoogste exponent van priemfactor p die voorkomt in 1 .. n? Dat is die k zodanig dat
p^k <= n en
p^{k + 1} > n.
En dat is dus
\lfloor \log_{p}{n} \rfloor (de haken betekenen: afronden naar beneden (floor))
Conclusie: kgv(1, ..., n) heeft als priemfactoren alle priemfactoren in 1 ... n (dus alle priemgetallen
\leq n), met als exponent de hoogst voorkomende exponent van p in 1 .. n, oftewel:
kgv(1, ..., n) =
\prod_{p \leq n} p^{ \lfloor \log_{p}{n} \rfloor} voor alle priemgetallen p.