Divisione di polinomi. Algoritmo di Euclide

INFORMAZIONI DI BASE DELLA TEORIA

Definizione 4.1.

Si chiama il polinomio j(x) in P[x]. divisore comune polinomi g(x) ef(x) da P[x] se f(x) eg(x) sono divisibili per j(x) senza resto.

Esempio 4.1. Dati due polinomi: (X) g(x)= x 4 − 3x 3 − 4x 2 + 2x + 2 О R[x]. I divisori comuni di questi polinomi sono: j1(x)= x 3 − 4x 2 + 2 = О R[x], j2(x)=(x 2 − 2x − 2) О R[x], j3(x)=(x − 1) О R[x], j4(x)= 1 О R[x]. (Controllo!)

Definizione 4.2.

Massimo comun divisorepolinomi diversi da zero f(x) e g(x) da P[x] è un polinomio d(x) da P[x] che è il loro divisore comune ed è esso stesso divisibile per qualsiasi altro divisore comune di questi polinomi.

Esempio 4.2. Per i polinomi dell'esempio 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] il massimo comun divisore è il polinomio d(x) = j1(x) = x 3 − 4x 2 + 2 О R[x], poiché questo è un polinomio d(x) è diviso per tutti gli altri divisori comuni j 2 (x), j 3 (x),j4(x).

Il massimo comun divisore (MCD) è indicato dal simbolo:

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

Esiste un massimo comun divisore per due polinomi qualsiasi f(x),g(x) О P[x] (g(x) N. 0). La sua esistenza determina Algoritmo euclideo che è il seguente.

Dividiamo f(x) SU g(x). Il resto e il quoziente ottenuti dalla divisione sono indicati con r1 (x) E q1(x). Allora se r1 (x)¹ 0, dividi g(x) SU r1(x), otteniamo il resto r2(x) e privato q2(x) eccetera. Gradi dei residui risultanti r1(x), r2(x),... diminuirà. Ma la sequenza degli interi non negativi è limitata dal basso dal numero 0. Di conseguenza il processo di divisione sarà finito e arriveremo al resto rk(x), in cui il resto precedente verrà completamente diviso rk – 1 (x). L’intero processo di divisione può essere scritto come segue:

f(x)= g(x) × q1(x) + r1(x), grado r1 (x)< deg g(x);

g(x)= r1 (x)× q2(x) + r2(x), grado r2(x) < deg r1(x);

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

rk – 2 (x)= rk – 1 (x)× qk(x) + rk(x), grado rk (x)< deg rk – 1 (x);

rk – 1 (x) = rk (x) × qk +1 (x).(*)

Dimostriamolo rk (x) sarà il massimo comun divisore dei polinomi f(x) E g(x).

1) Mostriamolo rk (x)È divisore comune polinomi dei dati.

Passiamo alla penultima uguaglianza:

r k –-2 (x)= r k –-1 (x)× qk(x) + rk(x), O r k –-2 (x)= rk (x) × qk +1 (x) × qk(x) + rk(x).

Il suo lato destro è diviso in rk(x). Pertanto anche il lato sinistro è divisibile per rk(x), quelli. r k –-2 (x) diviso per rk(x).

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

Qui r k –- 1 (x) E r k –- 2 (x) sono divisi in rk(x), ne consegue che la somma a destra dell'uguaglianza è divisibile per rk(x). Ciò significa che anche il lato sinistro dell'uguaglianza è divisibile per rk(x), quelli. r k –- 3 (x) diviso per rk(x). Muovendosi in questo modo successivamente verso l'alto, otteniamo i polinomi f(x) E g(x) sono divisi in rk(x). Così lo abbiamo dimostrato rk (x)È divisore comune dati polinomiali (definizione 4.1.).

2) Mostriamolo rk (x) diviso per qualsiasi altro divisore comune j(x) polinomi f(x) E g(x), questo è massimo comun divisore questi polinomi .

