# Are there any real life applications of the greatest common divisor of two or more integers?

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

-

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)$.

-
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 (http://en.wikipedia.org/wiki/Missing_fundamental).

-

Err, reducing fractions?

gcd(391,544) = 17

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

-