1

I have been trying to solve this with no success. Could you suggest me a solution?

H-a-y-K
  • 661

2 Answers2

3

Back to the basics! Remember how you do it for integers? For example, how would you find $x$, $y$ such that $23x+47y=1$? That's right, Euclid's algorithm.

Let's try to calculate the GCD of $(x+1)^2$ and $x^2+x+1$.

$$ (x+1)^2 - (x^2+x+1) = x\\ (x^2+x+1) - x(x+1) = 1 $$ Hence, $$(x^2+x+1) - ((x+1)^2 - (x^2+x+1))(x+1) = 1$$ Therefore, $$- (x+1)(x+1)^2 + (x+2)(x^2+x+1) = 1$$

  • Okay, as I understand, here you replaced x with $(x+1)^2 - (x^2+x+1)$.$(x^2+x+1) - ((x+1)^2 - (x^2+x+1))(x+1) = 1$. But why? This should be part of a specific algorithm and I can't find a pattern. for example, what would be the equivalent to these steps in case of 23x + 47y = 1? P.S. I know how Euclid's algorithm works generally. – H-a-y-K Mar 25 '21 at 18:48
  • Maybe $23x+47y=1$ is not a good example because it's just $(x,y)=(-2,1)$, so let's say $23x+30y=1$. $$ 30-23=7\ 23 - 3\cdot7=2\ 7 - 3\cdot2=1 $$ Then we can work backwards, substituting the equations into each other, until we've got a linear combination of $23$ and $30$. The first step would be $7 - 3\cdot(23-3\cdot7)=1$. Do you see how that finishes? –  Mar 26 '21 at 08:00
  • ohhh I think I got it. Basically we say that $a = q_1b + r_1$; $b = q_2r_1 + r_2$; $r_1 = q_3r_2 + r_3$ and so on until we reach $r_{k-1} = q_{k+1}r_k$. so by substituting b and $r_1$ we solve the problem. Now I remember there was a ready result of the substitution in my book. Thanks! – H-a-y-K Mar 26 '21 at 08:15
  • 1
    thanks! I got it and just solved the problem. – H-a-y-K Mar 26 '21 at 09:57
  • @vrugtehagel What does 'you can't always do this for polynomials' mean here? This usual 'extended' Euclidean algorithm should be guaranteed to generate a pair $a(), b()$ that satisfies $a(x)f(x)+b(x)g(x)=\mathop{GCD}(f(x), g(x))$... – Steven Stadnicki Mar 29 '21 at 17:25
  • I'll just flat out admit I haven't done some proper math in ages and I came back here for some nostalgia - clearly I'm more rusty than I thought I was. I remember something that was different about polynomials with integer coefficients, like e.g. $M_1(x) = x^2$ and $M_2(x) = 2x + 1$, but I guess even then this works to some extent. I'll remove that part, thanks for calling me out! –  Mar 30 '21 at 06:45
1

Here is an alternate basic approach based upon coefficient comparison of polynomials. We are looking for polynomials $M_1(x), M_2(x)$ so that the identity \begin{align*} \left(x^2+2x+1\right)M_1(x)+\left(x^2+x+1\right)M_2(x)=1\tag{1} \end{align*} is valid.

We start with some observations:

  • Since the right-hand side of (1) is a polynomial of degree zero, the left-hand side has also to be a polynomial of degree zero.

  • We are looking for polynomials $M_1$ and $M_2$ which have smallest possible degree. We observe setting $M_1(x)=1$ and $M_2(x)=-1$ is not appropriate since we get rid of the square terms but not of the linear terms.

  • Ansatz: We start with linear polynomials \begin{align*} M_1(x)=ax+b\qquad M_2(x)=cx+d \end{align*} with unknown coefficients $a,b,c,d\in\mathbb{R}$, multiply out and make a comparison of coefficients of LHS and RHS of (1).

We denote with $[x^n]$ the coefficient of $x^n$ of a polynomial and obtain from (1) \begin{align*} [x^3]:\qquad\qquad &a+c&=0\\ [x^2]:\qquad\qquad&(2a+b)+(c+d)&=0\\ [x^1]:\qquad\qquad&(a+2b)+(c+d)&=0\\ [x^0]:\qquad\qquad&b+d&=1\\ \end{align*}

Coefficient comparison of $[x^3]$ gives: $c=-a$. Putting this in the other three equations results in

\begin{align*} a+b+d&=0\\ 2b+d&=0\\ b+d&=1\\ \end{align*} from which we easily find $a=-1, b=-1, c=1, d=2$.

We finally obtain \begin{align*} \color{blue}{M_1(x)=-x-1\quad M_2(x)=x+2} \end{align*} in accordance with the other given answer.

Markus Scheuer
  • 108,315