CBSE Class 10 Mathematics Real Numbers Notes Set 08

Euclid's Division Lemma

Real numbers are the numbers that can represent actual physical quantities in a meaningful way. They can be shown on the number line, a geometrical straight line with an arbitrarily chosen zero (origin), and include all rational and irrational numbers.

Prime numbers: Natural numbers that have exactly two factors, 1 and the number itself, for example 2, 3, 5, 7, 11, 13, 17, 19, 23. Composite numbers: Natural numbers having more than two distinct factors. Note that 1 is neither prime nor composite.

Co-prime numbers: Numbers whose H.C.F. is 1 (the numbers themselves need not be prime), for example 4 and 9, as H.C.F.(4, 9) = 1. Any two consecutive numbers are always co-prime, and any two distinct prime numbers are always co-prime.

Divisibility

A non-zero integer b is said to divide an integer a if there is an integer q such that a = bq. The integer a is called the dividend, b the divisor and q the quotient. For example, 5 divides 35 because 35 = 5 × 7. If b divides a we write b | a (read as 'b divides a'); if b does not divide a we write b ∤ a.

Lemma and Statement of Euclid's Division Lemma

A lemma is a proven statement used to prove another statement or theorem.

Euclid's Division Lemma: Let a and b be any two positive integers. Then there exist unique integers q and r such that \( a = bq + r \), where \( 0 \le r < b \). If b | a, then r = 0. This can be restated as: Dividend = Divisor × Quotient + Remainder.

Note: In the division lemma, q or r may be 0, but r is always less than b.

Solved Examples on Euclid's Division Lemma

Example 1. Prove that any positive odd integer can be written in the form 4q + 1 or 4q + 3, where q is an integer.
Answer:
Let a be any positive odd integer. Taking 4 as the divisor, the division lemma gives \( a = 4q + r \), where \( 0 \le r < 4 \).
Putting r = 0, 1, 2, 3 we get \( a = 4q \), \( a = 4q+1 \), \( a = 4q+2 \), \( a = 4q+3 \).
The forms 4q and 4q + 2 give only even numbers. Since a is odd, it must be of the form \( 4q + 1 \) or \( 4q + 3 \).

Example 2. Prove that the square of any positive integer of the form 5q + 1 is of the same form.
Answer:
Let x = 5q + 1. Then \( x^2 = 25q^2 + 10q + 1 = 5q(5q + 2) + 1 \).
Let m = q(5q + 2). Then \( x^2 = 5m + 1 \), which is of the same form 5m + 1.

Example 3. Show that one and only one out of n, n + 2 or n + 4 is divisible by 3, where n is any positive integer.
Answer:
Let n = 3q + r, where \( 0 \le r < 3 \).
Case I (r = 0): n = 3q is divisible by 3. Then \( n+2 = 3q+2 \) leaves remainder 2 and \( n+4 = 3q+4 = 3(q+1)+1 \) leaves remainder 1, so neither is divisible by 3.
Case II (r = 1): n = 3q + 1. Then \( n+2 = 3q+3 = 3(q+1) \) is divisible by 3, while n leaves remainder 1 and \( n+4 = 3q+5 = 3(q+1)+2 \) leaves remainder 2.
Case III (r = 2): n = 3q + 2. Then \( n+4 = 3q+6 = 3(q+2) \) is divisible by 3, while n leaves remainder 2 and \( n+2 = 3q+4 = 3(q+1)+1 \) leaves remainder 1.
So exactly one of n, n + 2, n + 4 is divisible by 3.

Example 4. Use Euclid's division lemma to show that the cube of any positive integer is of the form 9m, 9m + 1 or 9m + 8, for some integer m.
Answer:
Any positive integer x is of the form 3q, 3q + 1 or 3q + 2.
Case I: \( x^3 = (3q)^3 = 27q^3 = 9(3q^3) = 9m \), where \( m = 3q^3 \).
Case II: \( x^3 = (3q+1)^3 = 27q^3 + 27q^2 + 9q + 1 = 9(3q^3 + 3q^2 + q) + 1 = 9m + 1 \), where \( m = 3q^3 + 3q^2 + q \).
Case III: \( x^3 = (3q+2)^3 = 27q^3 + 54q^2 + 36q + 8 = 9(3q^3 + 6q^2 + 4q) + 8 = 9m + 8 \), where \( m = 3q^3 + 6q^2 + 4q \).
Hence the cube of any positive integer is of the form 9m, 9m + 1 or 9m + 8.

