search
Log In
0 votes
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)$
in Numerical Ability
edited by
304 views
0
A?

2 Answers

0 votes
Answer will be (A) based on the euclidian method to find GCD.
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)

Related questions

1 vote
1 answer
1
273 views
Number of real solutions of the equation $x^7 + 2x^5 + 3x^3 + 4x = 2018$ is $1$ $3$ $5$ $7$
asked May 11, 2019 in Numerical Ability akash.dinkar12 273 views
2 votes
1 answer
2
306 views
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$
asked May 11, 2019 in Numerical Ability akash.dinkar12 306 views
0 votes
1 answer
3
216 views
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)$
asked May 11, 2019 in Numerical Ability akash.dinkar12 216 views
0 votes
0 answers
4
231 views
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$
asked May 11, 2019 in Numerical Ability akash.dinkar12 231 views
...