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

Άλλα εργαλεία

Υπολογιστής εμβαδού{$ ',' | translate $}
Υπολογιστής περιμέτρου{$ ',' | translate $}
Εργαλείο υπολογισμού όγκου{$ ',' | translate $}
Πίνακας πολλαπλασιασμού{$ ',' | translate $}
Περιοδικός πίνακας{$ ',' | translate $}
Υπολογιστής μήτρας{$ ',' | translate $}
Υπολογιστής ΕΚΠ{$ ',' | translate $}
Υπολογιστής τριγωνομετρίας{$ ',' | translate $}

Αριθμομηχανή μέγιστου κοινού διαιρέτη

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

Είναι γνωστό ότι ένας ακέραιος αριθμός μπορεί να έχει πολλούς διαιρέτες. Μας ενδιαφέρει η ταυτόχρονη πρόσβαση σε αυτά από αρκετούς ακέραιους αριθμούς. Θεωρούμε ότι ο κοινός διαιρέτης πολλών ακεραίων είναι ο αριθμός που μπορεί να λειτουργήσει ως διαιρέτης για κάθε αριθμό από την καθορισμένη σειρά.

Για παράδειγμα, οι αριθμοί 8 και 12 έχουν τους ακόλουθους κοινούς διαιρέτες: 1 και 4. Αυτό μπορεί εύκολα να επαληθευτεί γράφοντας μαθηματικές παραστάσεις: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.

Θα πρέπει να σημειωθεί ότι κάθε αριθμός αρχικά έχει τουλάχιστον δύο κοινούς διαιρέτες: οποιοσδήποτε αριθμός διαιρείται από τον εαυτό του χωρίς υπόλοιπο και διαιρείται επίσης με το 1.

Προσδιορισμός του μεγαλύτερου κοινού διαιρέτη

Ο μεγαλύτερος κοινός διαιρέτης (GCD) δύο φυσικών αριθμών είναι ο μεγαλύτερος από τους φυσικούς αριθμούς με τον οποίο μπορούμε να διαιρέσουμε δύο από τους αριθμούς μας. Εάν η τιμή του μεγαλύτερου κοινού διαιρέτη δύο φυσικών αριθμών είναι 1, τότε ονομάζουμε αυτούς τους αριθμούς συνπρωτικούς.

Για δύο αριθμούς a και b, ο μεγαλύτερος κοινός διαιρέτης είναι ο αριθμός με τον οποίο μπορούν να διαιρεθούν τα a και b χωρίς υπόλοιπο. Αυτή η έκφραση γράφεται ως εξής: gcd (a, b) = c.

Ένας άλλος τρόπος για να γράψετε GCD: (a, b) = c. Ωστόσο, στις περισσότερες περιπτώσεις, χρησιμοποιείται η πρώτη επιλογή.

Έτσι, για παράδειγμα, οι αριθμοί 4 και 16 έχουν τον μεγαλύτερο κοινό διαιρέτη ίσο με 4. Ας γράψουμε: gcd (4, 16) = 4.

Ας περιγράψουμε πώς καταλήξαμε σε αυτό το αποτέλεσμα:

Διαγράψαμε όλους τους διαιρέτες του αριθμού 4. Πήραμε: 4, 2, 1.
Στη συνέχεια, ζωγραφίσαμε όλους τους διαιρέτες του 16. Πήραμε: 16, 8, 4, 2, 1.
Επιλέξαμε διαιρέτες που είναι κοινοί για το 4 και το 16. Πήραμε: 4, 2, 1.
Από τους κοινούς διαιρέτες που προέκυψαν, επιλέχθηκε ο μεγαλύτερος. Αυτό είναι 4.
Λαμβάνουμε την απάντηση: για τους αριθμούς 4 και 16 το GCD είναι 4.

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

Έτσι, για παράδειγμα, ο μεγαλύτερος διαιρέτης για τους ακέραιους αριθμούς 6, 12, 18, 42 θα είναι ο αριθμός 6, δηλαδή, gcd (6, 12, 18, 42) = 6. Η απάντηση λήφθηκε χρησιμοποιώντας έναν αλγόριθμο παρόμοιο με αυτό που περιγράφηκε παραπάνω - για αριθμούς από μια σειρά, όλοι οι διαιρέτες γράφτηκαν διαδοχικά και μετά επιλέχθηκαν οι μεγαλύτεροι από αυτούς.

Ιδιότητες GCD

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

Ιδιότητα 1