Check Your Progress: Euclid's Division Lemma

Check Your Progress 1. Let a and b be any two positive integers. Then there exist unique integers q and r such that a = bq + r. If b = 5, find the possible values of r.
Answer:
Since \( 0 \le r < 5 \), the possible values are r = 0, 1, 2, 3, 4.

Check Your Progress 2. Check whether the number 21q + 18 is of the form 7q + 4, for some integer q.
Answer:
\( 21q + 18 = 7(3q + 2) + 4 \). With \( m = 3q+2 \) this is \( 7m + 4 \), so yes, it is of the form 7m + 4.

Check Your Progress 3. If n = 3q + 2, then check whether n + 7 is divisible by 3, for some integer q.
Answer:
\( n + 7 = 3q + 9 = 3(q + 3) \), so yes, it is divisible by 3.

Check Your Progress 4. If n = 5q + 4, then check whether n² − 1 is divisible by 5, for some integer q.
Answer:
\( n^2 - 1 = (n-1)(n+1) = (5q+3)(5q+5) = 5(5q+3)(q+1) \), so yes, it is divisible by 5.

Check Your Progress 5. Show that the cube of a number of the form 4q + 3 is of the form 4q + 3, for some integer q.
Answer:
\( (4q+3)^3 = 64q^3 + 144q^2 + 108q + 27 = 4(16q^3 + 36q^2 + 27q + 6) + 3 \), which is of the form 4m + 3.

Check Your Progress 6. Out of the numbers n, n + 1 and n + 2, show that only one number is divisible by 3.
Answer:
Write n = 3q + r with r = 0, 1 or 2. If r = 0, n is divisible by 3; if r = 1, then n + 2 = 3(q+1) is divisible by 3; if r = 2, then n + 1 = 3(q+1) is divisible by 3. In each case exactly one of the three numbers is divisible by 3.

Euclid's Division Algorithm

An algorithm is a sequence of steps to carry out a task, and the order of the steps is very important.

If a and b are positive integers such that \( a = bq + r \), then every common divisor of a and b is a common divisor of b and r, and vice-versa. The H.C.F. of positive integers a and b (a > b) is obtained as follows.

Step 1: Apply Euclid's division lemma to a and b, that is, find whole numbers q and r such that \( a = bq + r \), \( 0 \le r < b \).
Step 2: If r = 0, then b is the H.C.F. of a and b. If \( r \ne 0 \), apply the division lemma to b and r.
Step 3: Continue the process till the remainder is 0. The divisor at this stage is the H.C.F. of a and b.

This procedure works because the H.C.F. of a and b is the same as the H.C.F. of b and r.

Solved Examples on Euclid's Division Algorithm

Example 5. Use Euclid's division algorithm to find the H.C.F. of 196 and 38318.
Answer:
Applying Euclid's division lemma to 196 and 38318:
\( 38318 = 196 \times 195 + 98 \)
\( 196 = 98 \times 2 + 0 \)
The remainder at the second stage is zero. So the H.C.F. of 38318 and 196 is 98.

Example 6. Use Euclid's division algorithm to find the H.C.F. of (i) 56 and 814 (ii) 6265 and 76254.
Answer:
(i)
\( 814 = 56 \times 14 + 30 \)
\( 56 = 30 \times 1 + 26 \)
\( 30 = 26 \times 1 + 4 \)
\( 26 = 4 \times 6 + 2 \)
\( 4 = 2 \times 2 + 0 \)
Hence the H.C.F. of 56 and 814 is 2.
(ii)
\( 76254 = 6265 \times 12 + 1074 \)
\( 6265 = 1074 \times 5 + 895 \)
\( 1074 = 895 \times 1 + 179 \)
\( 895 = 179 \times 5 + 0 \)
Hence the H.C.F. of 6265 and 76254 is 179.

Example 7. If the H.C.F. of 657 and 963 is expressible in the form \( 657x + 963 \times (-15) \), find x.
Answer:
Applying Euclid's division lemma to 657 and 963:
\( 963 = 657 \times 1 + 306 \)
\( 657 = 306 \times 2 + 45 \)
\( 306 = 45 \times 6 + 36 \)
\( 45 = 36 \times 1 + 9 \)
\( 36 = 9 \times 4 + 0 \)
So the H.C.F. of 657 and 963 is 9. Given \( 657x + 963 \times (-15) = 9 \), so \( 657x = 9 + 963 \times 15 = 14454 \).
\( x = \dfrac{14454}{657} = \) 22.

