Divizibilitatea polinoamelor: cel mai mare divizor comun și algoritmul lui Euclid

Două polinoame de gradul al patrulea nu-și spun rădăcinile cu una-două. Întrebarea „au ele vreo rădăcină comună?" primește totuși, la clasa a XII-a, un răspuns obținut în două-trei împărțiri, fără să afli nici măcar una dintre rădăcini. Cel mai mare divizor comun a două polinoame $f$ și $g$ din $K[X]$, nu ambele nule, este polinomul monic care le divide pe amândouă și care, la rândul lui, se divide cu orice alt divizor comun al lor. Procedeul care îl scoate la iveală este algoritmul lui Euclid — exact algoritmul pe care îl folosești din gimnaziu la numere naturale, mutat, cu aceleași cuvinte, pe polinoame.

Această lecție face parte din suplimentul pentru Bacalaureat M1: inelele, corpurile și polinoamele peste un corp sunt în programa pe care o dau sesiunile 2027–2029, deși nu mai apar în programa nouă a clasei a XII-a. Ce urmează se sprijină direct pe împărțirea polinoamelor peste un corp și duce, peste două lecții, la rădăcinile multiple și derivata formală. Noutatea față de ce ai făcut în clasa a X-a nu este divizibilitatea în sine, ci faptul că avem acum un algoritm care produce divizorul comun maxim, oricare ar fi corpul coeficienților — $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$ sau ${\mathbb{Z}}_p$.

Ce vei învăța

• Vei ști să definești cel mai mare divizor comun a două polinoame și să explici de ce se cere ca el să fie monic.
• Vei ști să aplici algoritmul lui Euclid pe polinoame, cu împărțiri succesive, până la restul nul.
• Vei ști să verifici fiecare împărțire înmulțind înapoi și să normalizezi ultimul rest nenul.
• Vei ști să recunoști polinoamele prime între ele și să folosești acest fapt în probleme.
• Vei ști să afli rădăcinile comune a două polinoame fără să rezolvi nicio ecuație.
• Vei ști să lucrezi cu algoritmul lui Euclid și peste ${\mathbb{Z}}_p$, inversând coeficientul dominant al împărțitorului.

Hai să descoperim împreună

1. Ce este cel mai mare divizor comun a două polinoame?

Fie $K$ un corp comutativ — în practică $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$ sau ${\mathbb{Z}}_p$ cu $p$ prim — și fie $f,g\in K[X]$ două polinoame nenule. Spunem, ca în divizibilitatea polinoamelor de la clasa a X-a, că $d$ divide pe $f$, și scriem $d\mid f$, dacă există $q\in K[X]$ cu $f=d\cdot q$. Un polinom $d$ care divide și pe $f$, și pe $g$, se numește divizor comun al lor.

Divizorii comuni sunt mulți: orice constantă nenulă divide orice polinom, pentru că într-un corp constantele nenule sunt inversabile. Ne interesează cel mai „gras" dintre ei, iar exprimarea corectă a acestui „cel mai gras" nu este prin grad, ci prin divizibilitate.

Cel mai mare divizor comun a două polinoame nenule este polinomul monic $d$ care le divide pe amândouă și care se divide, la rândul lui, cu orice alt divizor comun al lor; se notează $\mathrm{cmmdc}(f,g)$ și, tocmai datorită cerinței ca $d$ să fie monic, este unic determinat.

Notația din manuale pentru numere, $(a,b)$, nu se folosește la polinoame: ar semăna prea bine cu o pereche. Scriem întotdeauna $\mathrm{cmmdc}(f,g)$.

Merită oprit o clipă asupra cuvântului „mare". La numere naturale el are sensul obișnuit: dintre divizorii comuni ai lui $84$ și $60$ îl alegem pe cel mai mare, adică pe $12$. La polinoame nu există o relație de ordine care să compare orice două polinoame, așa că sensul lui „mare" trebuie mutat: mare înseamnă divizibil cu toți ceilalți. Din fericire cele două formulări se potrivesc, pentru că un polinom divizibil cu toți ceilalți divizori comuni are și gradul cel mai mare dintre ei. Definiția prin divizibilitate este însă cea corectă, iar la ea ne întoarcem ori de câte ori trebuie justificat un pas.

Rămâne o întrebare pe care definiția nu o rezolvă: de unde știm că un asemenea polinom există? Definiția descrie o proprietate, nu produce obiectul. Răspunsul îl dă chiar algoritmul din secțiunile următoare: el construiește efectiv polinomul cerut, deci existența nu este postulată, ci demonstrată prin construcție — exact ca la numere naturale.

2. De ce trebuie ca cel mai mare divizor comun să fie monic?

Fără această cerință, „cel mai mare divizor comun" nu ar fi un polinom, ci o familie întreagă. Într-adevăr, dacă $d$ este divizor comun al lui $f$ și $g$, atunci și $cd$ este divizor comun, pentru orice constantă $c\ne 0$: din $f=dq$ obținem $f=(cd)\left(\frac{1}{c}q\right)$, iar împărțirea la $c$ este permisă pentru că suntem într-un corp.

Două polinoame care se divid reciproc se numesc asociate; ele diferă exact printr-un factor constant nenul. Cerința ca reprezentantul ales să fie monic, adică să aibă coeficientul dominant egal cu $1$, taie ambiguitatea: din toată familia $\{cd\mid c\in K^{\ast }\}$ rămâne exact un polinom.

O consecință practică pe care o vei folosi la fiecare exercițiu: dacă în timpul calculelor obții $-3X^2+12X+12$, răspunsul final nu este acesta, ci $X^2-4X-4$, obținut prin înmulțire cu $-\frac{1}{3}$. Coeficienții incomozi de pe drum nu strică nimic; ei dispar la normalizarea finală.

