Euclid’s division algorithm provides an easier way to compute the Highest Common Factor (HCF) of two given positive integers. Let us now prove the following theorem.

**Euclid’s Division Algorithm**

In the previous
section, we have studied about Euclid’s division lemma and its applications. We
now study the concept Euclid’s Division Algorithm. The word ‘algorithm’ comes from the name of
9th century Persian Mathematician Al-khwarizmi. An algorithm means a series of
methodical step-by-step procedure of calculating successively on the results of
earlier steps till the desired answer is obtained.

Euclid’s division
algorithm provides an easier way to compute the Highest Common Factor (HCF) of
two given positive integers. Let us now prove the following theorem.

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.

**Euclid’s Division Algorithm**

To find Highest
Common Factor of two positive integers *a *and *b*, where *a *>
*b*

**Step1: **Using Euclid’s
division lemma *a *= *bq *+ *r *; 0 ≤ *r *< *b*.
where *q *is the quotient, *r *is the remainder. If *r *= 0 then
*b *is the Highest Common Factor of *a *and *b*.

**Step 2: **Otherwise applying
Euclid’s division lemma divide *b *by *r *to
get *b *= *rq*_{1} + *r*_{1},
0 ≤ *r*_{1} < *r.*

**Step 3: **If *r*_{1}
= 0 then *r *is the Highest common factor of *a *and *b.*

**Step 4: **Otherwise using
Euclid’s division lemma, repeat the process until we get the remainder zero. In
that case, the corresponding divisor is the HCF of *a *and *b*.

**NOTE**

·
The above algorithm will always produce remainder zero at some
stage. Hence the algorithm should terminate.

·
Euclid’s Division Algorithm is a repeated application of
Division Lemma until we get zero remainder.

·
Highest Common Factor (HCF) of two positive numbers is denoted
by (a,b).

· Highest Common Factor (HCF) is also called as Greatest Common Divisor (GCD)

Using the above
Algorithm, let us find HCF of two given positive integers. Let *a*= 273and
*b *= 119 be the two given positive integers such that *a *> *b *.

We start dividing 273
by 119 using Euclid’s division lemma, we get

273 = 119 × 2 + 35 ………..(2)

The remainder is 35 ≠ 0

Therefore, applying
Euclid’s Division Algorithm to the divisor 119 and remainder 35, we get

119 = 35 × 3 + 14 ………..(2)

The remainder is 14 ≠ 0

Applying Euclid’s
Division Algorithm to the divisor 35 and remainder 14, we get

35 =14 ×2 + 7 …(3)

The remainder is 7 ≠
0.

Applying Euclid’s
Division Algorithm to the divisor 14 and remainder 7. we get,

14 =7 × 2 + 0 …(4)

The remainder at this
stage= 0.

The divisor at this
stage= 7 .

Therefore Highest
Common Factor of 273, 119 = 7.

If the Highest Common
Factor of 210 and 55 is expressible in the form 55*x *- 325 , find *x.*

Using Euclid’s
Division Algorithm, let us find the HCF of given numbers

210 = 55 × 3 + 45

55 = 45 ×1 + 10

45 = 10 × 4 + 5

10 = 5 × 2 + 0

The remainder is zero.

So, the last divisor 5
is the Highest Common Factor (HCF) of 210 and 55.

Since, HCF is
expressible in the form 55*x *− 325 = 5

Gives 55*x*=
330

Hence *x*= 6

Find the greatest
number that will divide 445 and 572 leaving remainders4 and 5 respectively.

Since the remainders
are 4, 5 respectively the required number is the HCF of the number 445 − 4 =
441, 572 − 5 = 567

Hence, we will
determine the HCF of 441 and 567. Using Euclid’s Division Algorithm, we have

567 = 441×1 + 126

441 = 126 × 3 + 63

126 = 63 × 2 + 0

Therefore HCF of 441, 567 = 63 and so the required number is 63.

If *a*, *b *are
two positive integers with *a *> *b *then G.C.D of (*a*,*b*)
= GCD of (*a *-*b*,*b*).

Using this Activity,
find the HCF of

(i) 90,15

(ii) 80,25

(iii) 40,16

(iv) 23,12

(v) 93,13

We can apply Euclid’s
Division Algorithm twice to find the Highest Common Factor (HCF) of three
positive integers using the following procedure.

Let a, b, c be the
given positive integers.

(i) Find HCF of a,b.
Call it as d

d = (a,b)

(ii) Find HCF of d and
c.

This will be the HCF
of the three given numbers a, b, c

Find the HCF of 396,
504, 636.

To find HCF of three
given numbers, first we have to find HCF of the first two numbers.

To find HCF of 396 and
504

Using Euclid’s
division algorithm we get 504 = 396 ×1 + 108

The remainder is 108 ≠
0

Again applying
Euclid’s division algorithm396 = 108 × 3 + 72

The remainder is 72 ≠ 0,

Again applying
Euclid’s division algorithm 108 = 72 ×1 + 36

The remainder is 36 ≠ 0,

Again applying
Euclid’s division algorithm 72 = 36 × 2 + 0

Here the remainder is
zero. Therefore HCF of 396, 504 = 36 . To find the HCF of 636 and 36.

Using Euclid’s
division algorithm we get636 = 36 ×17 + 24

The remainder is 24 ≠ 0

Again applying
Euclid’s division algorithm36 = 24 ×1 + 12

The remainder is 12 ≠ 0

Again applying Euclid’s
division algorithm 24 = 12 × 2 + 0

Here the remainder is
zero. Therefore HCF of 636,36 = 12

Therefore Highest
Common Factor of 396, 504 and 636 is 12.

Tags : Theorem, Illustration, Example, Solution | Mathematics Theorem, Illustration, Example, Solution | Mathematics

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.