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

26.09.2019

Αυτό το άρθρο αφορά εύρεση του μεγαλύτερου κοινού διαιρέτη (GCD)δύο ή περισσότερους αριθμούς. Αρχικά, ας δούμε τον αλγόριθμο Ευκλείδη που σας επιτρέπει να βρείτε το gcd δύο αριθμών. Μετά από αυτό, θα επικεντρωθούμε σε μια μέθοδο που μας επιτρέπει να υπολογίσουμε το gcd των αριθμών ως το γινόμενο των κοινών πρώτων παραγόντων τους. Στη συνέχεια, θα εξετάσουμε την εύρεση του μεγαλύτερου κοινού διαιρέτη τριών ή περισσότερων αριθμών και επίσης θα δώσουμε παραδείγματα υπολογισμού του gcd αρνητικών αριθμών.

Πλοήγηση στη σελίδα.

Ευκλείδειος αλγόριθμος για την εύρεση GCD

Σημειώστε ότι αν είχαμε στραφεί στον πίνακα των πρώτων αριθμών από την αρχή, θα είχαμε ανακαλύψει ότι οι αριθμοί 661 και 113 είναι πρώτοι αριθμοί, από τους οποίους θα μπορούσαμε αμέσως να πούμε ότι ο μεγαλύτερος τους κοινός διαιρέτηςισούται με 1.

Απάντηση:

GCD(661, 113)=1.

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

Ας εξετάσουμε έναν άλλο τρόπο εύρεσης του GCD. Ο μεγαλύτερος κοινός διαιρέτης μπορεί να βρεθεί με παραγοντοποίηση των αριθμών σε πρώτους παράγοντες. Ας διαμορφώσουμε έναν κανόνα: Το gcd δύο θετικών ακεραίων a και b είναι ίσο με το γινόμενο όλων των κοινών πρώτων παραγόντων που βρίσκονται στους πρώτους παραγοντοποιήσεις των αριθμών a και b.

Ας δώσουμε ένα παράδειγμα για να εξηγήσουμε τον κανόνα για την εύρεση GCD. Ας γνωρίζουμε τις αποσυνθέσεις των αριθμών 220 και 600 σε πρώτους παράγοντες, έχουν τη μορφή 220=2·2·5·11 και 600=2·2·2·3·5·5. Οι κοινοί πρώτοι παράγοντες που εμπλέκονται στην παραγοντοποίηση των αριθμών 220 και 600 είναι το 2, το 2 και το 5. Επομένως, GCD(220, 600)=2·2·5=20.

Έτσι, αν συνυπολογίσουμε τους αριθμούς a και b σε πρώτους παράγοντες και βρούμε το γινόμενο όλων των κοινών παραγόντων τους, τότε θα βρεθεί ο μεγαλύτερος κοινός διαιρέτης των αριθμών a και b.

Ας εξετάσουμε ένα παράδειγμα εύρεσης GCD σύμφωνα με τον αναφερόμενο κανόνα.

Παράδειγμα.

Βρείτε τον μεγαλύτερο κοινό διαιρέτη των αριθμών 72 και 96.

Λύση.

Ας συνυπολογίσουμε τους αριθμούς 72 και 96 σε πρώτους παράγοντες:

Δηλαδή 72=2·2·2·3·3 και 96=2·2·2·2·2·3. Κοινοί πρώτοι παράγοντες είναι οι 2, 2, 2 και 3. Έτσι, GCD(72, 96)=2·2·2·3=24.

Απάντηση:

GCD(72, 96)=24 .

Συμπερασματικά της παραγράφου αυτής, σημειώνουμε ότι η εγκυρότητα του παραπάνω κανόνα για την εύρεση GCD προκύπτει από την ιδιότητα του μέγιστου κοινού διαιρέτη, η οποία αναφέρει ότι GCD(m a 1 , m b 1)=m GCD(a 1 , b 1), όπου m είναι οποιοσδήποτε θετικός ακέραιος αριθμός.

Εύρεση του gcd τριών ή περισσότερων αριθμών

Η εύρεση του μεγαλύτερου κοινού διαιρέτη τριών ή περισσότερων αριθμών μπορεί να μειωθεί στη διαδοχική εύρεση του gcd δύο αριθμών. Το αναφέραμε όταν μελετήσαμε τις ιδιότητες του GCD. Εκεί διατυπώσαμε και αποδείξαμε το θεώρημα: ο μεγαλύτερος κοινός διαιρέτης πολλών αριθμών a 1, a 2, ..., a k ίσο με τον αριθμό d k , το οποίο βρίσκεται με διαδοχικό υπολογισμό GCD(a 1 , a 2)=d 2 , GCD(d 2 , a 3)=d 3 , GCD(d 3 , a 4)=d 4 , …, GCD(d k - 1 , a k)=d k .

Ας δούμε πώς μοιάζει η διαδικασία εύρεσης του gcd πολλών αριθμών εξετάζοντας τη λύση του παραδείγματος.

Παράδειγμα.

Βρείτε τον μεγαλύτερο κοινό παράγοντα τεσσάρων αριθμών 78, 294, 570 και 36.

Λύση.

Σε αυτό το παράδειγμα, a 1 =78, a 2 =294, a 3 =570, a 4 =36.

Αρχικά, χρησιμοποιώντας τον ευκλείδειο αλγόριθμο, προσδιορίζουμε τον μεγαλύτερο κοινό διαιρέτη d 2 των δύο πρώτων αριθμών 78 και 294. Κατά τη διαίρεση, λαμβάνουμε τις ισότητες 294 = 78 3 + 60 ; 78=60·1+18 ; 60=18·3+6 και 18=6·3. Έτσι, d2 =GCD(78, 294)=6.

Τώρα ας υπολογίσουμε d 3 =GCD(d 2, a 3)=GCD(6, 570). Ας εφαρμόσουμε ξανά τον ευκλείδειο αλγόριθμο: 570=6·95, επομένως, d 3 = GCD(6, 570)=6.

Μένει να υπολογιστεί d 4 =GCD(d 3, a 4)=GCD(6, 36). Εφόσον το 36 διαιρείται με το 6, τότε d 4 = GCD(6, 36) = 6.

Έτσι, ο μεγαλύτερος κοινός διαιρέτης των τεσσάρων δεδομένων αριθμών είναι d 4 =6, δηλαδή gcd(78, 294, 570, 36)=6.

Απάντηση:

GCD(78, 294, 570, 36)=6.

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

Παράδειγμα.

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

Λύση.

Ας συνυπολογίσουμε τους αριθμούς 78, 294, 570 και 36 σε πρώτους παράγοντες, παίρνουμε 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2 ·3· 3. Οι κοινοί πρώτοι παράγοντες και των τεσσάρων αυτών αριθμών είναι οι αριθμοί 2 και 3. Ως εκ τούτου, GCD(78, 294, 570, 36)=2·3=6.

Το υλικό που παρουσιάζεται παρακάτω είναι μια λογική συνέχεια της θεωρίας από το άρθρο με τίτλο LCM - ελάχιστο κοινό πολλαπλάσιο, ορισμός, παραδείγματα, σύνδεση μεταξύ LCM και GCD. Εδώ θα μιλήσουμε για βρίσκοντας το ελάχιστο κοινό πολλαπλάσιο (LCM), Και Ιδιαίτερη προσοχήΑς επικεντρωθούμε στην επίλυση παραδειγμάτων. Αρχικά, θα δείξουμε πώς υπολογίζεται το LCM δύο αριθμών χρησιμοποιώντας το GCD αυτών των αριθμών. Στη συνέχεια, θα εξετάσουμε την εύρεση του λιγότερου κοινού πολλαπλάσιου με παραγοντοποίηση των αριθμών σε πρώτους παράγοντες. Μετά από αυτό, θα επικεντρωθούμε στην εύρεση του LCM τριών ή περισσότερων αριθμών και επίσης θα δώσουμε προσοχή στον υπολογισμό του LCM των αρνητικών αριθμών.

Πλοήγηση στη σελίδα.

Υπολογισμός του ελάχιστου κοινού πολλαπλού (LCM) μέσω GCD

Ένας τρόπος για να βρείτε το λιγότερο κοινό πολλαπλάσιο βασίζεται στη σχέση μεταξύ LCM και GCD. Υπάρχουσα σύνδεσημεταξύ LCM και GCD σάς επιτρέπει να υπολογίσετε το ελάχιστο κοινό πολλαπλάσιο δύο θετικών ακεραίων χρησιμοποιώντας έναν γνωστό μεγαλύτερο κοινό διαιρέτη. Ο αντίστοιχος τύπος είναι LCM(a, b)=a b:GCD(a, b) . Ας δούμε παραδείγματα εύρεσης του LCM χρησιμοποιώντας τον συγκεκριμένο τύπο.