3. Lema pe care se sprijină întreg algoritmul

Toată eficiența metodei vine dintr-o singură observație, pe care o demonstrăm pentru că fără ea algoritmul rămâne o rețetă nejustificată.

Lemă. Fie $f,g\in K[X]$, cu $g\ne 0$, și fie $f=gq+r$ împărțirea cu rest a lui $f$ la $g$. Atunci perechile $(f,g)$ și $(g,r)$ au aceiași divizori comuni; în particular $\mathrm{cmmdc}(f,g)=\mathrm{cmmdc}(g,r)$.

Demonstrație. Fie $d$ un divizor comun al lui $f$ și $g$, deci $f=d{f}_1$ și $g=d{g}_1$. Din $r=f-gq$ obținem $r=d{f}_1-d{g}_{1}q=d(f_1-g_{1}q)$, deci $d\mid r$; cum $d\mid g$, rezultă că $d$ e divizor comun al lui $g$ și $r$.

Reciproc, fie $d$ un divizor comun al lui $g$ și $r$, deci $g=d{g}_1$ și $r=d{r}_1$. Din $f=gq+r$ obținem $f=d{g}_{1}q+d{r}_1=d(g_{1}q+r_1)$, deci $d\mid f$; cum $d\mid g$, rezultă că $d$ e divizor comun al lui $f$ și $g$.

Cele două mulțimi de divizori comuni coincid, deci și cel mai mare element al lor, în sensul divizibilității, coincide. $■$

Ce spune lema, pe scurt: poți înlocui deîmpărțitul cu restul, fără să pierzi nimic. Iar restul are gradul strict mai mic decât împărțitorul — de aici scurtarea.

4. Cum se calculează cel mai mare divizor comun cu algoritmul lui Euclid?

Aplicăm lema la nesfârșit. Pornim de la $f$ și $g$ (cu $\mathrm{grad}f\ge \mathrm{grad}g$, altfel le schimbăm între ele) și facem împărțiri succesive:

$$f=g{q}_1+r_1,g=r_1{q}_2+r_2,r_1=r_2{q}_3+r_3,\dots$$

La fiecare pas, împărțitorul de la pasul anterior devine deîmpărțit, iar restul devine împărțitor. Gradele resturilor scad strict:

$$\mathrm{grad}{r}_1>\mathrm{grad}{r}_2>\mathrm{grad}{r}_3>\cdots \ge 0,$$

deci procedeul se oprește obligatoriu după cel mult $\mathrm{grad}g+1$ pași: un șir strict descrescător de numere naturale nu poate fi infinit. Se oprește atunci când un rest este nul.

Rezultatul. Dacă $r_k$ este ultimul rest nenul, atunci $\mathrm{cmmdc}(f,g)$ este $r_k$ făcut monic. Motivul: aplicând lema pas cu pas,

$$\mathrm{cmmdc}(f,g)=\mathrm{cmmdc}(g,r_1)=\mathrm{cmmdc}(r_1,r_2)=\cdots =\mathrm{cmmdc}(r_{k-1},r_k)=\mathrm{cmmdc}(r_k,0),$$

iar divizorii comuni ai lui $r_k$ și $0$ sunt exact divizorii lui $r_k$, pentru că orice polinom divide polinomul nul. Cel mai mare dintre ei, monic, este $r_k$ normalizat.

Două observații practice, care scutesc de greșeli. Prima: nu are importanță de la care polinom pornești. Dacă gradul lui $f$ este mai mic decât al lui $g$, prima împărțire dă câtul nul și restul $f$, iar la pasul următor cele două polinoame apar pur și simplu schimbate între ele; algoritmul se corectează singur, cu prețul unei împărțiri fără conținut. A doua: rezultatul nu depinde de ordinea argumentelor, deci $\mathrm{cmmdc}(f,g)$ și $\mathrm{cmmdc}(g,f)$ sunt același polinom, chiar dacă șirurile de câturi diferă.

Merită și o comparație cinstită între metode. Dacă știi deja descompunerile în factori ale celor două polinoame, cel mai mare divizor comun se citește direct: iei factorii comuni, fiecare la puterea cea mai mică. Dar descompunerea este exact partea grea; pentru un polinom de gradul al cincilea cu coeficienți urâți ea poate fi imposibil de obținut cu mijloacele clasei. Algoritmul lui Euclid, în schimb, nu are nevoie de nicio descompunere și de nicio rădăcină: lucrează numai cu împărțiri, adică numai cu operațiile din corp. Acesta este motivul pentru care el este metoda de referință, iar descompunerea rămâne doar o scurtătură ocazională.

5. Primul exemplu complet, cu verificare

Calculăm $\mathrm{cmmdc}(f,g)$ pentru $f=X^4+X^3-3X^2-4X-4$ și $g=X^3+X^2-4X-4$, ambele din $\mathbb{Q}[X]$.

Pasul 1. Împărțim $f$ la $g$:

$$X^4+X^3-3X^2-4X-4=(X^3+X^2-4X-4)\cdot X+(X^2-4).$$

Verificăm înmulțind înapoi: $(X^3+X^2-4X-4)X=X^4+X^3-4X^2-4X$, iar adunând $X^2-4$ obținem exact $f$. ✓ Deci $q_1=X$ și $r_1=X^2-4$.

Pasul 2. Împărțim $g$ la $r_1$:

$$X^3+X^2-4X-4=(X^2-4)(X+1)+0.$$

Verificare: $(X^2-4)(X+1)=X^3+X^2-4X-4$. ✓ Restul este nul, deci ne oprim.

