TAOCP 4.6.1 Exercise 1
Let u(x)=x^6+x^5-x^4+2x^3+3x^2-x+2, and
Section 4.6.1: Division of Polynomials
Exercise 1. [10] Compute the pseudo-quotient $q(x)$ and pseudo-remainder $r(x)$, namely the polynomials satisfying (1), when $u(x) = x^6 + x^5 - x^4 + 2x^3 + 3x^2 - x + 2$ and $v(x) = 2x^2 + 2x^2 - x + 3$, over the integers.
Verified: yes
Solve time: 5m45s
Let
$$ u(x)=x^6+x^5-x^4+2x^3+3x^2-x+2, $$
and
$$ v(x)=2x^2+2x^2-x+3=4x^2-x+3. $$
Since $\deg u=6$, $\deg v=2$, and the leading coefficient of $v$ is $v_n=4$, the pseudo-division identity is
$$ 4^{,6-2+1}u(x)=q(x)v(x)+r(x), \qquad \deg r<2. $$
Hence we seek $q(x)$ and $r(x)$ such that
$$ 1024,u(x)=q(x)(4x^2-x+3)+r(x). $$
We perform pseudo-division. At each step, if the current dividend is $A(x)$, we replace it by
$$ 4A(x)-a x^{k}v(x), $$
where $a x^{k}$ is the leading term of $A(x)$.
The initial dividend is
$$ A_0(x)=u(x). $$
Its leading term is $x^6$. Therefore
$$ A_1(x) =4A_0(x)-x^4v(x). $$
Computing,
$$ 4A_0(x) =4x^6+4x^5-4x^4+8x^3+12x^2-4x+8, $$
$$ x^4v(x)=4x^6-x^5+3x^4, $$
hence
$$ A_1(x) =5x^5-7x^4+8x^3+12x^2-4x+8. $$
The first quotient term is $x^4$.
The leading term of $A_1$ is $5x^5$. Thus
$$ A_2(x) =4A_1(x)-5x^3v(x). $$
Since
$$ 4A_1(x) =20x^5-28x^4+32x^3+48x^2-16x+32, $$
$$ 5x^3v(x)=20x^5-5x^4+15x^3, $$
we obtain
$$ A_2(x) =-23x^4+17x^3+48x^2-16x+32. $$
The second quotient term is $5x^3$.
The leading term of $A_2$ is $-23x^4$. Thus
$$ A_3(x) =4A_2(x)+23x^2v(x). $$
Now
$$ 4A_2(x) =-92x^4+68x^3+192x^2-64x+128, $$
$$ 23x^2v(x) =92x^4-23x^3+69x^2, $$
so
$$ A_3(x) =45x^3+261x^2-64x+128. $$
The third quotient term is $-23x^2$.
The leading term of $A_3$ is $45x^3$. Hence
$$ A_4(x) =4A_3(x)-45x,v(x). $$
Since
$$ 4A_3(x) =180x^3+1044x^2-256x+512, $$
$$ 45x,v(x) =180x^3-45x^2+135x, $$
we get
$$ A_4(x) =1089x^2-391x+512. $$
The fourth quotient term is $45x$.
The leading term of $A_4$ is $1089x^2$. Therefore
$$ A_5(x) =4A_4(x)-1089,v(x). $$
Now
$$ 4A_4(x) =4356x^2-1564x+2048, $$
$$ 1089,v(x) =4356x^2-1089x+3267, $$
hence
$$ A_5(x) =-475x-1219. $$
The fifth quotient term is $1089$.
Since $\deg A_5=1<2=\deg v$, the algorithm terminates. The pseudo-remainder is
$$ r(x)=-475x-1219. $$
The pseudo-quotient is obtained from the recursive rule
$$ Q_{i+1}=4Q_i+t_i, $$
where $t_i$ is the quotient term selected at stage $i$. Starting with $Q_0=0$,
$$ \begin{aligned} Q_1&=x^4,\ Q_2&=4x^4+5x^3,\ Q_3&=16x^4+20x^3-23x^2,\ Q_4&=64x^4+80x^3-92x^2+45x,\ Q_5&=256x^4+320x^3-368x^2+180x+1089. \end{aligned} $$
Thus
$$ q(x)=256x^4+320x^3-368x^2+180x+1089, $$
$$ r(x)=-475x-1219. $$
A direct expansion gives
$$ q(x)(4x^2-x+3) = 1024x^6+1024x^5-1024x^4+2048x^3 +3072x^2-549x+3267, $$
and therefore
$$ q(x)(4x^2-x+3)+r(x) = 1024x^6+1024x^5-1024x^4+2048x^3 +3072x^2-1024x+2048 = 1024,u(x). $$
Hence
$$ \boxed{ q(x)=256x^4+320x^3-368x^2+180x+1089, \qquad r(x)=-475x-1219. } $$