Έστω ότι ψάχνουμε τον ΜΚΔ(''α'',''β''). Παραγοντοποιούμε τους ''α'' και ''β'' σε [[γινόμενο πρώτων παραγόντων]]. Ο ΜΚΔ(''α'',''β'') ισούται με το γινόμενο των κοινών πρώτων παραγόντων στη μικρότερη κοινή δύναμη.
''Απόδειξη'': Έστω δύο αριθμοί ''α'' και ''β'' και ο ΜΚΔ τους ''γ''. Αφού ο ''γ'' διαιρεί το ''α'' τότε έχει κοινούς πρώτους παράγοντες με το ''α''. Αφού διαιρεί και το ''β'' τότε έχει κοινούς πρώτους παράγοντες με το ''β''. Συνεπάγεται ότι ο ''γ'' έχει για πρώτους παράγοντες αυτούς οι οποίοι είναι κοινοί για το ''α'' και το ''β''. Αν δεν υπάρχουν κοινοί πρώτοι παράγοντες τότε ο ΜΚΔ είναι το ένα αφού όλοι οι αριθμοί διαιρούνται με τη μονάδα. Μένει να αποδείξουμε ότι οι πρώτοι παράγοντες είναι υψωμένοι στη μικρότερη κοινή δύναμη. Έστω ο κοινός πρώτος παράγοντας ''π'' ο οποίος είναι υψωμένος εις την ''μ'' στην περίπτωση του ''α'' και εις την ''ν'' στην περίπτωση του ''β''. Έστω ''ξ'' το ελάχιστο των ''μ'' και ''ν''. Αν ''ν''=''μ'' τότε ''ξ''=''ν''=''μ'' και φαίνεται αμέσως ότι το ''ξ'' είναι ο κατάλληλος εκθέτης για το γινόμενο πρώτων παραγόντων του ''γ''. Αν ''ν''>''μ'', τότε ''ξ''=''μ''. Αν θέσουμε την τιμή του εκθέτη της ζητούμενης δύναμης για το ''γ'' μεγαλύτερη από το ''ξ'' τότε δεν θα διαιρεί τη δύναμη με εκθέτη ''μ'' καθώς το πηλίκο θα είναι μικρότερο του ενός και φυσικά όχι μηδέν. Αν τη θέσουμε μικρότερη από το ''ξ'' τότε το πηλικό θα είναι δύναμη του πρώτου παράγοντα με εκθέτη τουλάχιστον ένα και για το ''μ'' και για το ''ν''. Άρα η μέγιστη δύναμη που διαιρεί και τις δύο δυνάμεις έχει εκθέτη ''ξ''. Ομοίως και για ''ν''<''μ''.
''Παράδειγμα α'': Έστω ότι α =120 και β =350. Από την παραγοντοποίηση έχουμε 120 = 2<sup>3</sup>*3*5 και 350 = 2*5<sup>2</sup>*7. Οι κοινοί πρώτοι παράγοντες είναι οι 2, 5 και οι μη κοινοί οι 3, 7. Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε 2, 5. Άρα ΜΚΔ(α,β)= 2*5 = 10.
''Παράδειγμα β'': Έστω ότι α=150 και β=350. Από την παραγοντοποίηση έχουμε 150=2*3*5<sup>2</sup> και 350=2*5<sup>2</sup>*7. Οι κοινοί πρώτοι παράγοντες είναι οι 2, 5 και οι μη κοινοί οι 3, 7. Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε 2, 5<sup>2</sup>. Άρα ΜΚΔ(α,β)=2*5<sup>2</sup>=50.
=== Με τον [[αλγόριθμος του Ευκλείδη|αλγόριθμο του Ευκλείδη]] ===