Example 8. If d is the H.C.F. of 468 and 222, find x and y satisfying \( d = 468x + 222y \). Also show that x and y are not unique.
Answer:
\( 468 = 222 \times 2 + 24 \) ... (i)
The remainder 24 is not 0, so apply the lemma to 222 and 24: \( 222 = 24 \times 9 + 6 \) ... (ii)
Apply it to 24 and 6: \( 24 = 6 \times 4 + 0 \) ... (iii)
The remainder is now zero, so the last divisor 6 is the H.C.F. (d = 6).
From (ii): \( 6 = 222 - 24 \times 9 \). From (i): \( 24 = 468 - 222 \times 2 \). Therefore \( 6 = 222 - (468 - 222 \times 2) \times 9 = 222 \times 19 - 468 \times 9 \).
So \( x = -9 \) and \( y = 19 \).
Also \( 6 = 19 \times 222 - 9 \times 468 + (222 \times 468 - 222 \times 468) = (19 + 468) \times 222 - (9 + 222) \times 468 = 487 \times 222 - 231 \times 468 \), giving \( x = -231 \) and \( y = 487 \).
Hence x and y are not unique.

Example 9. 144 cartons of coke cans and 90 cartons of pepsi cans are to be stacked in a canteen. If each stack is of the same height and is to contain cartons of the same drink, what would be the greatest number of cartons each stack would have?
Answer:
To stack cartons of the same drink with the same number in every stack, we need the greatest number that divides 144 and 90 exactly, that is, their H.C.F. Using Euclid's division algorithm:
\( 144 = 90 \times 1 + 54 \)
\( 90 = 54 \times 1 + 36 \)
\( 54 = 36 \times 1 + 18 \)
\( 36 = 18 \times 2 + 0 \)
So the H.C.F. of 144 and 90 is 18. Each stack would have 18 cartons.

Check Your Progress: Euclid's Division Algorithm

Check Your Progress 1. Find the H.C.F. of 1650 and 847.
Answer:
\( 1650 = 847 \times 1 + 803 \)
\( 847 = 803 \times 1 + 44 \)
\( 803 = 44 \times 18 + 11 \)
\( 44 = 11 \times 4 + 0 \)
The H.C.F. is 11.

Check Your Progress 2. Find the H.C.F. of 2781 and 1242.
Answer:
\( 2781 = 1242 \times 2 + 297 \)
\( 1242 = 297 \times 4 + 54 \)
\( 297 = 54 \times 5 + 27 \)
\( 54 = 27 \times 2 + 0 \)
The H.C.F. is 27.

Check Your Progress 3. Find the H.C.F. of 13281 and 15844.
Answer:
\( 15844 = 13281 \times 1 + 2563 \)
\( 13281 = 2563 \times 5 + 466 \)
\( 2563 = 466 \times 5 + 233 \)
\( 466 = 233 \times 2 + 0 \)
The H.C.F. is 233.

Check Your Progress 4. Find the H.C.F. of 97 and 101.
Answer:
\( 101 = 97 \times 1 + 4 \)
\( 97 = 4 \times 24 + 1 \)
\( 4 = 1 \times 4 + 0 \)
The H.C.F. is 1.

Check Your Progress 5. If the H.C.F. of 408 and 1032 is expressible in the form \( 1032m - 408 \times 5 \), find m.
Answer:
Using Euclid's algorithm: \( 1032 = 408 \times 2 + 216 \), \( 408 = 216 \times 1 + 192 \), \( 216 = 192 \times 1 + 24 \), \( 192 = 24 \times 8 + 0 \). So the H.C.F. is 24.
\( 1032m - 2040 = 24 \), so \( 1032m = 2064 \) and m = 2.

Check Your Progress 6. 105 goats and 140 sheep have to be taken across a river. There is only one boat, which will have to make many trips in order to do so. The lazy boatman has his own conditions for transporting them. He insists that he will take the same number of animals in every trip and they have to be of the same kind. He will naturally like to take the largest possible number each time. Can you tell how many animals went in each trip?
Answer:
The largest possible equal number is the H.C.F. of 105 and 140.
\( 140 = 105 \times 1 + 35 \), \( 105 = 35 \times 3 + 0 \). So the H.C.F. is 35 and 35 animals went in each trip.