Passiamo alla prima uguaglianza: f(x)=g(x) × q1 (x) + r1(x).

Permettere d(x)– qualche divisore comune f(x) E g(x). Quindi, secondo le proprietà di divisibilità, la differenza f(x)–g(x) × q1 (x) anche diviso in d(x), cioè il lato sinistro dell'uguaglianza f(x)–g(x) × q1 (x)= r1 (x) diviso per d(x). Poi r1 (x) sarà diviso per d(x). Proseguendo il ragionamento in modo analogo, scendendo successivamente attraverso le uguaglianze, otteniamo che rk (x) diviso per d(x). Quindi, secondo definizione 4.2.rk (x) sarà massimo comun divisore polinomi f(x) E g(x): d(x) = (f(x), g(x)) = rk(x).

Massimo comun divisore di polinomi f(x) E g(x)è unico a meno di un fattore: un polinomio di grado zero o, si potrebbe dire, fino all'associazione(definizione 2.2.).

Abbiamo quindi dimostrato il teorema:

Teorema 4.1. /Algoritmo euclideo/.

Se per polinomi f(x),g(x) О P[x] (g(x)¹ 0) il sistema di uguaglianze e diseguaglianze è corretto(*), allora l'ultimo resto diverso da zero sarà il massimo comun divisore di questi polinomi.

Esempio 4.3. Trovare il massimo comun divisore di polinomi

f(x)= x 4 + x 3 +2x 2 + x + 1 e g(x)= x3–2x2 + x–2.

Soluzione.

1 passo.

Scriviamo i passaggi della divisione sotto forma di un sistema di uguaglianze e diseguaglianze, come in (*) :

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

g(x)= r1 (x)× q2(x).

Secondo Teorema 4.1./Algoritmo euclideo/ l'ultimo resto diverso da zero r 1 (x) = 7x 2 + 7 sarà il massimo comun divisore d(x) questi polinomi :

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

Poiché la divisibilità in un anello polinomiale è definita fino all'associazione ( Proprietà 2.11.) , allora come MCD possiamo prendere non 7x 2 + 7, ma ( 7x2+7) = x2+1.

Definizione 4.3.

Verrà chiamato il massimo comun divisore con coefficiente iniziale 1 massimo comun divisore normalizzato.

Esempio 4.4. Nell'esempio 4.2. è stato trovato il massimo comun divisore d(x) = (f(x), g(x)) = 7x 2 + 7 polinomi f(x)= x 4 + x 3 +2x 2 + x + 1 e g(x)= x3–2x2 + x–2. Sostituendolo con il polinomio associato d1(x)= x 2 + 1, otteniamo il massimo comun divisore normalizzato di questi polinomi( f(x), g(x)) = x2 + 1.

Commento. Utilizzando l'algoritmo euclideo per trovare il massimo comun divisore di due polinomi, possiamo trarre la seguente conclusione. Massimo comun divisore di polinomi f(x) E g(x) non dipende dal fatto che lo consideriamo f(x) E g(x) sopra il campo P o sulla sua estensione P'.

Definizione 4.4.

Massimo comun divisorepolinomi f 1 (x), f 2 (x), f 3 (x),… f n (x) Î P[x] è detto polinomio d(x)Î P[x], che è il loro divisore comune ed è esso stesso divisibile per qualsiasi altro divisore comune di questi polinomi.

Poiché l'algoritmo di Euclide è adatto solo per trovare il massimo comun divisore di due polinomi, per trovare il massimo comun divisore di n polinomi dobbiamo dimostrare il seguente teorema.

Definizione. Se ciascuno di due polinomi è divisibile per un terzo polinomio, allora si dice divisore comune dei primi due.

Massimo Comun Divisore (MCD) due polinomi è detto divisore comune di massimo grado.

Il GCD può essere trovato utilizzando la fattorizzazione irriducibile o utilizzando l'algoritmo euclideo.

Esempio 40 Trova il mcd dei polinomi
.