Παράδειγμα.

Βρείτε το ελάχιστο κοινό πολλαπλάσιο δύο αριθμών 126 και 70.

Λύση.

Σε αυτό το παράδειγμα a=126 , b=70 . Ας χρησιμοποιήσουμε τη σύνδεση μεταξύ LCM και GCD, που εκφράζεται με τον τύπο LCM(a, b)=a b:GCD(a, b). Δηλαδή, πρώτα πρέπει να βρούμε τον μεγαλύτερο κοινό διαιρέτη των αριθμών 70 και 126, μετά τον οποίο μπορούμε να υπολογίσουμε το LCM αυτών των αριθμών χρησιμοποιώντας τον γραπτό τύπο.

Ας βρούμε το GCD(126, 70) χρησιμοποιώντας τον ευκλείδειο αλγόριθμο: 126=70·1+56, 70=56·1+14, 56=14·4, επομένως, GCD(126, 70)=14.

Τώρα βρίσκουμε το απαιτούμενο ελάχιστο κοινό πολλαπλάσιο: GCD(126, 70)=126·70:GCD(126, 70)= 126·70:14=630.

Απάντηση:

LCM(126, 70)=630.

Παράδειγμα.

Με τι ισούται το LCM(68, 34);

Λύση.

Επειδή Το 68 διαιρείται με το 34, τότε το GCD(68, 34)=34. Τώρα υπολογίζουμε το ελάχιστο κοινό πολλαπλάσιο: GCD(68, 34)=68·34:GCD(68, 34)= 68·34:34=68.

Απάντηση:

LCM(68, 34)=68 .

Σημειώστε ότι το προηγούμενο παράδειγμα ταιριάζει με τον ακόλουθο κανόνα για την εύρεση του LCM για θετικούς ακέραιους αριθμούς a και b: εάν ο αριθμός a διαιρείται με το b, τότε το ελάχιστο κοινό πολλαπλάσιο αυτών των αριθμών είναι το a.

Εύρεση LCM με παραγοντοποίηση αριθμών

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

Ο αναφερόμενος κανόνας για την εύρεση του LCM προκύπτει από την ισότητα LCM(a, b)=a b:GCD(a, b). Πράγματι, το γινόμενο των αριθμών α και β είναι ίσο με το γινόμενο όλων των παραγόντων που εμπλέκονται στην επέκταση των αριθμών α και β. Με τη σειρά του, το GCD(a, b) είναι ίσο με το γινόμενο όλων των πρώτων παραγόντων που υπάρχουν ταυτόχρονα στις επεκτάσεις των αριθμών a και b (όπως περιγράφεται στην ενότητα για την εύρεση GCD χρησιμοποιώντας την επέκταση των αριθμών σε πρώτους παράγοντες).

Ας δώσουμε ένα παράδειγμα. Ας ξέρουμε ότι 75=3·5·5 και 210=2·3·5·7. Ας συνθέσουμε το γινόμενο από όλους τους συντελεστές αυτών των επεκτάσεων: 2·3·3·5·5·5·7 . Τώρα από αυτό το γινόμενο εξαιρούμε όλους τους παράγοντες που υπάρχουν τόσο στην επέκταση του αριθμού 75 όσο και στην επέκταση του αριθμού 210 (αυτοί οι παράγοντες είναι 3 και 5), τότε το γινόμενο θα πάρει τη μορφή 2·3·5·5·7 . Η τιμή αυτού του γινόμενου είναι ίση με το ελάχιστο κοινό πολλαπλάσιο του 75 και του 210, δηλαδή NOC(75, 210)= 2·3·5·5·7=1.050.

Παράδειγμα.

Υπολογίστε τους αριθμούς 441 και 700 σε πρώτους παράγοντες και βρείτε το λιγότερο κοινό πολλαπλάσιο αυτών των αριθμών.

Λύση.

Ας συνυπολογίσουμε τους αριθμούς 441 και 700 σε πρώτους παράγοντες:

Παίρνουμε 441=3·3·7·7 και 700=2·2·5·5·7.

Τώρα ας δημιουργήσουμε ένα προϊόν από όλους τους παράγοντες που εμπλέκονται στην επέκταση αυτών των αριθμών: 2·2·3·3·5·5·7·7·7. Ας εξαιρέσουμε από αυτό το προϊόν όλους τους παράγοντες που υπάρχουν ταυτόχρονα και στις δύο επεκτάσεις (υπάρχει μόνο ένας τέτοιος παράγοντας - αυτός είναι ο αριθμός 7): 2·2·3·3·5·5·7·7. Ετσι, LCM(441, 700)=2·2·3·3·5·5·7·7=44 100.

Απάντηση:

NOC(441, 700)= 44 100 .

Ο κανόνας για την εύρεση του LCM χρησιμοποιώντας παραγοντοποίηση αριθμών σε πρώτους παράγοντες μπορεί να διατυπωθεί λίγο διαφορετικά. Εάν οι συντελεστές που λείπουν από την επέκταση του αριθμού b προστεθούν στους συντελεστές από τη διεύρυνση του αριθμού α, τότε η τιμή του γινόμενου που προκύπτει θα είναι ίση με το ελάχιστο κοινό πολλαπλάσιο των αριθμών a και b.

Για παράδειγμα, ας πάρουμε τους ίδιους αριθμούς 75 και 210, οι αποσυνθέσεις τους σε πρώτους παράγοντες είναι οι εξής: 75=3·5·5 και 210=2·3·5·7. Στους παράγοντες 3, 5 και 5 από την επέκταση του αριθμού 75 προσθέτουμε τους συντελεστές 2 και 7 που λείπουν από την επέκταση του αριθμού 210, παίρνουμε το γινόμενο 2·3·5·5·7, η τιμή του οποίου είναι ίσο με LCM(75, 210).

Παράδειγμα.

Βρείτε το ελάχιστο κοινό πολλαπλάσιο του 84 και του 648.

Λύση.

Λαμβάνουμε πρώτα τις αποσυνθέσεις των αριθμών 84 και 648 σε πρώτους παράγοντες. Μοιάζουν με 84=2·2·3·7 και 648=2·2·2·3·3·3·3. Στους παράγοντες 2, 2, 3 και 7 από την επέκταση του αριθμού 84 προσθέτουμε τους συντελεστές 2, 3, 3 και 3 που λείπουν από την επέκταση του αριθμού 648, παίρνουμε το γινόμενο 2 2 2 3 3 3 3 7, που ισούται με 4 536 . Έτσι, το επιθυμητό ελάχιστο κοινό πολλαπλάσιο του 84 και του 648 είναι 4.536.

Απάντηση:

LCM(84, 648)=4,536.

Εύρεση του LCM τριών ή περισσότερων αριθμών

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

Θεώρημα.

Έστω θετικοί ακέραιοι αριθμοί a 1 , a 2 , …, a k, το λιγότερο κοινό πολλαπλάσιο m k αυτών των αριθμών βρίσκεται με διαδοχικό υπολογισμό m 2 = LCM(a 1 , a 2), m 3 = LCM(m 2 , a 3) , … , m k = LCM(m k−1 , a k) .

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

Παράδειγμα.

Βρείτε το LCM τεσσάρων αριθμών 140, 9, 54 και 250.

Λύση.

Σε αυτό το παράδειγμα, a 1 =140, a 2 =9, a 3 =54, a 4 =250.

Πρώτα βρίσκουμε m 2 = LOC(a 1, a 2) = LOC(140, 9). Για να γίνει αυτό, χρησιμοποιώντας τον ευκλείδειο αλγόριθμο, προσδιορίζουμε το GCD(140, 9), έχουμε 140=9·15+5, 9=5·1+4, 5=4·1+1, 4=1·4, επομένως, GCD(140, 9)=1 , από όπου GCD(140, 9)=140 9:GCD(140, 9)= 140·9:1=1.260. Δηλαδή, m 2 = 1 260.

Τώρα βρίσκουμε m 3 = LOC (m 2 , a 3) = LOC (1 260, 54). Ας το υπολογίσουμε μέσω του GCD(1 260, 54), το οποίο προσδιορίζουμε επίσης χρησιμοποιώντας τον ευκλείδειο αλγόριθμο: 1 260=54·23+18, 54=18·3. Τότε gcd(1,260, 54)=18, από το οποίο gcd(1,260, 54)= 1,260·54:gcd(1,260, 54)= 1,260·54:18=3,780. Δηλαδή, m 3 = 3 780.

Το μόνο που μένει είναι να βρεθεί m 4 = LOC(m 3, a 4) = LOC(3 780, 250). Για να γίνει αυτό, βρίσκουμε το GCD(3,780, 250) χρησιμοποιώντας τον ευκλείδειο αλγόριθμο: 3,780=250·15+30, 250=30·8+10, 30=10·3. Επομένως, GCM(3,780, 250)=10, από όπου GCM(3,780, 250)= 3 780 250: GCD(3 780, 250)= 3.780·250:10=94.500. Δηλαδή m 4 =94.500.

