Μέγιστος κοινός διαιρέτης
 |
Αυτό το λήμμα ή η ενότητα δεν αναφέρει τις πηγές του ή δεν περιέχει επαρκείς παραπομπές. Μπορείτε να βοηθήσετε την Βικιπαίδεια προσθέτοντας κατάλληλες πηγές και παραπομπές που να υποστηρίζουν το λήμμα. Η σήμανση τοποθετήθηκε στις 16/06/2012. |
Ο μέγιστος κοινός διαιρέτης είναι ένας σημαντικός αριθμός για τους υπολογισμούς των ακεραίων αριθμών. Έστω δύο φυσικοί αριθμοί α και β.
Πίνακας περιεχομένων |
Ορολογία [Επεξεργασία]
Διαιρέτης του αριθμού α λέγεται κάθε φυσικός αριθμός κ για τον οποίο υπάρχει αριθμός μ τέτοιος, ώστε: α=μκ Με άλλα λόγια όποιος από τους αριθμούς α, α/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.
Με τον αλγόριθμο του Ευκλείδη [Επεξεργασία]
Δείτε επίσης [Επεξεργασία]
- Ελάχιστο κοινό πολλαπλάσιο
- Παραγοντοποίηση
- Πρώτος αριθμός
- Θεωρία αριθμών
- Τέλειος αριθμός
- Αλγόριθμος του Ευκλείδη
