Μέγιστος κοινός διαιρέτης και ελάχιστο κοινό πολλαπλάσιο

Ο μέγιστος κοινός διαιρέτης και το ελάχιστο κοινό πολλαπλάσιο

Στο μάθημα για τη διαιρετότητα και τη διαίρεση με υπόλοιπο μελετήθηκε η σχέση $d \mid a$ μεταξύ δύο φυσικών. Όταν εξετάζουμε δύο αριθμούς μαζί, μας ενδιαφέρουν οι διαιρέτες που έχουν κοινούς και τα πολλαπλάσια που μοιράζονται. Κάθε ζεύγος φυσικών $a$ και $b$ έχει τουλάχιστον έναν κοινό διαιρέτη, τον $1$, και το πολύ πεπερασμένο πλήθος κοινών διαιρετών, επειδή κανένας διαιρέτης του $a$ δεν υπερβαίνει τον $a$· έχει επιπλέον άπειρα κοινά πολλαπλάσια, μεταξύ των οποίων το γινόμενο $ab$. Αν αυτό ισχύει, ο ακόλουθος ορισμός έχει νόημα.

Ορισμός (μέγιστος κοινός διαιρέτης και ελάχιστο κοινό πολλαπλάσιο). Μέγιστος κοινός διαιρέτης δύο φυσικών $a$ και $b$, που γράφεται $\operatorname{\text{ΜΚΔ}}(a, b)$, είναι ο μεγαλύτερος φυσικός που διαιρεί και τους δύο. Ελάχιστο κοινό πολλαπλάσιο, που γράφεται $\operatorname{\text{ΕΚΠ}}(a, b)$, είναι ο μικρότερος φυσικός που είναι πολλαπλάσιο και των δύο.

Το δεύτερο είναι το ελάχιστο στοιχείο ενός μη κενού συνόλου φυσικών, που υπάρχει λόγω της αρχής της καλής διάταξης. Ο πρώτος είναι το μέγιστο στοιχείο του συνόλου των κοινών διαιρετών, το οποίο δεν είναι κενό και φράσσεται από τον $a$· ότι ένα μη κενό σύνολο φυσικών που είναι άνω φραγμένο έχει μέγιστο προκύπτει επίσης από την καλή διάταξη: το σύνολο των άνω φραγμάτων του δεν είναι κενό και έχει ελάχιστο $M$, και ο $M$ ανήκει στο σύνολο, διότι διαφορετικά κάθε στοιχείο θα ήταν μικρότερο από τον $M$ και, αφού δεν υπάρχουν φυσικοί μεταξύ του $M - 1$ και του $M$, όχι μεγαλύτερο από τον $M - 1$, ο οποίος θα ήταν άνω φράγμα μικρότερο από τον $M$ (αν $M = 1$, το σύνολο είναι το $\{1\}$ και περιέχει τον $M$). Για παράδειγμα, οι κοινοί διαιρέτες του $12$ και του $18$ είναι οι $1$, $2$, $3$ και $6$, και τα κοινά πολλαπλάσιά τους είναι τα $36$, $72$, $108$ και ούτω καθεξής:

Από τον ορισμό προκύπτουν αμέσως ορισμένες ειδικές περιπτώσεις: $\operatorname{\text{ΜΚΔ}}(a, 1) = 1$ και $\operatorname{\text{ΕΚΠ}}(a, 1) = a$· $\operatorname{\text{ΜΚΔ}}(a, a) = \operatorname{\text{ΕΚΠ}}(a, a) = a$· και, αν ο $a$ διαιρεί τον $b$, τότε $\operatorname{\text{ΜΚΔ}}(a, b) = a$ και $\operatorname{\text{ΕΚΠ}}(a, b) = b$. Οι δύο πράξεις είναι, επιπλέον, συμμετρικές: η σειρά των αριθμών δεν αλλάζει το αποτέλεσμα.

Υπολογισμός με την ανάλυση σε πρώτους παράγοντες

Σύμφωνα με το θεμελιώδες θεώρημα της αριθμητικής, κάθε φυσικός μεγαλύτερος από τον $1$ αναλύεται με μοναδικό τρόπο σε πρώτους παράγοντες. Είναι βολικό να γράφουμε τους $a$ και $b$ με τους ίδιους πρώτους $p_1, \ldots, p_k$, δεχόμενοι μηδενικούς εκθέτες για τους πρώτους που εμφανίζονται μόνο στον έναν από αυτούς:

Ένας φυσικός $d$ διαιρεί τον $a$ ακριβώς όταν στην ανάλυσή του δεν εμφανίζονται άλλοι πρώτοι εκτός από εκείνους του $a$, και ο καθένας με εκθέτη όχι μεγαλύτερο από εκείνον που έχει στον $a$. Από αυτό έπεται ότι ο $d$ διαιρεί συγχρόνως τον $a$ και τον $b$ όταν ο εκθέτης κάθε πρώτου στον $d$ δεν υπερβαίνει κανέναν από τους δύο εκθέτες· ο μεγαλύτερος κοινός διαιρέτης προκύπτει επομένως αν πάρουμε για κάθε πρώτο τον μικρότερο από τους δύο εκθέτες. Με τον ίδιο τρόπο, ο $m$ είναι κοινό πολλαπλάσιο όταν ο εκθέτης κάθε πρώτου στον $m$ φτάνει και τους δύο, και το μικρότερο κοινό πολλαπλάσιο παίρνει για κάθε πρώτο τον μεγαλύτερο από τους δύο εκθέτες. Για παράδειγμα:

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