Άρα το λιγότερο κοινό πολλαπλάσιο των αρχικών τεσσάρων αριθμών είναι το 94.500.

Απάντηση:

LCM(140, 9, 54, 250)=94.500.

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

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

Παράδειγμα.

Βρείτε το ελάχιστο κοινό πολλαπλάσιο των πέντε αριθμών 84, 6, 48, 7, 143.

Λύση.

Αρχικά, λαμβάνουμε τις αποσυνθέσεις αυτών των αριθμών σε πρώτους παράγοντες: 84=2·2·3·7, 6=2·3, 48=2·2·2·2·3, 7 (το 7 είναι πρώτος αριθμός, συμπίπτει με την αποσύνθεσή του σε πρώτους παράγοντες) και 143=11·13.

Για να βρείτε το LCM αυτών των αριθμών, στους συντελεστές του πρώτου αριθμού 84 (είναι 2, 2, 3 και 7), πρέπει να προσθέσετε τους παράγοντες που λείπουν από την επέκταση του δεύτερου αριθμού 6. Η αποσύνθεση του αριθμού 6 δεν περιέχει παράγοντες που λείπουν, αφού και το 2 και το 3 είναι ήδη παρόντα στην αποσύνθεση του πρώτου αριθμού 84. Στη συνέχεια, στους παράγοντες 2, 2, 3 και 7 προσθέτουμε τους παράγοντες 2 και 2 που λείπουν από την επέκταση του τρίτου αριθμού 48, παίρνουμε ένα σύνολο παραγόντων 2, 2, 2, 2, 3 και 7. Δεν θα χρειαστεί να προσθέσετε πολλαπλασιαστές σε αυτό το σύνολο στο επόμενο βήμα, καθώς το 7 περιέχεται ήδη σε αυτό. Τέλος, στους παράγοντες 2, 2, 2, 2, 3 και 7 προσθέτουμε τους συντελεστές 11 και 13 που λείπουν από την επέκταση του αριθμού 143. Παίρνουμε το γινόμενο 2·2·2·2·3·7·11·13, που ισούται με 48.048.

Η εύρεση του μεγαλύτερου κοινού διαιρέτη τριών ή περισσότερων αριθμών μπορεί να μειωθεί στη διαδοχική εύρεση του gcd δύο αριθμών. Το αναφέραμε όταν μελετήσαμε τις ιδιότητες του GCD. Εκεί διατυπώσαμε και αποδείξαμε το θεώρημα: ο μεγαλύτερος κοινός διαιρέτης πολλών αριθμών a 1, a 2, …, a kίσο με τον αριθμό dk, το οποίο βρίσκεται με διαδοχικό υπολογισμό GCD(a 1 , a 2)=d 2, GCD(d 2 , a 3)=d 3, GCD(d 3 , a 4)=d 4, …,GCD(d k-1, a k)=d k.

Ας δούμε πώς μοιάζει η διαδικασία εύρεσης του gcd πολλών αριθμών εξετάζοντας τη λύση του παραδείγματος.

Παράδειγμα.

Βρείτε τον μεγαλύτερο κοινό διαιρέτη τεσσάρων αριθμών 78 , 294 , 570 Και 36 .

Λύση.

Σε αυτό το παράδειγμα a 1 = 78, a 2 =294, a 3 =570, a 4 =36.

Αρχικά, χρησιμοποιώντας τον ευκλείδειο αλγόριθμο, προσδιορίζουμε τον μεγαλύτερο κοινό διαιρέτη δ 2δύο πρώτοι αριθμοί 78 Και 294 . Κατά τη διαίρεση παίρνουμε τις ισότητες 294=78 3+60; 78=60 1+18;60=18·3+6Και 18=6·3. Ετσι, d 2 =GCD(78, 294)=6.

Τώρα ας υπολογίσουμε d 3 =GCD(d 2, a 3)=GCD(6, 570). Ας χρησιμοποιήσουμε ξανά τον ευκλείδειο αλγόριθμο: 570=6·95, ως εκ τούτου, d 3 =GCD(6, 570)=6.

Μένει να υπολογιστεί d 4 =GCD(d 3, a 4)=GCD(6, 36). Επειδή 36 διαιρείται με 6 , Οτι d 4 =GCD(6, 36)=6.

Έτσι, ο μεγαλύτερος κοινός διαιρέτης των τεσσάρων δεδομένων αριθμών είναι d 4 =6, αυτό είναι, GCD(78, 294, 570, 36)=6.

Απάντηση:

GCD(78, 294, 570, 36)=6.

Παράδειγμα.

Λύση.

Ας αναλύσουμε τους αριθμούς 78 , 294 , 570 Και 36 από πρωταρχικούς παράγοντες, παίρνουμε 78=2·3·13,294=2·3·7·7, 570=2 3 5 19, 36=2·2·3·3. Οι κοινοί πρώτοι παράγοντες και των τεσσάρων αριθμών που δίνονται είναι οι αριθμοί 2 Και 3 . Ως εκ τούτου, GCD(78, 294, 570, 36)=2·3=6.

Απάντηση:

GCD(78, 294, 570, 36)=6.

Αρχή σελίδας

Εύρεση gcd αρνητικών αριθμών

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

Παράδειγμα.

Βρείτε το gcd των αρνητικών ακεραίων −231 Και −140 .

Λύση.

Η απόλυτη τιμή ενός αριθμού −231 ισοδυναμεί 231 , και το μέτρο του αριθμού −140 ισοδυναμεί 140 , Και GCD(−231, −140)=GCD(231, 140). Ο Ευκλείδειος αλγόριθμος μας δίνει τις ακόλουθες ισότητες: 231=140 1+91; 140=91 1+49; 91=49 1+42; 49=42 1+7Και 42=7 6. Ως εκ τούτου, GCD(231, 140)=7. Τότε ο επιθυμητός μεγαλύτερος κοινός διαιρέτης αρνητικών αριθμών είναι −231 Και −140 ισοδυναμεί 7 .

Απάντηση:

GCD(−231, −140)=7.

Παράδειγμα.

Προσδιορίστε το gcd τριών αριθμών −585 , 81 Και −189 .

Λύση.

Όταν βρίσκουμε τον μεγαλύτερο κοινό διαιρέτη, οι αρνητικοί αριθμοί μπορούν να αντικατασταθούν από τις απόλυτες τιμές τους, δηλαδή GCD(−585, 81, −189)=GCD(585, 81, 189). Αριθμητικές επεκτάσεις 585 , 81 Και 189 σε πρώτους παράγοντες έχουν τη μορφή 585=3·3·5·13, 81=3·3·3·3Και 189=3·3·3·7. Οι κοινοί πρώτοι παράγοντες αυτών των τριών αριθμών είναι 3 Και 3 . Επειτα GCD(585, 81, 189)=3·3=9, ως εκ τούτου, GCD(−585, 81, −189)=9.

Απάντηση:

GCD(−585, 81, −189)=9.

35. Ρίζες πολυωνύμου. Το θεώρημα του Bezout. (33 και άνω)

36. Πολλαπλές ρίζες, κριτήριο πολλαπλότητας ριζών.

Ο μεγαλύτερος φυσικός αριθμός με τον οποίο διαιρούνται οι αριθμοί a και b χωρίς υπόλοιπο ονομάζεται μέγιστο κοινό διαιρέτηαυτούς τους αριθμούς. Συμβολίστε GCD(a, b).

Ας εξετάσουμε το ενδεχόμενο εύρεσης GCD χρησιμοποιώντας το παράδειγμα δύο φυσικούς αριθμούς 18 και 60:

1 Ας συνυπολογίσουμε τους αριθμούς σε πρώτους παράγοντες:
18 = 2×3×3
60 = 2 × 2 × 3 × 5

2 Εξαλείψτε από την επέκταση του πρώτου αριθμού όλους τους παράγοντες που δεν περιλαμβάνονται στην επέκταση του δεύτερου αριθμού, παίρνουμε 2×3×3 .

3 Πολλαπλασιάζουμε τους υπόλοιπους πρώτους παράγοντες μετά τη διαγραφή και παίρνουμε τον μεγαλύτερο κοινό διαιρέτη των αριθμών: gcd( 18 , 60 )=2×3= 6 .

4 Σημειώστε ότι δεν έχει σημασία αν διαγράψουμε τους παράγοντες από τον πρώτο ή τον δεύτερο αριθμό, το αποτέλεσμα θα είναι το ίδιο:
18 = 2×3×3
60 = 2 × 2 × 3 × 5

324 , 111 Και 432

Ας συνυπολογίσουμε τους αριθμούς σε πρώτους παράγοντες:

