Quick way to find the GCD of 7602 and 7710

Question

I've been reading through my book and I see that to find the GCD of these two numbers, I can look at the difference of these two numbers. However, how do I determine the GCD from the difference? I've got that $7710 - 7602 = 108$. And $108$ is $2^2 * 3^3$.

Answer 1

After you found the difference $108=2^2\cdot 3^3$, you can use the divisibility tests to find out that $7602$ is:

• divisible by $2$, as it ends in $0$
• not divisible by $4$, as it ends in $10$
• divisible by $3$, since the sum of digits is $15$
• not divisible by $9$, by the previous item.

So, $6$ is the greatest divisor of $180$ that also divides $7602$.

Answer 2

By Euclide's Algorithm we have $$\gcd(7710,7602)=\gcd(108,7602)=\gcd(108,70\times108+42)=\gcd(108,42)=\gcd(2\times42+24,42)=\gcd(24,42)=\gcd(24,18)=\gcd(6,18)=6$$