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

5x5 +10x2 5x2 + 1

X3 + 7x2 + 14x + 8 1

– x2 – 3x – 2

X3 + 3x2 + 2x – x – 4

3x2 + 9x + 6

3x2 + 9x + 6

12у4 ± 18ху3 30x2y2 6y2 – 2xy – 9x2 =

– 4x3 – 12x2y2 – 11x3y + 3x4

± 4ху3 6х2у2 ± 10х3у

– 18x2y2 – x3y + 3x4

± 18х2у2 27х3у ± 45х4

– 28х3у + 48х4 = μέγεθος γραμματοσειράς:14.0pt;line-height:150%">Επομένως, ;

Απάντηση: , .

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

Παράδειγμα Νο. 3

Μειώστε το κλάσμα .

Λύση

Εφαρμόζοντας τον Ευκλείδειο αλγόριθμο, παίρνουμε

X4 x3 ± 3x2 μέγεθος γραμματοσειράς: 14,0 pt; line-height:150%"> 4 1

2x3 + 6x2 + 3x – 2

μέγεθος γραμματοσειράς: 14,0 pt; γραμμή-ύψος:150%">2) 2(x4 + x3 – 3x2 + 4) = 2x4 + 2x3 – 6x2 + 8 2x3 + 6x2 + 3x – 2

2x4 6x3 3x2 ± 2x x – 2

– 4x3 – 9x2 + 2x + 8

± 4х3 ± 12х2 ± 6х μέγεθος γραμματοσειράς: 14,0 pt; line-height:150%">4

3x2 + 8x + 4

6x3 font-size:14.0pt">16x2 font-size:14.0pt">8x 2x +

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

φά(Χ) = σολ(Χ)∙q(Χ) + r(Χ), (*)

σε αυτή την περίπτωση ο βαθμός του υπολοίπου είναι μικρότερος από τον βαθμό του διαιρέτη, πολυωνύμου σολ(Χ), και, επιπλέον, σύμφωνα με αυτά τα πολυώνυμα φά(Χ) Και σολ(Χ) το πηλίκο και το υπόλοιπο βρίσκονται μοναδικά. Αν η ισότητα (*) έχει υπόλοιπο r(Χ) ισούται με το μηδενικό πολυώνυμο (μηδέν), τότε λένε ότι το πολυώνυμο φά(Χ) διαιρείται με σολ(Χ) χωρίς υπόλοιπο.
Ο αλγόριθμος αποτελείται από διαδοχική διαίρεση με το υπόλοιπο πρώτο του πρώτου δεδομένου πολυωνύμου, φά(Χ), Στο δεύτερο, σολ(Χ):

φά(Χ) = σολ(Χ)∙q 1 (Χ) + r 1 (Χ), (1)

τότε αν r 1 (Χ) ≠ 0, – το δεύτερο δεδομένο πολυώνυμο, σολ(Χ), στο πρώτο υπόλοιπο - σε ένα πολυώνυμο r 1 (Χ):

σολ(Χ) = r 1 (Χ)∙q 2 (Χ) + r 2 (Χ), (2)

r 1 (Χ) = r 2 (Χ)∙q 3 (Χ) + r 3 (Χ), (3)

τότε αν r 3 (Χ) ≠ 0, – το δεύτερο υπόλοιπο στο τρίτο:

r 2 (Χ) = r 3 (Χ)∙q 4 (Χ) + r 4 (Χ), (4)

και τα λοιπά. Δεδομένου ότι σε κάθε στάδιο ο βαθμός του επόμενου υπολοίπου μειώνεται, η διαδικασία δεν μπορεί να συνεχιστεί επ 'αόριστον, οπότε σε κάποιο στάδιο θα έρθουμε σίγουρα σε μια κατάσταση όπου το επόμενο, n+ 1ο υπόλοιπο r n+ 1 ισούται με μηδέν:

