Chapter 1.1 — Introduction — Euclid's Division Lemma

Five Nested Families

Each set of numbers below sits inside the next — every natural number is a whole number, every whole number is an integer, and so on, until you reach the real numbers, which contain everything.

Notice that Q and Q′ never overlap — a number is either expressible as a fraction of two integers or it isn't, never both — yet together they fill up R completely. That "either/or" split is exactly what makes the irrationality proofs later in this chapter work: showing a number cannot be written as p/q is enough, by itself, to place it firmly in Q′.

It's also worth flagging a common classification slip here: something that looks irrational because it has a root sign, such as √4 or √9, may simplify to a whole number (√4 = 2, √9 = 3) and so is actually rational. Always simplify a root before deciding which set it belongs to.

An Ancient Idea About Division

The central tool of this chapter comes from Euclid, the Greek mathematician whose thirteen-book work Elements laid out much of classical geometry and number theory. Book VII contains a short, almost obvious-looking statement about division that later mathematicians built an entire branch of number theory on top of — it is often called the foundation of the fundamentals of number theory.

Here a is the dividend, b the divisor, q the quotient, and r the remainder. The real content of the lemma is the condition on r: whatever remainder you get from dividing one positive integer by another, it is always smaller than the divisor and never negative. That sounds like common sense from ordinary long division — Euclid's contribution was proving it holds without exception, for every possible pair of positive integers, not just the ones that happen to divide neatly.

Reading the Lemma in an Ordinary Division

Two worked divisions make the abstract statement concrete. Dividing 13 by 3 gives a quotient of 4 with remainder 1:

and dividing 34 by 9 gives quotient 3 with remainder 7:

In both cases the remainder — 1 and 7 — is smaller than the divisor — 3 and 9 — exactly the condition 0 ≤ r < b demands. This is the same long division you already know how to do; the lemma is simply the guarantee that this pattern, quotient times divisor plus a remainder strictly smaller than the divisor, never breaks down for any pair of positive integers you might choose.

Turning the Lemma Into an Algorithm

Apply the lemma once and you split one division into a quotient and a remainder. Apply it repeatedly — dividing the old divisor by the new remainder, again and again — and you get a fast, purely arithmetic way to find the Highest Common Factor (HCF) of two numbers: the largest positive integer that divides both exactly. This repeated process is called Euclid's Division Algorithm.

Take 100 and 60. Divide the larger by the smaller, then keep dividing the previous divisor by the newest remainder, until the remainder finally reaches zero:

• 100 = 60 × 1 + 40 — remainder 40, so divide 60 by 40 next
• 60 = 40 × 1 + 20 — remainder 20, so divide 40 by 20 next
• 40 = 20 × 2 + 0 — remainder 0, so the algorithm stops here

The last divisor used before the remainder hit zero was 20 — so HCF(100, 60) = 20. You can sanity-check the method against a smaller pair by listing factors directly: 8 and 12 have factors {1, 2, 4, 8} and {1, 2, 3, 4, 6, 12}, and their highest shared factor is 4 — exactly what the same repeated-division process produces (12 = 8×1+4, then 8 = 4×2+0, so HCF = 4). For small numbers either method works fine; for large ones, the algorithm is far faster than listing every factor by hand.

Why does the algorithm always finish? Each new remainder is strictly smaller than the one before it, and no remainder can ever be negative. A sequence of whole numbers that keeps shrinking but can never go below zero has nowhere to go except zero itself — so after finitely many steps, it must land there. That is the whole reason Euclid's Division Algorithm is guaranteed to terminate, for any starting pair of positive integers, however large.

Four HCF Pairs to Try

The same pattern — divide, take the remainder as the new divisor, repeat until the remainder is 0 — works identically on any pair of positive integers, however large:

Notice how quickly the algorithm finishes even for four-digit numbers like 1860 and 2015 — just two division steps. That speed is precisely why Euclid's Division Algorithm, rather than factor-listing, is the standard method for finding HCF once the numbers involved get large.

A Small but Important Detail

One detail trips up first attempts at this algorithm: the HCF is the divisor at the step where the remainder first becomes 0 — not the remainder from the step before that. In the 100-and-60 example above, the remainder sequence was 40, then 20, then 0; the HCF is 20 (the divisor in the last step), not 40. It's also conventional, though not strictly required, to start by dividing the larger number by the smaller — dividing the smaller by the larger first just wastes one step, since the "quotient" would be 0 and the "remainder" would be the smaller number itself, sending you right back to the same division you'd have started with anyway.

Where the Algorithm Leads

Euclid's Division Lemma does more than compute HCFs. Exercise 1.1 uses the same a = bq + r idea to prove general statements about whole families of integers — for instance, that the square of any positive integer is always of the form 3p or 3p + 1, with no other possibility. Exercise 1.2 then switches from division to multiplication, using prime factorisation to find HCF and LCM a second, often faster way, and that same factorisation approach reappears in Exercise 1.3, where a denominator's prime factors decide whether its decimal terminates. The chapter closes with Exercise 1.4's irrationality proofs and Exercise 1.5 on logarithms. If you would like a refresher on where rational and irrational numbers were first introduced, Class 9's Real Numbers chapter covers the groundwork this chapter builds on.