← 2017 Paper 2

UPSC 2017 Maths Optional Paper 2 Q2c — Step-by-Step Solution

20 marks · Section A

Euclidean domains · Algebra · asked 6× in 14 yrs · Read the full method →

Question

Let $F$ be a field and $F[X]$ denote the ring of polynomials over $F$ in a single variable $X$. For $f(X),g(X)\in F[X]$ with $g(X)\ne0$, show that there exist $q(X),r(X)\in F[X]$ such that $\deg(r(X))<\deg(g(X))$ and $f(X)=q(X)\cdot g(X)+r(X)$.

(Convention: $\deg 0=-\infty$, so the inequality $\deg r<\deg g$ also covers the case $r=0$.)

Technique

Strong induction on $\deg f$; each step subtracts $a_n b_m^{-1}X^{n-m}g$ to cancel the leading term (this is polynomial long division). Field $\Rightarrow$ $b_m^{-1}$ exists; domain $\Rightarrow$ degree additive (for uniqueness).

Solution

We prove existence of the quotient $q$ and remainder $r$ (the question asks only for existence; we add uniqueness as a bonus). The field hypothesis is used to divide by the leading coefficient of $g$, which is the one place invertibility is needed.

Step 1 — Set up; trivial case

Let $g(X)=b_mX^m+\cdots+b_0$ with leading coefficient $b_m\ne0$, so $\deg g=m\ge0$ and $b_m$ is invertible in $F$ (field).

If $f=0$, take $q=r=0$: then $\deg r=-\infty<\deg g$ and $f=q g+r$. Likewise if $\deg f<\deg g$, take $q=0,\ r=f$; then $\deg r=\deg f<\deg g$ and $f=0\cdot g+f$. Both satisfy the requirement, so assume henceforth $f\ne0$ and $\deg f\ge\deg g$.

Step 2 — Existence by strong induction on $\deg f$

We argue by strong induction on $n=\deg f\ (\ge m)$.

Inductive construction (one reduction step). Let $f(X)=a_nX^n+\cdots+a_0$ with $a_n\ne0$, $n\ge m$. Define the “leading-term cancelling” polynomial

This uses $b_m^{-1}\in F$, available because $F$ is a field. The term of degree $n$ in $q_1 g$ is $(a_n b_m^{-1}X^{n-m})(b_mX^m)=a_nX^n$, which exactly cancels the leading term of $f$. Hence

Base / induction hypothesis. Apply the statement to $f_1$, which has strictly smaller degree:

• If $\deg f_1<m=\deg g$, we are done in one step: $f=q_1 g+f_1$ with remainder $r=f_1$, $\deg r<\deg g$.
• Otherwise $\deg f_1\ge m$; by the strong induction hypothesis (degree strictly less than $n$) there exist $q_2,r\in F[X]$ with

Substitute back:

Set $q=q_1+q_2$. Then $f=qg+r$ with $\deg r<\deg g$. This completes the induction, establishing existence for all $f$.

Answer