Question

According to euclid's division algorithm HCF of any two positive integers a and b with a> b is obtained by applying euclid's division lemma to a and b to find q and r such that a = bq +r where r must satisfy

Answer 1

Ok, a general case.

If we take for example, a = 5 and b = 2

we have:

a/b = 5/2 = 2 + 1

where q = 2, the quotient

and r = 1, the rest.

then we have:

5 = 2*2 + 1 or a = q*b + r

So r must satisfy that is the difference between a and the multiple of b that is closest to a from bellow.

So another example. a = 8 and b = 3.

The closest multiple of b, that is closest to 8 (from bellow) is

3*2 = 6

the difference between 8 and 6 is: 8 - 6 = 2

so we have r = 2.

then:

a = q*b + r is: 8 = 2*3 + 2,