Find m and n if GCD if 325 and 858 is m325 plus n858?

Answer 1

This is my method to find GCD of 2 big numbers A and B and expressing that gcd of the form mA + nB

First, let us find the gcd. Let us call it as d

1) Divide the bigger number by the smaller one.

2) Divide the smaller number by the remainder u get in step 1.

3) Divide the step 1 remainder by step 2, then each remainder by the next remainder and so on.

4) Reach the step when u get no remainder at all. The divisor will be the LCM.

Let me explain it with an example.

Q. Find the gcd of 858 and 325 and express it in the form of m858 + n325.

Solution :

858 = 325*2 + 208

325 = 208*1 + 117

208 = 117*1 + 91

117 = 91*1 + 26

91 = 26*3 + 13

26 = 13.2

thr4, gcd 0f 858 and 325 is d = 13

d = 13 = 91 - 26*3

= 91 -3(117 - 91*1)

= 91*4 - 117*3

=4(208-117) - 117*3

= 4*208 - 7*117

= 4*208 - 7(325-208)

=11*208 -7*325

=11*(858-325*2) - 7*325

=11*858 - 29*325

thr4, d = 13 = m*858 + n*325 where m =11 and n = -29