Ultimul rest nenul este $X^2-4$, care este deja monic, prin urmare

$$\mathrm{cmmdc}(f,g)=X^2-4.$$

Controlul independent. Descompunem: $g=(X+1)(X-2)(X+2)$ și $f=(X^2-4)(X^2+X+1)$. Divizorii comuni sunt așadar generați de $(X-2)(X+2)$, pentru că $X+1$ nu divide $X^2+X+1$ (valoarea în $-1$ este $1\ne 0$). Rezultatul se confirmă.

6. Când trebuie normalizat rezultatul?

De fiecare dată când ultimul rest nenul nu este monic — iar asta se întâmplă des.

Cazul $g\mid f$. Fie $f=X^3-2X^2-X+2$ și $g=2X^2-2$. O singură împărțire:

$$X^3-2X^2-X+2=(2X^2-2)\left(\frac{1}{2}X-1\right)+0.$$

Ultimul rest nenul este chiar $g=2X^2-2$, care nu este monic. Îl înmulțim cu $\frac{1}{2}$ și obținem $\mathrm{cmmdc}(f,g)=X^2-1$. Regula generală, de reținut: dacă $g\mid f$, atunci $\mathrm{cmmdc}(f,g)$ este $g$ făcut monic.

Cazul unui rest constant. Fie $f=X^3+1$ și $g=X^2+1$. Trei împărțiri:

$$X^3+1=(X^2+1)X+(-X+1),X^2+1=(-X+1)(-X-1)+2,-X+1=2\left(-\frac{1}{2}X+\frac{1}{2}\right)+0.$$

Ultimul rest nenul este constanta $2$; făcută monică, ea devine $1$. Deci $\mathrm{cmmdc}(f,g)=1$: cele două polinoame nu au niciun divizor comun de grad cel puțin $1$.

7. Algoritmul lui Euclid peste ${\mathbb{Z}}_p$

Nimic nu se schimbă în algoritm, pentru că ${\mathbb{Z}}_p$ cu $p$ prim este corp: orice clasă nenulă este inversabilă. Calculul cu clase de resturi și căutarea rădăcinilor sunt cele din lecția despre rădăcinile în ${\mathbb{Z}}_p$ și funcția polinomială. Singura deosebire practică este că, la fiecare împărțire, coeficientul dominant al împărțitorului se inversează modulo $p$, în loc să fie „împărțit".

Lucrăm în ${\mathbb{Z}}_5[X]$ cu $f=X^4+X^3+X^2$ și $g=\hat{2}{X}^3+\hat{3}$. Avem nevoie de ${\hat{2}}^{-1}=\hat{3}$, pentru că $\hat{2}\cdot \hat{3}=\hat{6}=\hat{1}$.

Pasul 1. $X^4:\hat{2}{X}^3$ dă $\hat{3}X$; apoi $\hat{3}X\cdot (\hat{2}{X}^3+\hat{3})=X^4+\hat{4}X$. Continuând,

$$X^4+X^3+X^2=(\hat{2}{X}^3+\hat{3})(\hat{3}X+\hat{3})+(X^2+X+\hat{1}).$$

Verificare: $(\hat{2}{X}^3+\hat{3})(\hat{3}X+\hat{3})=\hat{6}{X}^4+\hat{6}{X}^3+\hat{9}X+\hat{9}=X^4+X^3+\hat{4}X+\hat{4}$, iar adunând $X^2+X+\hat{1}$ obținem $X^4+X^3+X^2+\hat{5}X+\hat{5}=X^4+X^3+X^2$. ✓

Pasul 2. $\hat{2}{X}^3+\hat{3}=(X^2+X+\hat{1})(\hat{2}X+\hat{3})+\hat{0}$. Verificare: $(X^2+X+\hat{1})(\hat{2}X+\hat{3})=\hat{2}{X}^3+\hat{5}{X}^2+\hat{5}X+\hat{3}=\hat{2}{X}^3+\hat{3}$. ✓

Ultimul rest nenul, $X^2+X+\hat{1}$, este monic, deci $\mathrm{cmmdc}(f,g)=X^2+X+\hat{1}$ în ${\mathbb{Z}}_5[X]$. Controlul: $f=X^2(X^2+X+\hat{1})$ și $g=\hat{2}(X-\hat{1})(X^2+X+\hat{1})$, iar $X^2$ și $X-\hat{1}$ nu au divizori comuni de grad pozitiv.

8. Polinoame prime între ele și rădăcinile comune

Două polinoame $f$ și $g$ se numesc prime între ele (sau relativ prime) dacă $\mathrm{cmmdc}(f,g)=1$, adică dacă singurii lor divizori comuni sunt constantele nenule.

Propoziție. Fie $f,g\in K[X]$ nenule și $d=\mathrm{cmmdc}(f,g)$. Un element $a\in K$ este rădăcină comună a lui $f$ și $g$ dacă și numai dacă $a$ este rădăcină a lui $d$.

Demonstrație. Dacă $d(a)=0$, atunci $X-a$ divide $d$, iar $d$ divide și pe $f$, și pe $g$; prin tranzitivitate $X-a$ le divide pe amândouă, deci $f(a)=g(a)=0$. Reciproc, dacă $f(a)=g(a)=0$, atunci, prin teorema lui Bézout, $X-a$ este divizor comun al lui $f$ și $g$; din definiția lui $\mathrm{cmmdc}$, orice divizor comun divide pe $d$, deci $X-a\mid d$ și $d(a)=0$. $■$

