Υπολογιστής ΕΚΠ & ΜΚΔ

Ο ΜΚΔ είναι ο μεγαλύτερος θετικός ακέραιος που διαιρεί όλους τους δεδομένους αριθμούς χωρίς υπόλοιπο.

Χρησιμοποιήστε τον ευκλείδειο αλγόριθμο για αποτελεσματικό υπολογισμό: διαιρέστε επαναλαμβανόμενα και πάρτε τα υπόλοιπα μέχρι να φτάσετε στο 0.

Το ΕΚΠ είναι ο μικρότερος θετικός ακέραιος που διαιρείται από όλους τους δεδομένους αριθμούς.

Υπολογίστε το χρησιμοποιώντας ανάλυση σε πρώτους παράγοντες (πάρτε τις υψηλότερες δυνάμεις) ή τον τύπο: ΕΚΠ = (a × b) / ΜΚΔ.

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

Λειτουργούν αντίθετα: ο ΜΚΔ κοιτάζει προς τα κάτω για τον μεγαλύτερο κοινό παράγοντα, ενώ το ΕΚΠ κοιτάζει προς τα πάνω για το μικρότερο κοινό πολλαπλάσιο. Για το 12 και το 18, ο ΜΚΔ είναι 6 και το ΕΚΠ είναι 36.

Σύμφωνα με το Wolfram MathWorld, ο ΜΚΔ γράφεται επίσης gcd(a, b) ή (a, b), και ο όρος "highest common factor" (HCF) είναι ένα κοινό βρετανικό συνώνυμο για την ίδια ποσότητα.

Ο αλγόριθμος του Ευκλείδη βρίσκει το ΜΚΔ αντικαθιστώντας επαναλαμβανόμενα τον μεγαλύτερο αριθμό με το υπόλοιπο της διαίρεσής του με τον μικρότερο, σταματώντας όταν το υπόλοιπο μηδενιστεί. Το τελευταίο μη μηδενικό υπόλοιπο είναι ο ΜΚΔ.

Για το 48 και το 18: 48 = 2×18 + 12, έπειτα 18 = 1×12 + 6, και τέλος 12 = 2×6 + 0, άρα mcd(48, 18) = 6.

Η Encyclopaedia Britannica σημειώνει ότι αυτή η μέθοδος χρονολογείται από τα Στοιχεία του Ευκλείδη (περ. 300 π.Χ.), καθιστώντας την έναν από τους αρχαιότερους αλγορίθμους που εξακολουθούν να χρησιμοποιούνται καθημερινά. Η αποδοτικότητά του είναι ο λόγος που οι βιβλιοθήκες λογισμικού τον προτιμούν αντί να αναλύουν μεγάλους αριθμούς σε παράγοντες.

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

Για το 12 = 2²×3 και το 18 = 2×3², παίρνουμε το 2² και το 3², οπότε ΕΚΠ = 4×9 = 36. Για τον ΜΚΔ, αντίθετα, παίρνουμε κάθε κοινό πρώτο στη μικρότερη δύναμή του: 2¹×3¹ = 6.

Η Khan Academy διδάσκει αυτή τη συγκριτική μέθοδο διότι καθιστά οπτική τη διαφορά μεταξύ ΕΚΠ και ΜΚΔ. Η ανάλυση σε πρώτους παράγοντες είναι διαισθητική για μικρούς αριθμούς, αλλά πιο αργή από τον αλγόριθμο του Ευκλείδη για μεγάλους, καθώς ο υπολογισμός των παραγόντων είναι computationally δύσκολος.

Για οποιουσδήποτε δύο θετικούς ακέραιους a και b, ΕΚΠ(a, b) × ΜΚΔ(a, b) = a × b. Αυτή η ταυτότητα σάς επιτρέπει να υπολογίσετε το ένα μέγεθος από το άλλο: ΕΚΠ(a, b) = (a × b) / ΜΚΔ(a, b).

Για το 12 και το 18, ο ΜΚΔ είναι 6, οπότε ΕΚΠ = (12 × 18) / 6 = 216 / 6 = 36, και πράγματι 6 × 36 = 216 = 12 × 18.

Το Wolfram MathWorld τεκμηριώνει αυτή τη σχέση ως τη βασική γέφυρα μεταξύ των δύο συναρτήσεων. Σημειώστε ότι ο τύπος ισχύει μόνο για δύο αριθμούς. Για τρεις ή περισσότερους, τον εφαρμόζετε ανά ζεύγη αντί να υποθέσετε ότι το γινόμενο ισούται με ΕΚΠ × ΜΚΔ.

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

Για παράδειγμα, gcd(12, 18, 24) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6, και lcm(4, 6, 8) = lcm(lcm(4, 6), 8) = lcm(12, 8) = 24. Και οι δύο πράξεις είναι προσεταιριστικές, επομένως η σειρά ομαδοποίησης δεν αλλάζει την απάντηση.

