Question

State and prove division Algorithm.

Answer 1

Division Algorithm of Euclid to find the HCF or GCD of two positive integers.

Let a and b be given positive Integers.  Let a >= b.
Let a = b * q + r,   where q >= 0, and  0 <= r < b.

Euclid's algorithm:    HCF (a , b) = HCF (a-b , b)
                           or,  HCF(a , b) = HCF(b, r)

Example :  HCF ( 100, 24) = HCF (76, 24) = HCF(24, 100 - 4*24)

Let   a = b * q + r
Let  c be the GCD of a and b.  So a = x * c   and   b = y * c.  
x and y are >= 1.

So   x c = y c q + r    =>   r = c (x - y q)
So   c divides r also. 
Hence,  HCF(a, b) = HCF(a, r) = HCF(b, r) = c.   PROVED.

So in each step of the algorithm, we find the reminder, which is used in the next step for finding the remainder and hence gcd.