Τότε το τελευταίο μη μηδενικό υπόλοιπο r n και θα είναι ο μεγαλύτερος κοινός διαιρέτης του αρχικού ζεύγους πολυωνύμων φά(Χ) Και σολ(Χ).
Πράγματι, αν λόγω της ισότητας ( n+ 2) αντικαταστήστε το 0 r n + 1 (Χ) στην ισότητα ( n+ 1), τότε – η προκύπτουσα ισότητα r n – 1 (Χ) = r n (Χ)∙q n + 1 (Χ) αντί r n – 1 (Χ) – στην ισότητα ( n), Τελικά φαίνεται πως r n – 2 (Χ) = r n (Χ)∙q n + 1 (Χ) q n (Χ) + r n (Χ), δηλ. r n – 2 (Χ) = r n (Χ)(q n + 1 (Χ) q n (Χ) + 1) κ.λπ. Στην ισότητα (2) μετά την αντικατάσταση παίρνουμε ότι σολ(Χ) = r n (Χ)∙Q(Χ), και, τέλος, από την ισότητα (1) – αυτό φά(Χ) = r n (Χ)∙μικρό(Χ), Οπου QΚαι μικρό– μερικά πολυώνυμα. Ετσι, r n (Χ) είναι ο κοινός διαιρέτης των δύο αρχικών πολυωνύμων και το γεγονός ότι είναι ο μεγαλύτερος (δηλαδή ο μεγαλύτερος δυνατός βαθμός) προκύπτει από τη διαδικασία του αλγορίθμου.
Εάν ο μεγαλύτερος κοινός διαιρέτης δύο πολυωνύμων δεν περιέχει μεταβλητή (δηλαδή είναι αριθμός), τα αρχικά πολυώνυμα φά(Χ) Και σολ(Χ) λέγονται αμοιβαία πρωταρχική.

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

Μεγαλύτερος κοινός διαιρέτης (GCD) δύο πολυώνυμα λέγονται κοινός διαιρέτης ανώτατου βαθμού τους.

Το GCD μπορεί να βρεθεί χρησιμοποιώντας μη αναγώγιμη παραγοντοποίηση ή χρησιμοποιώντας τον ευκλείδειο αλγόριθμο.

Παράδειγμα 40Να βρείτε το gcd των πολυωνύμων
.

Λύση.Ας συνυπολογίσουμε και τα δύο πολυώνυμα:

Από την επέκταση είναι σαφές ότι το απαιτούμενο GCD θα είναι το πολυώνυμο ( Χ– 1).

Παράδειγμα 41Να βρείτε gcd πολυωνύμων
Και
.

Λύση.Ας συνυπολογίσουμε και τα δύο πολυώνυμα.

Για ένα πολυώνυμο
ΧΧ– 1) σύμφωνα με το σχήμα του Horner.

Για ένα πολυώνυμο
πιθανές ορθολογικές ρίζες είναι οι αριθμοί 1, 2, 3 και 6. Χρησιμοποιώντας την αντικατάσταση το επαληθεύουμε Χ= 1 είναι η ρίζα. Διαιρέστε το πολυώνυμο με ( Χ– 1) σύμφωνα με το σχήμα του Horner.

Επομένως, , όπου η επέκταση του τετραγωνικού τριωνύμου
παρήχθη χρησιμοποιώντας το θεώρημα του Vieta.

Συγκρίνοντας την παραγοντοποίηση των πολυωνύμων, βρίσκουμε ότι το απαιτούμενο GCD θα είναι το πολυώνυμο ( Χ– 1)(Χ– 2).

Ομοίως, μπορείτε να βρείτε GCD για πολλά πολυώνυμα.

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

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

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

Παράδειγμα 42Να βρείτε gcd πολυωνύμων
Και
.

Λύση.Ας χωρίσουμε
επί
"γωνία":

Χ

Τώρα ας διαιρέσουμε τον διαιρέτη
για το υπόλοιπο Χ– 1:

Χ+ 1

Δεδομένου ότι η τελευταία διαίρεση έγινε χωρίς υπόλοιπο, το GCD θα είναι Χ– 1, δηλαδή το πολυώνυμο που χρησιμοποιείται ως διαιρέτης σε αυτή τη διαίρεση.

Παράδειγμα 43Να βρείτε gcd πολυωνύμων
Και
.

Λύση. Για να βρούμε το GCD θα χρησιμοποιήσουμε τον ευκλείδειο αλγόριθμο. Ας χωρίσουμε
επί
"γωνία":

1

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

Το υπόλοιπο αποδείχθηκε ίσο με μηδέν, που σημαίνει τον τελευταίο διαιρέτη, δηλ. ένα πολυώνυμο

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

1. Κλασματικές ορθολογικές συναρτήσεις

Ορισμοί και δηλώσεις για το 2.5 βρίσκονται στο .

Μια κλασματική ορθολογική συνάρτηση με πραγματικούς συντελεστές ονομάζεται έκφραση της μορφής , Οπου
Και
- πολυώνυμα.

