Elements of correction

$(1)$

Define:

$$f = f_m x^m + \cdots + f_1 x + f_0 \ \ {\rm and} \ \ g = x^n + \cdots + g_1 x + g_0.$$ (1)

The following discussion is meant to give upper bounds for the quotient $q$ and the remainder $r$ in the division-with-remainder of $f$ by $g$ . We follow the classical algorithm (not the fast one) as stated at the beginning of the chapter on fast division.

Observe that the quotient $q$ has degree $m -n$ , so we define:

$$q = q_{m-n} x^{m-n} + \cdots + q_1 x + q_0.$$ (2)

Since $g$ is monic, we clearly have:

$$q_{m-n} = f_m.$$ (3)

Let $r_0 = f$ be the ``initial'' remainder and let $C_0 = B_f$ be the largest absolute value of a coefficient in $r_0$ . During the first iteration $r_0$ is replaced by

$$r_1 = r_0 - q_{m-n} g x^{m-n}.$$ (4)

The ``intermediate'' remainder $r_1$ is either null or $C_1$ the largest absolute value of a coefficient in $r_1$ satisfies:

$$C_1 \leq C_0 + C_0 B_g = C_0 (1 + B_g)$$ (5)

If $r_1 \neq 0$ , then the next intermediate remainder $r_2$ satisfies

$$r_2 = r_1 - {\rm lc}(r_1) g x^{{\deg}(r_1) - n}$$ (6)

where ${\rm lc}(r_1)$ is the leading coefficient of $r_1$ and, also, the next non-zero coefficient in $q$ . If $r_2 \neq 0$ , then $C_2$ the largest absolute value of a coefficient in $r_2$ satisfies:

$$C_2 \leq C_1 + C_1 B_g \leq C_0 (1 + B_g)^2.$$ (7)

Then, an easy induction leads to:

$$B_q \leq B_f (1 + B_g)^{m-n}.$$ (8)

Observe that an upper bound for the absolute value of a coefficient in $r$ is rather

$$B_r \leq B_f (1 + B_g)^{m-n+1}.$$ (9)

$(2)$

We make a preliminary observation. Let $m \geq 1$ be an odd integer such that we have

$$m/2 > B_f (1 + B_g)^{m-n+1}.$$ (10)

Note that this implies

$$m/2 > B_f, \ m/2 > B_g \ \ {\rm and} \ \ m/2 > B_q.$$ (11)

We represent the elements of ${\mbox{${\mathbb{Z}}$}}/m{\mbox{${\mathbb{Z}}$}}$ with the symmetric range $-\frac{m-1}{2} \cdots \frac{m-1}{2}$ . Let ${\Psi}_m$ be the corresponding canonical ring homomorphism from ${\mbox{${\mathbb{Z}}$}}[x]$ to ${\mbox{${\mathbb{Z}}$}}/m{\mbox{${\mathbb{Z}}$}}[x]$ . In ${\mbox{${\mathbb{Z}}$}}[x]$ we have:

$$f = q g + r \ \ {\rm and} \ \ {\deg}(r) < {\deg}(g).$$ (12)

This implies the following in ${\mbox{${\mathbb{Z}}$}}/m{\mbox{${\mathbb{Z}}$}}[x]$ :

$${\Psi}_m(f) = {\Psi}_m(q) {\Psi}_m(g) + {\Psi}_m(r) \ \ {\rm and} \ \ {\deg}({\Psi}_m(r)) < {\deg}({\Psi}_m(g)).$$ (13)

Observe that we have:

$${\Psi}_m(f) = f, \ {\Psi}_m(g) = g, \ {\Psi}_m(q) = q \ \ {\rm and} \ \ {\Psi}_m(r) = r.$$ (14)

We shall describe now how to compute ${\Psi}_m(q)$ and ${\Psi}_m(r)$ , and thus $q$ and $r$ .

Consider $p_1 < \cdots < p_r$ odd primes such that their product $m$ satisfies (10). For all $1 \leq i \leq r$ , let $f_{p_i}$ , $g_{p_i}$ , $q_{p_i}$ and $r_{p_i}$ be the respective images of $f$ , $g$ , $q$ and $r$ in ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$ . Thus, for all $1 \leq i \leq r$ , we have in ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$

$$f_{p_i} = g_{p_i} q_{p_i} + r_{p_i} \ \ {\rm and} \ \ {\deg}(r_{p_i}) < {\deg}(g_{p_i}).$$ (15)

By virtue of the uniqueness of the division by a monic polynomial, this implies that for all $1 \leq i \leq r$ , the couple $(q_{p_i}, r_{p_i})$ is the couple quotient-remainder in the division of $f_{p_i}$ by $g_{p_i}$ . Applying coefficient-wise the Chinese Remaindering Algorithm (see course notes) we construct polynomials $f_m$ , $g_m$ , $q_m$ and $r_m$ in ${\mbox{${\mathbb{Z}}$}}/m{\mbox{${\mathbb{Z}}$}}[x]$ such that

$$f_m = g_m q_m + r_m \ \ {\rm and} \ \ {\deg}(r_m) < {\deg}(g_m).$$ (16)

Moreover, the Chinese Remaindering Theorem tells us that we have:

$$f_m = {\Psi}_m(f), g_m = {\Psi}_m(g), q_m = {\Psi}_m(q) \ \ {\rm and} \ \ r_m = {\Psi}_m(r).$$ (17)

Using the preliminary remark, we conclude that $q_m = q$ and $r_m = r$ . This approach is interesting when fast division is available in each ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$ .

To summarize the key ideas for this exercise are:

• $B_f (1 + B_g)^{m-n}$ is an upper bound for (the absolute value of a coefficient in) the quotient
• for designing a modular method that reconstruct both $q$ and $r$ we can use the bound $B_f (1 + B_g)^{m-n+1}$ ; alternatively, we can
  • reconstruct the quotient $q$ only and then use the smaller bound $B_f (1 + B_g)^{m-n}$ ,
  • then, get $r$ as $f - q g$ .
• the modular reconstruction relies on
  • the correct choice of the product $m$ of the primes, which must be greater than twice the bound,
  • the Chinese Remaindering Theorem and Algorithm,
  • the uniqueness of the division-with-remainder by a monic polynomial.