1. ## Coprime polynomials

Can you help me with this problem:

I have to prove that if gcd(f(x),g(x))=1 then there exist unique u(x) and v(x) such that u(x)f(x)+v(x)g(x)=1 and deg u(x)< deg g(x) , deg v(x)< deg f(x).

This problem seems so strange. How to prove this?

2. this is just gcd of two polynomials. to prove unique suppose not then arrive at a contradiction. this is only an existence and uniqueness proof

3. Originally Posted by xianghu21
this is just gcd of two polynomials. to prove unique suppose not then arrive at a contradiction. this is only an existence and uniqueness proof

To be honest I thought the same.Indeed, this problem seems trivial. So I should take u(x)f(x)+v(x)g(x)=1 as grated without proof?

4. Existence is given by euclidean algorithm: Here it is: An important consequence of the Euclidean algorithm is finding integers and such that

This can be done by starting with the equation for , substituting for from the previous equation, and working upward through the equations. Now just prove uniqueness. Then you are done. i.e. euclidean algorithm is valid for any ring of polynomials.

5. Originally Posted by andreas
Can you help me with this problem:

I have to prove that if gcd(f(x),g(x))=1 then there exist unique u(x) and v(x) such that u(x)f(x)+v(x)g(x)=1 and deg u(x)< deg g(x) , deg v(x)< deg f(x).

This problem seems so strange. How to prove this?
those who replied to your question forgot that we also need to have $\displaystyle \deg u(x) < \deg g(x)$ and $\displaystyle \deg v(x) < \deg f(x).$ the problem is not trivial! anyway, i'll assume that the polynomials are over

a field. we know that there exist polynomials $\displaystyle u_1(x)$ and $\displaystyle v_1(x)$ such that $\displaystyle u_1(x)f(x) + v_1(x)g(x) = 1.$ now there exist polynomials $\displaystyle u(x)$ and $\displaystyle r(x)$ such that $\displaystyle u_1(x)=r(x)g(x) + u(x),$ where either

$\displaystyle u(x)=0,$ or $\displaystyle \deg u(x) < \deg g(x).$ also there exist polynomials $\displaystyle v(x)$ and $\displaystyle s(x)$ such that $\displaystyle v_1(x)=s(x)f(x)+v(x),$ where either $\displaystyle v(x)=0,$ or $\displaystyle \deg v(x) < \deg f(x).$

so: $\displaystyle (r(x) + s(x))f(x)g(x) + u(x)f(x) + v(x)g(x)=1,$ which is possible only if $\displaystyle r(x) + s(x)=0.$ why? therefore: $\displaystyle u(x)f(x) + v(x)g(x)=1,$ and the existence part is done. for the uniqueness

suppose we have $\displaystyle u(x)f(x) + v(x)g(x)=u'(x)f(x)+v'(x)g(x)=1,$ with $\displaystyle \deg u(x) < \deg g(x), \ \deg v(x) < \deg f(x),$ and $\displaystyle \deg u'(x) < \deg g(x), \ \deg v'(x) < \deg f(x).$ then we will have:

$\displaystyle (u(x)-u'(x))f(x)=(v'(x)-v(x))g(x).$ thus, since $\displaystyle \gcd(f(x),g(x))=1,$ we must have $\displaystyle f(x) \mid v'(x)-v(x),$ which is possible only if $\displaystyle v(x)-v'(x)=0,$ because $\displaystyle \deg(v(x)-v'(x)) < \deg f(x).$

hence $\displaystyle v(x)=v'(x),$ and therefore: $\displaystyle (u(x)-u'(x))f(x)=0,$ which gives us: $\displaystyle u(x)=u'(x). \ \ \Box$