Μια κλασματική-ορθολογική συνάρτηση (στο εξής θα την ονομάζουμε «κλάσμα») ονομάζεται σωστός, εάν ο βαθμός του πολυωνύμου στον αριθμητή είναι αυστηρά μικρότερος από τον βαθμό του πολυωνύμου στον παρονομαστή. Αλλιώς λέγεται λανθασμένος.

Ο αλγόριθμος για τη μετατροπή ενός ακατάλληλου κλάσματος σε ένα σωστό κλάσμα ονομάζεται "εξαγωγή ολόκληρου κλάσματος".

Παράδειγμα 44Επιλέξτε ολόκληρο το τμήμα του κλάσματος:
.

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

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

=
. Το κλάσμα που προκύπτει
είναι σωστό.

Κλάσμα της μορφής
λέγεται απλούστερο αν φ( Χ ) είναι ένα μη αναγώγιμο πολυώνυμο, και ο βαθμός
μικρότερο από το βαθμό φ( Χ ).

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

Για κλάσματα με πραγματικούς συντελεστές, υπάρχουν 4 τύποι απλών κλασμάτων:

Οποιοδήποτε σωστό κλάσμα μπορεί να παρασταθεί ως άθροισμα απλών κλασμάτων, οι παρονομαστές των οποίων είναι όλοι οι πιθανοί διαιρέτες
.

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

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

Συνυπολογίζουμε τον παρονομαστή του κατάλληλου κλάσματος σε παράγοντες.

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

Φέρνουμε το άθροισμα των κλασμάτων στη δεξιά πλευρά σε κοινό παρονομαστή.

Βρίσκοντας τους απροσδιόριστους συντελεστές:

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

Ή αντικαθιστώντας συγκεκριμένες (συνήθως τις ρίζες του κοινού τους παρονομαστή) τιμές Χ.

Γράφουμε την απάντηση λαμβάνοντας υπόψη ολόκληρο το μέρος του κλάσματος.

Παράδειγμα 45Αναλύστε το στο πιο απλό του
.

Λύση.Επειδή αυτή η κλασματική-ορθολογική συνάρτηση είναι λανθασμένη, επιλέγουμε ολόκληρο το μέρος:

1

= 1 +
.

Ας επεκτείνουμε το κλάσμα που προκύπτει
στο πιο απλό. Αρχικά, ας παραγοντοποιήσουμε τον παρονομαστή. Για να γίνει αυτό, βρίσκουμε τις ρίζες του χρησιμοποιώντας τον τυπικό τύπο:

Ας γράψουμε την αποσύνθεση μιας κλασματικής ορθολογικής συνάρτησης στις απλούστερες μορφές της, χρησιμοποιώντας απροσδιόριστους συντελεστές:

Ας φέρουμε τη δεξιά πλευρά της ισότητας σε έναν κοινό παρονομαστή:

Δημιουργούμε ένα σύστημα εξισώνοντας τους συντελεστές για τις ίδιες δυνάμεις στους αριθμητές του αριστερού και του δεξιού κλάσματος:

Απάντηση:
.

Παράδειγμα 46Αναλύστε το στο πιο απλό του
.

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

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

Σύμφωνα με τη δήλωση, οι παρονομαστές των απλούστερων κλασμάτων πρέπει να είναι όλων των ειδώνδιαιρέτες του παρονομαστή του κλάσματος:

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

Στο x = 1:

Στο Χ= ‑1:

Τώρα για να καθορίσουμε τους υπόλοιπους συντελεστές ΕΝΑΚαι ΜΕΘα είναι αρκετό να εξισωθούν οι συντελεστές του ανώτατου βαθμού και οι ελεύθεροι όροι. Μπορείτε να τα βρείτε χωρίς να ανοίξετε τις παρενθέσεις:

Η αριστερή πλευρά της πρώτης εξίσωσης περιέχει 0, αφού ο αριθμητής του αριστερού κλάσματος στην (2.2) δεν περιέχει τον όρο με , και στο δεξιό κλάσμα ο όρος με συντελεστής ΕΝΑ + ντο. Στην αριστερή πλευρά της δεύτερης εξίσωσης υπάρχει 0, αφού στον αριθμητή του αριστερού κλάσματος στο (2.2) ο ελεύθερος όρος είναι ίσος με μηδέν και στον αριθμητή του δεξιού κλάσματος στο (2.2) ο ελεύθερος όρος είναι ίσος με (- ΕΝΑ + σι + ντο + ρε). Εχουμε:

Απάντηση:
.

1. Ευκλείδειος αλγόριθμος

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

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

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

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

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

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

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

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

Παράδειγμα Νο. 1

