ISI2018-MMA-8

304 views

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

1. $\text{gcd}(r_1,r_2)$
2. $\text{gcd}(k_1,k_2)$
3. $\text{gcd}(k_1,r_2)$
4. $\text{gcd}(r_1,k_2)$

edited
0
A?

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

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)

Related questions

1 vote
1
273 views
Number of real solutions of the equation $x^7 + 2x^5 + 3x^3 + 4x = 2018$ is $1$ $3$ $5$ $7$
The sum of the infinite series $1+\frac{2}{3}+\frac{6}{3^2}+\frac{10}{3^3}+\frac{14}{3^4}+\dots$ is $2$ $3$ $4$ $6$
The $x$-axis divides the circle $x^2 + y^2 − 6x − 4y + 5 = 0$ into two parts. The area of the smaller part is $2\pi-1$ $2(\pi-1)$ $2\pi-3$ $2(\pi-2)$
The angle between the tangents drawn from the point $(1, 4)$ to the parabola $y^2 = 4x$ is $\pi /2$ $\pi /3$ $\pi /4$ $\pi /6$