Question

Find gcd of 4999 and 1109 and also express it in 4999m +1109n

Answer 1

Given:-

Two prime numbers 4999 and 1109.

To Find:-

Find the gcd of 4999 and 1109 and also express it in 4999m+1109n.

Solution:-

According to question we have to find the gcd of 4999 and 1109.

Since, 4999 and 1109 both the numbers are prime numbers which can't be further break into other smaller prime numbers.

Therefore, here, we use Euclid's Algorithm to find the gcd of 4999 and 1109:-

So, using Euclid's Algorithm , we have

Step.1 :- divide the larger number by the smaller one ;

$4999\div 1109=4+563$

Step.2 :- Divide the smaller number by the above operation's remainder;

$1109\div563=1+546$

Step.3 :- Divide the remainder from the step 1 by the remainder of step2;

$563\div546=1+17$

Step.4 :- Divide the remainder from the step 2 by the remainder of step.3;

$546\div17=32+2$

Step.5:- Divide the remainder from the step 3 by the remainder of step.4;

$17\div2=8+1$

Step.6 :- Divide the remainder from the step 4 by the remainder of step.5;

$2\div1=2+0$

here we stop , the remainder is zero and 1 is the last remainder thet is not zero.

Hence, gcd of 4999 and 1109 is 1.

Now, to represent in form of 4999m+1109n, we have

$546=1109-1*563\\546=1109-1(4999-1109*4)\\546=5*1109-4999\\17=563-546\\17=4999-4*1109-1109-563\\17=4999-4*1109-1109+4999-4*1109\\17=2*4999-9*1109\\2=546-17*32\\2=-65*4999+293*1109\\1=17-8*2\\1=522*4999-2353*1109$

Hence, 1 = 4999(522)+1109(-2353) where, m=522 and n=-2353.