How to evaluate the Greatest Common Divisor?

[matqkks]

What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers?
Should you use Euclid’s algorithm in some cases and prime decomposition in others?

 

[fresh_42]

Prime decomposition is hard for large numbers, the Euclidean algorithm is not. It is also fundamentally a different approach: prime decomposition has to use the fundamental theorem of arithmetics, the Euclidean algorithm is ring theory: $n\mathbb{Z} + m\mathbb{Z} = (n,m)\mathbb{Z}$ where only the property of a principal ideal domain is used. This might be the same, but the point of view is another.

 

[Michael Hardy]

If the prime factorization is $2\times2\times2\times2\times2\times2\times2\times2\times3\times3\times3$ then you can discover in a matter of seconds via only paper and pencil or maybe in your head that that's what it is. If it's $13679\times18269$ then you probably cannot. But Euclid's algorithm is very efficient.

One can also use a somewhat generalized version of Euclid's algorithm to find the gcd of two polynomials in one variable.

Another variant (involving only positive integers, not polynomials) involves not only the successive remainders but also the quotients. In that version one can find the multiplicative inverse of an integer modulo a number with which it has no prime factors in common. For example, by what must one multiply $322$ in order to get $1$, modulo $701$? (The answer in this example is $455$.)