Μειώστε το κλάσμα.

2. Δυνατότητες απλοποίησης των υπολογισμών GCD στον ευκλείδειο αλγόριθμο

Όταν πολλαπλασιάζεται το μέρισμα με έναν αριθμό όχι ίσο με το μηδέν, το πηλίκο και το υπόλοιπο πολλαπλασιάζονται με τον ίδιο αριθμό.

Απόδειξη

Έστω P το μέρισμα, F ο διαιρέτης, Q το πηλίκο, R το υπόλοιπο. Επειτα,

Πολλαπλασιάζοντας αυτή την ταυτότητα με τον αριθμό 0, παίρνουμε

όπου το πολυώνυμο P μπορεί να θεωρηθεί ως το μέρισμα και τα πολυώνυμα Q και R - ως το πηλίκο και το υπόλοιπο που λαμβάνονται με τη διαίρεση του πολυωνύμου P με το πολυώνυμο F. Έτσι, όταν πολλαπλασιάζουμε το μέρισμα με τον αριθμό 0, το πηλίκο και το υπόλοιπο είναι πολλαπλασιάζεται επίσης με, h.t. d

Συνέπεια

Ο πολλαπλασιασμός του διαιρέτη με τον αριθμό 0 μπορεί να θεωρηθεί ως πολλαπλασιασμός του μερίσματος με τον αριθμό.

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

Παράδειγμα Νο. 2

Να βρείτε το πηλίκο Q και το υπόλοιπο R κατά τη διαίρεση πολυωνύμων

πολυωνυμικός αλγόριθμος διαίρεσης Ευκλείδειος

Για να πάμε σε ακέραιους συντελεστές στο μέρισμα και στο διαιρέτη, πολλαπλασιάζουμε το μέρισμα με το 6, το οποίο θα οδηγήσει στον πολλαπλασιασμό του επιθυμητού πηλίκου Q και το υπόλοιπο R με το 6. Μετά από αυτό, πολλαπλασιάζουμε τον διαιρέτη με το 5, το οποίο θα οδηγήσει σε τον πολλαπλασιασμό του πηλίκου 6Q και του υπολοίπου 6R επί. Ως αποτέλεσμα, το πηλίκο και το υπόλοιπο που προκύπτουν από τη διαίρεση πολυωνύμων με ακέραιους συντελεστές θα διαφέρουν κατά ένα συντελεστή πολλές φορές από τις επιθυμητές τιμές του πηλίκου Q και το υπόλοιπο R που προκύπτει από τη διαίρεση αυτών των πολυωνύμων.

Ως εκ τούτου, ;

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

ΒΑΣΙΚΕΣ ΠΛΗΡΟΦΟΡΙΕΣ ΑΠΟ ΤΗ ΘΕΩΡΙΑ

Ορισμός 4.1.

Το πολυώνυμο j(x) στο P[x] ονομάζεται κοινός διαιρέτηςπολυώνυμα g(x) και f(x) από το P[x] αν τα f(x) και g(x) διαιρούνται με το j(x) χωρίς υπόλοιπο.

Παράδειγμα 4.1. Δίνονται δύο πολυώνυμα: (Χ) g(x)= x 4 − 3x 3 − 4x 2 + 2x + 2 О R[x]. Οι κοινοί διαιρέτες αυτών των πολυωνύμων είναι: j 1 (x) = x 3 − 4x 2 + 2 = О R[x], j 2 (x) =(x 2 − 2x − 2) О R[x], j 3 (x) =(x − 1) О R[x], j 4 (x) = 1 О R[x]. (Ελεγχος!)

Ορισμός 4.2.

Μέγιστο κοινό διαιρέτημη μηδενικά πολυώνυμα f(x) και g(x) από το P[x] είναι ένα πολυώνυμο d(x) από το P[x] που είναι ο κοινός διαιρέτης τους και διαιρείται το ίδιο με οποιοδήποτε άλλο κοινό διαιρέτη αυτών των πολυωνύμων.

Παράδειγμα 4.2. Για τα πολυώνυμα από το παράδειγμα 4.1. f(x)= x 4 − 4x 3 + 3x 2 + 2x − 6 О R[x], g(x)= x 4 − 3x 3 − 4x 2 + 2x + 2 О R[x] ο μεγαλύτερος κοινός διαιρέτης είναι το πολυώνυμο d(x) = j 1 (x) = x 3 − 4x 2 + 2 О R[x], αφού πρόκειται για πολυώνυμο Το d(x) διαιρείται με όλους τους άλλους κοινούς διαιρέτες τους j 2 (x), j 3 (x),j4(x).

