Aus der Schule kennt jeder den euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers (ggT). Mit diesem lässt sich auch das kleinste gemeinsame Vielfache (kgV) bestimmen, denn es gilt ggT(a,b) · kgV(a,b) = |a · b|.

Sobald man als zusätzliches Werkzeug die Primfaktorzerlegung beherrscht, kann man sowohl ggT als auch kgV einfach ablesen. Seien a und b ganze, positive Zahlen und

{style=”border: none”}

ihre kanonischen Primfaktorzerlegungen. Dann gilt

{style=”border: none”}

und

{style=”border: none”}

Man nimmt also immer den jeweils kleineren, bzw. größeren Exponenten des jeweiligen Primfaktors (der auch Null sein kann!). Am Beispiel würde das so aussehen:

{style=”border: none”}

Die kleinsten auftretenden Exponenten der Primfaktoren 2, 3 und 5 sind also 0, 2 und 0, die größten 1, 4 und 1. Damit ergibt sich der ggT(90,81)=3\^2=9 und kgV(90,81) = 2·3\^4·5 = 810. Die einzige Schwierigkeit ist nur, dass es noch keinen effizienten Algorithmus gibt, um die Primfaktorzerlegung für größere Zahlen durchzuführen, auch wenn man diese im vorliegenden Beispiel leicht im Kopf errechnen kann. Aber wenn man die Primfaktoren schon kennt, kommt man mit dieser Methode schneller ans Ziel.