EUCLID'S DIVISION ALGORITHM

Theorem 1 : 

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.

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

Step 1 : 

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₁ + r₁, 0 ≤ r₁ < r.

Step 3 : 

If r₁ = 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 H.C.F of a and b.

Note :

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

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

3. Highest Common Factor (H.C.F) of two positive numbers is denoted by (a, b).

4. Highest Common Factor (H.C.F) is also called as Greatest Common Divisor (G.C.D).

Illustration :

Using the above Algorithm, let us find H.C.F of two given positive integers. Let a = 273 and 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 x 2 + 35 ----(1)

The remainder is 35 ≠ 0.

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

119 = 35 x 3 + 14 ----(2)

The remainder is 14 ≠ 0.

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

35 = 14 x 2 + 7 ----(3)

The remainder is 7 ≠ 0.

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

14 = 7 x 2 + 0 ----(4)

The remainder at this stage = 0.

The divisor at this stage = 7.

Therefore Highest Common Factor of 273, 119 = 7.

Theorem 2 : 

If a, b are two positive integers with a > b then

GCD of (a, b) = GCD of (a - b, b)

*GCD = Greatest Common Divisor

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 H.C.F of d and c.

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

Two positive integers are said to be relatively prime or co prime if their Highest Common Factor is 1.

©All rights reserved. onlinemath4all.com