324 = 2 × 2 × 3 × 3 × 3 × 3

111 = 3×37

432 = 2 × 2 × 2 × 2 × 3 × 3 × 3

Διαγράφοντας από τον πρώτο αριθμό τους συντελεστές του οποίου δεν βρίσκονται στον δεύτερο και τον τρίτο αριθμό, παίρνουμε:

2 × 2 × 2 × 2 × 3 × 3 × 3 = 3

Ως αποτέλεσμα, GCD( 324 , 111 , 432 )=3

Εύρεση GCD χρησιμοποιώντας τον ευκλείδειο αλγόριθμο

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

Φόρμουλα υποτροπήςγια GCD, GCD(a, b)=GCD(b, a mod b), όπου a mod b είναι το υπόλοιπο του a διαιρούμενο με το b.

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

Παράδειγμα Βρείτε τον μεγαλύτερο κοινό διαιρέτη αριθμών 7920 Και 594

Ας βρούμε το GCD( 7920 , 594 ) χρησιμοποιώντας τον ευκλείδειο αλγόριθμο, θα υπολογίσουμε το υπόλοιπο της διαίρεσης χρησιμοποιώντας μια αριθμομηχανή.

GCD( 7920 , 594 )

GCD( 594 , 7920 mod 594 ) = GCD( 594 , 198 )

GCD( 198 , 594 mod 198 ) = GCD( 198 , 0 )

GCD( 198 , 0 ) = 198

7920 mod 594 = 7920 - 13 × 594 = 198
594 mod 198 = 594 – 3 × 198 = 0

Ως αποτέλεσμα, παίρνουμε GCD( 7920 , 594 ) = 198

Ελάχιστο κοινό πολλαπλάσιο

Για να βρεις κοινό παρονομαστήκατά την πρόσθεση και αφαίρεση κλασμάτων με διαφορετικούς παρονομαστέςπρέπει να ξέρεις και να μπορείς να υπολογίζεις ελάχιστο κοινό πολλαπλάσιο(ΝΟΚ).

Πολλαπλάσιο του αριθμού "a" είναι ένας αριθμός που διαιρείται από μόνος του με τον αριθμό "a" χωρίς υπόλοιπο.

Αριθμοί που είναι πολλαπλάσιοι του 8 (δηλαδή αυτοί οι αριθμοί διαιρούνται με το 8 χωρίς υπόλοιπο): αυτοί είναι οι αριθμοί 16, 24, 32...

Πολλαπλάσια του 9: 18, 27, 36, 45…

Υπάρχουν άπειρα πολλαπλάσια ενός δεδομένου αριθμού α, σε αντίθεση με τους διαιρέτες του ίδιου αριθμού. Υπάρχει ένας πεπερασμένος αριθμός διαιρετών.

Το κοινό πολλαπλάσιο δύο φυσικών αριθμών είναι ένας αριθμός που διαιρείται και με τους δύο αυτούς αριθμούς..

Ελάχιστο κοινό πολλαπλάσιο(LCM) δύο ή περισσότερων φυσικών αριθμών είναι ο μικρότερος φυσικός αριθμός που διαιρείται ο ίδιος με καθέναν από αυτούς τους αριθμούς.

Πώς να βρείτε το NOC

Το LCM μπορεί να βρεθεί και να γραφτεί με δύο τρόπους.

Ο πρώτος τρόπος για να βρείτε το LOC

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

Καταγράφουμε τα πολλαπλάσια για κάθε αριθμό σε μια γραμμή μέχρι να βρούμε ένα πολλαπλάσιο που είναι ίδιο και για τους δύο αριθμούς.
Το πολλαπλάσιο του αριθμού «α» συμβολίζεται με το κεφαλαίο γράμμα «Κ».

Παράδειγμα. Βρείτε το LCM 6 και 8.

Ο δεύτερος τρόπος για να βρείτε το LOC

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

Ο αριθμός των πανομοιότυπων παραγόντων στις αποσυνθέσεις των αριθμών μπορεί να είναι διαφορετικός.

Στην επέκταση των μικρότερων αριθμών, επισημάνετε τους παράγοντες που δεν περιλαμβάνονται στην επέκταση του μεγαλύτερου αριθμού (στο παράδειγμά μας, αυτός είναι 2) και προσθέστε αυτούς τους παράγοντες στην επέκταση του μεγαλύτερου αριθμού.
LCM(24, 60) = 2 2 3 5 2

Καταγράψτε το προϊόν που προκύπτει ως απάντηση.
Απάντηση: LCM (24, 60) = 120

Μπορείτε επίσης να επισημοποιήσετε την εύρεση του ελάχιστου κοινού πολλαπλάσιου (LCM) ως εξής. Ας βρούμε το LOC (12, 16, 24).

24 = 2 2 2 3

Όπως βλέπουμε από την αποσύνθεση των αριθμών, όλοι οι συντελεστές του 12 περιλαμβάνονται στην αποσύνθεση του 24 (ο μεγαλύτερος από τους αριθμούς), οπότε προσθέτουμε μόνο ένα 2 από την αποσύνθεση του αριθμού 16 στο LCM.

LCM (12, 16, 24) = 2 2 2 3 2 = 48

Απάντηση: LCM (12, 16, 24) = 48

Ειδικές περιπτώσεις εύρεσης ΝΟΕ

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

Για παράδειγμα, LCM (60, 15) = 60
Αφού είναι αμοιβαίο πρώτοι αριθμοίδεν έχουν κοινούς πρώτους παράγοντες, τότε το ελάχιστο κοινό πολλαπλάσιό τους είναι ίσο με το γινόμενο αυτών των αριθμών.

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

Αν ένας φυσικός αριθμός διαιρείται μόνο με το 1 και τον εαυτό του, τότε ονομάζεται πρώτος.

Κάθε φυσικός αριθμός διαιρείται πάντα με το 1 και τον εαυτό του.

Ο αριθμός 2 είναι ο μικρότερος πρώτος αριθμός. Αυτός είναι ο μόνος άρτιος πρώτος αριθμός, οι υπόλοιποι πρώτοι αριθμοί είναι περιττοί.

Υπάρχουν πολλοί πρώτοι αριθμοί και ο πρώτος από αυτούς είναι ο αριθμός 2. Ωστόσο, δεν υπάρχει τελευταίος πρώτος αριθμός. Στην ενότητα "Για μελέτη" μπορείτε να κάνετε λήψη ενός πίνακα με πρώτους αριθμούς έως το 997.

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

ο αριθμός 12 διαιρείται με το 1, με το 2, με το 3, με το 4, με το 6, με το 12.
Ο αριθμός 36 διαιρείται με το 1, με το 2, με το 3, με το 4, με το 6, με το 12, με το 18, με το 36.

Οι αριθμοί με τους οποίους ο αριθμός διαιρείται με ένα σύνολο (για το 12 είναι 1, 2, 3, 4, 6 και 12) ονομάζονται διαιρέτες του αριθμού.

Ο διαιρέτης ενός φυσικού αριθμού α είναι ένας φυσικός αριθμός που διαιρεί δεδομένου αριθμού"α" χωρίς υπόλοιπο.

Ένας φυσικός αριθμός που έχει περισσότερους από δύο διαιρέτες ονομάζεται σύνθετος.

Σημειώστε ότι οι αριθμοί 12 και 36 έχουν κοινούς παράγοντες. Αυτοί οι αριθμοί είναι: 1, 2, 3, 4, 6, 12. Ο μεγαλύτερος διαιρέτης αυτών των αριθμών είναι το 12.

Ο κοινός διαιρέτης δύο δεδομένων αριθμών "a" και "b" είναι ο αριθμός με τον οποίο διαιρούνται και οι δύο αριθμοί "a" και "b" χωρίς υπόλοιπο.

Μέγιστο κοινό διαιρέτη(GCD) δύο δεδομένων αριθμών "a" και "b" είναι μεγαλύτερος αριθμός, με το οποίο διαιρούνται και οι δύο αριθμοί «a» και «b» χωρίς υπόλοιπο.

Συνοπτικά, ο μεγαλύτερος κοινός διαιρέτης των αριθμών «α» και «β» γράφεται ως εξής::

Παράδειγμα: gcd (12; 36) = 12.

Οι διαιρέτες των αριθμών στην εγγραφή λύσεων συμβολίζονται με το κεφαλαίο γράμμα «D».

Οι αριθμοί 7 και 9 έχουν μόνο έναν κοινό διαιρέτη - τον αριθμό 1. Τέτοιοι αριθμοί καλούνται συμπρώτους αριθμούς.

Συμπρώτοι αριθμοί- αυτοί είναι φυσικοί αριθμοί που έχουν μόνο έναν κοινό διαιρέτη - τον αριθμό 1. Το gcd τους είναι 1.

