algoritm rezolvare en

7/29/2019 Algoritm Rezolvare En

1/6

AN ALGORITHM TO FIND A SOLUTIONFOR THE EQUATION fu + gv = h IN THE

RING R[X]

Eduard ASADURIAN

Abstract

It is known that if f, g R[X] and d = GCD(f, g) then thereexists u, v R[X] so that f u + gv = h. Using that R[X] is a principalideal domain the proof is obvious. But this proof is nonconstructivebecause it does no provide a way to find the polynomials u, v to verifythe relation f u + gv = h.

The purpose of this work is to present an algorithmic solution forthe equation

f u + gv = 0, deg u < deg g, deg v < deg f (1)

in the ring R[X], or more generally, in the ring K[X], where K is afield. The key to get a solution (u, v) is the resultant Res(f, g) of thepolynomials f, g Using a minimal theoretical device we can decide theexistence of a solution of the equation. The, starting from finding asolution for the equation f u + gv = c where c R, we get a solutionfor the equation f u + gv = h. An interesting fact is that if f, gand h are polynomials in Z[X], the we obtain a solution (u, v), alsocomposed of polynomials with integer composed of polynomials withinteger coefficients.

1 The existence of the nonzero solu-

tion

The first statement refers to the existence of certain type of nonzerosolution computable (u, v) of the equation f u + gv = 0.

Universitatea din Pitesti, Facultatea de Matematica Informatica, Targu din Vale 1,Pitesti, Romania

1


2/6

Propozitie 1.1. Let f, g R[X] two nonzero polynomials of degrees

1. Then the equation

f u + gv = 0, deg u < deg g, deg v < deg f (2)

has a nonzero solution (u, v)if and only if f, g have a nonconstantcommon factor.

Proof. If (u, v) is a nonzero solution, then f u = gv f|gv. Sup-posing that f, g are relatively prime, thus GCD(f, g) = 1, from f|gv itfollows that f|v, respectively deg f deg v, contradiction. So, thereexists h R[X] a common factor with deg h > 0. Conversely, let h bea nonconstant common factor of the polynomials f, g. If f = hf1 andg = hg1, then the ordered pair (g1, f1) is a nonzero solution of theequation (2).

The notion of the resultant is closely related to finding a nonzerosolution (u, v) for the equation (2). Then, if f, g R[X] are of theform

f = a0 + a1X + + alXl,

g = b0 + b1X + + bmXm,

(3)

then the solutions (u, v) of the equation (2) will be of form

u = u0 + u1X + + um1Xm1,

v = v0 + v1X + + vl1Xl1. (4)

We substitute the expressions of polynomials f , g , u and v in therelation f u + gv = 0 and we get the following homogeneous system ofm + l liniar equations with m + l unknowns:

a0u0 + b0v0 = 0,a1u0 + a0u1 + b1v0 + b0v1 = 0,

alum1 + bmvl1 = 0.

(5)

The matrix of the system (5), denoted Sylv(f, g) and called theSylvester matrixof the polynomials f, g is a (m + l) (m + l) square

2


3/6

matrix and is of form

a0 0 0 b0 0 0 0

a1 a0 0 b1 b0 0 0

a2 a1 0 b2 b1 b0 0

al al1 0 al 0 0

bm bm1 bm

0 0 al1 0 0 bm10 0 al 0 0 bm

The entries of the first m columns are the elements a0, a1, . . . , aland 0 and the entries of the latest are the elements b0, b1, . . . , bm and0. The determinant det(Sylv(f, g)) =: Res(f, g) is called the resultantof the polynomials f, g.

Now, the condition the equation (2) to have a nonzero solutionis equivalent with the condition that the system (5)has nonzero solu-tions. Therefore, we can formulate

Corolar 1.2. If f, g are two polynomial of degree > 1, then the fol-lowing statements are equivalent:

i) The equation f u + gv = 0, deg u < deg g, deg v < deg f has anonzero solution (u, v) R[X] R[X];

ii) The polynomials f, g have a nonconstant common factor;iii) Res(f, g) = 0.

The next proposition together with its proof, completes the theo-retical support of solving equation (1).

Propozitie 1.3. Iff, g R[X] are two nonconstant polynomials, then

the equation f u + gv = Res(f, g) (6)

