Μέγιστος κοινός διαιρέτης

Μέγιστος κοινός διαιρέτης στη θεωρία αριθμών ονομάζεται ο μεγαλύτερος ακέραιος που διαιρεί δύο ή περισσότερους ακέραιους αριθμούς. Ο μέγιστος κοινός διαιρέτης των $a$, $b$ συμβολίζεται με ΜΚΔ$(a,b)$ ή $gcd(a,b)$ ή απλούστερα $(a,b)$.

Ορολογία

Διαιρέτης του αριθμού α λέγεται κάθε φυσικός αριθμός κ για τον οποίο υπάρχει αριθμός μ τέτοιος, ώστε: α=μκ. Με άλλα λόγια όποιος από τους αριθμούς α, α/2, α/3, α/4, ... είναι φυσικός, είναι διαιρέτης του α. Κάθε διαιρέτης του α είναι μικρότερος ή ίσος του α, αφού ο μ είναι φυσικός (μη μηδενικός) αριθμός.

Κοινός διαιρέτης των αριθμών α και β λέγεται κάθε αριθμός κ, ο οποίος είναι ταυτόχρονα διαιρέτης του α και διαιρέτης του β. Δηλαδή υπάρχουν φυσικοί αριθμοί μ και ν τέτοιοι, ώστε α=μκ και β=νκ. Κάθε ζεύγος α και β έχει τουλάχιστον ένα κοινό διαιρέτη το 1. Κάθε κοινός διαιρέτης είναι μικρότερος ή ίσος με τους α και β.

Μέγιστος κοινός διαιρέτης των αριθμών α και β είναι ο μεγαλύτερος κοινός διαιρέτης των α και β. Επειδή κάθε κοινός διαιρέτης είναι μικρότερος ή ίσος με τους α και β, αποδεικνύεται ότι υπάρχει μέγιστος διαιρέτης τους.

Ο μέγιστος κοινός διαιρέτης των $a$, $b$ συμβολίζεται με ΜΚΔ$(a,b)$ ή $gcd(a,b)$ ή απλούστερα $(a,b)$.

Δύο ακέραιοι αριθμοί καλούνται σχετικά πρώτοι ή πρώτοι προς αλλήλους ή μεταξύ τους πρώτοι αν ο μέγιστος κοινός διαιρέτης αυτών είναι 1. Προκύπτει ότι οι ακέραιοι $a$ και $b$ είναι πρώτοι μεταξύ τους αν και μόνο αν υπάρχουν ακέραιοι αριθμοί $r$ και $s$ τέτοιοι ώστε να ισχύει $ra+sb=1$.

Τρόποι εύρεσης

Με παραγοντοποίηση

Έστω ότι ψάχνουμε τον ΜΚΔ(α,β). Παραγοντοποιούμε τους α και β σε γινόμενο πρώτων παραγόντων. Ο ΜΚΔ(α,β) ισούται με το γινόμενο των κοινών πρώτων παραγόντων στη μικρότερη κοινή δύναμη.

Απόδειξη: Έστω δύο αριθμοί α και β και ο ΜΚΔ τους γ. Αφού ο γ διαιρεί το α τότε έχει κοινούς πρώτους παράγοντες με το α. Αφού διαιρεί και το β τότε έχει κοινούς πρώτους παράγοντες με το β. Συνεπάγεται ότι ο γ έχει για πρώτους παράγοντες αυτούς οι οποίοι είναι κοινοί για το α και το β. Αν δεν υπάρχουν κοινοί πρώτοι παράγοντες τότε ο ΜΚΔ είναι το ένα αφού όλοι οι αριθμοί διαιρούνται με τη μονάδα. Μένει να αποδείξουμε ότι οι πρώτοι παράγοντες είναι υψωμένοι στη μικρότερη κοινή δύναμη. Έστω ο κοινός πρώτος παράγοντας π ο οποίος είναι υψωμένος εις την μ στην περίπτωση του α και εις την ν στην περίπτωση του β. Έστω ξ το ελάχιστο των μ και ν. Αν ν=μ τότε ξ=ν=μ και φαίνεται αμέσως ότι το ξ είναι ο κατάλληλος εκθέτης για το γινόμενο πρώτων παραγόντων του γ. Αν ν>μ, τότε ξ=μ. Αν θέσουμε την τιμή του εκθέτη της ζητούμενης δύναμης για το γ μεγαλύτερη από το ξ τότε δεν θα διαιρεί τη δύναμη με εκθέτη μ καθώς το πηλίκο θα είναι μικρότερο του ενός και φυσικά όχι μηδέν. Αν τη θέσουμε μικρότερη από το ξ τότε το πηλικό θα είναι δύναμη του πρώτου παράγοντα με εκθέτη τουλάχιστον ένα και για το μ και για το ν. Άρα η μέγιστη δύναμη που διαιρεί και τις δύο δυνάμεις έχει εκθέτη ξ. Ομοίως και για ν<μ.

Παράδειγμα α: Έστω ότι α =120 και β =350. Από την παραγοντοποίηση έχουμε 120 = 2³*3*5 και 350 = 2*5²*7. Οι κοινοί πρώτοι παράγοντες είναι οι 2, 5 και οι μη κοινοί οι 3, 7. Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε 2, 5. Άρα ΜΚΔ(α,β)= 2*5 = 10.

Παράδειγμα β: Έστω ότι α=150 και β=350. Από την παραγοντοποίηση έχουμε 150=2*3*5² και 350=2*5²*7. Οι κοινοί πρώτοι παράγοντες είναι οι 2, 5 και οι μη κοινοί οι 3, 7. Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε 2, 5². Άρα ΜΚΔ(α,β)=2*5²=50.

Δείτε επίσης

• Ελάχιστο κοινό πολλαπλάσιο
• Παραγοντοποίηση
• Πρώτος αριθμός
• Θεωρία αριθμών
• Τέλειος αριθμός
• Αλγόριθμος του Ευκλείδη