Real Numbers: Euclid's Algorithm, HCF, LCM and Irrationality Proofs
Real Numbers is where the paper tests Euclid's division algorithm, prime factorisation, HCF/LCM and irrationality proofs. Expect a 1-mark question on terminating decimals and a 2–3 mark HCF/LCM or proof question.
Euclid's division lemma
For positive integers a and b, a = bq + r with 0 ≤ r < b. Repeatedly replace (a, b) by (b, r) until r = 0; the last non-zero divisor is HCF(a, b).
Fundamental Theorem of Arithmetic
Every composite number has a unique prime factorisation. For two numbers, HCF is the product of the smallest power of each common prime; LCM is the product of the highest power of every prime that appears. For two numbers only, HCF × LCM = a × b.
Worked example
HCF and LCM of 96 and 404. 404 = 96 × 4 + 20; 96 = 20 × 4 + 16; 20 = 16 × 1 + 4; 16 = 4 × 4 + 0, so HCF = 4. LCM = (96 × 404)/4 = 9696.
Irrationality
To prove √2 irrational, assume √2 = a/b in lowest terms, so a and b are coprime. Then 2b² = a², so 2 divides a², hence 2 divides a. Writing a = 2c gives b² = 2c², so 2 divides b - contradicting that a, b are coprime. The same argument works for √3 and √5.
Traps that cost marks
- HCF × LCM = product fails for three numbers; it is a two-number result.
- A rational p/q in lowest terms has a terminating decimal only if q = 2^m·5^n.
- In the contradiction proof you must state that a and b are coprime - that is the source of the contradiction.
- If the question asks for HCF, do not stop after computing LCM.