Consecința pe care o folosești la Bacalaureat M1: dacă $\mathrm{cmmdc}(f,g)=1$, cele două polinoame nu au nicio rădăcină comună, pentru că polinomul constant $1$ nu are rădăcini. Atenție însă la reciproca ei, care este falsă: din $\mathrm{grad}\mathrm{cmmdc}(f,g)\ge 1$ nu rezultă că există o rădăcină comună în $K$. Peste $\mathbb{R}$, polinoamele $f=g=X^2+1$ au $\mathrm{cmmdc}(f,g)=X^2+1$, dar nicio rădăcină reală. Enunțul corect rămâne cel din propoziție: rădăcinile comune sunt exact rădăcinile lui $\mathrm{cmmdc}(f,g)$ — dacă acesta are rădăcini în $K$.

Această propoziție este motivul pentru care merită învățat algoritmul. Întrebarea „au polinoamele $f$ și $g$ o rădăcină comună?" pare să ceară rezolvarea a două ecuații; în realitate ea cere doar câteva împărțiri, după care rămâne de rezolvat o singură ecuație, de obicei de gradul întâi sau al doilea. Cu cât gradele inițiale sunt mai mari, cu atât economia este mai spectaculoasă.

Cel mai mare divizor comun are și o a doua întrebuințare, imediată: simplificarea fracțiilor cu polinoame. Dacă vrei să aduci $\frac{f}{g}$ la formă ireductibilă, calculezi $d=\mathrm{cmmdc}(f,g)$, împarți fiecare polinom la $d$ și obții o fracție în care numărătorul și numitorul sunt prime între ele. Este exact procedeul de la fracțiile cu numere, mutat pe polinoame, și îl vei folosi curent la calculul limitelor și la descompunerea în fracții simple. În lecția următoare din unitate vei descoperi o a treia întrebuințare, poate cea mai elegantă: cu $\mathrm{cmmdc}(f,f^{\prime })$ se poate afla dacă un polinom are rădăcini multiple, fără să i se calculeze nicio rădăcină.

Exemple rezolvate

Exemplul 1 — Un c.m.m.d.c. de gradul întâi

Determinați $\mathrm{cmmdc}(f,g)$ pentru $f=X^3-3X+2$ și $g=X^2-4$.

Rezolvare. Împărțim $f$ la $g$: $X^3-3X+2=(X^2-4)\cdot X+(X+2)$. Verificare: $(X^2-4)X=X^3-4X$, plus $X+2$ dă $X^3-3X+2$. ✓

Împărțim $g$ la restul obținut: $X^2-4=(X+2)(X-2)+0$. Restul este nul.

Ultimul rest nenul este $X+2$, monic, deci $\mathrm{cmmdc}(f,g)=X+2$. Confirmare prin descompuneri: $f=(X-1{)}^2(X+2)$ și $g=(X-2)(X+2)$, singurul factor comun fiind $X+2$. Singura rădăcină comună este $-2$.

Exemplul 2 — Un c.m.m.d.c. de gradul al doilea

Determinați $\mathrm{cmmdc}(f,g)$ pentru $f=X^4-3X^2+2$ și $g=X^3+X^2-X-1$.

Rezolvare. Prima împărțire: $X^4-3X^2+2=(X^3+X^2-X-1)(X-1)+(-X^2+1)$. Verificare: $(X^3+X^2-X-1)(X-1)=X^4-2X^2+1$, iar adunând $-X^2+1$ obținem $X^4-3X^2+2$. ✓

A doua împărțire: $X^3+X^2-X-1=(-X^2+1)(-X-1)+0$. Verificare: $(-X^2+1)(-X-1)=X^3+X^2-X-1$. ✓

Ultimul rest nenul este $-X^2+1$, care nu este monic. Îl înmulțim cu $-1$:

$$\mathrm{cmmdc}(f,g)=X^2-1.$$

Control: $f=(X^2-1)(X^2-2)$ și $g=(X^2-1)(X+1)$. Rădăcinile comune sunt $1$ și $-1$.

Exemplul 3 — Când unul divide pe celălalt

Determinați $\mathrm{cmmdc}(f,g)$ pentru $f=X^4-1$ și $g=3X^2-3$.

Rezolvare. O singură împărțire: $X^4-1=(3X^2-3)\left(\frac{1}{3}{X}^2+\frac{1}{3}\right)+0$. Verificare: $(3X^2-3)\left(\frac{1}{3}{X}^2+\frac{1}{3}\right)=X^4+X^2-X^2-1=X^4-1$. ✓

Ultimul rest nenul este $g$ însuși. Făcut monic, dă

$$\mathrm{cmmdc}(f,g)=X^2-1.$$

Coeficienții fracționari de la cât nu apar în răspuns: ei există doar pe drum, iar peste un corp avem tot dreptul să-i folosim.

Exemplul 4 — Algoritmul lui Euclid în ${\mathbb{Z}}_3[X]$

Determinați $\mathrm{cmmdc}(f,g)$ în ${\mathbb{Z}}_3[X]$, pentru $f=X^4+\hat{2}$ și $g=X^3+X+\hat{1}$.

Rezolvare. Toate calculele se fac modulo $3$.

$$X^4+\hat{2}=(X^3+X+\hat{1})X+(\hat{2}{X}^2+\hat{2}X+\hat{2}).$$

Verificare: $(X^3+X+\hat{1})X=X^4+X^2+X$, iar $X^4+X^2+X+\hat{2}{X}^2+\hat{2}X+\hat{2}=X^4+\hat{3}{X}^2+\hat{3}X+\hat{2}=X^4+\hat{2}$. ✓

$$X^3+X+\hat{1}=(\hat{2}{X}^2+\hat{2}X+\hat{2})(\hat{2}X+\hat{1})+(X+\hat{2}).$$

