Theorem
1.1 : (Euclid's Division Lemma)
Given positive integers a and b, there
exist unique integers q and r satisfying
a
= b q + r, 0 ≤ r < b
Euclid's Division Algorithm :
To obtain the HCF of two positive
integers, say c and d with c > d
(i)
Apply Euclid's division lemma to c and d. So, we find the whole numbers
q and r such that
c
= d q + r, 0 ≤ r < d
(ii)
If r = 0, d is the HCF of c and d
If r ≠ 0, apply the division lemma to d and r
(iii)
Continue till r = 0. The divisor at this stage will be the required HCF.
This algorithm works because HCF (c, d)
= HCF (d, r)
where the symbol HCF (c, d) denotes the
HCF of c and d, etc.
Example
- 1 : Use Euclid's
algorithm to find the HCF of 4052 and 12576
Solution :
Since 12576 > 4052, we apply the Division lemma to 12576 and 4052 to get
12576
= 4052 x 3 + 420 4052) 12576 ( 3
[ c =
d x q
+ r] 12156 420
Since, r ≠ 0, we apply the division
lemma to d and r i.e., 4052 and 420
4052
= 420 x 9 + 272
We consider the new divisor 420 and new
remainder 272 and apply the division lemma,
420
= 272 x 1 + 148
We consider the new divisor 272 and new
remainder 148 and apply the division lemma,
272
= 148 x
1 + 124
We consider the new divisor 148 and new
remainder 124 and apply the division lemma,
148
=
124 x 1
+ 24
We consider the new divisor 124 and new
remainder 24 and apply the division lemma,
124 = 24 x
5 + 4
Again, we consider the new divisor 24 and
new remainder 4 and apply the division lemma,
24
=
4 x 6 + 0
The remainder now becomes 0, so our
procedure stops. Since the divisor at this stage is 4, the HCF of 12576 and
4052 is 4.
Notice that 4 = HCF (24, 4) = HCF (124, 24)
= HCF (148, 124)
=
HCF (272, 148) = HCF ( 420, 272) = HCF (
4052, 420)
= HCF (12576, 4052)
Example - 2 : Show that every positive even integer is of the form 2q and
that every positive odd integer is of the form 2q + 1, where q is some integer.
Solution : Let a be any positive integer and b = 2. Then, by Euclid's
algorithm,
a = 2 q + r,
for some integer q ≥ 0 and
r = 0 or r =1 [Since, 0
≤ r < 2 ]
\
a = 2q or a
= 2 q + 1
If a is of the form 2q, then a is an even integer.
Also, a positive integer can be either even or odd. Therefore any positive odd
integer is of the form 2 q + 1
Example - 3
: Show that any positive odd integer is of the form 4 q + 1 or 4 q + 3, where q
is some integer
Solution
: Let a be a positive odd integer and b
= 4.
Since 0 ≤ r < 4, the
possible remainders are 0, 1, 2 and 3
i.e., a can be 4 q or 4
q + 1 or 4 q + 2 or 4 q + 3,where q is the quotient.
Since a is odd, it cannot be 4 q or 4 q + 2 (since both are divisible by
2)
\
any positive odd integer is of the form 4 q + 1 or 4 q + 3.
Example - 4
: A sweetseller has 420 kaju barfis and 130 badam barfis. She wants to stack
them in such a way that each stack has the same number and they take up the
least area of the tray. What is the number of that can be placed in each stack for this purpose?
Solution
: We need to
find the HCF ( 4420, 130). This number will give the maximum number of barfis in each stack and the number of stacks
will then be the least. The area of the tray that is used up is the least.
Let us apply the Euclid's algorithm to find the HCF
( 420, 130)
420 = 130 x 3 + 30
130 =
30 x 4 + 10
30 = 10
x 3 + 0
The HCF of
420 and 130 is 10.
No comments:
Post a Comment