KGV van meer dan 2 getallen

[janutrecht]

Hallo,

Ik heb een concrete vraag: hoe bereken je de kgv van 3 getallen. Overal waar ik kijk, gaat het over 2 getallen..

De vraag komt voort uit het 3 keer uitvoeren van vigenere cipher. De lengte van de sleutel is namelijk de kgv van de gebruikte sleutellengtes. In dit geval 7, 8 en 9.

Groeten,
Jan

[David]

Hallo Jan,

Als je drie getallen hebt en je gaat die priemfactoriseren (weet je wat dat is?) krijg je 3 factorisaties. Kijk bij elke priem in die 3 factorisaties naar de grootste exponent van die drie, vermenigvuldig dat en je hebt de kleinste k.g.v.
vb: . er staan 3 priemgetallen, 2, 3 en 5. Voor 2 is de grootste exponent van de 3 factoren 1, in 30. Voor 3 is de grootste exponent 3, in 27. en voor 5 is de grooste exponent 1, in 15.

[janutrecht]

Daco, dankjewel voor de snelle reactie. Je hebt mijn vraag duidelijk beantwoord.
Groeten,
Jan

[David]

Jan, graag gedaan, succes verder.

[arie]

Ter aanvulling:
Bovenstaande is helemaal correct, maar als je met erg grote getallen gaat werken is het veel efficienter om het algoritme van Euclides te gebruiken.
Herleid eerst:
kgv(a,b,c) = kgv(a, kgv(b,c))

kgv(b,c) = (b*c) / ggd(b,c)

en bepaal ggd(b,c) met het algoritme van Euclides, zie bijvoorbeeld http://nl.wikipedia.org/wiki/Algoritme_van_Euclides
Nu is ggd(b,c) dus ook kgv(b,c) bekend.

Vervolgens doe je hetzelfde nog een keer om kgv(a, kgv(b,c)) te berekenen.

Voor de doorzetters: bepaal kgv(5621977, 8359721, 31014497).