.
Μέγιστος κοινός διαιρέτης στη θεωρία των αριθμών ονομάζεται ο μεγαλύτερος ακέραιος που διαιρεί ακριβώς δύο ακέραιους αριθμούς.
Ορολογία
Διαιρέτης του αριθμού α λέγεται κάθε φυσικός αριθμός κ για τον οποίο υπάρχει αριθμός μ τέτοιος, ώστε: α=μκ Με άλλα λόγια όποιος από τους αριθμούς α, α/2, α/2, α/4, ... είναι φυσικός, είναι διαιρέτης του α. Κάθε διαιρέτης του α είναι μικρότερος ή ίσος του α, αφού ο μ είναι φυσικός (μη μηδενικός) αριθμός.
Κοινός διαιρέτης των αριθμών α και β λέγεται κάθε αριθμός κ, ο οποίος είναι ταυτόχρονα διαιρέτης του α και διαιρέτης του β. Δηλαδή υπάρχουν φυσικοί αριθμοί μ και ν τέτοιοι, ώστε α=μκ και β=νκ. Κάθε ζεύγος α και β έχει τουλάχιστον ένα κοινό διαιρέτη το 1. Κάθε κοινός διαιρέτης είναι μικρότερος ή ίσος με τους α και β.
Μέγιστος κοινός διαιρέτης των αριθμών α και β είναι ο μεγαλύτερος κοινός διαιρέτης των α και β. Επειδή κάθε κοινός διαιρέτης είναι μικρότερος ή ίσος με τους α και β, αποδεικνύεται ότι υπάρχει μέγιστος διαιρέτης τους.
ο μέγιστος κοινός διαιρέτης των α, β συμβολίζεται με ΜΚΔ(α,β).
Τρόποι εύρεσης
Με παραγοντοποίηση
Έστω ότι ψάχνουμε τον ΜΚΔ(α,β). Παραγοντοποιούμε τους α και β σε γινόμενο πρώτων παραγόντων. Ο ΜΚΔ(α,β) ισούται με το γινόμενο των κοινών πρώτων παραγόντων στη μικρότερη κοινή δύναμη.
Απόδειξη: Έστω δύο αριθμοί α και β και ο ΜΚΔ τους γ. Αφού ο γ διαιρεί το α τότε έχει κοινούς πρώτους παράγοντες με το α. Αφού διαιρεί και το β τότε έχει κοινούς πρώτους παράγοντες με το β. Συνεπάγεται ότι ο γ έχει για πρώτους παράγοντες αυτούς οι οποίοι είναι κοινοί για το α και το β. Αν δεν υπάρχουν κοινοί πρώτοι παράγοντες τότε ο ΜΚΔ είναι το ένα αφού όλοι οι αριθμοί διαιρούνται με τη μονάδα. Μένει να αποδείξουμε ότι οι πρώτοι παράγοντες είναι υψωμένοι στη μικρότερη κοινή δύναμη. Έστω ο κοινός πρώτος παράγοντας π ο οποίος είναι υψωμένος εις την μ στην περίπτωση του α και εις την ν στην περίπτωση του β. Έστω ξ το ελάχιστο των μ και ν. Αν ν=μ τότε ξ=ν=μ και φαίνεται αμέσως ότι το ξ είναι ο κατάλληλος εκθέτης για το γινόμενο πρώτων παραγόντων του γ. Αν ν>μ, τότε ξ=μ. Αν θέσουμε την τιμή του εκθέτη της ζητούμενης δύναμης για το γ μεγαλύτερη από το ξ τότε δεν θα διαιρεί τη δύναμη με εκθέτη μ καθώς το πηλίκο θα είναι μικρότερο του ενός και φυσικά όχι μηδέν. Αν τη θέσουμε μικρότερη από το ξ τότε το πηλικό θα είναι δύναμη του πρώτου παράγοντα με εκθέτη τουλάχιστον ένα και για το μ και για το ν. Άρα η μέγιστη δύναμη που διαιρεί και τις δύο δυνάμεις έχει εκθέτη ξ. Ομοίως και για ν<μ.
Παράδειγμα α: Έστω ότι α =120 και β =350. Από την παραγοντοποίηση έχουμε 120 = 23*3*5 και 350 = 2*52*7. Οι κοινοί πρώτοι παράγοντες είναι οι 2, 5 και οι μη κοινοί οι 3, 7. Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε 2, 5. Άρα ΜΚΔ(α,β)= 2*5 = 10.
Παράδειγμα β: Έστω ότι α=150 και β=350. Από την παραγοντοποίηση έχουμε 150=2*3*52 και 350=2*52*7. Οι κοινοί πρώτοι παράγοντες είναι οι 2, 5 και οι μη κοινοί οι 3, 7. Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε 2, 52. Άρα ΜΚΔ(α,β)=2*52=50.
Με τον αλγόριθμο του Ευκλείδη
Δείτε επίσης
Ελάχιστο κοινό πολλαπλάσιο
Παραγοντοποίηση
Πρώτος αριθμός
Θεωρία αριθμών
Τέλειος αριθμός
Αλγόριθμος του Ευκλείδη
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
