The Hong Kong University of Science and Technology · FACULTY OF MATHEMATICS

MATH2001 Chap.4 Integers and Polynomials

- one subject, every graph, every model, every mark
7 Chapters4-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 4 of 5 · MATH2001

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.

In this chapter

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

Q [10 marks]. AskSia-authored practice. Find the multiplicative inverse of 17 modulo 43 and verify it. The marks shown are an AskSia study allocation, not the University marking scheme.
The alternating boxes show the remainder sequence for two integers, decreasing until the final nonzero remainder gives the greatest common divisor.The alternating boxes show the remainder sequence for two integers, decreasing until the final nonzero remainder gives the greatest common divisor.252198543618Each nonzero remainder is smaller; the last one is the gcd.
The alternating boxes show the remainder sequence for two integers, decreasing until the final nonzero remainder gives the greatest common divisor.
  • 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.
Divide 43 by 17 to get 43=2 times 17+9, then 17=1 times 9+8, and 9=1 times 8+1. Back-substitution gives 1=9-8=9-(17-9)=2 times 9-17=2 times (43-2 times 17)-17=2 times 43-5 times 17. Thus -5 is an inverse of 17 modulo 43, equivalently 38. Verification gives 17 times 38=646, and 646 leaves remainder one after division by 43.
Sia tip — Keep every Euclidean row because the backward pass needs exactly those equations in reverse order.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 13 of your subjects at The Hong Kong University of Science and Technology, plus 1,000+ more Bibles across the AskSia library.
Sia - your MATH2001 tutor, unlimited, worked the way the exam marks it
The full 4-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works