Can the GCD and Euclidean Algorithm Solve Real Life Problems?

In summary, the greatest common divisor (GCD) of two or more integers has various real life applications, including simplifying ratios, finding the inverse of a number in finite fields, solving empirical formulas, and determining the cheapest way to buy equal amounts of items sold in different sized packages. It is also useful in solving linear Diophantine equations. The Euclidean algorithm is a method commonly used to find the GCD.
  • #1
matqkks
285
5
Are there any real life applications of the greatest common divisor of two or more integers?
 
Mathematics news on Phys.org
  • #2
Yes. i.e. whenever you have something depending on a ratio ...

It's not normally expressed in that way though.
Mostly - the lesson is important for the practise it gives in a kind of problem solving.
 
Last edited:
  • #3
There are a whole bunch. I use the idea regularly so it is difficult to point to a specific thing...
 
  • #4
rexregisanimi said:
There are a whole bunch. I use the idea regularly so it is difficult to point to a specific thing...
Aww go on - show us one... what's the one you use regularly that you last used?
 
  • #5
  • Like
Likes 1 person
  • #6
matqkks said:
Are there any real life applications of the greatest common divisor of two or more integers?
I can't think of any real world applications. The closest I can think of is the Euclid algorithm for finding the GCD which can be extended and used to find the inverse of a number in finite field, but it's seldom used because there are other and better methods. For example, if the field isn't very large, a lookup table can be used. In the case of hardware implementations of inversion based on "binary" finite fields (which is part of AES encryption), there are complex methods (sub-field mapping) that involve fewer gates than a lookup table. Wiki article for extended Euclid algorithm:

wiki_inverse_in_finite_field.htm
 
Last edited:
  • Like
Likes 1 person
  • #7
GCD is used any time you want to simplify integers, but have the same ratios as the others have said. Another way to say it is the numbers scale equally. An example is in solving empirical formulas, where you reduce all integers in a chemical formula. Such as hexane C6H8 -> C3H4 GCD(6,8) is 2 so divide each by 2 to get the answer. Though it isn't of much use, but it has a name.
 
  • Like
Likes 1 person
  • #8
The store sells 8-packs of hotdogs and 12-packs of buns. If you want the same (nonzero) number of each, what's the cheapest way to do it?
 
  • #9
@economicsnerd: good example, well done!
Most people wouldn't do that by listing the divisors, but I suppose there are examples less amenable to a bit of trial and error.
Do HS math textbooks no longer have examples like that these days?
 
  • #10
economicsnerd said:
The store sells 8-packs of hotdogs and 12-packs of buns. If you want the same (nonzero) number of each, what's the cheapest way to do it?
Wouldn't this be the "lowest common multiple" as opposed to the "greatest common divisor"?
 
  • #11
rcgldr said:
Wouldn't this be the "lowest common multiple" as opposed to the "greatest common divisor"?

Directly, I guess it's not really either.
Computing either the GCD or the LCM would get you close to knowing how many bags of each to buy. You either compute {h/GCD(h,b), b/GCD(h,b)} or {LCM(h,b)/h, LCM(h,b)/b}.
 
  • #12
If you can think of a real life application of linear Diophantine equations, then the GCD and the Euclidean algorithm have applications to solving those.
 

What is a greatest common divisor?

A greatest common divisor, also known as a greatest common factor, is the largest number that divides evenly into two or more numbers. It is denoted as GCD(a, b) where a and b are the numbers being considered.

How do you find the greatest common divisor?

The easiest way to find the greatest common divisor is to list out all the factors of the numbers being considered and then find the largest number that appears in all of these lists. Another method is to use the Euclidean algorithm, which involves repeatedly dividing the larger number by the smaller number until the remainder is 0.

What is the difference between greatest common divisor and least common multiple?

The greatest common divisor is the largest number that divides evenly into two or more numbers, while the least common multiple is the smallest number that is a multiple of two or more numbers. In other words, the GCD is a divisor of the numbers, while the LCM is a multiple of the numbers.

Why is the greatest common divisor useful?

The greatest common divisor is useful in many mathematical and practical applications. It is commonly used in simplifying fractions, finding equivalent fractions, and solving certain types of equations. It can also be used in real-life scenarios, such as determining the smallest amount of material needed to evenly divide into a given number of objects.

Can the greatest common divisor be a negative number?

No, the greatest common divisor is always a positive number. This is because it is a common divisor of two or more numbers, and negative numbers cannot be divided evenly into positive numbers. If one or both of the numbers being considered is negative, the greatest common divisor is still positive.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
902
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Replies
19
Views
4K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
6
Views
774
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
Replies
5
Views
2K
Back
Top