Πώς να βρείτε τον μεγαλύτερο κοινό διαιρέτη

Για να βρείτε το gcd δύο ή περισσότερων φυσικών αριθμών χρειάζεστε:

να αποσυνθέσετε τους διαιρέτες των αριθμών σε πρώτους παράγοντες.

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

64 = 2 2 2 2 2 2
Βρείτε το γινόμενο πανομοιότυπων πρώτων παραγόντων και γράψτε την απάντηση.
GCD (28; 64) = 2 2 = 4

Απάντηση: GCD (28; 64) = 4

Μπορείτε να επισημοποιήσετε τη θέση του GCD με δύο τρόπους: σε μια στήλη (όπως έγινε παραπάνω) ή "σε μια σειρά".

Ο πρώτος τρόπος για να γράψετε GCD

Βρείτε το gcd 48 και 36.

GCD (48; 36) = 2 2 3 = 12

Ο δεύτερος τρόπος για να γράψετε gcd

Τώρα ας γράψουμε τη λύση για την αναζήτηση GCD σε μια γραμμή. Βρείτε το gcd 10 και 15.

Στον ιστότοπο πληροφοριών μας μπορείτε επίσης να χρησιμοποιήσετε τον διαδικτυακό βοηθό Greatest Common Divisor για να ελέγξετε τους υπολογισμούς σας.

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

Το υλικό που παρουσιάζεται παρακάτω είναι μια λογική συνέχεια της θεωρίας από το άρθρο με τίτλο LCM - ελάχιστο κοινό πολλαπλάσιο, ορισμός, παραδείγματα, σύνδεση μεταξύ LCM και GCD. Εδώ θα μιλήσουμε για βρίσκοντας το ελάχιστο κοινό πολλαπλάσιο (LCM), και θα δώσουμε ιδιαίτερη προσοχή στην επίλυση παραδειγμάτων. Αρχικά, θα δείξουμε πώς υπολογίζεται το LCM δύο αριθμών χρησιμοποιώντας το GCD αυτών των αριθμών. Στη συνέχεια, θα εξετάσουμε την εύρεση του ελάχιστου κοινού πολλαπλάσιου με παραγοντοποίηση αριθμών σε πρώτους παράγοντες. Μετά από αυτό, θα επικεντρωθούμε στην εύρεση του LCM τριών ή περισσότερων αριθμών και επίσης θα δώσουμε προσοχή στον υπολογισμό του LCM των αρνητικών αριθμών.

Πλοήγηση στη σελίδα.

Υπολογισμός του ελάχιστου κοινού πολλαπλού (LCM) μέσω GCD

Ένας τρόπος για να βρείτε το λιγότερο κοινό πολλαπλάσιο βασίζεται στη σχέση μεταξύ LCM και GCD. Η υπάρχουσα σύνδεση μεταξύ LCM και GCD μας επιτρέπει να υπολογίσουμε το ελάχιστο κοινό πολλαπλάσιο δύο θετικών ακεραίων μέσω ενός γνωστού μεγαλύτερου κοινού διαιρέτη. Ο αντίστοιχος τύπος είναι LCM(a, b)=a b:GCD(a, b). Ας δούμε παραδείγματα εύρεσης του LCM χρησιμοποιώντας τον συγκεκριμένο τύπο.

Βρείτε το ελάχιστο κοινό πολλαπλάσιο δύο αριθμών 126 και 70.

Σε αυτό το παράδειγμα a=126 , b=70 . Ας χρησιμοποιήσουμε τη σύνδεση μεταξύ LCM και GCD, που εκφράζεται με τον τύπο LCM(a, b)=a·b:GCD(a, b) . Δηλαδή, πρώτα πρέπει να βρούμε τον μεγαλύτερο κοινό διαιρέτη των αριθμών 70 και 126, μετά τον οποίο μπορούμε να υπολογίσουμε το LCM αυτών των αριθμών χρησιμοποιώντας τον γραπτό τύπο.

Ας βρούμε το GCD(126, 70) χρησιμοποιώντας τον ευκλείδειο αλγόριθμο: 126=70·1+56, 70=56·1+14, 56=14·4, επομένως, GCD(126, 70)=14.

Τώρα βρίσκουμε το απαιτούμενο ελάχιστο κοινό πολλαπλάσιο: LCM(126, 70)=126·70:GCD(126, 70)= 126·70:14=630.

Με τι ισούται το LCM(68, 34);

Εφόσον το 68 διαιρείται με το 34, τότε GCD(68, 34)=34. Τώρα υπολογίζουμε το ελάχιστο κοινό πολλαπλάσιο: LCM(68, 34)=68·34:GCD(68, 34)= 68·34:34=68.

Σημειώστε ότι το προηγούμενο παράδειγμα ταιριάζει με τον ακόλουθο κανόνα για την εύρεση του LCM για θετικούς ακέραιους αριθμούς a και b: εάν το a διαιρείται με το b, τότε το λιγότερο κοινό πολλαπλάσιο αυτών των αριθμών είναι το a.

Εύρεση LCM με παραγοντοποίηση αριθμών

Ο αναφερόμενος κανόνας για την εύρεση του LCM προκύπτει από την ισότητα LCM(a, b)=a·b:GCD(a, b) . Πράγματι, το γινόμενο των αριθμών α και β είναι ίσο με το γινόμενο όλων των παραγόντων που εμπλέκονται στην επέκταση των αριθμών α και β. Με τη σειρά του, το GCD(a, b) είναι ίσο με το γινόμενο όλων των πρώτων παραγόντων που υπάρχουν ταυτόχρονα στις επεκτάσεις των αριθμών a και b (όπως περιγράφεται στην ενότητα για την εύρεση GCD χρησιμοποιώντας την επέκταση των αριθμών σε πρώτους παράγοντες).

Ας δώσουμε ένα παράδειγμα. Ας ξέρουμε ότι 75=3·5·5 και 210=2·3·5·7. Ας συνθέσουμε το γινόμενο από όλους τους συντελεστές αυτών των επεκτάσεων: 2·3·3·5·5·5·7 . Τώρα από αυτό το γινόμενο εξαιρούμε όλους τους παράγοντες που υπάρχουν τόσο στην επέκταση του αριθμού 75 όσο και στην επέκταση του αριθμού 210 (αυτοί οι παράγοντες είναι 3 και 5), τότε το γινόμενο θα πάρει τη μορφή 2·3·5·5·7 . Η τιμή αυτού του γινόμενου είναι ίση με το ελάχιστο κοινό πολλαπλάσιο των αριθμών 75 και 210, δηλαδή LCM(75, 210)= 2·3·5·5·7=1050.

Ας συνυπολογίσουμε τους αριθμούς 441 και 700 σε πρώτους παράγοντες:

Παίρνουμε 441=3·3·7·7 και 700=2·2·5·5·7.

Τώρα ας δημιουργήσουμε ένα προϊόν από όλους τους παράγοντες που εμπλέκονται στην επέκταση αυτών των αριθμών: 2·2·3·3·5·5·7·7·7. Ας εξαιρέσουμε από αυτό το προϊόν όλους τους παράγοντες που υπάρχουν ταυτόχρονα και στις δύο επεκτάσεις (υπάρχει μόνο ένας τέτοιος παράγοντας - αυτός είναι ο αριθμός 7): 2·2·3·3·5·5·7·7. Έτσι, LCM(441, 700)=2·2·3·3·5·5·7·7=44 100 .

NOC(441, 700)= 44 100 .

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

Βρείτε το ελάχιστο κοινό πολλαπλάσιο του 84 και του 648.

Εύρεση του LCM τριών ή περισσότερων αριθμών

Βρείτε το LCM τεσσάρων αριθμών 140, 9, 54 και 250.

Πρώτα βρίσκουμε m 2 = LCM(a 1 , a 2) = LCM(140, 9) . Για να γίνει αυτό, χρησιμοποιώντας τον ευκλείδειο αλγόριθμο, προσδιορίζουμε το GCD(140, 9), έχουμε 140=9·15+5, 9=5·1+4, 5=4·1+1, 4=1·4, επομένως, GCD(140, 9)=1, από το οποίο LCM(140, 9)=140·9:GCD(140, 9)= 140·9:1=1,260. Δηλαδή, m 2 = 1 260.

Τώρα βρίσκουμε m 3 = LCM(m 2 , a 3) = LCM(1 260, 54). Ας το υπολογίσουμε μέσω του GCD(1 260, 54), το οποίο προσδιορίζουμε επίσης χρησιμοποιώντας τον ευκλείδειο αλγόριθμο: 1 260=54·23+18, 54=18·3. Τότε gcd(1,260, 54)=18, από το οποίο gcd(1,260, 54)= 1,260·54:gcd(1,260, 54)= 1,260·54:18=3,780. Δηλαδή, m 3 = 3 780.

