
Content Curator
While dealing with the chapter on real numbers we are encountered with Euclid’s Division Lemma, Euclid’s Division Algorithm and Fundamental Theorem of Arithmetic, and other such important topics which make our understanding of the chapter easy. Lemma is a statement that can be useful in proving other statements. And an algorithm is the step-by-step procedure of performing any task or operation. This chapter deals with the definition, use, and application of such important topics.
| Table of Content |
Read Also: Properties of Real Numbers
Euclid’s Division Lemma
Theorem: “Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.”
The above theorem is known as Euclid’s Division Lemma. According to Euclid’s Division Lemma if a and b are two positive integers; where a > b, then there are two integers q and r which can define the relationship between a and b as a = bq + r, where r is less than b and greater than or equal to 0.
For example, take a = 11 and b = 2, then we can relate them as
11 = 2 × 5 + 1, when we compare this with the statement of Euclid’s Division Lemma we observe that for the positive integers a = 11 and b = 2 there are unique integers q = 5 and r = 1 which can define the relationship between a = 11 and b = 2.
Euclid’s Division Algorithm
“The step by step use of Euclid’s Division Lemma for finding the HCF of two positive numbers is called Euclid’s Division Algorithm.”
It should be noted that though Euclid’s Division Lemma and Euclid’s Division Algorithm are closely related, they are slightly different and hence cannot be considered the same.
Steps to find the HCF of two numbers using Euclid’s Division Algorithm-
Given that there are two positive numbers a and b with a > b and we’ve to find their HCF.
- Step 1: We’ll apply Euclid’s Division Lemma to a and b and find the integers q and r which will satisfy the relation a = bq + r.
- Step 2: After applying Euclid’s Division Lemma if we get r = 0 then b is the HCF of a and b.
- Step 3: If the value of r is not equal to zero, we’ll repeat step 1 for b and r till we get remainder = 0. When we get r = 0, the corresponding value of the divisor will be the HCF of a and b.
Example. Use Euclid’s Division Algorithm to find the HCF of 196 and 38220.
Solution. Here, 38220 is greater than 196 so taking a = 38820 and b = 196 and applying the Euclid’s Division Lemma to a and b-
38220 = 196 × 195 + 0
Here, we get the value of remainder equal to 0, hence 196 is the HCF of 196 and 38220.
Fundamental Theorem of Arithmetic
Theorem: “Every composite number can be expressed (factorized) as a product of primes, and this factorization is unique, apart from the order in which the prime factors occur.”
Or,
“The prime factorization of a natural number is unique, except for the order of its factors.”
The above theorem is known as the Fundamental Theorem of Arithmetic. According to this theorem whenever we factorize a composite number we can represent the factors as prime numbers because every composite number is a product of prime numbers. When expressing the composite number as a product of prime numbers the sequence of their occurrence (the occurrence of prime numbers as factors) does not matter (is of no use).
For example, take the composite number 24; we can represent it as 12 × 2, which again can be represented as 6 × 2 × 2, which again can be represented as 3 × 2 × 2 × 2, which means we can represent 24 as 24 = 3 × 2 × 2 × 2. So, what we ultimately get is the product of prime numbers 2 and 3. And if we write 24 = 3 × 2 × 2 × 2 as 24 = 2 × 3 × 2 × 2 or 24 = 2 × 2 × 2 × 3, we’ll get the same thing, hence the order of occurrence of prime numbers does not matter when we factorize a composite number as a product of prime numbers.
Prime Factorisation Method
We can use the Fundamental Theorem of Arithmetic to find the LCM and HCF of two or more numbers. The method which is used to find the LCM and HCF of given numbers using the Fundamental Theorem of Arithmetic is called Prime Factorisation Method.
Example. Find the LCM and HCF of 510 and 92 by prime factorization method.
Solution. First we’ll find the prime factors of 92 and 510,
92 = 2 × 2 × 23 = 22 × 23
510 = 2 × 3 × 5 × 17
So, HCF(92, 510) = 2 and LCM(92, 510) = 2 × 2 × 3 × 5 × 17 × 23 = 23460.
Irrational Numbers
“A number which cannot be represented in as p/q, (where p and q are integers and q is not equal to zero)is called an irrational number.”
Examples of irrational numbers are √2, √3, √11, π, 0.10110111011110…, etc.
- If we perform addition or subtraction between a rational and an irrational number we’ll get an irrational number.
- If we perform multiplication or division between a rational and an irrational number we’ll get an irrational number.
Theorem: “If p is a prime number and it divides a2, then it also divides a, where a is a positive integer.”
Example. Prove that √5 is irrational.
Solution. Assume that √5 is a rational number and hence it can be represented in the form p/q.
We’ll find integers r and s, (s is not equal to zero) such that √5 = r/s and assuming that r and s have a common factor other than 1. Then we’ll simplify r/s by dividing from their common factor to get √5 = a/b, where a and b are co-prime numbers.
√5 = a/b
Or, b√5 = a
Squaring both sides,
5b2 = a2
From the theorem stated above, we observe that a is divisible by 5.
Now writing a = 5c and substituting this in 5b2 = a2. We get
5b2 = 25c2 => b2 = 5c2
The equation obtained above implies that b is divisible by 5 and we’ve already proved that a is also divisible by 5, which means that 5 is the common factor of a and b. But a and b are co-prime numbers, so they cannot have a common factor other than 1. So, this proves that our assumption of √5 being a rational number is wrong.
Hence, √5 is an irrational number.
Decimal Expansions of Rational Numbers
- “If we’re given a rational number having a terminating decimal expansion, then it can be expressed as p/q, where p and q are co-prime numbers and we factorize q we’ll get the factors as 2n5m, where n and m are non-negative integers.”
The above statement can be understood from the example of 0.0875.
0.0875 = 875/10000 = 875/104 = (7 × 53)/(24 × 54) = 7/(24 × 5)
In the case of 0.0875 we observe that 0.0875 is a rational number with terminating decimal expression and we’ve expressed it as p/q = 875/104 and after factorising q = 104 we get 104 = 24 × 54 which is of the form 2n5m.
- “If we’re given a number x = p/q where prime factorization of q is of the form 2n5m, then the decimal expansion of such a number will be terminating.”
For example, take 13/125 we can write it as
13/125 = 13/53 = (13 × 23)/(52 × 23) = 104/103 = 0.104
In this case, we saw that the prime factorization of q = 125 = 53 is not of the form 2n5m but we converted it into the form of 2n5m by multiplying the numerator and denominator with 23 and the given number became a rational number of form p/q with the prime factorization of q as 2n5m. Simplifying it further we get 13/125 = 0.104 which is a terminating decimal expression.
- “if we’re given a rational number of the form p/q where p and q are co-prime numbers and the prime factorization of q is not of the form 2n5m, then p/q has a non-terminating repeating decimal expression.”
For example, 1 and 7 are co-prime numbers when we write them as p/q = 1/7, we see that prime factorization of 7 is not of form 2n5m and when we simplify it we get 1/7= 0.1428571428571…, which is non-terminating repeating.
Read Also: Revision of Arithmetic Properties
Things to Remember
- Euclid’s Division Lemma gives the relation between two positive integers a and b as a = bq + r, where 0 ≤ r < b < a and q and r are unique positive integers.
- The use of Euclid’s Division Lemma to find the HCF of two numbers in step by step method is called Euclid’s Division Algorithm.
- The Fundamental Theorem of Arithmetic states that every composite number can be represented as a product of prime numbers, where the order of occurrence of prime numbers is not taken into consideration.
- Prime Factorisation Method is used to find the LCM and HCF of given numbers using Fundamental Theorem of Arithmetic.
- The square root of prime numbers and the numbers which cannot be written as p/q are irrational numbers (e.g. √2, √3, π, 0.10110111011110…, etc)
- Every terminating decimal expression can be written in the form of p/q where the factors of q are of the form 2n5m.
- Every rational number of the form p/q with prime factors of q of the form 2n5m can be expressed in the form of terminating decimal expression, otherwise, it will be a non-terminating repeating decimal expression.
Sample Questions
Ques. An army contingent of 616 members is to march behind an army band of 32 members in a parade. The two groups are to march in the same number of columns. What is the maximum number of columns in which they can march?
Solution. To find the maximum number of columns we need to find the HCF of a number of army contingent members and the number of army band members, i.e. the HCF of 616 and 32. Applying Euclid’s Division Algorithm to 616 and 32, we get-
616 = 32 × 19 + 8
Now,
32 = 8 × 4 + 0
Hence, 4 is the HCF of 616 and 32. So, the maximum number of columns in which the army contingent of 616 members can march behind the army band of 32 members is 4.
Ques. Find the LCM and HCF of 336 and 54 and verify that LCM × HCF = 336 × 54 (product of the given numbers).
Solution.
336 = 2 × 2 × 2 × 2 × 3 × 7 = 24 × 3 × 7
And, 54 = 2 × 3 × 3 × 3 = 2 × 33
So, LCM (336, 54) = 3024 and HCF (336, 54) = 6.
Now,
LCM (336, 54) × HCF (336, 54) = 3024 × 6 = 18144.
And, 336 × 54 = 18144
Hence, LCM (336, 54) × HCF (336, 54) = 336 × 54 (product of the given numbers) = 18144.
Ques. Given that HCF (306, 657) = 9, find LCM (306, 657).
Solution. Because HCF × LCM = Product of the numbers.
Hence,
HCF (306, 657) × LCM (306, 657) = 306 × 657
= > 9 × LCM (306, 657) = 306 × 657
= > LCM (306, 657) = (306 × 657)/6
= > LCM (306, 657) = 51 × 657
= > LCM (306, 657) = 33507
Ques. Prove that 6 + √2 is irrational.
Solution. Assume that 6 + √2 is rational and hence it can be written as 6 + √2 = r/s.
Now,
6 + √2 = r/s
= > 6 – r/s = √2
= > √2 = 6 – r/s
= > √2 = (6s – r)/s
Since r and s are integers, 6 – r/s is rational which implies that √2 is rational. But √2 is an irrational number which means that our assumption of 6 + √2 being a rational number was wrong.
Hence, 6 + √2 is an irrational number.
Ques. Without performing actual division check whether the decimal expression of 77/200 is terminating or non-terminating.
Solution. We can write 77/200 as
77/200 = 77/(2 × 2 × 2 × 5 × 5) = 77/(23 × 52)
Because on performing the prime factorization of 200 we get its factors in the form of 2n5m, hence the decimal expression of 77/200 is terminating.









Comments