Ο μεγαλύτερος κοινός διαιρέτης (GCD) υποδεικνύεται με το σύμβολο:

d(x) = (f(x), g(x)).

Ο μεγαλύτερος κοινός διαιρέτης υπάρχει για οποιαδήποτε δύο πολυώνυμα f(x),g(x) О P[x] (g(x)Νο. 0). Η ύπαρξή του καθορίζει Ευκλείδειος αλγόριθμοςπου έχει ως εξής.

Χωρίζουμε f(x)επί g(x). Το υπόλοιπο και το πηλίκο που προκύπτουν με διαίρεση συμβολίζονται με r 1 (x)Και q 1 (x).Τότε αν r 1 (x)¹ 0, διαίρεση g(x)επί r 1 (x),παίρνουμε το υπόλοιπο r2(x)και ιδιωτική q2(x)και τα λοιπά. Βαθμοί υπολειμμάτων που προκύπτουν r 1 (x), r 2 (x),... θα μειωθεί. Αλλά η ακολουθία των μη αρνητικών ακεραίων περιορίζεται από κάτω από τον αριθμό 0. Κατά συνέπεια, η διαδικασία διαίρεσης θα είναι πεπερασμένη και θα φτάσουμε στο υπόλοιπο r k (x),στο οποίο θα χωριστεί πλήρως το προηγούμενο υπόλοιπο r k – 1 (x).Η όλη διαδικασία διαίρεσης μπορεί να γραφτεί ως εξής:

f(x)= g(x) × q 1 (x) + r 1 (x), deg r 1 (x)< deg g(x);

g(x)= r 1 (x)× q 2 (x) + r 2 (x), deg r2(x) < deg r 1(x);

. . . . . . . . . . . . . . . . . . . . . . . .

r k – 2 (x)= r k – 1 (x)× qk(x) + r k (x), deg r k (x)< deg r k – 1 (x);

r k – 1 (x) = r k (x) × q k +1 (x).(*)

Ας το αποδείξουμε r k (x)θα είναι ο μεγαλύτερος κοινός διαιρέτης των πολυωνύμων f(x)Και g(x).

1) Ας το δείξουμε r k (x)είναι κοινός διαιρέτηςπολυώνυμα δεδομένων.

Ας στραφούμε στην προτελευταία ισότητα:

r k –-2 (x)= r k –-1 (x)× qk(x) + r k (x),ή r k –-2 (x)= r k (x) × q k +1 (x) × qk(x) + r k (x).

Η δεξιά πλευρά του χωρίζεται σε r k (x).Επομένως, η αριστερή πλευρά διαιρείται επίσης με r k (x),εκείνοι. r k –-2 (x)διαιρείται με r k (x).

r k –- 3 (x)= r k –- 2 (x)× q k – 1 (x) + r k –- 1 (x).

Εδώ r k –- 1 (x)Και r k –- 2 (x)χωρίζονται σε r k (x),προκύπτει ότι το άθροισμα στη δεξιά πλευρά της ισότητας διαιρείται με r k (x).Αυτό σημαίνει ότι η αριστερή πλευρά της ισότητας διαιρείται επίσης με r k (x),εκείνοι. r k –- 3 (x)διαιρείται με r k (x).Κινούμενοι με αυτόν τον τρόπο διαδοχικά προς τα πάνω, παίρνουμε ότι τα πολυώνυμα f(x)Και g(x)χωρίζονται σε r k (x).Έτσι το δείξαμε r k (x)είναι κοινός διαιρέτηςπολυωνυμικά δεδομένα (ορισμός 4.1.).

2) Ας το δείξουμε r k (x)διαιρείται με τιποτα αλλοκοινός διαιρέτης j(x)πολυώνυμα f(x)Και g(x),αυτό είναι μέγιστο κοινό διαιρέτηαυτά τα πολυώνυμα .

Ας στραφούμε στην πρώτη ισότητα: f(x)=g(x) × q 1 (x) + r 1 (x).

