ISI2018-MMA-8

Question

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

• A. $\text{gcd}(r_1,r_2)$
• B. $\text{gcd}(k_1,k_2)$
• C. $\text{gcd}(k_1,r_2)$
• D. $\text{gcd}(r_1,k_2)$

Comments

A?

Answer 1

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)

Answer 2

Answer will be (A) based on the euclidian method to find GCD.