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+k} x^{n+k} + \cdots + a_n x^n + \cdots + a_1 x + a_0$ and $b = b_n x^n + \cdots + b_1 x + b_0$ . 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^2 + 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