General formula for the gcd.

Question

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?

Answer 1

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.