Exercise 3.

Let a and b be two univariate polynomials in $\mbox{${\mathbb Z}$}$[x]. We assume that b is monic and has degree n > 0 and that a has degree n + k whith k $\geq$ 0. We define a = a_n+kx^n+k + ^... + a_nxⁿ + ^... + a₁x + a₀ and b = b_nxⁿ + ^... + b₁x + b₀. We are interesting in computing the remainder r of the Euclidean division of a by b (regarding them as polynomials in $\mbox{${\mathbb Q}$}$[x]), by a modular method. Let p be a prime number and $\Phi_{{p}}^{{}}$ be the application that maps every integer z with its residue class $\Phi_{{p}}^{{}}$(z) in $\mbox{${\mathbb Z}$}$/p$\mbox{${\mathbb Z}$}$. We extend this application to a map denoted $\Phi_{{p}}^{{}}$ again, from $\mbox{${\mathbb Z}$}$[x] to $\mbox{${\mathbb Z}$}$/p$\mbox{${\mathbb Z}$}$[x], such that x is mapped to x.

1. Explain why the remainder r belongs to $\mbox{${\mathbb Z}$}$[x], that is no fractions appears during the computations.
2. Consider a = x² + 7x + 1 and b = x + 4. Compute q and r.
3. Consider p = 3. Compute $\Phi_{{p}}^{{}}$(a) and $\Phi_{{p}}^{{}}$(b). Then compute the quotient and the remainder of $\Phi_{{p}}^{{}}$(a) by $\Phi_{{p}}^{{}}$(b).
4. In the general case, what is the relation between r and the remainder of $\Phi_{{p}}^{{}}$(a) by $\Phi_{{p}}^{{}}$(b)?
5. Design a modular method to compute r.

Answer 4  

Answer 5