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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

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

Ορολογία[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

Ο μέγιστος κοινός διαιρέτης των , συμβολίζεται με ΜΚΔ ή ή απλούστερα .[3]

Δύο ακέραιοι αριθμοί καλούνται σχετικά πρώτοι ή πρώτοι προς αλλήλους ή μεταξύ τους πρώτοι αν ο μέγιστος κοινός διαιρέτης αυτών είναι 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.

Με τον αλγόριθμο του Ευκλείδη[Επεξεργασία | επεξεργασία κώδικα]

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Παπαδημητράκης Μιχάλης. «Θεωρία Αριθμών. Κεφάλαιο 3 Μέγιστος κοινός διαιρέτης», σελ. 11, από Πανεπιστήμιο Κρήτης-Τμήμα Μαθηματικών. Αρχειοθετήθηκε 03/04/2018. Ανακτήθηκε 16/01/2019.
  2. Τζανάκης Γ.Ν., (2012). «Θεμελιώδης Θεωρία Αριθμών», σελ. 7, από Πανεπιστήμιο Κρήτης-Τμήμα Μαθηματικών. Αρχειοθετήθηκε 10/01/2017. Ανακτήθηκε 16/01/2019.
  3. Κάτος, Β., Στεφανίδης, Γ., (2003). «Τεχνικές Κρυπτογραφίας και Κρυπτανάλυσης. 3.Θεωρία αριθμών - αλγεβρικές δομές», σελ. 6, Εκδόσεις: ΖΥΓΟΣ, (ISBN 960-8065-40-2). Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.