Find gcd(15570555, 10872579)

Question

How do I find this?

I know that I should use perhaps:

$gcd(a,b) = gcd(a,a-b) $

But then I get:

$gcd(15570555,4697976) $

Which seems still too large for me to do anything further.

Answer 1

$$\text{gcd}(15570555,4697976)=(15\cdot 1038037,24\cdot 195749)=3(1038037,195749)$$ $$(1038037,195749)=(5\cdot 195749+59292,195749)=(59292,195749)=(4\cdot 14823,195749)$$ But $195749=13\cdot 14823+3050$ $$\text{gcd}(15570555,4697976)=3(14823,195749)=3(14823,13\cdot 14823+3050)=3(14823,3050)=3(14823,50\cdot 61)$$ $$(14823,61)=(243\cdot 61,61)=61$$ $$\text{gcd}(15570555,4697976)=3\cdot 61=183$$

I used repeatedly the properties:

• $(a,b)=(a,b-a)$.
• If $a=bk+r$ then $(a,b)=(b,r)$.
• If $(a,c)=1$ then $(a,bc)=(a,b)$.
• $(ak,bk)=k(a,b)$

Answer 2

You did one step. Keep going.

$1557055 - 10872579 = 4697976$ so $\gcd(1557055,10872579) = \gcd(10872579,4697976)$

$10872579-2*4697976 = 1476627$ so $\gcd(10872579,4697976)= \gcd(4697976,1476627)$

and so on..

$4697976 - 3*1476627 = 268095$

$1476627 -5*268095=136152$

$268095 - 136152=131943$

$136152 - 131943= 4209$

$131943-31*4209 =1464$

$4209 - 2*1464=1281$

$1464 - 1281 = 183$

$1281 - 7*183 = 0$

So $\gcd(1557055,10872579)= 183$

==== earlier answer in which in order to make it easier, I probably made it harder ======

If $p$ is prime and $p \not \mid c$ but $p |b$ then $\gcd(b,c) = \gcd(b/p,c)$ as $p$ will not be a common factor. And if $m|c$ and $m|b$ then $\gcd(b,c) = m \gcd(b/m,c/m)$.

So $15570555 = 5*3*1038037$

$4697976 = 8*3*195749$ so $\gcd(1557055, 4697976) = 3\gcd(1038037,195749)$.

Using the $11$ division trick of every other digit I see $11|1038037$ $1038037=11*94367$. But $11 \not \mid 195749$

So $\gcd(1557055, 4697976)=3\gcd(94367,195749)$

We can use euclid's algorithm now.

$195,749 - 2*94,367= 7015$

So $\gcd(94367,195749)=\gcd(94367,7015)$

$94,367 - 13*7015 = 3172$

$7015 - 2*3172 = 671$

$3172 - 4*671 = 488$

$671 - 488 = 183$

$488 - 2*183 = 122$

$183 - 122 = 61$

$122 = 2*61$

so $\gcd(94367,7015)=61$

And $\gcd(1557055, 4697976) = 3*61 = 183$

Answer 3

Hint:

Use the Euclidean algorithm: $$\gcd(a,b)=\gcd(b, a\bmod b)$$ ($11$ steps). You should find $183$. Further, using the extended Euclidean algorithm yields the coefficients of a Bézout's relation.