X Maths

REAL NUMBERS

Euclid's Division Algorithm

• It states that every positive integer 'a' can be divided by another positive integer 'b' leaving a remainder 'r' such that 0≤r≤b.
• It is related to divisibility of integers.

Example:-

When 35 is divided by 8, quotient is 4 and remainder is 3

We can write,              35 = 8 x 4 + 3

Here,                           a = 35, b = 8 , q = 4 and r = 3

Clearly,                       a = bq + r, where 0 ≤ r ≤ 8

Lemma : - A lemma is a statement which is used to prove another statement.

Algorithm :- It is a series of well defined steps giving a procedure to solve a particular type of problem.

Steps To Solve Euclid’s Division Algorithm

In order to find the HCF of two positive integers a and b (a > b), following steps are required

Step 1 à Apply Euclid’s division lemma to a and b. For this find whole numbers (non-negative integers) q and r satisfying

            a = br + r,                 where 0 ≤ r ≤ b

Step 2 à If r = 0; divisor b is the HCF of a and b. But if r ≠ 0, apply Euclid’s divison lemma to divisor b and remainder r.

              Now, Let  b = cr + r₁

Step 3 à If r₁ = 0, then divisor c is the HCF of a and b otherwise apply the Euclid’s division lemma again to divisor c and remainder r₁ and proceed as before till remainder become 0.

           The divisor d when remainder become 0 then d will be the required HCF of a and b.