Verificare: $(\hat{2}{X}^2+\hat{2}X+\hat{2})(\hat{2}X+\hat{1})=\hat{4}{X}^3+\hat{6}{X}^2+\hat{6}X+\hat{2}=X^3+\hat{2}$, iar adunând $X+\hat{2}$ obținem $X^3+X+\hat{4}=X^3+X+\hat{1}$. ✓

$$\hat{2}{X}^2+\hat{2}X+\hat{2}=(X+\hat{2})(\hat{2}X+\hat{1})+\hat{0}.$$

Ultimul rest nenul este $X+\hat{2}$, monic, deci $\mathrm{cmmdc}(f,g)=X+\hat{2}$. Într-adevăr, $\hat{2}=-\hat{1}$ este rădăcină comună: $f(\hat{2})=\widehat{16}+\hat{2}=\hat{1}+\hat{2}=\hat{0}$ și $g(\hat{2})=\hat{8}+\hat{2}+\hat{1}=\hat{2}+\hat{2}+\hat{1}=\hat{0}$.

Exemplul 5 — Un parametru dintr-o condiție de rădăcină comună

Determinați valorile reale ale lui $m$ pentru care polinoamele $f=X^3+mX+6$ și $g=X^2-X-6$ au o rădăcină comună, apoi calculați $\mathrm{cmmdc}(f,g)$ pentru fiecare valoare găsită.

Rezolvare. O rădăcină comună este, în particular, rădăcină a lui $g=(X-3)(X+2)$, deci poate fi doar $3$ sau $-2$.

Pentru $x=3$: $f(3)=27+3m+6=3m+33=0$, deci $m=-11$. Pentru $x=-2$: $f(-2)=-8-2m+6=-2m-2=0$, deci $m=-1$.

Pentru $m=-11$, algoritmul lui Euclid dă $X^3-11X+6=(X^2-X-6)(X+1)+(-4X+12)$, apoi $X^2-X-6=(-4X+12)\left(-\frac{1}{4}X-\frac{1}{2}\right)+0$; ultimul rest nenul, normalizat, este $X-3$, deci $\mathrm{cmmdc}(f,g)=X-3$.

Pentru $m=-1$, analog: $X^3-X+6=(X^2-X-6)(X+1)+(6X+12)$, apoi restul $0$; obținem $\mathrm{cmmdc}(f,g)=X+2$.

Exemplul 6 — Exemplu tip Bacalaureat M1

Se consideră polinoamele $f=X^4-5X^3+7X^2-5X+6$ și $g=X^3-4X^2+X+6$, cu coeficienți reali. a) Determinați câtul și restul împărțirii lui $f$ la $g$. b) Determinați $\mathrm{cmmdc}(f,g)$. c) Determinați rădăcinile comune ale polinoamelor $f$ și $g$.

Rezolvare. Este structura obișnuită a unei probleme de la Subiectul al II-lea: un calcul, o noțiune, o concluzie.

a) Împărțind, obținem câtul $q=X-1$ și restul $r=2X^2-10X+12$:

$$X^4-5X^3+7X^2-5X+6=(X^3-4X^2+X+6)(X-1)+(2X^2-10X+12).$$

Verificare prin înmulțire înapoi: $(X^3-4X^2+X+6)(X-1)=X^4-5X^3+5X^2+5X-6$, iar adunând restul obținem $X^4-5X^3+7X^2-5X+6$. ✓

b) Continuăm algoritmul lui Euclid, împărțind $g$ la restul de la punctul a):

$$X^3-4X^2+X+6=(2X^2-10X+12)\left(\frac{1}{2}X+\frac{1}{2}\right)+0.$$

Ultimul rest nenul este $2X^2-10X+12$; înmulțit cu $\frac{1}{2}$, dă

$$\mathrm{cmmdc}(f,g)=X^2-5X+6.$$

c) Conform propoziției din lecție, rădăcinile comune sunt exact rădăcinile lui $\mathrm{cmmdc}(f,g)$. Din $X^2-5X+6=0$ obținem $x_1=2$ și $x_2=3$. Control direct: $f(2)=16-40+28-10+6=0$ și $g(2)=8-16+2+6=0$; $f(3)=81-135+63-15+6=0$ și $g(3)=27-36+3+6=0$. ✓

Să exersăm

La fiecare exercițiu, verifică fiecare împărțire înmulțind înapoi și nu uita să faci monic ultimul rest nenul.

1. Determină $\mathrm{cmmdc}(X^2-1,X^2-3X+2)$.

2. Determină $\mathrm{cmmdc}(X^3-1,X^2-1)$ și precizează rădăcina comună.

3. Determină $\mathrm{cmmdc}(X^4-1,X^3+X^2+X+1)$.

4. Determină $\mathrm{cmmdc}(X^3+X^2-X-1,X^2+2X+1)$.

5. (Adevărat/Fals cu motivare.) „Cel mai mare divizor comun a două polinoame poate avea coeficientul dominant egal cu $2$."

6. Determină $\mathrm{cmmdc}(X^3-X,X^2+X)$ și rădăcinile comune ale celor două polinoame.

7. Arată că polinoamele $X^2+X+1$ și $X^2-X+1$ sunt prime între ele.

8. În ${\mathbb{Z}}_3[X]$, determină $\mathrm{cmmdc}(X^3+\hat{2},X^2+\hat{2})$.

9. Determină $\mathrm{cmmdc}(X^4+X^3+X^2+X,X^3+X)$.

10. (Problemă aplicată.) Într-un model de proiectare, două mărimi sunt date de polinoamele $f=X^3-X^2-4X+4$ și $g=X^3+4X^2+X-6$. Simplifică fracția $\frac{f}{g}$ până la forma ireductibilă, folosind cel mai mare divizor comun.

