Question

If a and b are positive integers, then you know that a=bq+r, such that r is less than or equal to 0 and r is less than b, where q is a whole number. Prove that HCF(a,b) = HCF(b, r). ​

Answer 1

SOLUTION

GIVEN

a and b are positive integers, then you know that a = bq + r, such that 0 ≤ r ≤ b , where q is a whole number.

TO PROVE

HCF(a,b) = HCF(b, r)

PROOF

Let c = HCF(a,b) & d = HCF(b, r)

Since c = HCF(a,b)

⟹ c divides a and c divides b

⟹ c divides a and c divides bq

⟹ c divides a - bq

⟹ c divides r

⟹ c is a common divisor of b & r

⟹ c divides d

Similarly we can show that d divides c

Now c and d are positive integers

Consequently c = d

Hence HCF(a,b) = HCF(b, r)

Hence proved

━━━━━━━━━━━━━━━━

Learn more from Brainly :-

$1.$ If HCF of two numbers be 40 then which of the following cannot be their LCM.

https://brainly.in/question/28609013

2. The HCF and LCM of two numbers are 17 & 1666 respectively. if one of the numbers is 119 find the other

https://brainly.in/question/13812250