MATH2001 Chap.4 Integers and Polynomials
Integers and Polynomials
Division creates a decreasing remainder
The integer division algorithm writes a as qb plus r with the remainder between zero and the positive divisor. Polynomial division over a field uses the same pattern, replacing numeric size by degree. Repeated division produces the Euclidean algorithm. Termination follows because the remainder size or degree decreases through nonnegative integers.
That explicit decreasing measure belongs in a rigorous explanation.
The invariant identifies the gcd
From a equals qb plus r, the common divisors of a and b are exactly the common divisors of b and r. This invariant justifies every Euclidean row and makes the last nonzero remainder a greatest common divisor.
Back-substitution reverses the stored equations and expresses the gcd as a linear combination of the original inputs. The result is a Bezout identity, which produces modular inverses when the gcd is one.
Polynomials repeat the method with new normalization
Over a coefficient field, polynomial leading coefficients can be divided, so Euclid works with degree as the descent measure.
A polynomial gcd is unique only up to a nonzero scalar, and the monic convention selects one version. Irreducible polynomials play the role of primes. Bezout identities then prove that quotienting by an irreducible polynomial produces a field, while the factor theorem connects roots, divisibility and quotient classes.
What this chapter covers
- 01
Integer division algorithm
- 02
Euclidean remainder descent
- 03
Greatest common divisors
- 04
Bezout back-substitution
- 05
Polynomial division
- 06
Irreducibility and factors
- 07
Quotient fields and rational functions
Worked example · free
Find an inverse with Euclid
- 3Run the Euclidean algorithm until the last nonzero remainder.
- 4Back-substitute to express one as a combination of 17 and 43.
- 3Read the coefficient of 17 modulo 43 and verify the product.
Key terms
- Division Algorithm
- The unique quotient-remainder decomposition with a remainder strictly smaller than the divisor in the stated measure.
- Euclidean Algorithm
- Repeated division that preserves common divisors while reducing the remainder until zero is reached.
- Greatest Common Divisor
- A normalized common divisor divisible by every other common divisor of the inputs.
- Bezout Identity
- A formula expressing a greatest common divisor as a linear combination of the original inputs.
- Monic Polynomial
- A polynomial whose leading coefficient is one, used to normalize a polynomial gcd.
- Irreducible Polynomial
- A polynomial that has no factorization into lower-degree nonunits over the announced coefficient field.
- Quotient Field
- A field formed from polynomial classes when the modulus is irreducible over the coefficient field.
Integers and Polynomials FAQ
Why does the Euclidean algorithm stop?
Each nonzero integer remainder is smaller than the preceding positive divisor, so the process gives a strictly decreasing sequence of nonnegative integers. For polynomials, nonzero remainder degrees strictly decrease. Neither kind of sequence can continue indefinitely, so a zero remainder is eventually reached.
Why is a polynomial gcd made monic?
Multiplying a polynomial gcd by any nonzero field scalar leaves the same divisibility information, so without normalization there are many associates. Requiring leading coefficient one selects a unique representative. State this convention when reporting the gcd, especially after a Euclidean calculation produces another scalar multiple.
How does Bezout give a modular inverse?
If gcd(a,n) is one, back-substitution gives ua+vn=1. Reducing this equality modulo n removes the vn term and leaves ua congruent to one. Thus the residue class of u is the inverse of the residue class of a. Verify by multiplying and reducing the remainder.
Exam move
Practise Euclid in two visibly separated passes. During the forward pass, write quotient and remainder equations and check the remainder condition. Circle the last nonzero remainder. During the backward pass, substitute one equation at a time and collect coefficients only after each replacement. For polynomial problems, annotate the coefficient field and degree at every row.
Finish with two independent checks: the gcd divides the inputs, and the final linear combination evaluates to the claimed gcd. Maintain a remainder ledger containing the dividend, divisor, quotient and remainder on every line. Beside each row, record the decreasing measure that guarantees termination. When normalizing a polynomial gcd, separate the Euclidean calculation from the final monic rescaling.
For modular inverse questions, substitute the Bezout coefficients back into the congruence before declaring the inverse, since a sign or coefficient error is then immediately visible.
Working through Integers and Polynomials in MATH2001? Sia is AskSia’s AI Mathematics tutor — ask any MATH2001 Integers and Polynomials question and get a clear, step-by-step explanation grounded in how MATH2001 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.