The Real Number System
Real numbers
Use Euclid's division lemma and prime factorisation to find HCF and LCM, and tell a rational number from an irrational one.
Dividing 455 by 42 does not come out exactly. You get 10 whole lots of 42, which is 420, and 35 left over. Euclid's division lemma says that this always happens and always in exactly one way: for any two whole numbers a and b, there is one quotient and one remainder, and the remainder is always smaller than what you divided by.
The lemma
a = bq + r, with r smaller than b. Nothing clever yet — it is the long division you already do, written down carefully enough to build on.
What it builds is a way of finding an HCF without listing a single factor. Divide, then divide the divisor by the remainder, then again, and again. The remainders shrink every time, so the process has to stop. The last remainder before zero is the HCF.
Worked example
Find the HCF of 96 and 404.
404 = 96 × 4 + 20.
Start with the larger number divided by the smaller. The remainder, 20, is what carries on.
The fundamental theorem of arithmetic
Every whole number bigger than 1 is a product of primes, in exactly one way apart from the order. 360 is 2³ × 3² × 5 and it is nothing else. That uniqueness is what makes HCF and LCM by prime factorisation work at all.
Try it together
Let us find the HCF of 867 and 255 by Euclid's algorithm.
Divide, take the remainder, divide again. Three lines is all it takes here.
1.Divide 867 by 255. What is the remainder?
Have a play
Move along this line between 1 and 2, a tenth at a time. Every tick you land on is a fraction — a whole number over a whole number.
Tap anywhere on the line.
Have a go
Have a go on your own: find the HCF of 135 and 225 using Euclid's algorithm.
Hint: 225 = 135 × 1 + 90 gets you started.
Ready to practice?
Eight questions on what you have just read. Nothing is timed, and you can play as many times as you like.