Chapter 1.2 — Exercise 1.1 — Division Lemma Problems

Three HCF Pairs, Worked Through

The first question asks for the HCF of three pairs using the division algorithm: divide the larger number by the smaller, then keep dividing the previous divisor by the newest remainder until a remainder of 0 appears.

The middle pair is the one worth pausing on: 38220 divides by 196 exactly, with no remainder at all, on the very first step. Whenever that happens — one number is simply a multiple of the other — the smaller number is the HCF, and there is nothing further to compute. Always check for this before grinding through several rounds of division.

The Core Trick: Check Every Remainder Once

The rest of the exercise proves statements about every positive integer using a single idea. Let a be any positive integer and pick a small divisor b. By the Division Lemma, a = bq + r for some r with 0 ≤ r < b — and since b is small, there are only finitely many values r can take. Instead of checking infinitely many integers a, you only need to check the finitely many possible remainders. Whatever you can prove for each remainder in turn, you have proved for every positive integer.

Even and Odd, from First Principles

Take b = 2. The Division Lemma gives a = 2q + r with r equal to 0 or 1 — no other value is possible.

• If r = 0, then a = 2q, which is an even integer by definition.
• If r = 1, then a = 2q + 1, which is an odd integer by definition.

Since 0 and 1 are the only remainders b = 2 allows, every positive integer must fall into one of these two forms — proving that every even integer is of the form 2q and every odd integer is of the form 2q + 1, with nothing left over.

Sharpening the Same Idea: Divide by 4

The same approach, with b = 4 instead of b = 2, proves a more specific result about odd integers. Here a = 4q + r with r taking values 0, 1, 2, or 3.

• r = 0: a = 4q = 2(2q) — even.
• r = 1: a = 4q + 1 = 2(2q) + 1 — odd.
• r = 2: a = 4q + 2 = 2(2q+1) — even.
• r = 3: a = 4q + 3 = 2(2q+1) + 1 — odd.

Only r = 1 and r = 3 produce odd integers, so every positive odd integer is of the form 4q + 1 or 4q + 3 — a tighter classification than "2q + 1" alone, and one that resurfaces whenever a proof needs odd numbers split into two distinct families rather than one.

Odd Integers, Split Three Ways

Question 2 pushes the divisor further, to b = 6, giving six possible remainders: 0 through 5.

Substituting each remainder shows r = 0, 2, 4 always give an even integer (each simplifies to 2 times a whole number), while r = 1, 3, 5 always give an odd one. So every positive odd integer must be of the form 6q + 1, 6q + 3, or 6q + 5 — three families instead of two, because a divisor of 6 splits the remainders more finely than a divisor of 4 does.

What Happens to a Square

Question 3 asks about squares rather than the integers themselves. Take b = 3, so a = 3q + r with r equal to 0, 1, or 2, and look at what a² becomes in each case.

• r = 0: a = 3q, so a² = 9q² = 3(3q²) — of the form 3p.
• r = 1: a = 3q+1, so a² = 9q²+6q+1 = 3(3q²+2q)+1 — of the form 3p + 1.
• r = 2: a = 3q+2, so a² = 9q²+12q+4 = 3(3q²+4q+1)+1 — again of the form 3p + 1.

The form 3p + 2 never appears anywhere in this list — which is exactly the claim being proved. The square of any positive integer is always 3p or 3p + 1, never anything else.

The Same Idea, One Power Higher

Question 4 repeats the b = 3 split, but cubes each form instead of squaring it. Expanding carefully and pulling out a common factor of 9 at each step:

• a = 3q: a³ = 27q³ = 9(3q³) — the form 9m.
• a = 3q+1: a³ = 27q³+27q²+9q+1 = 9(3q³+3q²+q)+1 — the form 9m + 1.
• a = 3q+2: a³ = 27q³+54q²+36q+8 = 9(3q³+6q²+4q)+8 — the form 9m + 8.

The algebra here is the heaviest in the exercise — the step most worth double-checking is factoring 9 cleanly out of all three terms after expanding, rather than stopping partway and mislabelling the remainder.

One in Three, Always

The final question asks about three numbers at once: n, n+2, and n+4. Dividing n by 3 gives a remainder of 0, 1, or 2, and checking all three numbers against each remainder shows that exactly one of the three is always a multiple of 3, regardless of which case holds.

Because every positive integer n falls into exactly one of these three rows, exactly one of n, n+2, n+4 is divisible by 3 — never zero of them, and never more than one.

Choosing the Right Divisor

Every proof in this exercise starts with the same decision: which divisor b to plug into a = bq + r. That choice isn't arbitrary — it's dictated entirely by what the question is asking you to show.

A larger divisor always gives more remainders to check, but a finer classification in return — b = 6 splits odd integers into three separate families instead of the two that b = 4 gives, simply because 6 allows more possible remainders than 4 does. There's no shortcut around checking every single remainder, either: skipping even one case leaves a genuine gap in the proof, since that missing remainder could in principle produce a result outside the pattern claimed for all the others.

Carrying This Forward

Every proof in this exercise follows the same shape: pick a divisor, list its possible remainders, and check each one. Exercise 1.2 takes a different route to some of the same destinations — using prime factorisation instead of remainders to study HCF and LCM — while the remainder-checking technique itself returns directly in Exercise 1.4, where it becomes the engine behind proving numbers like √2 are irrational. If the Division Lemma itself needs a refresher first, see the chapter introduction.