#### Exercise 3.

Let and be two univariate polynomials in . We assume that is monic and has degree and that has degree whith . We define and . We are interesting in computing the remainder of the Euclidean division of by (regarding them as polynomials in ), by a modular method. Let be a prime number and be the application that maps every integer with its residue class in . We extend this application to a map denoted again, from to , such that is mapped to .
1. Explain why the remainder belongs to , that is no fractions appears during the computations.
2. Consider and . Compute and .
3. Consider . Compute and . Then compute the quotient and the remainder of by .
4. In the general case, what is the relation between and the remainder of by ?
5. Design a modular method to compute .