 # 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??

Thanks in advance 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
//