Use the Euclidean algorithm to find a highest common factor of the polynomials

and express this highest common factor as a polynomial linear combination of $f(X)$ and $g(X)$.

As in the example considered before the proof of Theorem 4.6.5 in Appendix A, let $A=\{1,5,9,13,\dots\}$ be the set of all natural numbers of the form $4m+1$, and define a ‘‘prime number in $A$’’ to be an element of $A$ greater than $1$ whose only divisors in $A$ are $1$ and itself. Which is the smallest element of $A$ greater than $1$ which is not prime in $A$?

Apply the Self-Explanation strategy from Appendix C to the proof of the Fundamental Theorem of Arithmetic (Theorem 4.6.5) as it is given in Appendix A.

Use the Euclidean algorithm to find a highest common factor of the polynomials

and express this highest common factor as a polynomial linear combination of $h(X)$ and $k(X)$.

(Euclid’s Lemma for polynomials) Let $f(X)$, $g(X)$ and $h(X)$ be non-zero polynomials, and suppose that $1$ is a highest common factor of $f(X)$ and $g(X)$ and that $f(X)$ divides $g(X)h(X)$. Prove that $f(X)$ divides $h(X)$.

[Hint: imitate the proof of Theorem 4.4.8 in the notes.]

Give an alternative proof of the existence part of Theorem 7.1.10, using proof by contradiction instead of induction. The idea is as follows: the case where $g(X)$ divides $f(X)$ is easy, so we may suppose that $g(X)$ does not divide $f(X)$. Then the set

does not contain $0$. Take a polynomial $r(X)\in S$ of smallest degree (after checking that $S$ is not empty), and use Lemma 7.1.9 to see that the assumption $\deg r(X)\geqslant\deg g(X)$ leads to a contradiction.