Από την αλλαγή θέσεων αριθμών, η τελική τιμή του GCD δεν θα αλλάξει. Μπορείτε να γράψετε αυτήν τη δήλωση ως εξής:

gcd(a, b) = gcd(b, a).

Ιδιότητα 2

Αν το a διαιρείται με το b, τότε το σύνολο των κοινών διαιρετών του a και του b είναι ίδιο με το σύνολο των διαιρετών του b. Γράφτηκε ως εξής:

gcd(a, b) = b.

Η αποδεδειγμένη ιδιότητα του μεγαλύτερου διαιρέτη μπορεί να χρησιμοποιηθεί για την εύρεση του gcd δύο αριθμών όταν ο ένας από αυτούς διαιρείται με τον άλλο. Σε αυτήν την περίπτωση, το GCD είναι ίσο με έναν από αυτούς τους αριθμούς, με τον οποίο διαιρείται ένας άλλος αριθμός.

Για παράδειγμα:

gcd(12, 4) = 4.

Παρόμοιο:

gcd(10, 1) = 1.

Ιδιότητα 3

Αν a = bq + c, όπου τα a, b, c και q είναι ακέραιοι, τότε το σύνολο των κοινών διαιρετών των a και b είναι το ίδιο με το σύνολο των κοινών διαιρετών των b και c.

Η ισότητα gcd (a, b) = gcd (b, c) καθίσταται έγκυρη.

Ιδιότητα 4

Η έκφραση gcd(ma, mb) = m ⋅ gcd(a, b) είναι αληθής υπό τον όρο ότι m είναι οποιοσδήποτε φυσικός αριθμός.

Ιδιότητα 5

Ας υποθέσουμε ότι το p είναι οποιοσδήποτε κοινός διαιρέτης των a και b.

Στη συνέχεια:

gcd(a / p, b / p) = gcd(a, b) / p.

Αν p = gcd(a, b), παίρνουμε:

gcd (a / gcd (a, b), b / gcd (a, b)) = 1,

Έτσι, οι αριθμοί a / gcd (a, b) και b / gcd (a, b) είναι συμπρώτοι.

Ιδιότητα 6

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

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

Πώς θα βρεις το μέγιστο κοινό παράγοντα

Η εύρεση του μεγαλύτερου κοινού διαιρέτη (gcd) είναι μια αρκετά δημοφιλής εργασία. Αυτή η ενέργεια μας βοηθά να πραγματοποιήσουμε υπολογισμούς στους οποίους εμφανίζονται συνηθισμένα κλάσματα.

Μέθοδοι εύρεσης GCD

Υπάρχουν πολλά κόλπα για να βρείτε τον μεγαλύτερο κοινό διαιρέτη. Θα εξετάσουμε τα πιο δημοφιλή από αυτά.

Εύρεση του GCD με αποσύνθεση αριθμών σε πρώτους παράγοντες

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

Ο αλγόριθμος για τον προσδιορισμό του GCD με αποσύνθεση σε πρώτους παράγοντες αποτελείται από τα ακόλουθα βήματα:

Παριστάνουμε τους αριθμούς ως πρώτους παράγοντες. Για παράδειγμα, ο αριθμός 20 μπορεί να αναπαρασταθεί ως γινόμενο 2 ⋅ 2 ⋅ 5.
Επιλέξτε τους παράγοντες που θα υπάρχουν και στις δύο επεκτάσεις.
Βρείτε το γινόμενο αυτών των παραγόντων.

Ας εξετάσουμε μερικά παραδείγματα εφαρμογής αυτού του αλγορίθμου στην πράξη:

Προσδιορίστε το GCD των αριθμών 12 και 8.

Αποσύνθεση 12 και 8 σε πρώτους παράγοντες:

12 = 2 ⋅ 2 ⋅ 3.
8 = 2 ⋅ 2 ⋅ 2.

Εξετάζουμε ποιοι παράγοντες υπάρχουν και στις δύο επεκτάσεις. Βρείτε: 2 και 2.

Πολλαπλασιάζουμε τους παράγοντες και παίρνουμε:

2 ⋅ 2 = 4.

Απάντηση: gcd (12, 8) = 4.

Προσδιορίστε το GCD των αριθμών 75 και 150.

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

Ας αντιπροσωπεύσουμε το 75 και το 150 ως πρώτους παράγοντες:

75 = 3 ⋅ 5 ⋅ 5.
150 = 2 ⋅ 3 ⋅ 5 ⋅ 5.

