Soluzioni
  • L'algoritmo delle divisioni successive è un processo mediante il quale è possibile calcolare il massimo comune divisore tra polinomi e si basa sull'uso ripetuto della divisione euclidea (o per meglio dire divisione polinomiale). Ad ogni passo, la divisione fornisce un polinomio resto, necessario per l'iterata successiva.

    L'algoritmo ha termine quando si ottiene un resto identicamente nullo: in tal caso il massimo comune divisore è l'ultimo resto diverso da zero.

    Non rimaniamo troppo sul vago, cerchiamo di essere più espliciti.

    Siano F(x)\ \mbox{e} \ G(x) due polinomi non nulli tali che il grado del polinomio F(x) sia maggiore o al più uguale a quello di G(x). Effettuiamo la divisione polinomiale di F(x) (dividendo) per G(x) (divisore) così da ricavare due polinomi, Q_0(x)\ \mbox{e} \ R_0(x) (rispettivamente quoziente e resto), che realizzano l'uguaglianza:

    F(x)=Q_0(x)G(x)+R_0(x)

    con il grado del polinomio R_0(x) minore del grado di G(x).

    Si possono verificare due possibilità:

    - se R_0(x) è identicamente nullo, il massimo comune divisore tra F(x)\ \mbox{e} \ G(x) coincide con G(x);

    - se il resto della divisione è diverso da zero, il massimo comune divisore tra F(x)\ \mbox{e}\ G(x) coincide con il massimo comune divisore tra G(x)\ \mbox{e} \ R_0(x), in simboli:

    MCD(F(x),G(x))=MCD(G(x),R_0(x))

    Chiaramente per il calcolo del MCD di G(x)\ \mbox{e} \ R_0(x), dividiamo G(x) per R_0(x) determinando Q_1(x)\ \mbox{e} \ R_1(x) tali che

    G(x)=Q_1(x)R_0(x)+R_1(x)

    con il grado di R_1(x) minore del grado di R_0(x). Come prima:

    - se R_1(x) è identicamente nullo, l'algoritmo si ferma e il massimo comune divisore è R_0(x);

    - se R_1(x) è diverso da zero, il massimo comune divisore tra G(x)\ \mbox{e} \ R_1(x) è uguale a quello tra R_0(x)\ \mbox{e}\ R_1(x), di conseguenza:

    MCD(F(x),G(x))=MCD(G(x),R_0(x))=MCD(R_0(x), R_1(x))

    Al passo generico i\ge 2, dovremo calcolare il massimo comun divisore tra i resti R_{i-2}(x)\ \mbox{e} \ R_{i-1}(x): determiniamo quindi Q_{i}(x)\ \mbox{e} \ R_{i}(x) della divisione tra R_{i-2}(x)\ \mbox{e} \ R_{i-1}(x) tali che:

    R_{i-2}(x)=Q_{i}(x)R_{i-1}(x)+R_{i}(x)

    con il grado di R_{i}(x) minore del grado R_{i-1}(x), oppure R_{i}(x)=0. Possono quindi verificarsi due possibilità:

    - se R_{i}(x) è nullo, in tal caso il massimo comun divisore è R_{i-1}(x) (resto del passo precedente);

    - se R_{i}(x) è diverso da zero, il massimo comune divisore tra R_{i-2}(x) \ \mbox{e} \ R_{i-1}(x) è uguale al massimo comune divisore tra R_{i-1}(x)\ \mbox{e} \ R_{i}(x), pertanto

    \\ MCD(F(x),G(x))=\ ...\ =MCD(R_{i-2}(x), R_{i-1}(x))=\\ \\ =MCD(R_{i-1}(x), R_{i}(x))

    Osservazione importante: proprio perché i gradi dei resti diminuiscono a ogni passo, prima o poi raggiungeremo la condizione di uscita, nel senso che otterremo una divisione con resto nullo.

    Il metodo è molto più semplice da applicare che da spiegare, ecco perché procediamo con l'esempio guida: il nostro obiettivo consiste nel calcolare il massimo comune divisore tra i polinomi

    F(x)=5x^5-2x^2-3\ \ \ ; \ \ \ G(x)=x^3-1 \ \ \ \mbox{in} \ \mathbb{R}[x]

    Eseguiamo la divisione tra F(x)\ \mbox{e} \ G(x) così da ricavare il quoziente Q_{0}(x) e il resto R_{0}(x)

    \begin{array}{ccc|cc}5x^5&-2x^2&-3&x^3&-1\\ \cline{4-5}&&&5x^5&\\ -5x^5&+5x^2&&&\\ \cline{1-3}//&3x^2&-3&&\end{array}

    Deduciamo quindi che

    Q_{0}(x)=5x^5 \ \ \ \mbox{e} \ \ \ R_{0}(x)=3x^2-3

    Poiché il resto non è nullo, siamo costretti a effettuare un'altra iterata dell'algoritmo: impostiamo la tabella per la divisione tra x^3-1\ \mbox{e} \ 3x^2-3 ed estrapoliamo sia il quoziente che il resto

    \begin{array}{ccc|cc}x^3&&-1&3x^2&-3\\ \cline{4-5} &&&\frac{1}{3}x&\\ -x^3&+x&\\ \cline{1-3} // &+x&-1\end{array}

    Scopriamo pertanto che

    Q_{1}(x)=\frac{1}{3}x\ \ \ \mbox{e} \ \ \ R_1(x)=x-1

    Il resto non è nullo, pertanto continuiamo con l'algoritmo: eseguiremo la divisione tra 3x^2-3\ \mbox{e} \ x-1:

    \begin{array}{ccc|cc}3x^2&&-3&x&-1\\ \cline{4-5}&&&3x&+3\\ -3x^2&+3x&&\\ \cline{1-3}//&3x&-3\\&&&& \\ &-3x&+3&&\\ \cline{1-3} &//&//\end{array}

    Finalmente! La divisione ha resto nullo e in accordo con l'algoritmo, possiamo affermare che il massimo comun divisore tra i polinomi F(x)\ \mbox{e} \ G(x) è R_{1}(x)=x-1:

    MCD(F(x),G(x))=MCD(R_0(x),R_1(x))=x-1

    Abbiamo finito.

    Risposta di Ifrit
 
MEDIEGeometriaAlgebra e Aritmetica
SUPERIORIAlgebraGeometriaAnalisiAltro
UNIVERSITÀAnalisiAlgebra LineareAlgebraAltro
EXTRAPilloleWiki
 
Esercizi simili e domande correlate
Domande della categoria Università - Algebra