Informaţii, definiţii, teoreme, formule, exerciţii şi probleme rezolvate din matematica de liceu.

»ALGORITMUL LUI EUCLID (polinoame)

Data publicarii: 09 Iunie, 2010

TEORIE

Fie doua polinoame f,g de K[X], unde K este un corp comutativ (camp)

(cazurile cel mai des intalnite fiind multimea numerelor complexe si multimea

claselor de resturi modulo n, cu n numar prim).

Pentru identificarea polinomului (f,g) (c.m.m.d.c. al polinoamelor f si g) se parcurg

urmatoarele etape:

1) Dacă f = g =O (ambele sunt egale cu polinomul nul), atunci (f,g) = O.

2) Dacă f = O, iar g este nenul, atunci (f,g) = g, iar daca g = O, iar f este nenul,

atunci (f,g) = f.

3) Fie f şi g doua polinoame nenule, astfel incat grad(f) > grad(g).

Conform teoremei impartirii cu rest,

$\exists{q_1,r_1}\in{K[X]},$ \exists{q_1,r_1}\in{K[X]},

astfel incat:

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

Avem cazurile:

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

$b)\;{ r_1}\not={0},\;atunci\;\exists{q_2,r_2}\in{K[X]},\;astfel\;incat:$ b)\;{ r_1}\not={0},\;atunci\;\exists{q_2,r_2}\in{K[X]},\;astfel\;incat:

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

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

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

atunci se continua procedeul, obtinand relatiile:

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

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

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

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

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

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

Din cele de mai sus rezulta ca:

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

S-a obtinut un sir descrescator de numere naturale, ceea ce conduce la ideea ca

$\exists{m}\in{\mathbb{N}},\;astfel\;incat\;{r_m}\not={0}\;si\;{r_{m+1}}=0,$ \exists{m}\in{\mathbb{N}},\;astfel\;incat\;{r_m}\not={0}\;si\;{r_{m+1}}=0,