Soluzione. Fattorizziamo entrambi i polinomi:

Dall'espansione è chiaro che il MCD richiesto sarà il polinomio ( X– 1).

Esempio 41 Trova MCD dei polinomi
E
.

Soluzione. Fattorizziamo entrambi i polinomi.

Per un polinomio
XX– 1) secondo lo schema di Horner.

Per un polinomio
le possibili radici razionali sono i numeri 1, 2, 3 e 6. Usando la sostituzione lo verifichiamo X= 1 è la radice. Dividere il polinomio per ( X– 1) secondo lo schema di Horner.

Pertanto, , dove l'espansione del trinomio quadratico
è stato prodotto utilizzando il teorema di Vieta.

Confrontando la fattorizzazione dei polinomi, troviamo che il MCD richiesto sarà il polinomio ( X– 1)(X– 2).

Allo stesso modo, puoi trovare MCD per diversi polinomi.

Tuttavia, il metodo per trovare il MCD mediante fattorizzazione non è sempre disponibile. Un metodo che permette di trovare un MCD per tutti i casi è chiamato algoritmo euclideo.

Lo schema dell'algoritmo di Euclide è il seguente. Uno dei due polinomi viene diviso da un altro il cui grado non è superiore al grado del primo. Inoltre, ogni volta si prende come dividendo il polinomio che è servito da divisore nell'operazione precedente, e come divisore si prende il resto ottenuto nella stessa operazione. Questo processo si interrompe non appena il resto è zero. Dimostriamo questo algoritmo con degli esempi.

Diamo un'occhiata ai polinomi utilizzati nei due esempi precedenti.

Esempio 42 Trova MCD dei polinomi
E
.

Soluzione. Dividiamo
SU
"angolo":

X

Ora dividiamo il divisore
per il resto X– 1:

X+ 1

Poiché l'ultima divisione è avvenuta senza resto, il GCD sarà X– 1, ovvero il polinomio utilizzato come divisore in questa divisione.

Esempio 43 Trova MCD dei polinomi
E
.

Soluzione. Per trovare il MCD utilizzeremo l'algoritmo euclideo. Dividiamo
SU
"angolo":

1

Facciamo una seconda divisione. Per fare ciò dovremmo dividere il divisore precedente
per il resto
, ma da allora
=
, per comodità divideremo il polinomio
Non sopra
e così via
. Tale sostituzione non cambierà la soluzione del problema, poiché il mcd di una coppia di polinomi è determinato a meno di un fattore costante. Abbiamo:

Il resto risulta essere uguale a zero, il che significa l'ultimo divisore, cioè un polinomio

e sarà il GCD desiderato.

1. Funzioni razionali frazionarie

Le definizioni e le dichiarazioni per 2.5 possono essere trovate in .

Una funzione razionale frazionaria a coefficienti reali è detta espressione della forma , Dove
E
- polinomi.

Viene chiamata una funzione frazionaria-razionale (di seguito la chiameremo “frazione”) corretto, se il grado del polinomio al numeratore è strettamente inferiore al grado del polinomio al denominatore. Altrimenti si chiama sbagliato.

L’algoritmo per convertire una frazione impropria in una frazione propria è chiamato “estrazione della frazione intera”.

Esempio 44 Seleziona la parte intera della frazione:
.

Soluzione. Per isolare l'intera parte di una frazione, devi dividere il numeratore della frazione per il suo denominatore. Dividi il numeratore di questa frazione per il suo denominatore usando un "angolo":

Poiché il grado del polinomio risultante è inferiore al grado del divisore, il processo di divisione è completo. Infine:

=
. La frazione risultante
è corretta.

Frazione della forma
è detto più semplice se φ( X ) è un polinomio irriducibile e il grado
inferiore al grado φ( X ).

Commento. Si tenga presente che le potenze del numeratore e polinomio irriducibile al denominatore (senza tener conto del grado α).

Per le frazioni a coefficienti reali, esistono 4 tipi di frazioni semplici:

