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

Στην θεωρία αριθμών, ο μέγιστος κοινός διαιρέτης στη θεωρία αριθμών ονομάζεται ο μεγαλύτερος ακέραιος που διαιρεί δύο ή περισσότερους ακέραιους αριθμούς.Παπαδημητράκης Μιχάλης. «Θεωρία Αριθμών. Κεφάλαιο 3 Μέγιστος κοινός διαιρέτης», σελ. 11, από Πανεπιστήμιο Κρήτης-Τμήμα Μαθηματικών. Αρχειοθετήθηκε 03/04/2018. Ανακτήθηκε 16/01/2019.Τζανάκης Γ.Ν., (2012). «Θεμελιώδης  Θεωρία  Αριθμών», σελ. 7, από Πανεπιστήμιο Κρήτης-Τμήμα Μαθηματικών. Αρχειοθετήθηκε 10/01/2017. Ανακτήθηκε 16/01/2019. Ο μέγιστος κοινός διαιρέτης των ,  συμβολίζεται με ΜΚΔ ή  ή απλούστερα . 

Για παράδειγμα, ο μέγιστος κοινός διαιρέτης του  και του  είναι το , ενώ του  και του  είναι το .

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

Για παράδειγμα, οι διαιρέτες του  είναι οι αριθμοί  και του  είναι οι αριθμοί .

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

Για παράδειγμα, κοινοί διαιρέτες των  και του  είναι οι αριθμοί , δηλαδή η τομή των συνόλων  και .

Μέγιστος κοινός διαιρέτης των ακεραίων  και  είναι ο μεγαλύτερος κοινός τους διαιρέτης. Επειδή το σύνολο  είναι πεπερασμένο και έχει τουλάχιστον ένα στοιχείο, έπεται ότι πάντα υπάρχει ο μέγιστος κοινός διαιρέτης δύο ακεραίων. Ο μέγιστος κοινός διαιρέτης των ,  συμβολίζεται με  ή  ή απλούστερα .Κάτος, Β., Στεφανίδης, Γ., (2003). «Τεχνικές Κρυπτογραφίας και Κρυπτανάλυσης. 3.Θεωρία αριθμών - αλγεβρικές δομές», σελ. 6, Εκδόσεις: ΖΥΓΟΣ, . Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.

Για παράδειγμα, ο μέγιστος κοινός κοινός διαιρέτης του  και του  είναι το .

Δύο ακέραιοι αριθμοί καλούνται σχετικά πρώτοι αν ο μέγιστος κοινός διαιρέτης αυτών είναι 1.

 Ιδιότητες 

Ο μέγιστος κοινός διαιρέτης 
 .

 Για κάθε , ισχύει ότι .
Σημείωση: Η ιδιότητα αυτή χρησιμεύει στην απόδειξη της ορθότητας του αλγόριθμου του Ευκλείδη για την εύρεση του ΜΚΔ.

 Υπάρχουν ακέραιοι  ώστε .

 .

 Για κάθε , ισχύει ότι .

 .

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

 .

 , τότε .

 (Λήμμα Ευκλείδη) Αν  και , τότε .Δείτε την απόδειξη στο σχετικό λήμμα.
 Αν ,  και , τότε .

 Αν , τότε .

 Αν  και , τότε  .

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

 Παράδειγμα 1ο 
Έστω ότι  και . Από την παραγοντοποίηση έχουμε
 και . 
Οι κοινοί πρώτοι παράγοντες είναι οι ,  και οι μη κοινοί οι , . Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε , . Άρα 
.

 Παράδειγμα 2ο 
Έστω ότι  και . Από την παραγοντοποίηση έχουμε 
 και .
Οι κοινοί πρώτοι παράγοντες είναι οι ,  και οι μη κοινοί οι , . Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε , . Άρα 
.

 Με τον αλγόριθμο του Ευκλείδη 

Ο αλγόριθμος του Ευκλείδη υπολογίζει τον μέγιστο κοινό διαιρέτη δύο αριθμών χρησιμοποιώντας την εξής αναδρομική σχέση που αποδείξαμε παραπάνω:

int gcd(int a, int b) {
   if (a mod b == 0) return b;
   return gcd(b, a mod b);
}

Ο επεκταμένος αλγόριθμος που Ευκλείδη, επιστρέφει επίσης δύο αριθμούς  τέτοιους ώστε .

 Παράδειγμα 1ο 

 Παράδειγμα 2ο 

 Για παραπάνω από δύο ακεραίους 

Ο ορισμός του μέγιστου κοινού διαιρέτη γενικεύεται για δύο ή περισσότερους ακέραιους αριθμούς. 

Οι κοινοί διαιρέτες των αριθμών  είναι η τομή των συνόλων των διαιρετών των αριθμών αυτών, δηλαδή
.
Το σύνολο αυτό περιέχει τουλάχιστον ένα στοιχείο (το ) και είναι πεπερασμένο, καθώς κάθε στοιχείο είναι μικρότερο του .

Ο μέγιστος κοινός διαιρέτης των αριθμών  είναι το μέγιστο στοιχείο του , δηλαδή 
.

 Ιδιότητες 
Για κάθε ακεραίους  ισχύουν οι εξής ιδιότητες:
 .

 .
Σημείωση: Η παραπάνω ιδιότητα ανάγει τον υπολογισμό του μέγιστου κοινού διαιρέτη πολλών αριθμών στον υπολογισμό του μέγιστου κοινού διαιρέτη δύο αριθμών.

 Υπάρχουν ακέραιοι  τέτοιοι ώστε
.

 Αν , τότε .

 Αν , τότε 
.
 Για κάθε , τότε .
 Δείτε επίσης 
Ελάχιστο κοινό πολλαπλάσιο
Παραγοντοποίηση
Αλγόριθμος του Ευκλείδη

 Παραπομπές 



Κατηγορία:Θεωρία αριθμών