Υπολογιστής GCD & LCM

Ο GCD, που ονομάζεται επίσης Μέγιστος Κοινός Παράγοντας (GCF), είναι ο μεγαλύτερος θετικός ακέραιος που διαιρεί και τους δύο αριθμούς χωρίς υπόλοιπο. Για παράδειγμα, ο GCD του 12 και του 18 είναι 6, επειδή το 6 είναι ο μεγαλύτερος αριθμός που διαιρεί και τους δύο ισόποσα.

Ο LCM είναι ο μικρότερος θετικός ακέραιος που διαιρείται και από τους δύο αριθμούς. Για παράδειγμα, ο LCM του 4 και του 6 είναι το 12, επειδή το 12 είναι ο μικρότερος αριθμός που διαιρείται τόσο από το 4 όσο και από το 6.

Για οποιουσδήποτε δύο θετικούς ακέραιους αριθμούς a και b: GCD(a,b) × LCM(a,b) = a × b. Αυτή η σχέση σας επιτρέπει να υπολογίσετε το LCM αν γνωρίζετε το GCD, ή το αντίστροφο.

Το GCD είναι απαραίτητο για την απλοποίηση κλασμάτων (διαιρεί τον αριθμητή και τον παρονομαστή με το GCD τους), την επίλυση διοφαντικών εξισώσεων και διάφορες εφαρμογές στην κρυπτογραφία και την επιστήμη των υπολογιστών.

Για να απλοποιήσετε ένα κλάσμα, διαιρέστε τόσο τον αριθμητή όσο και τον παρονομαστή με το GCD τους. Για παράδειγμα, για να απλοποιήσετε το 24/36: βρείτε το GCD(24,36) = 12, στη συνέχεια διαιρέστε και τα δύο με το 12 για να λάβετε τα 2/3. Αυτό σας δίνει το κλάσμα στους χαμηλότερους όρους του.

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

Σπάστε κάθε αριθμό σε πρώτους παράγοντες και, στη συνέχεια, πολλαπλασιάστε τους κοινούς παράγοντες με τις χαμηλότερες δυνάμεις. Για παράδειγμα, 48 = 2^4 × 3 και 18 = 2 × 3^2. Οι κοινοί παράγοντες είναι 2^1 και 3^1, οπότε GCD = 2 × 3 = 6.

Διαχωρίστε κάθε αριθμό σε πρώτους παράγοντες και, στη συνέχεια, πολλαπλασιάστε όλους τους παράγοντες χρησιμοποιώντας τις υψηλότερες δυνάμεις. Για το 12 = 2^2 × 3 και το 18 = 2 × 3^2, πάρτε το 2^2 και το 3^2, οπότε LCM = 4 × 9 = 36.

Ο ευκλείδειος αλγόριθμος βρίσκει αποτελεσματικά το GCD με επανειλημμένες διαιρέσεις και λήψη υπολοίπων. Για το GCD(48,18): Όταν το υπόλοιπο είναι 0, ο τελευταίος διαιρέτης (6) είναι ο GCD.

Οι συντριπτικοί αριθμοί (που ονομάζονται επίσης σχετικά πρώτοι) δεν έχουν κοινούς παράγοντες εκτός από το 1. Για τους συζυγείς αριθμούς, GCD = 1 και LCM = το γινόμενό τους. Για παράδειγμα, οι αριθμοί 8 και 15 είναι συνομήλικοι: GCD(8,15) = 1 και LCM(8,15) = 120.