has at least a nonzero solution (u, v) with deg u < deg g, deg v < deg f.Furthermore, if f, g Z[X] and Res(f, g) = 0, then there exists asolution with polynomials u, v Z[X].

Proof. If Res(f, g) = 0, then Corollary 1.2 assure the existence ofnonzero solutions. If Res(f, g) = 0, then Corollary 1.2 implies thatGCD(f, g) = 1. If f and g have the form (3), the first we search for

u, v of the form (4) solutions of the equations f u + gv = 1. But to

3


4/6

solve the equation f u + gv = 1 it means solving the system of linear

equations

a0u

0+ b0v

0= 0,

a1u

0+ a0u

1+ b1v

0+ b0v

1= 0,

alu

m1 + bmv

l1 = 1,

(7)

that differs from the system (5) only the last equation. BecauseRes(f, g) = 0 it results that the system (7) has a unique solution thatwe can obtain using Crammers rule. The expression of each unknown

ui, v

j is a fraction with denominator Res, and the numerator a sumof products with coefficients ai, bj. Using this remark, if f, g Z[X],

then u = Res(f, g)u and v = Res(f, g)v are polynomials over Z.

2 Elaborating the algorithm

The previous statements together with those proofs make up the sup-port of an algorithmic way to solve equation (1). So,1) If Res(f, g) = 0, then GCD(f, g) = 1. In these conditions

(i) The equation f u + gv = 0, deg u < deg g, deg v < deg f hasonly solution zero according to Corollary 1.2.

(ii) The equation f u + gv = 1, has a nonzero solution (u, v) from

which we obtain the solution u = hu

, v = hv

of the equation (1).2) If Res(f, g) = 0, then f and g have a nonconstant common factorand let d =GCD(f, g).

(i) Equation f u + gv = 0 has a nonzero solution that we get bysolving the system (5).

(ii) The equation f u + gv = c, where c R, has no solutionsbecause if f = df1 and g = dg1, then from d(f1u + g1v) = c it results

d|c, impossible because of the degrees.(iii) The equation f u + gv = h, where deg h > 0, has no solution if

d h. Otherwise, if h = dh1, then the solving of the equation(1) reduces to the solving of the equation f1u + g1v = h1, with

Res(f1, g1) = 0. From the proof of the Proposition 1.3 the equa-tion f1u

+ g1v = 0 has a nonzero solution (u, v). From this solution

we obtain f1uh1d+g1u

h1d = h1d, respectively f(uh1) +g(v

h1) = h.Thus, u = uh1 and v = v

h1 is a nonzero solution of the equation (1).Concerning the algorithm that follows, the calculus of the resultant

Res(f, g) is algorithmized (see [1]) and for solving of the system (5)or of the system (7) there are commands of several computer algebrasystems.

We emphasize that the algorithm work for the equation (1) in theconditions deg f > 1 and deg g > 1. The solving of the equation (1)

4


5/6

with f =const. or g =const. is obvious, so these possibilities was

ignored in the elaborating of the algorithmAlgorithm to find the solution of equation

f u + gv = h, deg u < deg g, deg v < deg f

Input: f , g , h/* f, g are nonconstant polynomials */

Output: (u, v);res:=Res(f, g)if h = 0 then

if res = 0 then(u, v):= the pair of polynomials obtained by solving the system (5)else

(u, v) := (0, 0)

if deg h = 0 thenif res = 0 then

(u, v):= equation has no solutionselse

(u, v):= are nonconstant polynomials;(u, v) := (uh, vh)

if deg h > 0 thenif res = 0 then

d :=GCD(f, g);

r:=remainder of the division of h by d;if r = 0 then

f := f|d;

g := g|d;

h := h|d;(u, v):=the pair of polynomials obtained by solving the system(7);(u, v) := (uh,vh)

else

(u, v) := equation has no solutions

else(u, v):= the pair of polynomials obtained by solving the system (7);(u, v) := (hu, hv)

5


6/6

Bibliografie

[1] D.Cox, J.Little, D.O.Shea, Ideals, Varieties and Algorithms,Springer-Verlag, 1991.

[2] V.Ene, Capitole de algebra asistata de calculator, Ex Ponto,Constanta, 2002.

6

algoritm rezolvare en

Documents