Αφήνω d(x)– κάποιο κοινό διαιρέτη f(x)Και g(x). Στη συνέχεια, σύμφωνα με τις ιδιότητες διαιρετότητας, η διαφορά f(x)–g(x) × q 1 (x)επίσης χωρίζεται σε d(x),δηλαδή η αριστερή πλευρά της ισότητας f(x)–g(x) × q 1 (x)= r 1 (x)διαιρείται με d(x).Επειτα r 1 (x)θα διαιρεθεί με d(x).Συνεχίζοντας το συλλογισμό με παρόμοιο τρόπο, κατεβαίνοντας διαδοχικά μέσα από τις ισότητες, παίρνουμε ότι r k (x)διαιρείται με d(x).Στη συνέχεια, σύμφωνα με ορισμός 4.2.r k (x)θα είναι μέγιστο κοινό διαιρέτηπολυώνυμα f(x)Και g(x): d(x) = (f(x), g(x)) = r k (x).

Ο μεγαλύτερος κοινός διαιρέτης πολυωνύμων f(x)Και g(x)είναι μοναδικό μέχρι έναν παράγοντα - ένα πολυώνυμο βαθμού μηδέν, ή, θα έλεγε κανείς, μέχρι την ένωση(ορισμός 2.2.).

Έτσι, αποδείξαμε το θεώρημα:

Θεώρημα 4.1. /Ευκλείδειος αλγόριθμος/.

Αν για πολυώνυμα f(x),g(x) О P[x] (g(x)¹ 0) το σύστημα των ισοτήτων και των ανισοτήτων είναι σωστό(*), τότε το τελευταίο μη μηδενικό υπόλοιπο θα είναι ο μεγαλύτερος κοινός διαιρέτης αυτών των πολυωνύμων.

Παράδειγμα 4.3. Βρείτε τον μεγαλύτερο κοινό διαιρέτη πολυωνύμων

f(x)= x 4 + x 3 +2x 2 + x + 1 και g(x)= x 3 –2x 2 + x –2.

Λύση.

1 βήμα, 2 βήμα.

Ας γράψουμε τα βήματα της διαίρεσης με τη μορφή ενός συστήματος ισοτήτων και ανισοτήτων, όπως στο (*) :

f(x)= g(x) × q 1 (x) + r 1 (x), deg r 1 (x)< deg g(x);

g(x)= r 1 (x)× q2(x).

Σύμφωνα με Θεώρημα 4.1./Ευκλείδειος αλγόριθμος/ το τελευταίο μη μηδενικό υπόλοιπο r 1 (x) = 7x 2 + 7 θα είναι ο μεγαλύτερος κοινός διαιρέτης d(x)αυτά τα πολυώνυμα :

(f(x), g(x)) = 7x 2 + 7.

Δεδομένου ότι η διαιρετότητα σε έναν πολυωνυμικό δακτύλιο ορίζεται μέχρι τη συσχέτιση ( Ιδιοκτησία 2.11.) , τότε ως GCD μπορούμε να πάρουμε όχι 7x 2 + 7, αλλά ( 7x 2 + 7) = x 2 + 1.

Ορισμός 4.3.

Θα λέγεται ο μεγαλύτερος κοινός διαιρέτης με πρώτο συντελεστή 1 κανονικοποιημένος μέγιστος κοινός διαιρέτης.

Παράδειγμα 4.4. Στο παράδειγμα 4.2. βρέθηκε ο μεγαλύτερος κοινός διαιρέτης d(x) = (f(x), g(x)) = 7x 2 + 7 πολυώνυμα f(x)= x 4 + x 3 +2x 2 + x + 1 και g(x)= x 3 –2x 2 + x –2. Αντικαθιστώντας το με το σχετικό πολυώνυμο του d1(x)= x 2 + 1, λαμβάνουμε τον κανονικοποιημένο μέγιστο κοινό διαιρέτη αυτών των πολυωνύμων( f(x), g(x)) = x 2 + 1.

Σχόλιο.Χρησιμοποιώντας τον ευκλείδειο αλγόριθμο για να βρούμε τον μεγαλύτερο κοινό διαιρέτη δύο πολυωνύμων, μπορούμε να βγάλουμε το ακόλουθο συμπέρασμα. Ο μεγαλύτερος κοινός διαιρέτης πολυωνύμων f(x)Και g(x)δεν εξαρτάται από το αν θεωρούμε f(x)Και g(x)πάνω από το γήπεδο Πή πάνω από την επέκτασή του Π'.

Ορισμός 4.4.

Μέγιστο κοινό διαιρέτηπολυώνυμα f 1 (x), f 2 (x), f 3 (x),… f n (x) Î Το P[x] ονομάζεται τέτοιο πολυώνυμο d(x)Î P[x], που είναι ο κοινός διαιρέτης τους και διαιρείται από μόνος του με οποιονδήποτε άλλο κοινό διαιρέτη αυτών των πολυωνύμων.

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