Applications of GCD in competitive programming

general
, , , ,
1

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??
Want to know more about GCD!! please suggest some of them.

Thanks in advance :slight_smile:

1 Like
2

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)

For details Follow this

2 Likes
3

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.

4

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
    to n. (go this link)
  • 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!

5 Likes
5

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
6

You said “Reducing Fractions - Fractions can be reduced to irreducible form.” How to reduce fractions using GCD ??

7

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

5 Likes