11. (Adevărat/Fals cu motivare.) „Dacă $\mathrm{cmmdc}(f,g)=1$, atunci $f$ și $g$ nu au nicio rădăcină comună."

12. Determină $\mathrm{cmmdc}(X^3-2X^2+X-2,X-2)$ și explică rezultatul folosind valoarea lui $f$ în $2$.

13. Determină valorile reale ale lui $m$ pentru care $f=X^3+mX+6$ și $g=X^2-X-6$ au un divizor comun de grad cel puțin $1$.

14. Explică, în două-trei fraze, de ce algoritmul lui Euclid aplicat unui polinom de gradul al cincilea și unuia de gradul al patrulea se oprește după cel mult cinci împărțiri.

15. (Exercițiu tip Bacalaureat M1.) Se consideră $f=X^4-2X^3+2X-1$ și $g=X^3-3X+2$. a) Determinați restul împărțirii lui $f$ la $g$. b) Determinați $\mathrm{cmmdc}(f,g)$. c) Arătați că $1$ este rădăcină comună a celor două polinoame.

16. În ${\mathbb{Z}}_5[X]$, determină $\mathrm{cmmdc}(X^4+\hat{4},X^2+\hat{4})$.

17. Determină $\mathrm{cmmdc}(X^4-16,2X^2-8)$ și formulează regula generală pentru cazul în care $g$ divide $f$.

18. (Provocare.) Arată că $\mathrm{cmmdc}(X^6-1,X^4-1)=X^2-1$ și formulează, pe baza acestui rezultat, o regulă pentru $\mathrm{cmmdc}(X^m-1,X^n-1)$.

Răspunsuri și explicații

1. $X^2-1=(X^2-3X+2)\cdot 1+(3X-3)$; apoi $X^2-3X+2=(3X-3)\left(\frac{1}{3}X-\frac{2}{3}\right)+0$. Ultimul rest nenul, $3X-3$, făcut monic dă $\mathrm{cmmdc}=X-1$.

2. $X^3-1=(X^2-1)X+(X-1)$; apoi $X^2-1=(X-1)(X+1)+0$. Deci $\mathrm{cmmdc}=X-1$, iar rădăcina comună este $1$.

3. O singură împărțire: $X^4-1=(X^3+X^2+X+1)(X-1)+0$. Deci $g\mid f$ și $\mathrm{cmmdc}=X^3+X^2+X+1$ (deja monic).

4. $X^3+X^2-X-1=(X^2+2X+1)(X-1)+0$, deci $\mathrm{cmmdc}=X^2+2X+1$. (Într-adevăr, $f=(X+1{)}^2(X-1)$ și $g=(X+1{)}^2$.)

5. Fals. Prin definiție, cel mai mare divizor comun este monic, adică are coeficientul dominant $1$. Polinomul $2X-2$ este, ce-i drept, tot un divizor comun al lui $X^2-1$ și $X^2-3X+2$, dar reprezentantul ales al familiei de asociați este $X-1$.

6. $X^3-X=(X^2+X)(X-1)+0$, deci $\mathrm{cmmdc}=X^2+X$. Rădăcinile comune sunt rădăcinile lui $X^2+X=X(X+1)$, adică $0$ și $-1$.

7. $X^2+X+1=(X^2-X+1)\cdot 1+2X$; apoi $X^2-X+1=2X\left(\frac{1}{2}X-\frac{1}{2}\right)+1$; apoi $2X=1\cdot 2X+0$. Ultimul rest nenul este constanta $1$, deci $\mathrm{cmmdc}=1$: polinoamele sunt prime între ele.

8. În ${\mathbb{Z}}_3[X]$: $X^3+\hat{2}=(X^2+\hat{2})X+(X+\hat{2})$, apoi $X^2+\hat{2}=(X+\hat{2})(X+\hat{1})+\hat{0}$. Deci $\mathrm{cmmdc}=X+\hat{2}$. Verificare: $\hat{2}$ este rădăcină pentru amândouă, căci $\hat{8}+\hat{2}=\hat{0}$ și $\hat{4}+\hat{2}=\hat{0}$.

9. $X^4+X^3+X^2+X=(X^3+X)(X+1)+0$, deci $\mathrm{cmmdc}=X^3+X$. (Descompunerile sunt $f=X(X+1)(X^2+1)$ și $g=X(X^2+1)$.)

10. Prima împărțire dă restul $-5X^2-5X+10$, iar a doua rest nul; normalizat, $\mathrm{cmmdc}(f,g)=X^2+X-2$. Cum $f=(X^2+X-2)(X-2)$ și $g=(X^2+X-2)(X+3)$, fracția se simplifică la $\frac{X-2}{X+3}$.

11. Adevărat. Rădăcinile comune ale lui $f$ și $g$ sunt exact rădăcinile lui $\mathrm{cmmdc}(f,g)$, iar polinomul constant $1$ nu are rădăcini. Atenție: implicația inversă nu e adevărată — $\mathrm{cmmdc}$ poate avea gradul $\ge 1$ fără ca rădăcinile lui să fie în corpul de lucru.

12. $X^3-2X^2+X-2=(X-2)(X^2+1)+0$, deci $\mathrm{cmmdc}=X-2$. Explicația: $f(2)=8-8+2-2=0$, deci $X-2$ divide $f$; fiind și divizor al lui însuși, el este cel mai mare divizor comun.