Qualsiasi frazione propria può essere rappresentato come una somma di frazioni semplici, i cui denominatori sono tutti i possibili divisori
.

Algoritmo per decomporre una frazione nella sua forma più semplice:

Se la frazione è impropria, selezioniamo l'intera parte e scomponiamo la frazione propria risultante in frazioni semplici.

Scomponiamo in fattori il denominatore della frazione propria.

Scriviamo una frazione propria come somma di frazioni semplici con coefficienti indeterminati.

Portiamo la somma delle frazioni sul lato destro a un denominatore comune.

Trovare i coefficienti indeterminati:

O uguagliando i coefficienti per le stesse potenze dei numeratori ridotti sinistro e destro;

Oppure sostituendo valori specifici (di solito le radici del loro comune denominatore). X.

Scriviamo la risposta tenendo conto dell'intera parte della frazione.

Esempio 45 Scomponilo nel modo più semplice
.

Soluzione. Poiché questa funzione frazionaria-razionale non è corretta, selezioniamo l'intera parte:

1

= 1 +
.

Espandiamo la frazione risultante
al più semplice. Per prima cosa fattorizziamo il denominatore. Per fare ciò, troviamo le sue radici utilizzando la formula standard:

Scriviamo lo sviluppo di una funzione razionale frazionaria nelle sue forme più semplici, utilizzando coefficienti indeterminati:

Portiamo il lato destro dell'uguaglianza a un denominatore comune:

Creiamo un sistema uguagliando i coefficienti delle stesse potenze nei numeratori delle frazioni sinistra e destra:

Risposta:
.

Esempio 46 Scomponilo nel modo più semplice
.

Soluzione. Poiché questa frazione è propria (cioè il grado del numeratore è inferiore al grado del denominatore), non è necessario evidenziare l'intera parte. Fattorizziamo il denominatore della frazione:

Scriviamo la scomposizione di questa frazione nelle sue forme più semplici, utilizzando coefficienti indeterminati:

Secondo l'affermazione, i denominatori delle frazioni più semplici devono essere tutti i tipi di divisori del denominatore della frazione:

. (2.2) Sarebbe possibile creare un sistema di equazioni uguagliando i numeratori delle frazioni di sinistra e di destra, ma in questo esempio i calcoli sarebbero troppo macchinosi. La seguente tecnica aiuterà a semplificarli: sostituiamo una per una le radici del denominatore nei numeratori.

A x = 1:

A X= ‑1:

Ora determiniamo i restanti coefficienti UN E CON Basterà uguagliare i coefficienti di massimo grado ed i termini liberi. Possono essere trovati senza aprire le parentesi:

Il lato sinistro della prima equazione contiene 0, poiché il numeratore della frazione sinistra nella (2.2) non contiene il termine con , e nella frazione destra il termine con coefficiente UN + C. Il lato sinistro della seconda equazione contiene 0, poiché il numeratore della frazione sinistra nella (2.2) ha un termine libero uguale a zero, e il numeratore della frazione destra nella (2.2) ha un termine libero pari a (‑ UN + B + C + D). Abbiamo:

Risposta:
.

DIVISIONE DEI POLINOMI. ALGORITMO DI EUCLIDE

§1. Divisione di polinomi

Durante la divisione, i polinomi sono rappresentati in forma canonica e sono disposti in potenze discendenti di una lettera, rispetto alla quale viene determinato il grado del dividendo e del divisore. Il grado del dividendo deve essere maggiore o uguale al grado del divisore.

Il risultato della divisione è una singola coppia di polinomi: il quoziente e il resto, che devono soddisfare l'uguaglianza:

< делимое > = < делитель > ´ < частное > + < остаток > .

Se un polinomio di grado nPn(x ) è divisibile,

Polinomio di grado mRk(x ) è un divisore ( n³m),

Polinomio Qn – m (x ) – quoziente. Il grado di questo polinomio è uguale alla differenza tra i gradi del dividendo e del divisore,

