Class 10 Mathematics: Board Exam Revision · lesson 1 of 8

Real numbers and Euclid's division lemma

About 40 minutes

Why this matters

Real numbers open the board paper. Every year there is a one-mark question on HCF or LCM, a two-mark question on Euclid's lemma or the fundamental theorem of arithmetic, and often a three-mark proof that a number like √2 is irrational. Together this chapter is worth about six marks, and the marks are easy once the two ideas below are clear.

The idea

Euclid's division lemma is a precise way of saying what you already do when you divide. The lemma states that for any two positive integers a and b, there exist unique whole numbers q and r such that a = bq + r, where 0 ≤ r < b. The quotient is the number q, which tells how many times b fits into a. The remainder is the number r, which is what is left over and is always smaller than b.

The HCF is the highest common factor, the largest number that divides both of two given numbers exactly. Euclid's algorithm finds the HCF by repeating the lemma: divide the larger number by the smaller, then divide the smaller by the remainder, and continue until the remainder becomes zero. The last non-zero remainder is the HCF.

The fundamental theorem of arithmetic says that every composite number can be written as a product of primes in exactly one way, apart from the order of the factors. A prime number is a number greater than 1 whose only factors are 1 and itself. A composite number is a number greater than 1 that has a factor other than 1 and itself.

Two useful facts follow. The LCM is the lowest common multiple, the smallest number that both given numbers divide into. For any two positive integers, HCF × LCM = product of the two numbers. An irrational number is a number that cannot be written as p ÷ q with integers p and q.

Worked examples

Example 1: HCF by Euclid's algorithm

Find the HCF of 135 and 225.

  1. Divide the larger by the smaller: 225 = 135 × 1 + 90.
  2. Now divide 135 by 90: 135 = 90 × 1 + 45.
  3. Now divide 90 by 45: 90 = 45 × 2 + 0.
  4. The remainder is zero, so stop. The last non-zero remainder was 45.

Answer: HCF(135, 225) = 45.

Example 2: LCM from the HCF

Find the LCM of 135 and 225 without listing multiples.

  1. From Example 1, HCF = 45.
  2. Product of the numbers: 135 × 225 = 30375.
  3. LCM = product ÷ HCF = 30375 ÷ 45 = 675.

Answer: LCM(135, 225) = 675. Check: 675 = 135 × 5 = 225 × 3.

Example 3: Is this number composite?

Show that 7 × 11 × 13 + 13 is a composite number.

  1. Both terms contain 13, so take it out: 13 × (7 × 11 + 1).
  2. Inside the bracket, 7 × 11 + 1 = 78.
  3. So the number equals 13 × 78, a product of two numbers greater than 1.

Answer: It is composite, because 13 divides it and 13 is neither 1 nor the number itself.

Example 4: Proving √2 is irrational

  1. Suppose √2 = p ÷ q where p and q are integers with no common factor and q is not zero.
  2. Squaring gives 2q² = p², so p² is even, which means p is even. Write p = 2m.
  3. Then 2q² = 4m², so q² = 2m², which means q is also even.
  4. Both p and q are even, so they share the factor 2. That contradicts our assumption.

Answer: The assumption was false, so √2 is irrational.

Common mistakes

  • Stopping the algorithm one step early and reporting the last divisor instead of the last non-zero remainder. Keep dividing until the remainder is exactly zero.
  • Writing r ≤ b instead of 0 ≤ r < b in the statement of the lemma. The remainder must be strictly smaller than the divisor.
  • Trying to find the LCM by listing multiples of large numbers. Use HCF × LCM = product of the numbers; it is faster and less error-prone.
  • Forgetting to state "p and q have no common factor" in the irrationality proof. Without it there is no contradiction to reach.

Try it yourself

  1. Use Euclid's algorithm to find the HCF of 96 and 404.
  2. The HCF of two numbers is 6 and their product is 1152. Find their LCM.
  3. Show that 5 × 7 × 11 + 7 is composite.

Answers: 1. 404 = 96 × 4 + 20, 96 = 20 × 4 + 16, 20 = 16 × 1 + 4, 16 = 4 × 4 + 0, so the HCF is 4. 2. LCM = 1152 ÷ 6 = 192. 3. Take out 7: 7 × (55 + 1) = 7 × 56, so it is composite.

Quiz

Five questions built from this lesson. Start at Core; the level adapts to your score.

Flashcards

Turn the key terms of this lesson into cards that come back just before you forget them.