Santem in Z5 .Sa se calculeze cmmmc si cmmdc al polinoamelor:
f(x)=x^5+x^4+1 si g(x)=x^5+x^3+x^2+3x+2 (cifrele sant cu caciuli).
Daca se poate rezolva fara a utiliza algoritmul Euclid multumesc.

[Citat] Santem in Z5 .Sa se calculeze cmmmc si cmmdc al polinoamelor: f(x)=x^5+x^4+1 si g(x)=x^5+x^3+x^2+3x+2 (cifrele sant cu caciuli). Daca se poate rezolva fara a utiliza algoritmul Euclid multumesc.

Descompui in factori polinoamele cu schema lui Horner(descompunerea este unica deoarece 5 este prim)

[Citat] Santem in Z5 .Sa se calculeze cmmmc si cmmdc al polinoamelor: f(x)=x^5+x^4+1 si g(x)=x^5+x^3+x^2+3x+2 (cifrele sant cu caciuli). Daca se poate rezolva fara a utiliza algoritmul Euclid multumesc.

Pentru asa ceva sunt acum programe (libere) pe piata.

sage: R.<x> = PolynomialRing( IntegerModRing(5) )
sage: R
Univariate Polynomial Ring in x over Ring of integers modulo 5
sage: R.is_unique_factorization_domain()
True
sage:
sage: factor( x^5 + x^4 + 1 )
(x + 2) * (x^2 + x + 1) * (x^2 + 3*x + 3)
sage: factor( x^5 + x^3 + x^2 + 3*x + 2 )
(x + 2) * (x^2 + 2) * (x^2 + 3*x + 3)
sage:
sage: gcd( x^5 + x^4 + 1, x^5 + x^3 + x^2 + 3*x + 2 )
x^3 + 4*x + 1
sage: gcd( x^5 + x^4 + 1, x^5 + x^3 + x^2 + 3*x + 2 ).factor()
(x + 2) * (x^2 + 3*x + 3)


Nu conteaza ca sunt si ca sunt libere in primul rand, conteaza doar ca ele gandesc si se exprima ca un matematician, calculele se fac in cadru conceptual apropiat de matematica (nu (neaparat) de informatica) si ele pot ajuta prin numarul mare de exemple pe care le putem cere si construi la o mai buna intelegere si la un drum efectiv...

Solutia "cealalta" (fara Euclid) se bazeaza atunci pe urmatoarele fapte:

1. (ca si cea cu Euclid)
Inelul de polinoame peste corpul GF(5) = ZZ/5 este inel "factorial", i.e. inel cu descompunere unica in factori primi = ireductibili.

2. Se descompun la maxim cele doua polinoame.
Mai sus avem doua descompuneri destul de bune, o droaie de factori! "Atomii" ramasi au grad cel mult doi.

3. Un polinom de grad doi sau trei (peste un corp) este reductibil daca si numai daca are un factor liniar, deci o radacina in corp.
Ramane de vazut ca factorii de grad doi nu au radacini in ZZ/5.

4. Deci descompunerile de mai sus sunt in factori primi. (Cum le-am obtinut nu trebuie sa divulgam, dar in acest secol putem spune prozaic "cu computerul" fara rusine. Orice altceva ar fi putin rusinos...)

5. Luam factorii comuni la puterile minime ce apar pentru cmmdc....

Buna ziua
Explicatiile sant foarte clare si la obiect(dealtfel ca de obicei).
Am inteles foarte bine si am luat din programul Dvs.descompunerile in factori ireductibili inclusiv observatia ca polinoamele de grad doi in Z5 din problema nu se mai pot descompune.Acum merg pe definitia cmmmc si cmmdc si cred ca cmmmc este egal cu (x+2)(x^2+2)(x+2+x+1)(x^2+3x+3) iar cmmdc este (x+2)(x^2+3x+3)(cred ca este bine).La fel ca la aplicatiile numerice obisnuite.
Multumesc mult

Hmm...tot mai usor e cu Euclid.