13. Un divizor comun de grad cel puțin $1$ înseamnă, aici, un factor de gradul întâi al lui $g=(X-3)(X+2)$, adică o rădăcină comună. Din $f(3)=3m+33=0$ obținem $m=-11$, iar din $f(-2)=-2m-2=0$ obținem $m=-1$. Pentru $m=-11$ divizorul comun este $X-3$, iar pentru $m=-1$ este $X+2$.

14. Restul primei împărțiri are gradul cel mult $3$, iar la fiecare pas următor gradul restului scade cu cel puțin $1$. Șirul gradelor $3>2>1>0$ are cel mult patru termeni, deci după prima împărțire mai urmează cel mult patru: în total cel mult cinci împărțiri, adică $\mathrm{grad}g+1$.

15. a) $X^4-2X^3+2X-1=(X^3-3X+2)(X-2)+(3X^2-6X+3)$, deci restul este $3X^2-6X+3$. b) A doua împărțire: $X^3-3X+2=(3X^2-6X+3)\left(\frac{1}{3}X+\frac{2}{3}\right)+0$; normalizând ultimul rest nenul, $\mathrm{cmmdc}(f,g)=X^2-2X+1$. c) Din $\mathrm{cmmdc}(f,g)=(X-1{)}^2$ rezultă că $1$ este rădăcină a lui $\mathrm{cmmdc}$, deci rădăcină comună; direct, $f(1)=1-2+2-1=0$ și $g(1)=1-3+2=0$.

16. În ${\mathbb{Z}}_5[X]$: $X^4+\hat{4}=(X^2+\hat{4})(X^2+\hat{1})+\hat{0}$, deci $\mathrm{cmmdc}=X^2+\hat{4}$. (Verificare: $(X^2+\hat{4})(X^2+\hat{1})=X^4+\hat{5}{X}^2+\hat{4}=X^4+\hat{4}$.)

17. $X^4-16=(2X^2-8)\left(\frac{1}{2}{X}^2+2\right)+0$, deci $g\mid f$, iar ultimul rest nenul este $g$. Normalizat, $\mathrm{cmmdc}=X^2-4$. Regula: dacă $g\mid f$, atunci $\mathrm{cmmdc}(f,g)$ este $g$ făcut monic.

18. $X^6-1=(X^4-1)X^2+(X^2-1)$, apoi $X^4-1=(X^2-1)(X^2+1)+0$. Ultimul rest nenul este $X^2-1$, monic, deci $\mathrm{cmmdc}=X^2-1$. Cum $2$ este cel mai mare divizor comun al numerelor $6$ și $4$, regula care se ghicește (și care este adevărată) este $\mathrm{cmmdc}(X^m-1,X^n-1)=X^d-1$, unde $d$ este cel mai mare divizor comun al numerelor naturale $m$ și $n$.

De reținut

• Cel mai mare divizor comun a două polinoame nenule este polinomul monic care le divide pe amândouă și care se divide cu orice alt divizor comun al lor; se notează $\mathrm{cmmdc}(f,g)$.
• Cerința de a fi monic este necesară pentru unicitate, pentru că orice divizor comun înmulțit cu o constantă nenulă rămâne divizor comun.
• Lema fundamentală spune că, dacă $f=gq+r$, atunci $\mathrm{cmmdc}(f,g)=\mathrm{cmmdc}(g,r)$; pe ea se sprijină întreg algoritmul lui Euclid.
• Algoritmul lui Euclid înlocuiește pas cu pas perechea $(f,g)$ cu perechea $(g,r)$, se oprește la primul rest nul, iar răspunsul este ultimul rest nenul făcut monic.
• Rădăcinile comune ale două polinoame sunt exact rădăcinile celui mai mare divizor comun al lor, deci se pot afla fără să rezolvi vreuna dintre cele două ecuații.

Greșeli frecvente

• Uitarea normalizării. Ultimul rest nenul este adesea $-3X^2+6X-3$ sau $2X-4$; răspunsul corect este acela înmulțit cu inversul coeficientului dominant, adică $X^2-2X+1$, respectiv $X-2$. Un c.m.m.d.c. nemonic este considerat greșit.
• Oprirea la penultimul rest. Algoritmul se oprește când restul este zero, iar răspunsul este restul dinaintea lui. Cine ia ultimul rest calculat, adică $0$, ajunge la un răspuns fără sens.
• Confuzia dintre grad mare și divizor comun. Nu polinomul de grad maxim dintre divizorii comuni „câștigă" prin definiție, ci acela care se divide cu toți ceilalți. Din fericire, la polinoame peste un corp cele două formulări dau același rezultat — dar definiția corectă este cea prin divizibilitate.
• „$\mathrm{cmmdc}$ de grad $\ge 1$ înseamnă rădăcină comună." Fals peste $\mathbb{Q}$ și peste $\mathbb{R}$: pentru $f=g=X^2+1$ avem $\mathrm{cmmdc}(f,g)=X^2+1$, fără nicio rădăcină reală. Corect este că rădăcinile comune sunt rădăcinile lui $\mathrm{cmmdc}(f,g)$, dacă acesta are rădăcini în corpul de lucru.
• Spaima de coeficienți fracționari. Într-un corp, împărțirea cu orice element nenul este permisă, deci fracțiile apărute pe drum nu sunt o eroare. Ele dispar la normalizarea finală și nu se transmit în răspuns.

Aplică acasă

1. Euclid la numere și la polinoame, în paralel. Calculează cel mai mare divizor comun al numerelor $84$ și $60$ prin împărțiri succesive și, alături, $\mathrm{cmmdc}(X^4-1,X^6-1)$. Scrie cele două șiruri de împărțiri unul lângă altul și observă că regula este cuvânt cu cuvânt aceeași; singura deosebire este că, la polinoame, „mai mic" înseamnă „de grad mai mic".

