pgcd

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: MacManus

Bjr !

Je cherche à calculer le PGCD des polynômes X^6-1 et -X^5+X^3+X^2-1 de R[X] . Je note A et B ces polynômes respectivement. Je peux dire que PGCD(A,B) = PGCD(B,R) (R étant un polynôme : le reste de la div.eucl. de A par B). Mais comment reconnaître le polynôme PGCD de A et B ensuite ? c'est bien le dernier reste non nul ?

merci d'avance!


Posted by: leon1789

par divisions euclidiennes successives, on "remplace" un pgcd par un autre où les polynômes sont de degrés plus petits. Mais la suite des degrés ne peut pas diminuer indéfiniment (ils sont dans N) donc on arrive à un truc spécial au bout d'un certain temps...

Ce truc spécial, c'est que le reste de la division euclidienne "n'a pas de degré" : en clair, le reste est nul. Et à ce moment, on peut donner la réponse car pgcd(K, 0) = K

En résumé, pgcd(A,B) = pgcd(B,R_1) = pgcd(R_1,R_2) = ... = pgcd(R_n, 0) = R_n

On dit que le pgcd est le dernier reste non nul dans la suite des divisions euclidiennes. (C'est l'algo d'Euclide ! )


Posted by: ThSQ

Enfin ici on peut sans aucune difficulté factoriser les deux polynômes en produit de d° <= 2.


Posted by: MacManus

D'accord merci c'est pas compliqué mais j'avais un peu oublier ....


Posted by: MacManus

Oui je suis d'accord avec toi ThSQ

-X^5+X^3+X^2-1 = -(X-1)^2(X+1)(X^2+X+1) dans R[X] et
X^6-1 = (X-1)(X+1)(X^4+X^2+1) dans R[X] également.


Posted by: mathelot

\displaystyle X^6-1=(X^2-1)(X^2 - 2 \Re(e^{i \frac{\pi}{3}})X +1)(X^2 - 2 \Re(e^{i \frac{2 \pi}{3}})X + 1)


Posted by: MacManus

ah oui ce que tu donnes là mathelot est finalement la factorisation dans C[X]. d'accord ok! Mais si l'on fait ces deux factorisations pour A et B, on peut en déduire le pgcd de A et B, c'est à dire trouver un polynôme de de plus grand degré qui divise à la fois A et B. mais le fait de factoriser A dans C[X] et B dans R[X] ne "marche" pas.. si ?

il faut rester dans R[X] non ?

merci


Posted by: MacManus

arff je suis allé un peu vite je crois, la décomposition de X^6-1 que tu donnes mathelot, est dans R[X].

Je trouve que PGCD(A,B) = X^4+X^3-X-1
c'est correct ?
merci encore


Posted by: leon1789

Citation:
Posté par ThSQ
Enfin ici on peut sans aucune difficulté factoriser les deux polynômes en produit de d° <= 2.

Certes oui, mais l'algo d'Euclide est, ici, tout aussi efficace (si ce n'est davantage !) :
X^6-1 + X(-X^5+X^3+X^2-1) = X^4+X^3-X-1
(-X^5+X^3+X^2-1) + (X-1)(X^4+X^3-X-1) = 0
donc pgcd = X^4+X^3-X-1

Factoriser et l'algo d'Euclide, les deux sont rapides sur ton exemple... c'est de la chance car très souvent la factorisation est très compliquée (si ce n'est davantage ! ).
Citation:
Posté par MacManus
arff je suis allé un peu vite je crois, la décomposition de X^6-1 que tu donnes mathelot, est dans R[X].

Je trouve que PGCD(A,B) = X^4+X^3-X-1
c'est correct ?
merci encore

oui, mais pourquoi ne pas écrire la forme factorisée si elle te vient comme ça avec méthode de factorisation ?

Citation:
Posté par MacManus
il faut rester dans R[X] non ?

Personnellement, je suis resté dans Z[X] tout simplement !


Posted by: MacManus

merci léon1789, donc sous forme factorisée j'obtiens :
pgcd(A,B) = X^4+X^3-X-1 = (X-1)(X+1)(X^2+X+1) dans Z[X]










-