Exercise 3.

Let $m \in {\mbox{${\mathbb{Q}}$}}[x]$ be a non-constant polynomial of degree $n$ . Let $R = Q[x] / \langle m \rangle$ be the set of the residue classes modulo $m$ .

1.

Let $p \in {\mbox{${\mathbb{Q}}$}}[x]$ be a polynomial. How many elements are there in the residue class $\overline{p}$ of $p$ modulo $m$ with degree less than $n$ ?

2.

Explain why we can view each element of $R$ as a vector of $n$ coordinates in ${\mbox{${\mathbb{Q}}$}}$ .

Given two polynomial $c$ and $a$ in ${\mbox{${\mathbb{Q}}$}}[x]$ we want to decide whether there exists a polynomial $f$ such that we have $c \equiv a f \ \mod{ m}$ . For instance, with $m = x^3 - 1$ , $c = x - 1$ and $a = x^2 - 1$ , one solution is $f = x^2 + 1$ . Indeed, we have $(x^2 + 1)(x^2 - 1) = x^4 - 1 \equiv x - 1 \mod{x^3 - 1}$ . (Working modulo $x^3 - 1$ means replacing every occurrence of $x^3$ by $1$ .)

3.

Assume first that ${\gcd}(a,m) = 1$ . Explain why such a polynomial $f$ exists and is unique.

4.

Now, assume that ${\gcd}(a,m) = g$ where $g$ is a non-constant polynomial. Indicate briefly a strategy for solving our problem in this case.

5.

Solve our problem for the particular $m = x^3 - 1$ , $c = x - 1$ and $a = x^2 + 1$ .