Greatest common divisor


by matqkks
Tags: maths, number theory
matqkks
matqkks is offline
#1
Jun29-13, 02:43 AM
P: 150
Are there any real life applications of the greatest common divisor of two or more integers?
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
Simon Bridge
Simon Bridge is offline
#2
Jun29-13, 03:08 AM
Homework
Sci Advisor
HW Helper
Thanks ∞
PF Gold
Simon Bridge's Avatar
P: 11,009
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.
rexregisanimi
rexregisanimi is offline
#3
Jun29-13, 03:15 PM
P: 28
There are a whole bunch. I use the idea regularly so it is difficult to point to a specific thing...

Simon Bridge
Simon Bridge is offline
#4
Jun29-13, 10:58 PM
Homework
Sci Advisor
HW Helper
Thanks ∞
PF Gold
Simon Bridge's Avatar
P: 11,009

Greatest common divisor


Quote Quote by rexregisanimi View Post
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?
Permanence
Permanence is offline
#5
Jun30-13, 12:04 AM
P: 48
Here take a look at this Wikipedia article.
https://en.wikipedia.org/wiki/Euclidean_algorithm

Besides all the mathematical applications, I'm sure that you must sometimes call upon the GCD when shopping or possibly even cooking.
rcgldr
rcgldr is offline
#6
Jun30-13, 04:29 AM
HW Helper
P: 6,925
Quote Quote by matqkks View Post
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
dm164
dm164 is offline
#7
Jun30-13, 07:15 AM
P: 21
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.
economicsnerd
economicsnerd is offline
#8
Jul8-13, 01:58 PM
P: 207
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?
Simon Bridge
Simon Bridge is offline
#9
Jul9-13, 12:51 AM
Homework
Sci Advisor
HW Helper
Thanks ∞
PF Gold
Simon Bridge's Avatar
P: 11,009
@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 text books no longer have examples like that these days?
rcgldr
rcgldr is offline
#10
Jul9-13, 03:16 AM
HW Helper
P: 6,925
Quote Quote by economicsnerd View Post
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"?
economicsnerd
economicsnerd is offline
#11
Jul9-13, 12:19 PM
P: 207
Quote Quote by rcgldr View Post
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}.
Stephen Tashi
Stephen Tashi is offline
#12
Jul9-13, 03:55 PM
Sci Advisor
P: 3,175
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.


Register to reply

Related Discussions
Greatest common divisor. Calculus & Beyond Homework 5
greatest common divisor Calculus & Beyond Homework 1
Greatest Common Divisor General Math 1
greatest common divisor Calculus & Beyond Homework 24
greatest common divisor Calculus & Beyond Homework 19