0 votes

Let $a$ and $b$ be two positive integers such that $a = k_1b + r_1$ and $b = k_2r_1 + r_2,$ where $k_1,k_2,r_1,r_2$ are positive integers with $r_2 < r_1 < b$ Then $\text{gcd}(a, b)$ is same as

- $\text{gcd}(r_1,r_2)$
- $\text{gcd}(k_1,k_2)$
- $\text{gcd}(k_1,r_2)$
- $\text{gcd}(r_1,k_2)$

0 votes

Answer (A)

Using eucledian algorithm i.e.

**If a = bq + r, then GCD(a, b) = GCD(b, r).**

using this in question

a= $k_{1}b + r_{1}$ => GCD(a,b)= GCD(b,$r_{1}$)

b= $k_{2},$r_{1}$ + r_{2}$ => GCD(b,r1)= GCD($r_{1}$,$r_{2}$)

hence GCD(a,b) = GCD(b,r1)= GCD($r_{1}$,$r_{2}$)

Prove of eucledian algorithm

If a = bq + r, then an integer d is a common divisor of a and b if, and only if, d is a common divisor of b and r.

Let d be a common divisor of a and b. Then d divides a and d divides b. Thus d divides (a − bq), which means d disvides r, since r = a − bq. Thus d is a common divisor of b and r.

** a = bq + r, then GCD(a, b) = GCD(b, r)**