edited by
1,158 views
0 votes
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

  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 by

2 Answers

1 votes
1 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 votes
1 votes
1 answer
1
akash.dinkar12 asked May 11, 2019
948 views
Number of real solutions of the equation $x^7 + 2x^5 + 3x^3 + 4x = 2018$ is$1$$3$$5$$7$
2 votes
2 votes
1 answer
2
akash.dinkar12 asked May 11, 2019
717 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$
0 votes
0 votes
1 answer
3
akash.dinkar12 asked May 11, 2019
675 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)$
0 votes
0 votes
1 answer
4
akash.dinkar12 asked May 11, 2019
728 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$