Αυτός ο υπολογιστής διαχειρίζεται παρτίδες αυτόματα, αλλά η συντόμευση ΕΚΠ×ΜΚΔ = γινόμενο δεν επεκτείνεται σε τρεις ή περισσότερες εισόδους, ένα σημείο στο οποίο δίνει έμφαση το Wolfram MathWorld.

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

Για παράδειγμα, gcd(8, 15) = 1: το 8 = 2³ και το 15 = 3×5 δεν έχουν κοινό πρώτο παράγοντα, άρα είναι πρώτοι μεταξύ τους. Όταν οι αριθμοί είναι πρώτοι μεταξύ τους, το ΕΚΠ τους ισούται με το γινόμενό τους: lcm(8, 15) = 120 = 8×15.

Το Wolfram MathWorld σημειώνει ότι η ιδιότητα του να είναι οι αριθμοί πρώτοι μεταξύ τους αποτελεί τη βάση της αρθρωτής αριθμητικής και της κρυπτογραφίας RSA, όπου η δημιουργία κλειδιών απαιτεί έναν εκθέτη πρώτο ως προς το totient του Euler. Η ιδιότητα αυτή αφορά το ζεύγος και όχι τους μεμονωμένους αριθμούς.

Το ΕΚΠ και ο ΜΚΔ εμφανίζονται πολύ πέρα από τα σχολικά βιβλία.

Ο ΜΚΔ απλοποιεί τα κλάσματα στους μικρότερους δυνατούς όρους (το 12/18 γίνεται 2/3 μετά τη διαίρεση με το 6) και βρίσκει τις μεγαλύτερες ομάδες ίisου μεγέθους κατά τη διανομή αντικειμένων — και μόλις καθοριστούν αυτές οι ομάδες, ένας υπολογιστής παραγοντικού μετράει τους τρόπους ταξινόμησης των αντικειμένων μέσα σε καθεμία από αυτές.

Το ΕΚΠ βρίσκει πότε συμπίπτουν επαναλαμβανόμενα συμβάντα, όπως δύο λεωφορεία που αναχωρούν κάθε 12 και 18 λεπτά και συναντιούνται ξανά μετά από 36 λεπτά, ενώ παράγει και τον κοινό παρονομαστή για την πρόσθεση κλάσματος.

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

Η ταυτότητα του Bézout αναφέρει ότι για τους ακέραιους a και b, υπάρχουν ακέραιοι x και y τέτοιοι ώστε ax + by = gcd(a, b).

Για το 12 και το 18, ο ΜΚΔ είναι 6, και μια λύση είναι 12×(−1) + 18×(1) = −12 + 18 = 6. Ο εκτεταμένος αλγόριθμος του Ευκλείδη υπολογίζει αυτούς τους συντελεστές ταυτόχρονα με τον ΜΚΔ, κάτι που αποτελεί ακριβώς τον τρόπο με τον οποίο βρίσκονται τα αρθρωτά αντίστroφα στην κρυπτογραφία.

Το Wolfram MathWorld και η Ψηφιακή Βιβλιοθήκη Μαθηματικών Συναρτήσεων του NIST αντιμετωπίζουν την ταυτότητα του Bézout ως θεμελιώδες αποτέλεσμα της στοιχειώδους θεωρίας αριθμών, καθώς εγγυάται ότι υπάρχει πάντα ένας γραμμικός συνδυασμός ίσος με τον ΜΚΔ.

Αρκετά συνηθισμένα λάθη δυσκολεύουν τους ανθρώπους κατά τον υπολογισμό του ΕΚΠ και του ΜΚΔ:

• Ένα συχνό σφάλμα είναι η εναλλαγή των δύο: ο ΜΚΔ δεν είναι ποτέ μεγαλύτερος από τη μικρότερη είσοδο, ενώ το ΕΚΠ δεν είναι ποτέ μικρότερο από τη μεγαλύτερη είσοδο, οπότε ελέγξτε την απάντησή σας με βάση αυτό το όριο.

• Ένα άλλο λάθος είναι η υπόθεση ότι το ΕΚΠ × ΜΚΔ = γινόμενο ισχύει για τρεις ή περισσότερους αριθμούς, κάτι που δεν συμβαίνει.

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

• Τέλος, όταν οι αριθμοί είναι πρώτοι μεταξύ τους, θυμηθείτε ότι ο ΜΚΔ είναι 1 (όχι 0) και το ΕΚΠ ισούται με το γινόμενό τους.

Η επαλήθευση με την ταυτότητα ΕΚΠ×ΜΚΔ = a×b αποτρέπει τα περισσότερα λάθη σε υπολογισμούς δύο αριθμών.