Scribd
Upload
21 views2 pages

Division Algorithm For Polynomials

The document presents the Division Algorithm for Polynomials, stating that for polynomials f(x) and g(x) (with g(x) ≠ 0), there exist unique polynomials q(x) and r(x) such that f(x) = q(x)g(x) + r(x), where r(x) is either 0 or has a degree less than that of g(x). The proof is divided into two parts: existence, which uses induction on the degree of f(x), and uniqueness, which shows that if two pairs of (q, r) exist, they must be equal. The conclusion confirms the existence of unique polynomials q(x) and r(x) satisfying the division condition.

Uploaded by

Basit Rasool
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views2 pages

Division Algorithm For Polynomials

The document presents the Division Algorithm for Polynomials, stating that for polynomials f(x) and g(x) (with g(x) ≠ 0), there exist unique polynomials q(x) and r(x) such that f(x) = q(x)g(x) + r(x), where r(x) is either 0 or has a degree less than that of g(x). The proof is divided into two parts: existence, which uses induction on the degree of f(x), and uniqueness, which shows that if two pairs of (q, r) exist, they must be equal. The conclusion confirms the existence of unique polynomials q(x) and r(x) satisfying the division condition.

Uploaded by

Basit Rasool
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Proof of the Division Algorithm for Polynomials

Theorem (Division Algorithm for Polynomials)


Let f (x) and g(x) be polynomials over a field F , with g(x) ̸= 0. Then there
exist unique polynomials q(x) and r(x) in F [x] such that:

f (x) = q(x)g(x) + r(x)

where either r(x) = 0 or deg(r) < deg(g).

Proof
We prove the theorem in two parts: existence and uniqueness.

Part A: Existence
We use induction on the degree of f (x). Let deg(f (x)) = n and deg(g(x)) = m.
Base Case: If deg(f ) < deg(g), then we can take q(x) = 0 and r(x) = f (x).
Clearly,
f (x) = 0 · g(x) + f (x)
and deg(r) < deg(g), so the condition is satisfied.
Inductive Step: Assume the result is true for all polynomials of degree less
than n. Suppose deg(f (x)) = n ≥ m = deg(g(x)).
Let the leading term of f (x) be an xn , and the leading term of g(x) be bm xm .
Since F is a field, bm ̸= 0, so bamn ∈ F .
Let:
an n−m
s(x) = x
bm
Now define:
f1 (x) = f (x) − s(x)g(x)
Then deg(f1 ) < deg(f ). By the inductive hypothesis, there exist polynomials
q1 (x) and r(x) such that:

f1 (x) = q1 (x)g(x) + r(x), with deg(r) < deg(g)

1
Therefore,

f (x) = s(x)g(x) + f1 (x)


= s(x)g(x) + q1 (x)g(x) + r(x)
= (s(x) + q1 (x))g(x) + r(x)

Let q(x) = s(x) + q1 (x). Then:

f (x) = q(x)g(x) + r(x), with deg(r) < deg(g)

Hence, existence is proved.

Part B: Uniqueness
Suppose there are two pairs (q1 (x), r1 (x)) and (q2 (x), r2 (x)) such that:

f (x) = q1 (x)g(x) + r1 (x) = q2 (x)g(x) + r2 (x)

Subtracting both expressions:

(q1 (x) − q2 (x))g(x) = r2 (x) − r1 (x)

Let d(x) = q1 (x) − q2 (x) and s(x) = r2 (x) − r1 (x). Then:

d(x)g(x) = s(x)

Now: - If d(x) ̸= 0, then deg(d(x)g(x)) ≥ deg(g(x)) - But deg(s(x)) <


deg(g(x)), since both r1 and r2 are remainders
This contradiction implies d(x) = 0, so q1 (x) = q2 (x), and hence r1 (x) =
r2 (x)

Conclusion
There exist unique polynomials q(x) and r(x) such that:

f (x) = q(x)g(x) + r(x), where deg(r) < deg(g)

You might also like