Απομένει να βρούμε m 4 = LCM(m 3 , a 4) = LCM(3 780, 250). Για να γίνει αυτό, βρίσκουμε το GCD(3,780, 250) χρησιμοποιώντας τον ευκλείδειο αλγόριθμο: 3,780=250·15+30, 250=30·8+10, 30=10·3. Επομένως, GCD(3.780, 250)=10, από τα οποία GCD(3.780, 250)= 3.780·250:GCD(3.780, 250)= 3.780·250:10=94.500. Δηλαδή m 4 =94.500.

Άρα το λιγότερο κοινό πολλαπλάσιο των αρχικών τεσσάρων αριθμών είναι το 94.500.

LCM(140, 9, 54, 250)=94.500 .

Βρείτε το ελάχιστο κοινό πολλαπλάσιο των πέντε αριθμών 84, 6, 48, 7, 143.

Επομένως, LCM(84, 6, 48, 7, 143)=48.048.

LCM(84, 6, 48, 7, 143)=48,048 .

Βρίσκοντας το ελάχιστο κοινό πολλαπλάσιο αρνητικών αριθμών

Μερικές φορές υπάρχουν εργασίες στις οποίες πρέπει να βρείτε το λιγότερο κοινό πολλαπλάσιο αριθμών, μεταξύ των οποίων ένας, πολλοί ή όλοι οι αριθμοί είναι αρνητικοί. Σε αυτές τις περιπτώσεις, όλοι οι αρνητικοί αριθμοί πρέπει να αντικατασταθούν από τους αντίθετους αριθμούς τους και στη συνέχεια να βρεθεί το LCM των θετικών αριθμών. Αυτός είναι ο τρόπος για να βρείτε το LCM αρνητικών αριθμών. Για παράδειγμα, LCM(54, −34) = LCM(54, 34) και LCM(−622, −46, −54, −888) = LCM(622, 46, 54, 888) .

Μπορούμε να το κάνουμε αυτό επειδή το σύνολο των πολλαπλασίων του a είναι ίδιο με το σύνολο των πολλαπλασίων του −a (α και −a είναι αντίθετοι αριθμοί). Πράγματι, έστω b είναι κάποιο πολλαπλάσιο του a, τότε το b διαιρείται με το a, και η έννοια της διαιρετότητας δηλώνει την ύπαρξη ενός ακέραιου αριθμού q τέτοιο ώστε b=a·q. Θα ισχύει όμως και η ισότητα b=(−a)·(−q), η οποία, λόγω της ίδιας έννοιας της διαιρετότητας, σημαίνει ότι το b διαιρείται με το −a, δηλαδή το b είναι πολλαπλάσιο του −a. Το αντίστροφο ισχύει επίσης: αν το b είναι πολλαπλάσιο του −a, τότε το b είναι επίσης πολλαπλάσιο του a.

Να βρείτε το ελάχιστο κοινό πολλαπλάσιο των αρνητικών αριθμών −145 και −45.

Ας αντικαταστήσουμε τους αρνητικούς αριθμούς −145 και −45 με τους αντίθετους αριθμούς τους 145 και 45. Έχουμε LCM(−145, −45) = LCM(145, 45) . Έχοντας καθορίσει GCD(145, 45)=5 (για παράδειγμα, χρησιμοποιώντας τον ευκλείδειο αλγόριθμο), υπολογίζουμε GCM(145, 45)=145·45:GCD(145, 45)= 145·45:5=1 305 . Έτσι, το ελάχιστο κοινό πολλαπλάσιο των αρνητικών ακεραίων −145 και −45 είναι 1.305.

www.cleverstudents.ru

Συνεχίζουμε να μελετάμε τη διαίρεση. ΣΕ αυτό το μάθημαθα εξετάσουμε έννοιες όπως GCDΚαι NOC.

GCDείναι ο μεγαλύτερος κοινός διαιρέτης.

NOCείναι το λιγότερο κοινό πολλαπλάσιο.

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

Μέγιστο κοινό διαιρέτη

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

Για να κατανοήσουμε καλά αυτόν τον ορισμό, ας αντικαταστήσουμε τις μεταβλητές έναΚαι σιοποιοιδήποτε δύο αριθμοί, για παράδειγμα, αντί για μια μεταβλητή έναΑς αντικαταστήσουμε τον αριθμό 12 και αντί για τη μεταβλητή σιαριθμός 9. Τώρα ας προσπαθήσουμε να διαβάσουμε αυτόν τον ορισμό:

Ο μεγαλύτερος κοινός διαιρέτης αριθμών 12 Και 9 είναι ο μεγαλύτερος αριθμός κατά τον οποίο 12 Και 9 διαιρείται χωρίς υπόλοιπο.

Από τον ορισμό είναι σαφές ότι μιλάμε για τον κοινό διαιρέτη των αριθμών 12 και 9, και αυτός ο διαιρέτης είναι ο μεγαλύτερος από όλους τους υπάρχοντες διαιρέτες. Αυτός ο μεγαλύτερος κοινός διαιρέτης (GCD) πρέπει να βρεθεί.

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

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

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

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

12: 1 = 12
(Το 12 διαιρείται με το 1 χωρίς υπόλοιπο, που σημαίνει ότι το 1 είναι διαιρέτης του αριθμού 12)

12: 2 = 6
(Το 12 διαιρείται με το 2 χωρίς υπόλοιπο, που σημαίνει ότι το 2 είναι διαιρέτης του αριθμού 12)

12: 3 = 4
(Το 12 διαιρείται με το 3 χωρίς υπόλοιπο, που σημαίνει ότι το 3 είναι διαιρέτης του αριθμού 12)

12: 4 = 3
(Το 12 διαιρείται με το 4 χωρίς υπόλοιπο, που σημαίνει ότι το 4 είναι διαιρέτης του αριθμού 12)

12: 5 = 2 (2 έχουν απομείνει)
(Το 12 δεν διαιρείται με το 5 χωρίς υπόλοιπο, που σημαίνει ότι το 5 δεν είναι διαιρέτης του αριθμού 12)

12: 6 = 2
(Το 12 διαιρείται με το 6 χωρίς υπόλοιπο, που σημαίνει ότι το 6 είναι διαιρέτης του αριθμού 12)

12: 7 = 1 (5 έχουν απομείνει)
(Το 12 δεν διαιρείται με το 7 χωρίς υπόλοιπο, που σημαίνει ότι το 7 δεν είναι διαιρέτης του αριθμού 12)

12: 8 = 1 (4 που έχουν απομείνει)
(Το 12 δεν διαιρείται με το 8 χωρίς υπόλοιπο, που σημαίνει ότι το 8 δεν είναι διαιρέτης του 12)

12: 9 = 1 (3 που έχουν απομείνει)
(Το 12 δεν διαιρείται με το 9 χωρίς υπόλοιπο, που σημαίνει ότι το 9 δεν είναι διαιρέτης του αριθμού 12)

12: 10 = 1 (2 έχουν απομείνει)
(Το 12 δεν διαιρείται με το 10 χωρίς υπόλοιπο, που σημαίνει ότι το 10 δεν είναι διαιρέτης του αριθμού 12)

12: 11 = 1 (1 που περίσσεψε)
(Το 12 δεν διαιρείται με το 11 χωρίς υπόλοιπο, που σημαίνει ότι το 11 δεν είναι διαιρέτης του 12)

12: 12 = 1
(Το 12 διαιρείται με το 12 χωρίς υπόλοιπο, που σημαίνει ότι το 12 είναι διαιρέτης του αριθμού 12)

Τώρα ας βρούμε τους διαιρέτες του αριθμού 9. Για να το κάνετε αυτό, ελέγξτε όλους τους διαιρέτες από το 1 έως το 9

9: 1 = 9
(Το 9 διαιρείται με το 1 χωρίς υπόλοιπο, που σημαίνει ότι το 1 είναι διαιρέτης του αριθμού 9)

9: 2 = 4 (1 που περίσσεψε)
(Το 9 δεν διαιρείται με το 2 χωρίς υπόλοιπο, που σημαίνει ότι το 2 δεν είναι διαιρέτης του αριθμού 9)

9: 3 = 3
(Το 9 διαιρείται με το 3 χωρίς υπόλοιπο, που σημαίνει ότι το 3 είναι διαιρέτης του αριθμού 9)

9: 4 = 2 (1 που περίσσεψε)
(Το 9 δεν διαιρείται με το 4 χωρίς υπόλοιπο, που σημαίνει ότι το 4 δεν είναι διαιρέτης του αριθμού 9)

9: 5 = 1 (4 που έχουν απομείνει)
(Το 9 δεν διαιρείται με το 5 χωρίς υπόλοιπο, που σημαίνει ότι το 5 δεν είναι διαιρέτης του αριθμού 9)

