If a and b are positive integers, then you know that a = bq + r, 0 ≤ r < b, where q is a whole number. Prove that HCF (a, b) = HCF (b, r).

Given,

a, b are positive integer

a = bq + r and q is a whole number.

Let H.C.F. of a and b be c and let H.C.F. of b and r be d.

Since,

H.C.F. of a and b is c …….(1)

∴ a is divisible by c

∴ b is divisible by c or bq is divisible by c.

Given,

a = bq + r

r = a - bq

Since, c divides a and bq.

∴ a - bq is divisible by c.

∴ r is divisible by c.

∴ c is common divisor of b and r ….(2)

Since,

H.C.F. of b and r is d ……..(3)

∴ r is divisible by d

∴ b is divisible by d or bq is divisible by d.

Since, d divides r and bq.

∴ r + bq is divisible by d.

∴ a is divisible by d.

∴ d is common divisor of a and b ….(4)

From statements (1), (2), (3) and (4), we get :

c = d

∴ H.C.F. (a, b) = H.C.F. (b, r).

Hence, proved that H.C.F. (a, b) = H.C.F. (b, r).