el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el el
Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν. Μπορείτε να βοηθήσετε προσθέτοντας την κατάλληλη τεκμηρίωση. Υλικό που είναι ατεκμηρίωτο μπορεί να αμφισβητηθεί και να αφαιρεθεί.
Μέγιστος κοινός διαιρέτης στη θεωρία αριθμών ονομάζεται ο μεγαλύτερος ακέραιος που διαιρεί δύο ή περισσότερους ακέραιους αριθμούς.[1][2] Ο μέγιστος κοινός διαιρέτης των a {\displaystyle a} , b {\displaystyle b} συμβολίζεται με ΜΚΔ ( a , b ) {\displaystyle (a,b)} ή g c d ( a , b ) {\displaystyle gcd(a,b)} ή απλούστερα ( a , b ) {\displaystyle (a,b)} .
2.2 Με τον αλγόριθμο του Ευκλείδη
Κοινός διαιρέτης των αριθμών α και β λέγεται κάθε αριθμός κ, ο οποίος είναι ταυτόχρονα διαιρέτης του α και διαιρέτης του β. Δηλαδή υπάρχουν φυσικοί αριθμοί μ και ν τέτοιοι, ώστε α=μκ και β=νκ. Κάθε ζεύγος α και β έχει τουλάχιστον ένα κοινό διαιρέτη το 1. Κάθε κοινός διαιρέτης είναι μικρότερος ή ίσος με τους α και β.
Μέγιστος κοινός διαιρέτης των αριθμών α και β είναι ο μεγαλύτερος κοινός διαιρέτης των α και β. Επειδή κάθε κοινός διαιρέτης είναι μικρότερος ή ίσος με τους α και β, αποδεικνύεται ότι υπάρχει μέγιστος διαιρέτης τους.
Ο μέγιστος κοινός διαιρέτης των a {\displaystyle a}  , b {\displaystyle b}   συμβολίζεται με ΜΚΔ ( a , b ) {\displaystyle (a,b)}   ή g c d ( a , b ) {\displaystyle gcd(a,b)}   ή απλούστερα ( a , b ) {\displaystyle (a,b)}  .[3]
Δύο ακέραιοι αριθμοί καλούνται σχετικά πρώτοι ή πρώτοι προς αλλήλους ή μεταξύ τους πρώτοι αν ο μέγιστος κοινός διαιρέτης αυτών είναι 1. Προκύπτει ότι οι ακέραιοι a {\displaystyle a}   και b {\displaystyle b}   είναι πρώτοι μεταξύ τους αν και μόνο αν υπάρχουν ακέραιοι αριθμοί r {\displaystyle r}   και s {\displaystyle s}   τέτοιοι ώστε να ισχύει r a + s b = 1 {\displaystyle ra+sb=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.
Με τον αλγόριθμο του ΕυκλείδηΕπεξεργασία
↑ Παπαδημητράκης Μιχάλης. «Θεωρία Αριθμών. Κεφάλαιο 3 Μέγιστος κοινός διαιρέτης», σελ. 11, από Πανεπιστήμιο Κρήτης-Τμήμα Μαθηματικών. Αρχειοθετήθηκε 03/04/2018. Ανακτήθηκε 16/01/2019.
↑ Τζανάκης Γ.Ν., (2012). «Θεμελιώδης Θεωρία Αριθμών», σελ. 7, από Πανεπιστήμιο Κρήτης-Τμήμα Μαθηματικών. Αρχειοθετήθηκε 10/01/2017. Ανακτήθηκε 16/01/2019.
↑ Κάτος, Β., Στεφανίδης, Γ., (2003). «Τεχνικές Κρυπτογραφίας και Κρυπτανάλυσης. 3.Θεωρία αριθμών - αλγεβρικές δομές», σελ. 6, Εκδόσεις: ΖΥΓΟΣ, (ISBN 960-8065-40-2). Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.