9: 6 = 1 (3 που έχουν απομείνει)
(Το 9 δεν διαιρείται με το 6 χωρίς υπόλοιπο, που σημαίνει ότι το 6 δεν είναι διαιρέτης του αριθμού 9)

9: 7 = 1 (2 έχουν απομείνει)
(Το 9 δεν διαιρείται με το 7 χωρίς υπόλοιπο, που σημαίνει ότι το 7 δεν είναι διαιρέτης του αριθμού 9)

9: 8 = 1 (1 που περίσσεψε)
(Το 9 δεν διαιρείται με το 8 χωρίς υπόλοιπο, που σημαίνει ότι το 8 δεν είναι διαιρέτης του αριθμού 9)

9: 9 = 1
(Το 9 διαιρείται με το 9 χωρίς υπόλοιπο, που σημαίνει ότι το 9 είναι διαιρέτης του αριθμού 9)

Τώρα ας γράψουμε τους διαιρέτες και των δύο αριθμών. Οι αριθμοί που επισημαίνονται με μπλε είναι διαιρέτες. Ας τα γράψουμε:

Καταγράφοντας τους διαιρέτες, μπορείτε αμέσως να προσδιορίσετε ποιος είναι ο μεγαλύτερος και ο πιο κοινός.

Εξ ορισμού, ο μεγαλύτερος κοινός διαιρέτης των αριθμών 12 και 9 είναι ο αριθμός που διαιρεί το 12 και το 9 χωρίς υπόλοιπο. Ο μεγαλύτερος και κοινός διαιρέτης των αριθμών 12 και 9 είναι ο αριθμός 3

Τόσο ο αριθμός 12 όσο και ο αριθμός 9 διαιρούνται με το 3 χωρίς υπόλοιπο:

Άρα gcd (12 και 9) = 3

Ο δεύτερος τρόπος για να βρείτε το GCD

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

Παράδειγμα 1. Βρείτε το gcd των αριθμών 24 και 18

Αρχικά, ας συνυπολογίσουμε και τους δύο αριθμούς σε πρώτους παράγοντες:

Τώρα ας πολλαπλασιάσουμε τους κοινούς τους παράγοντες. Για να αποφευχθεί η σύγχυση, μπορούν να τονιστούν κοινοί παράγοντες.

Εξετάζουμε την επέκταση του αριθμού 24. Ο πρώτος παράγοντας του είναι το 2. Αναζητούμε τον ίδιο παράγοντα στην επέκταση του αριθμού 18 και βλέπουμε ότι υπάρχει και αυτός. Τονίζουμε και τα δύο:

Εξετάζουμε ξανά την επέκταση του αριθμού 24. Ο δεύτερος παράγοντας του είναι επίσης 2. Αναζητούμε τον ίδιο παράγοντα στην επέκταση του αριθμού 18 και βλέπουμε ότι για δεύτερη φορά δεν υπάρχει πια. Τότε δεν τονίζουμε τίποτα.

Τα επόμενα δύο στην επέκταση του αριθμού 24 επίσης απουσιάζουν από την επέκταση του αριθμού 18.

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

Έτσι, οι κοινοί συντελεστές των αριθμών 24 και 18 είναι οι παράγοντες 2 και 3. Για να λάβετε GCD, αυτοί οι παράγοντες πρέπει να πολλαπλασιαστούν:

Άρα gcd (24 και 18) = 6

Ο τρίτος τρόπος για να βρείτε το GCD

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

Για παράδειγμα, ας βρούμε το GCD για τους αριθμούς 28 και 16 χρησιμοποιώντας αυτήν τη μέθοδο. Πρώτα απ 'όλα, αναλύουμε αυτούς τους αριθμούς σε πρώτους παράγοντες:

Λάβαμε δύο επεκτάσεις: και

Τώρα από την αποσύνθεση του πρώτου αριθμού θα διαγράψουμε τους παράγοντες που δεν περιλαμβάνονται στην αποσύνθεση του δεύτερου αριθμού. Η επέκταση του δεύτερου αριθμού δεν περιλαμβάνει επτά. Ας το διαγράψουμε από την πρώτη επέκταση:

Τώρα πολλαπλασιάζουμε τους υπόλοιπους παράγοντες και παίρνουμε GCD:

Ο αριθμός 4 είναι ο μεγαλύτερος κοινός διαιρέτης των αριθμών 28 και 16. Και οι δύο αυτοί αριθμοί διαιρούνται με το 4 χωρίς υπόλοιπο:

Παράδειγμα 2.Βρείτε το gcd των αριθμών 100 και 40

Factoring του αριθμού 100

Factoring του αριθμού 40

Έχουμε δύο επεκτάσεις:

Τώρα από την αποσύνθεση του πρώτου αριθμού θα διαγράψουμε τους παράγοντες που δεν περιλαμβάνονται στην αποσύνθεση του δεύτερου αριθμού. Η επέκταση του δεύτερου αριθμού δεν περιλαμβάνει ένα πέντε (υπάρχει μόνο ένα πέντε). Ας το διαγράψουμε από την πρώτη επέκταση

Ας πολλαπλασιάσουμε τους υπόλοιπους αριθμούς:

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

GCD (100 και 40) = 20.

Παράδειγμα 3.Βρείτε το gcd των αριθμών 72 και 128

Factoring του αριθμού 72

Factoring του αριθμού 128

2 × 2 × 2 × 2 × 2 × 2 × 2

Τώρα από την αποσύνθεση του πρώτου αριθμού θα διαγράψουμε τους παράγοντες που δεν περιλαμβάνονται στην αποσύνθεση του δεύτερου αριθμού. Η επέκταση του δεύτερου αριθμού δεν περιλαμβάνει δύο τρίδυμα (δεν υπάρχουν καθόλου). Ας τα διαγράψουμε από την πρώτη επέκταση:

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

GCD (72 και 128) = 8

Εύρεση GCD για πολλούς αριθμούς

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

Για παράδειγμα, ας βρούμε το GCD για τους αριθμούς 18, 24 και 36

Ας παραγοντοποιήσουμε τον αριθμό 18

Ας παραγοντοποιήσουμε τον αριθμό 24

Ας παραγοντοποιήσουμε τον αριθμό 36

Έχουμε τρεις επεκτάσεις:

Τώρα ας επισημάνουμε και ας υπογραμμίσουμε τους κοινούς παράγοντες σε αυτούς τους αριθμούς. Οι κοινοί παράγοντες πρέπει να εμφανίζονται και στους τρεις αριθμούς:

Βλέπουμε ότι οι κοινοί παράγοντες για τους αριθμούς 18, 24 και 36 είναι οι παράγοντες 2 και 3. Πολλαπλασιάζοντας αυτούς τους παράγοντες, παίρνουμε το gcd που αναζητούμε:

Λάβαμε την απάντηση 6. Αυτό σημαίνει ότι ο αριθμός 6 είναι ο μεγαλύτερος κοινός διαιρέτης των αριθμών 18, 24 και 36. Αυτοί οι τρεις αριθμοί διαιρούνται με το 6 χωρίς υπόλοιπο:

GCD (18, 24 και 36) = 6

Παράδειγμα 2.Βρείτε το GCD για τους αριθμούς 12, 24, 36 και 42

Ας συνυπολογίσουμε κάθε αριθμό σε πρώτους παράγοντες. Τότε βρίσκουμε το γινόμενο των κοινών παραγόντων αυτών των αριθμών.

Ας παραγοντοποιήσουμε τον αριθμό 12

Ας παραγοντοποιήσουμε τον αριθμό 42

Έχουμε τέσσερις επεκτάσεις:

Τώρα ας επισημάνουμε και ας υπογραμμίσουμε τους κοινούς παράγοντες σε αυτούς τους αριθμούς. Οι κοινοί παράγοντες πρέπει να εμφανίζονται και στους τέσσερις αριθμούς:

Βλέπουμε ότι οι κοινοί παράγοντες για τους αριθμούς 12, 24, 36 και 42 είναι οι συντελεστές του 2 και του 3. Ο πολλαπλασιασμός αυτών των παραγόντων μαζί μας δίνει το gcd που αναζητούμε:

Λάβαμε την απάντηση 6. Αυτό σημαίνει ότι ο αριθμός 6 είναι ο μεγαλύτερος κοινός διαιρέτης των αριθμών 12, 24, 36 και 42. Αυτοί οι αριθμοί διαιρούνται με το 6 χωρίς υπόλοιπο:

GCD (12, 24, 36 και 42) = 6

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

Αποδεικνύεται ότι πολλοί αριθμοί μπορούν να έχουν ένα κοινό πολλαπλάσιο. Και τώρα θα μας ενδιαφέρει το πολλαπλάσιο των δύο αριθμών, και θα πρέπει να είναι όσο το δυνατόν μικρότερο.

