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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 4 down vote accepted

Suppose that you 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|cite|improve this answer
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. – Carry on Smiling 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. – Carry on Smiling Jul 4 '13 at 15:52
  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 (

share|cite|improve this answer

Err, reducing fractions?

gcd(391,544) = 17

391/544 = 17*23 / 17*32 = 23/32

share|cite|improve this answer

Your Answer


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.