It seems there is no closed form for the greatest common divisor of any two given integers.

Why is there no such formula?

Does the only way to compute the gcd is essentially to recursively apply the Euclidean algorithm?

  • 3
    $\begingroup$ Well, there certainly is a closed form if you have the prime factorizations. And, of course, that gives an alternative method for finding the gcd...though, for large numbers, factorization can be quite difficult so the Euclidean algorithm is to be preferred. $\endgroup$ – lulu Jul 4 at 20:52
  • $\begingroup$ Note that $n>1$ is prime iff $\gcd(n,(n-1)!)=1$ $\endgroup$ – Hagen von Eitzen Jul 4 at 22:33
  • $\begingroup$ For computing, there are also "binary" algorithms, and optimizations for very large numbers, like this one. $\endgroup$ – metamorphy Jul 20 at 7:44

There certainly is a closed formula, if you have the prime factorizations.

Let $$m=\prod p_i^{m_i}\quad \& \quad n=\prod p_i^{n_i}$$

Where the product is taken over the primes $\{p_i\}$ and it is understood that only finitely many of the $\{m_i\}$ and $\{n_i\}$ are non-zero.

Then $$\gcd(m,n)=\prod p_i^{\min(m_i,n_i)}$$

This also gives an alternative to the Euclidean Algorithm. It's not all that helpful, though, because it is, in general, extremely difficult to produce the prime factorization. By contrast, the Euclidean algorithm is easy to use, even for large numbers.

  • 1
    $\begingroup$ That would be a closed formula if you give a general non-recursive expression of the factorization of any natural number. $\endgroup$ – Dr Potato Jul 4 at 21:16
  • $\begingroup$ Sure. As I say, though, at least it gives an alternate method for finding the gcd, albeit a method that's generally far from optimal. $\endgroup$ – lulu Jul 4 at 22:13
  • $\begingroup$ This is not an answer for the question. $\endgroup$ – Dr Potato Jul 10 at 4:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.