Ορισμός. Ελάχιστο κοινό πολλαπλάσιο (LCM) αριθμών έναΚαι σι- έναΚαι σι ένακαι αριθμός σι.

Ο ορισμός περιέχει δύο μεταβλητές έναΚαι σι. Ας αντικαταστήσουμε οποιουσδήποτε δύο αριθμούς αντί για αυτές τις μεταβλητές. Για παράδειγμα, αντί για μεταβλητή έναΑς αντικαταστήσουμε τον αριθμό 9, και αντί για τη μεταβλητή σιΑς αντικαταστήσουμε τον αριθμό 12. Τώρα ας προσπαθήσουμε να διαβάσουμε τον ορισμό:

Ελάχιστο κοινό πολλαπλάσιο (LCM) αριθμών 9 Και 12 - Αυτό μικρότερος αριθμός, που είναι πολλαπλάσιο 9 Και 12 . Με άλλα λόγια, αυτός είναι ένας τόσο μικρός αριθμός που διαιρείται χωρίς υπόλοιπο με τον αριθμό 9 και κατά αριθμό 12 .

Από τον ορισμό είναι σαφές ότι το LCM είναι ο μικρότερος αριθμός που διαιρείται με το 9 και το 12 χωρίς υπόλοιπο.

Για να βρείτε το ελάχιστο κοινό πολλαπλάσιο (LCM), μπορείτε να χρησιμοποιήσετε δύο μεθόδους. Ο πρώτος τρόπος είναι ότι μπορείτε να γράψετε τα πρώτα πολλαπλάσια δύο αριθμών και στη συνέχεια να επιλέξετε ανάμεσα σε αυτά τα πολλαπλάσια έναν αριθμό που θα είναι κοινός και στους δύο αριθμούς και μικρός. Ας εφαρμόσουμε αυτή τη μέθοδο.

Πρώτα απ 'όλα, ας βρούμε τα πρώτα πολλαπλάσια του αριθμού 9. Για να βρείτε τα πολλαπλάσια του 9, πρέπει να πολλαπλασιάσετε αυτό το εννέα ένα προς ένα με αριθμούς από το 1 έως το 9. Οι απαντήσεις που θα προκύψουν θα είναι πολλαπλάσια του αριθμού 9. Άρα, ας ξεκινήσουμε. Θα επισημάνουμε πολλαπλάσια με κόκκινο:

Τώρα βρίσκουμε τα πολλαπλάσια του αριθμού 12. Για να γίνει αυτό, πολλαπλασιάζουμε το 12 ένα προς ένα με όλους τους αριθμούς 1 έως 12.

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

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

Ο αριθμός 12 διαιρείται με το 1, με το 2, με το 3, με το 4, με το 6, με το 12.

Ο αριθμός 36 διαιρείται με το 1, με το 2, με το 3, με το 4, με το 6, με το 12, με το 18, με το 36.

Οι αριθμοί με τους οποίους ο αριθμός διαιρείται με ένα σύνολο (για το 12 είναι 1, 2, 3, 4, 6 και 12) λέγονται διαιρέτες αριθμών. Διαιρέτης φυσικού αριθμού ένα- είναι ένας φυσικός αριθμός που διαιρεί έναν δεδομένο αριθμό έναχωρίς ίχνος. Ένας φυσικός αριθμός που έχει περισσότερους από δύο διαιρέτες ονομάζεται σύνθετος. Σημειώστε ότι οι αριθμοί 12 και 36 έχουν κοινούς παράγοντες. Αυτοί οι αριθμοί είναι: 1, 2, 3, 4, 6, 12. Ο μεγαλύτερος διαιρέτης αυτών των αριθμών είναι το 12.

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

Συνοπτικά ο μεγαλύτερος κοινός διαιρέτης αριθμών έναΚαι σιγράψε το ως εξής:

Παράδειγμα: GCD (12; 36) = 12.

Οι διαιρέτες των αριθμών στην εγγραφή λύσεων συμβολίζονται με το κεφαλαίο γράμμα «D».

Παράδειγμα:

GCD (7; 9) = 1

Οι αριθμοί 7 και 9 έχουν μόνο έναν κοινό διαιρέτη - τον αριθμό 1. Τέτοιοι αριθμοί καλούνται αμοιβαία πρωταρχικήτσι σλάμι.

Μέγιστος κοινός διαιρέτης (GCD), ιδιότητες.

Βασική ιδιότητα: μεγαλύτερος κοινός διαιρέτης ΜΚαι nδιαιρείται με οποιονδήποτε κοινό διαιρέτη αυτών των αριθμών. Παράδειγμα: Για τους αριθμούς 12 και 18, ο μεγαλύτερος κοινός διαιρέτης είναι το 6. διαιρείται με όλους τους κοινούς διαιρέτες αυτών των αριθμών: 1, 2, 3, 6.
Συμπέρασμα 1: σύνολο κοινών διαιρετών ΜΚαι nσυμπίπτει με το σύνολο των διαιρετών GCD( Μ, n).
Συμπέρασμα 2: σύνολο κοινών πολλαπλασίων ΜΚαι nσυμπίπτει με το σύνολο των πολλαπλών LCM ( Μ, n).

Αυτό σημαίνει, συγκεκριμένα, ότι για να αναγάγετε ένα κλάσμα σε μη αναγώγιμη μορφή, πρέπει να διαιρέσετε τον αριθμητή και τον παρονομαστή του με το gcd τους.

Ο μεγαλύτερος κοινός διαιρέτης αριθμών ΜΚαι nμπορεί να οριστεί ως το μικρότερο θετικό στοιχείο του συνόλου όλων των γραμμικών συνδυασμών τους:

και επομένως το αναπαριστάνουμε ως γραμμικό συνδυασμό αριθμών ΜΚαι n:

Αυτή η αναλογία ονομάζεται Η σχέση του Μπεζούτ, και τους συντελεστές uΚαι v — Συντελεστές Bezout. Οι συντελεστές Bezout υπολογίζονται αποτελεσματικά από τον εκτεταμένο ευκλείδειο αλγόριθμο. Αυτή η δήλωση γενικεύεται σε σύνολα φυσικών αριθμών - η σημασία της είναι ότι η υποομάδα της ομάδας που δημιουργείται από το σύνολο είναι κυκλική και δημιουργείται από ένα στοιχείο: GCD ( ένα 1 , ένα 2 , … , a n).

Υπολογίστε τον μεγαλύτερο κοινό διαιρέτη (GCD).

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

όπου υπάρχουν διακριτοί πρώτοι αριθμοί, και και είναι μη αρνητικοί ακέραιοι (μπορεί να είναι μηδενικοί αν ο αντίστοιχος πρώτος δεν είναι στην επέκταση). Στη συνέχεια GCD ( Μ,n) και NOC ( Μ,n) εκφράζονται με τους τύπους:

Εάν υπάρχουν περισσότεροι από δύο αριθμοί: , το gcd τους βρίσκεται χρησιμοποιώντας τον ακόλουθο αλγόριθμο:

- αυτό είναι το επιθυμητό GCD.

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

Ας δούμε τον υπολογισμό του μεγαλύτερου κοινού διαιρέτη βήμα προς βήμα:

1. Διασπάστε τους διαιρέτες των αριθμών σε πρώτους παράγοντες:

Είναι βολικό να γράφετε υπολογισμούς χρησιμοποιώντας μια κάθετη γραμμή. Στα αριστερά της γραμμής γράφουμε πρώτα το μέρισμα, στα δεξιά - τον διαιρέτη. Στη συνέχεια, στην αριστερή στήλη σημειώνουμε τις τιμές των πηλίκων. Ας το εξηγήσουμε αμέσως με ένα παράδειγμα. Ας συνυπολογίσουμε τους αριθμούς 28 και 64 σε πρώτους παράγοντες.

2. Τονίζουμε τους ίδιους πρώτους παράγοντες και στους δύο αριθμούς:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Βρείτε το γινόμενο πανομοιότυπων πρώτων παραγόντων και γράψτε την απάντηση:

gcd (28; 64) = 2. 2 = 4

Απάντηση: GCD (28; 64) = 4

Μπορείτε να επισημοποιήσετε τη θέση του GCD με δύο τρόπους: σε μια στήλη (όπως έγινε παραπάνω) ή "σε μια σειρά".

Ο πρώτος τρόπος για να γράψετε GCD:

Βρείτε το gcd 48 και 36.

GCD (48; 36) = 2. 2. 3 = 12

Ο δεύτερος τρόπος για να γράψετε GCD:

Τώρα ας γράψουμε τη λύση για την αναζήτηση GCD σε μια γραμμή. Βρείτε το gcd 10 και 15.

D (10) = (1, 2, 5, 10)

D (15) = (1, 3, 5, 15)

D (10, 15) = (1, 5)