Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for real life applications of gcd. I have found one with tiles but there must be many more of these type.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

Suppose that you have have two sets of people of cardinalities m,n and you want to divide them into teams of k people with every team being composed of people of only one of the original two sets. Then the maximum value of k where this is possible is $\gcd (m,n)$.

In fact if it is possible to do this with a specific k. Then $k |\gcd(m,n)$.

share|improve this answer
3  
Or, suppose you have a Chinese army, and when they're in different formations, some are left over, and... –  Eric Tressler Jun 29 '13 at 7:56
    
Might I ask why? Sorry if I am too stupid. –  awllower Jul 3 '13 at 10:37
    
You want teams of k people and you want everyone to play. If every team is to be made up of players of only one of the initial sets then k divides m (so everyone in the set of size m plays) and k divides n (so everyone in the set of size n plays). Therefore k|n and k|m. The largest number satisfying this is the gcd. –  user4140 Jul 3 '13 at 10:44
    
Excuse me, but I am really stucked. Why $k\mid m$? I think this is the only point I cannot understand now. As far as I know, the assumption implies that there are some numbers $\le k$ such that their sum is $m$? Am I mis-understanding something? Thanks. –  awllower Jul 4 '13 at 14:46
    
no, there are no numbers. There are simply m persons. and they need to be divided into teams of k people. there also exists another group of n people that also needs to be divided into teams of k people. it is clear that k divides m from the first requisite and it is also clear that k divides n from the second requisite. –  user4140 Jul 4 '13 at 15:52
add comment
  1. Finding inverses in modular arithmetic is an application of Euclid's algorithm, which is essentially be an application of the concept of gcd (look up RSA for why it's important in real life).

  2. The missing fundamental (http://en.wikipedia.org/wiki/Missing_fundamental).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.