# Applications of GCD in competitive programming

I know that it is the largest +ve number that divides the given numbers and one of its applications:
For any two numbers to be co-prime, GCD = 1.
Can you suggest some more applications that you have gone through??

Here are just a few:

Reducing fractions

Chinese remaindering (using extended Euclidean algorithm)

finite field arithmetic (in particular, multiplicative inverses, again using extended Euclidean algorithm)

RSA crypto (using above)

Factoring integers (Pollardâ€™s rho method, elliptic curve method, Shorâ€™s algorithm)

1 Like

GCD is used to find LCM. Also, If youâ€™ve learned Euclidean Algorithm (the algorithm to find GCD), you can find multiplicative inverse by extended euclid. There is also Chinese Remainder Theorem and many more.

I think the actual question on Quora was, â€śWhat are real life applications of the greatest common divisor of two or more integers?â€ť. But he asked for the applications of GCD in competitive programming. I donâ€™t think RSA crypto is much use in CP. Also I didnâ€™t found problems of Pollardâ€™s rho method, elliptic curve method, Shorâ€™s algorithm.

Just saying, itâ€™s non-ethical to copy something and donâ€™t mention it. You shouldâ€™ve given credit.

3 Likes

GCD in particular not asked directly in the most contest but its application can be seen more often.

• Euler Totient function - counts the
positive integers up to a given
integer n that are relatively prime
• Modular Multiplicative Inverse - ax =
1(mod m) or (1/a)mod m (This)
• Extended Euclid Algorithm - this
• Reducing Fractions - Fractions can be
reduced to irreducible form.
• LCM(a,b) = a*b/(gcd(a,b))

You can also go through this link to find the type of questions which are related to GCD.

Hope this helps!

4 Likes

You said â€śReducing Fractions - Fractions can be reduced to irreducible form.â€ť How to reduce fractions using GCD ??

suppose, youâ€™ve got the fraction 12/8. whatâ€™s their gcd? 4. divide them both by 4. youâ€™ve got the fraction 3/2

3 Likes
//