I How to evaluate the Greatest Common Divisor?

  • Thread starter matqkks
  • Start date
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?


Insights Author
2018 Award
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.
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##.)

Want to reply to this thread?

"How to evaluate the Greatest Common Divisor?" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads