Informations, définitions, théorèmes, formules, exercices et problèmes résolus sur les mathématiques du lycée.

»ALGORITHME D'EUCLIDE (polynomes)

Date de la publication: : 09 Juin, 2010

THEORIE

Etant donnés deux polynomes f,g de K[X], où K est un corps commutatif (champs)

(les cas le plus souvent rencontrés étant l'ensemble des nombres complexes et

l'ensemble des classes résiduelles modulo n, où n est un nombre premier).

Pour identifier le polynome (f,g) (p.g.d.c. des polynomes f et g) on parcourt les étapes

suivantes:

1) Si f = g =O (tous les deux sont égaux au polynome nul), alors (f,g) = O.

2) Si f = O et g est polynome non-nul, alors (f,g) = g et si g = O tandis que f est non-

nul, alors (f,g) = f.

3) Si f et g sont tous les deux non-nuls, tels que deg(f) > deg(g):

Conformément au théorème de la division dans l'ensemble des entiers,

$\exists{q_1,r_1}\in{K[X]},\;tels\;que:$ \exists{q_1,r_1}\in{K[X]},\;tels\;que:

$f=gq_1+r_1,\;{deg(r_1)}<{deg(g)}.\; On\;a\;les\;cas:$ f=gq_1+r_1,\;{deg(r_1)}<{deg(g)}.\; On\;a\;les\;cas:

$a)\; r_1=0.\;Alors\;(f,g)=g.$ a)\; r_1=0.\;Alors\;(f,g)=g.

$b)\;{ r_1}\not={0},\;alors\;\exists{q_2,r_2}\in{K[X]},\;tels\;que:$ b)\;{ r_1}\not={0},\;alors\;\exists{q_2,r_2}\in{K[X]},\;tels\;que:

$g={r_1}{q_2}+{r_2},\;{deg(r_2)}<{deg(r_1)}.$ g={r_1}{q_2}+{r_2},\;{deg(r_2)}<{deg(r_1)}.

$1)\;Si\;{r_2}=0,\;alors\;(f,g)={r_1}.$ 1)\;Si\;{r_2}=0,\;alors\;(f,g)={r_1}.

$2)\;Si\;{r_2}\not={0},$ 2)\;Si\;{r_2}\not={0},

alors on continue le procede, en obtenant les relations:

$f=gq_1+r_1,\;{deg(r_1)}<{deg(g)}.$ f=gq_1+r_1,\;{deg(r_1)}<{deg(g)}.

$g=r_1q_2+r_2,\;{deg(r_2)}<{deg(r_1)}.$ g=r_1q_2+r_2,\;{deg(r_2)}<{deg(r_1)}.

$r_1=r_2q_3+r_3,\;{deg(r_3)}<{deg(r_2)}.$ r_1=r_2q_3+r_3,\;{deg(r_3)}<{deg(r_2)}.

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

$r_{n-1}=r_nq_{n+1}+r_{n+1},\;{deg(r_{n+1})}<{deg(r_n)}.$ r_{n-1}=r_nq_{n+1}+r_{n+1},\;{deg(r_{n+1})}<{deg(r_n)}.

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

Il en résulte:

${deg(q)}>{deg(r_1)}>{deg(r_1)}>{deg(r_2)}>\cdots>{deg(r_n)}>\cdots\ge{0}.$ {deg(q)}>{deg(r_1)}>{deg(r_1)}>{deg(r_2)}>\cdots>{deg(r_n)}>\cdots\ge{0}.

On a obtenu une suite décroissante de nombres naturels, ce qui conduit à l'idée que

$\exists{m}\in{\mathbb{N}},\;tel\;que\;{r_m}\not={0}\;et\;{r_{m+1}}=0,\;par\;consequent:$ \exists{m}\in{\mathbb{N}},\;tel\;que\;{r_m}\not={0}\;et\;{r_{m+1}}=0,\;par\;consequent:

$(f,g)=(g,{r_1})=(r_1,r_2)=\cdots=(r_{m-1},r_m)=(r_m,0)=r_m.$ (f,g)=(g,{r_1})=(r_1,r_2)=\cdots=(r_{m-1},r_m)=(r_m,0)=r_m.

4) Le pénultième reste non-nul c'est, donc, un p.g.d.c. des polynomes f et g.

Observations:

a) On convient, d'habitude, de désigner pour p.g.d.c. le polynome unitaire qui

correspond au résultat ainsi trouvé (c'est-à-dire le polynome associé en divisibilité,

obtenu en le multipliant par l'inverse du coefficient dominant).

b) Dans la suite des divisions succéssives de l'algorithme d'Euclide ce sont les

restes obtenus qui comptent, et c'est pour ce raison que, pour avoir des calculs plus

simples, on les multiplie, assez souvent, par des éléments convenablement choisis du

corps K.

c) L'algorithme d'Euclide peut etre utilisé aussi pour trouver le p.g.d.c. de

plusieurs polynomes, par exemple f,g,h.

On calcule tout d'abord (f,g) = d, après (h,d) = e.

Posté dans ALGORITHME D'EUCLIDE (polynomes)

Revenir à la catégorie principale

Ajoutez un commentaire

Réponses et commentaires:

Pour instant, aucun commentaire n'a été ajouté.

LE ROUMAIN

Informations, définitions, théorèmes, formules, exercices et problèmes résolus sur les mathématiques du lycée.

THEORIE

Réponses et commentaires:

Sélectionner ce link pour me contacter par YAHOO MESSENGER!

CATEGORIES :

Archives du blog