Προσδιορίστε τους παράγοντες που επαναλαμβάνονται και στις δύο επεκτάσεις: 3, 5 και 5.

Πολλαπλασιάζουμε τους αριθμούς που προκύπτουν μεταξύ τους: 3 ⋅ 5 ⋅ 5 = 75.

Απάντηση: gcd (75, 150) = 75.

Προσδιορίστε το GCD των αριθμών 9 και 5.

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

Όταν συνυπολογίζουμε το 9 και το 5 σε πρώτους παράγοντες, θα δούμε ότι δεν έχουν τους ίδιους παράγοντες:

5 = 5.
9 = 3 ⋅ 3.

Πρέπει να θυμόμαστε ότι αυτή η περίπτωση είναι ιδιαίτερη. Τέτοιοι αριθμοί είναι συμπρώτοι και ο κοινός διαιρέτης τους είναι ένας.

Αλγόριθμος του Ευκλείδη

Αυτός ο αλγόριθμος πήρε το όνομά του από τον αρχαίο Έλληνα μαθηματικό Ευκλείδη, ο οποίος τον περιέγραψε πρώτος στα γραπτά του (7ο και 10ο βιβλίο των "Αρχών"). Είναι γνωστό ότι ο Ευκλείδης δεν ήταν ο συγγραφέας αυτού του αλγορίθμου. Ωστόσο, θεωρείται ένας από τους παλαιότερους αλγόριθμους που χρησιμοποιούνται σήμερα.

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

Για να βρείτε το GCD (a, b), αυτός ο αλγόριθμος μοιάζει με αυτό:

Αν a = 0 τότε gcd(a, b) = b επειδή gcd(0, b) = b και ο αλγόριθμος σταματά.
Αν b = 0 τότε gcd(a, b) = a επειδή gcd(a, 0) = a και ο αλγόριθμος σταματά.
Διαιρέστε το a με το b με το υπόλοιπο (a = b ⋅ q + r)
Βρείτε gcd(b, r) χρησιμοποιώντας τον αλγόριθμο του Ευκλείδη επειδή gcd(a, b) = gcd(b, r).

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

Είναι απαραίτητο να προσδιορίσετε το GCD των αριθμών 270 και 192.

a = 270, b = 192.
a ≠ 0.
b ≠ 0.

Διαιρέστε το a με το b, παίρνουμε:

270 / 192 = 1 (το υπόλοιπο είναι 78).

Μπορείτε να γράψετε το αποτέλεσμα ως: 270 = 192 ⋅ 1 + 78.

Στη συνέχεια, θα υπολογίσουμε το gcd (192, 78), αφού gcd (270, 192) = gcd (192, 78).

Ας προχωρήσουμε.

a = 192, b = 78.
a ≠ 0.
b ≠ 0.

Διαιρέστε το a με το b, παίρνουμε:

192 / 78 = 2 (το υπόλοιπο είναι 36).

Μπορεί να γραφτεί ως:

192 = 78 ⋅ 2 + 36.

Υπολογίστε gcd(78, 36) αφού gcd(192, 78) = gcd(78, 36).

a = 78, b = 36.
a ≠ 0.
b ≠ 0.

Διαιρέστε το a με το b, παίρνουμε:

78 / 36 = 2 (το υπόλοιπο είναι 0).

Ας γράψουμε το αποτέλεσμα ως:

78 = 36 ⋅ 2 + 6.

Υπολογίστε το gcd(36, 6) αφού gcd(78, 36) = gcd(36, 6).

a = 36, b = 6.
a ≠ 0.
b ≠ 0.

Διαιρέστε το Α με το Β, παίρνουμε 36 / 6 = 6 (το υπόλοιπο είναι 0).

Γράψτε το αποτέλεσμα με την ακόλουθη μορφή:

36 = 6 ⋅ 6 + 0.

Στη συνέχεια βρίσκουμε gcd(6, 0) αφού gcd(36, 6) = gcd(6, 0).

a = 6, b = 0.
a ≠ 0.
b = 0.

Σαν αποτέλεσμα έχουμε:

gcd(6, 0) = 6.

Έτσι, έχουμε την ακόλουθη σειρά υπολογισμών:

gcd(270, 192) = gcd(192, 78) = gcd(78, 36) = gcd(36, 6) = gcd(6, 0) = 6.

Ως αποτέλεσμα, έχουμε την απάντηση:

gcd(270, 192) = 6.

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