How to evaluate the Greatest Common Divisor?

In summary, the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers include its efficiency, as well as its use of ring theory rather than the fundamental theorem of arithmetic. It can also be used to find the gcd of two polynomials in one variable and find the multiplicative inverse of an integer modulo a number with no prime factors in common.
  • #1
matqkks
285
5
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?
 
Mathematics news on Phys.org
  • #2
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.
 
  • Like
Likes matqkks
  • #3
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##.)
 
  • Like
Likes matqkks

FAQ: How to evaluate the Greatest Common Divisor?

What is the definition of Greatest Common Divisor (GCD)?

The Greatest Common Divisor (GCD) of two or more numbers is the largest positive number that divides evenly into all of the given numbers. It is also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF).

How do you find the GCD of two numbers?

The most common method to find the GCD of two numbers is by using the Euclidean algorithm. This involves dividing the larger number by the smaller number, then dividing the remainder by the previous divisor, and so on until the remainder is zero. The last non-zero remainder is the GCD of the two numbers.

Can the GCD be negative?

No, the GCD is always a positive number. This is because it represents the largest positive number that divides evenly into all of the given numbers.

How is the GCD used in mathematics?

The GCD is used in many mathematical concepts, such as simplifying fractions, finding equivalent fractions, and solving equations with multiple variables. It is also used in computer science for tasks such as reducing fractions and finding the lowest common denominator.

Is there a faster way to find the GCD of more than two numbers?

Yes, there are various algorithms that can be used to find the GCD of more than two numbers, such as the binary GCD algorithm and the Lehmer's GCD algorithm. These methods are more efficient than finding the GCD of each pair of numbers individually.

Back
Top