2. Fabrica de perechi. Alege trei polinoame de gradul întâi, de exemplu $X-1$, $X+2$, $X-3$, și construiește $f$ ca produsul primelor două, $g$ ca produsul ultimelor două. Aplică algoritmul lui Euclid și verifică dacă rezultatul este chiar factorul comun. Repetă cu factori de gradul al doilea fără rădăcini reale.

3. Simplificatorul de fracții. Ia o fracție cu polinoame de la un exercițiu de analiză și, înainte de a-i studia limita, calculează-i $\mathrm{cmmdc}$ dintre numărător și numitor. Dacă iese diferit de $1$, simplifică fracția și compară efortul cu cel al metodei „caut rădăcini evidente".

Pentru părinți și profesori

Lecția transformă divizibilitatea polinoamelor, cunoscută de la clasa a X-a ca proprietate, într-un algoritm cu rezultat garantat. Valoarea ei formativă este dublă: pe de o parte arată că schema de la numere naturale se transferă intact la polinoame peste un corp, pe de alta oferă o metodă care răspunde la întrebarea „au rădăcini comune?" fără să rezolve nicio ecuație — ceea ce, pentru grade mari, este singura cale realistă.

De verificat în caiet: (1) fiecare împărțire este verificată prin înmulțire înapoi; (2) restul are gradul strict mai mic decât împărțitorul; (3) răspunsul final este monic; (4) elevul se oprește la restul nul și raportează restul dinaintea lui. Întrebări de control: „Ce înseamnă că un polinom este monic?"; „De ce se oprește algoritmul?"; „Ce legătură este între c.m.m.d.c. și rădăcinile comune?"; „Ce faci dacă ultimul rest nenul este $-2X+4$?".

La profilul matematică-informatică (mate-info), tema aceasta este singurul loc din liceu în care elevul întâlnește un algoritm cu terminare demonstrată. La BAC, ea apare în Subiectul al II-lea, în probleme cu polinoame: se cere restul unei împărțiri, apoi divizorul comun, apoi rădăcinile comune — exact ordinea din Exemplul 6. Semn că elevul a înțeles: la o problemă cu „arătați că $f$ și $g$ au o rădăcină comună" pornește algoritmul lui Euclid în loc să caute rădăcini prin încercări.

Întrebări frecvente

Ce este cel mai mare divizor comun a două polinoame? Este polinomul monic care divide ambele polinoame și care, la rândul lui, se divide cu orice alt divizor comun al lor. Se notează $\mathrm{cmmdc}(f,g)$ și este unic tocmai pentru că i se cere să fie monic. Fără această condiție ar exista o familie întreagă de răspunsuri, care diferă prin factori constanți nenuli.

Cum se calculează c.m.m.d.c. a două polinoame? Cu algoritmul lui Euclid: împarți primul polinom la al doilea, apoi al doilea la restul obținut, apoi restul precedent la restul nou și tot așa, până când un rest iese zero. Ultimul rest nenul, înmulțit cu inversul coeficientului său dominant ca să devină monic, este cel mai mare divizor comun căutat.

De ce se oprește algoritmul lui Euclid? Pentru că gradele resturilor formează un șir strict descrescător de numere naturale, iar un astfel de șir nu poate fi infinit. La fiecare pas restul are gradul strict mai mic decât împărțitorul, deci după cel mult $\mathrm{grad}g+1$ împărțiri se ajunge obligatoriu la restul nul, unde procedeul se încheie.

Ce înseamnă că două polinoame sunt prime între ele? Înseamnă că cel mai mare divizor comun al lor este polinomul constant $1$, adică singurii lor divizori comuni sunt constantele nenule. Consecința practică imediată: două polinoame prime între ele nu au nicio rădăcină comună, pentru că rădăcinile comune sunt exact rădăcinile celui mai mare divizor comun.

Cum aflu rădăcinile comune a două polinoame fără să le rezolv? Calculezi $\mathrm{cmmdc}(f,g)$ cu algoritmul lui Euclid și îi afli rădăcinile. Propoziția demonstrată în lecție spune că rădăcinile comune ale lui $f$ și $g$ sunt exact rădăcinile acestui polinom, care are de obicei gradul mult mai mic decât cele două date, deci este mult mai ușor de rezolvat.

De ce trebuie ca rezultatul să fie monic? Pentru unicitate. Dacă $d$ este divizor comun, atunci și $cd$ este divizor comun pentru orice constantă nenulă $c$, fiindcă într-un corp constantele nenule sunt inversabile. Alegând reprezentantul cu coeficientul dominant egal cu $1$, din toată familia de polinoame asociate rămâne exact unul, iar răspunsul devine bine determinat.

Funcționează algoritmul lui Euclid și peste ${\mathbb{Z}}_p$? Da, fără nicio modificare, pentru că ${\mathbb{Z}}_p$ cu $p$ prim este corp și orice clasă nenulă este inversabilă. Singura deosebire practică este că, la fiecare împărțire, coeficientul dominant al împărțitorului se inversează modulo $p$: în ${\mathbb{Z}}_5$, de exemplu, ${\hat{2}}^{-1}=\hat{3}$, iar toate calculele se reduc apoi modulo $5$.

Unde apare tema la Bacalaureat M1? În Subiectul al II-lea, la problemele cu polinoame: se cere restul unei împărțiri, apoi divizorul comun al două polinoame, apoi rădăcinile comune. Formularea tipică este „determinați rădăcinile comune ale polinoamelor $f$ și $g$", iar drumul cel mai scurt trece prin algoritmul lui Euclid, nu prin căutarea rădăcinilor.