Un polinomio di grado kRk (x ) è il resto di ( K< m ).

Quella uguaglianza

Pn(x) = Fm(x) × Qn – m(x) + Rk(x) (1,1)

devono essere soddisfatte in modo identico, cioè restare valide per qualsiasi valore reale di x.

Notiamo ancora una volta il grado del resto K deve essere inferiore alla potenza del divisore M . Lo scopo del resto è completare il prodotto dei polinomi Fm (x) e Qn – m (x ) ad un polinomio uguale al dividendo.

Se il prodotto di polinomi Fm (x) × Qn – m (x ) dà un polinomio uguale al dividendo, quindi il resto R = 0. In questo caso si dice che la divisione viene eseguita senza resto.

Diamo un'occhiata all'algoritmo per dividere i polinomi usando un esempio specifico.

Supponiamo di voler dividere il polinomio (5x5 + x3 + 1) per il polinomio (x3 + 2).

1. Dividi il termine principale del dividendo 5x5 per il termine principale del divisore x3:

Di seguito verrà mostrato come si trova in questo modo il primo termine del quoziente.

2. Il divisore viene moltiplicato per il successivo (inizialmente il primo) termine del quoziente e questo prodotto viene sottratto dal dividendo:

5x5 + x3 + 1 – 5x2(x3 + 2) = x3 – 10x2 + 1.

3. Il dividendo può essere rappresentato come

5x5 + x3 + 1 = 5x2(x3 + 2) + (x3 – 10x2 +

Se nell'azione (2) il grado della differenza risulta essere maggiore o uguale al grado del divisore (come nell'esempio in esame), allora con questa differenza si ripetono le azioni sopra indicate. In cui

1. Il termine iniziale della differenza x3 è diviso per il termine iniziale del divisore x3:

Di seguito verrà mostrato che il secondo termine del quoziente si trova in questo modo.

2. Il divisore viene moltiplicato per il successivo (ora secondo) termine del quoziente e questo prodotto viene sottratto dall'ultima differenza

X3 – 10x2 + 1 – 1 × (x3 + 2) = – 10x2 – 1.

3. Quindi, l'ultima differenza può essere rappresentata come

X3 – 10x2 + 1 = 1 × (x3 + 2) + (–10x2 +

Se il grado della differenza successiva risulta essere inferiore al grado del divisore (come quando si ripete l'azione (2)), la divisione viene completata con un resto pari all'ultima differenza.

Per confermare che il quoziente è la somma (5x2 + 1), sostituiamo nell'uguaglianza (1.2) il risultato della trasformazione del polinomio x3 – 10x2 + 1 (vedi (1.3)): 5x5 + x3 + 1 = 5x2(x3 + 2 ) + 1× (x3 + 2) + (– 10x2 – 1). Quindi, dopo aver tolto il fattore comune (x3 + 2) tra parentesi, otteniamo finalmente:

5x5 + x3 + 1 = (x3 + 2)(5x2 + 1) + (– 10x2 – 1).

Il quale, in accordo con l’uguaglianza (1.1), va considerato come il risultato della divisione del polinomio (5x5 + x3 + 1) per il polinomio (x3 + 2) con il quoziente (5x2 + 1) e il resto (– 10x2 – 1).

Queste azioni sono solitamente redatte sotto forma di un diagramma chiamato “divisione per angolo”. Allo stesso tempo, nello scrivere il dividendo e le successive differenze, è consigliabile produrre i termini della somma in tutte le potenze decrescenti dell'argomento senza saltare.

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 = dimensione carattere:14.0pt;altezza linea:150%">Quindi, ;

Risposta: , .

Si noti che se si trova il massimo comun divisore di questi polinomi, moltiplicandolo per qualsiasi numero diverso da zero, otterremo anche il massimo divisore di questi polinomi. Questa circostanza consente di semplificare i calcoli nell'algoritmo euclideo. Vale a dire, prima della divisione successiva, il dividendo o il divisore può essere moltiplicato per numeri selezionati in modo speciale in modo che il coefficiente del primo termine del quoziente sia un numero intero. Come mostrato sopra, la moltiplicazione del dividendo e del divisore porterà a una variazione corrispondente nel resto parziale, ma tale che, di conseguenza, il GCD di questi polinomi verrà moltiplicato per un numero uguale a zero, il che è accettabile.

Esempio n.3

Ridurre la frazione .

Soluzione

Applicando l'algoritmo euclideo otteniamo

X4x3±3x2 dimensione carattere: 14,0 pt; altezza linea:150%"> 4 1

2x3 + 6x2 + 3x – 2

dimensione carattere: 14,0 pt; altezza linea: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х dimensione carattere: 14,0 pt; altezza della linea:150%">4

3x2 + 8x + 4

Dimensione carattere 6x3: 14.0pt"> Dimensione carattere 16x2: 14.0pt">8x 2x +

1. Algoritmo euclideo

Se ciascuno di due polinomi è divisibile per un terzo polinomio, allora questo terzo polinomio si dice divisore comune dei primi due.

Il massimo comun divisore (MCD) di due polinomi è il loro comun divisore di massimo grado.

Si noti che qualsiasi numero diverso da zero è un divisore comune di due polinomi qualsiasi. Pertanto qualsiasi numero diverso da zero è chiamato divisore comune banale di questi polinomi.

L'algoritmo euclideo propone una sequenza di azioni che porta a trovare il mcd di due polinomi dati, oppure mostra che tale divisore sotto forma di polinomio di primo grado o superiore non esiste.

L'algoritmo euclideo è implementato come una sequenza di divisioni. Nella prima divisione, il polinomio di grado maggiore viene considerato come dividendo e quello minore come divisore. Se i polinomi per i quali si trova il MCD hanno gli stessi gradi, allora il dividendo e il divisore vengono scelti arbitrariamente.

Se nella divisione successiva il polinomio nel resto ha un grado maggiore o uguale a 1, il divisore diventa dividendo e il resto diventa divisore.

Se la successiva divisione dei polinomi dà come risultato un resto uguale a zero, allora è stato trovato il mcd di questi polinomi. È il divisore dell'ultima divisione.

Se, durante la successiva divisione dei polinomi, il resto risulta essere un numero diverso da zero, allora per questi polinomi non ci sono MCD diversi da quelli banali.

Esempio n.1

Ridurre la frazione.

2. Possibilità di semplificare i calcoli del GCD nell'algoritmo euclideo

Quando si moltiplica il dividendo per un numero diverso da zero, il quoziente e il resto vengono moltiplicati per lo stesso numero.

Prova

Sia P il dividendo, F il divisore, Q il quoziente, R il resto. Poi,

Moltiplicando questa identità per il numero 0, otteniamo

dove il polinomio P può essere considerato come il dividendo e i polinomi Q e R - come il quoziente e il resto ottenuti dividendo il polinomio P per il polinomio F. Pertanto, quando si moltiplica il dividendo per il numero 0, il quoziente e il resto sono anche moltiplicato per, h.t

Conseguenza

Moltiplicare il divisore per il numero 0 può essere considerato come moltiplicare il dividendo per il numero.

Pertanto, quando un divisore viene moltiplicato per un numero, 0 è il quoziente e il resto viene moltiplicato per.

Esempio n.2

Trova il quoziente Q e il resto R quando dividi i polinomi

Algoritmo polinomiale della divisione euclidea

Per passare ai coefficienti interi nel dividendo e nel divisore, moltiplichiamo il dividendo per 6, che porterà alla moltiplicazione del quoziente desiderato Q e del resto R per 6. Successivamente, moltiplichiamo il divisore per 5, che porterà a la moltiplicazione del quoziente 6Q e del resto 6R per. Di conseguenza, il quoziente e il resto ottenuti dividendo i polinomi con coefficienti interi differiranno di un fattore più volte dai valori desiderati del quoziente Q e del resto R ottenuti dividendo questi polinomi.

Quindi, ;

Si noti che se si trova il massimo comun divisore di questi polinomi, moltiplicandolo per qualsiasi numero diverso da zero, otterremo anche il massimo divisore di questi polinomi. Questa circostanza consente di semplificare i calcoli nell'algoritmo euclideo. Vale a dire, prima della divisione successiva, il dividendo o il divisore può essere moltiplicato per numeri selezionati in modo speciale in modo che il coefficiente del primo termine del quoziente sia un numero intero. Come mostrato sopra, la moltiplicazione del dividendo e del divisore porterà a una variazione corrispondente nel resto parziale, ma tale che, di conseguenza, il GCD di questi polinomi verrà moltiplicato per un numero uguale a zero, il che è accettabile.

Algoritmo euclideo per polinomi. L'algoritmo euclideo consente di trovare il massimo comun divisore di due polinomi, ovvero polinomio di grado massimo per il quale entrambi i polinomi dati si dividono senza resto.
L'algoritmo si basa sul fatto che per due polinomi qualsiasi nella stessa variabile, F(X) E G(X), esistono tali polinomi Q(X) E R(X) , chiamati rispettivamente quoziente e resto, che

F(X) = G(X)∙Q(X) + R(X), (*)

in questo caso il grado del resto è minore del grado del divisore, polinomio G(X), e, inoltre, secondo questi polinomi F(X) E G(X) il quoziente e il resto si trovano univocamente. Se l'uguaglianza (*) ha un resto R(X) è uguale al polinomio zero (zero), allora dicono che il polinomio F(X) diviso per G(X) senza resto.
L'algoritmo consiste in una divisione sequenziale con il primo resto del primo polinomio dato, F(X), Sul secondo, G(X):

F(X) = G(X)∙Q 1 (X) + R 1 (X), (1)

allora se R 1 (X) ≠ 0, – il secondo polinomio dato, G(X), al primo resto – ad un polinomio R 1 (X):

G(X) = R 1 (X)∙Q 2 (X) + R 2 (X), (2)

R 1 (X) = R 2 (X)∙Q 3 (X) + R 3 (X), (3)

allora se R 3 (X) ≠ 0, – il secondo resto al terzo:

R 2 (X) = R 3 (X)∙Q 4 (X) + R 4 (X), (4)

eccetera. Poiché in ogni fase il grado del resto successivo diminuisce, il processo non può continuare indefinitamente, quindi ad un certo punto arriveremo sicuramente a una situazione in cui il resto successivo, N+ 1° resto R N+ 1 uguale zero:

Quindi l'ultimo resto diverso da zero R N e sarà il massimo comun divisore della coppia originale di polinomi F(X) E G(X).
Infatti, se dovuto all’uguaglianza ( N+ 2) sostituisci invece 0 R N + 1 (X) nell'uguaglianza ( N+ 1), quindi – l'uguaglianza risultante R N – 1 (X) = R N (X)∙Q N + 1 (X) invece di R N – 1 (X) – nell’uguaglianza ( N), si scopre che R N – 2 (X) = R N (X)∙Q N + 1 (X) Q N (X) + R N (X), cioè. R N – 2 (X) = R N (X)(Q N + 1 (X) Q N (X) + 1), ecc. Nell'uguaglianza (2) dopo la sostituzione otteniamo che G(X) = R N (X)∙Q(X), e, infine, dall'uguaglianza (1) – quello F(X) = R N (X)∙S(X), Dove Q E S– alcuni polinomi. Così, R N (X) è il divisore comune dei due polinomi originali, e il fatto che sia il più grande (cioè il massimo grado possibile) deriva dalla procedura dell'algoritmo.
Se il massimo comun divisore di due polinomi non contiene una variabile (cioè è un numero), i polinomi originali F(X) E G(X) sono chiamati reciprocamente primi.