Euclid's Game

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Buy this applet
What if applet does not run?

The game is really very simple. It helps clarify the Euclid's algorithm and the notion of the Greatest Common Divisor of two integers. The difference of any two numbers is divisible by their gcd. Assuming the two original numbers are N and M and N > M (In the applet they are never equal.) Then the only numbers that could be obtained by taking differences are the multiples of gcd(N, M). Furthermore, all such numbers will eventually appear on the board regardless of the sequence of moves (why?). Therefore, the total number of integers that will be written on the board equals N/gcd(N, M). From here you may calculate whether it's preferable to start or let the computer make the first move.

(The game may be played on a square grid, see a Java implementation for example.)

Assume the game is over - it's impossible to add a new difference. Let a be the smallest number present. Then the collection of the numbers on the board coincides with the set A of all multiples of a not exceeding the largest of M and N. The proof is very similar to the way we established a fundamental property of gcd.

First of all, both a|N and a|M. If, for example, N = na + b, then we could form differences N - a, N - 2a, etc. and eventually get on the board b < a which would contradict the minimality of a. Therefore, for some n and m, N = na and M = ma. So what we have on the board is A = {ia: i = 1,... , max(n, m)}. Now recollect that a|gcd(N, M). On the other hand, as we already remarked, the difference of any two numbers is divisible by their gcd. Therefore, and number on the board is divisible by gcd(N, M). In particular, gcd(N, M)|a. Therefore, a = gcd(N, M).

Another way to explain this stems directly from the Euclid's algorithm. Assuming N > M, the first step is to form N = sM + r. Note that, sooner or later, r would appear on the board since it could be obtained by repeatedly subtracting M first from N and then from thus obtained numbers. The second step in the algorithm is to continue with M = tr + u. Having both M and r on the board and proceeding with taking differences we will eventually get u as well. Clearly we can now continue in this manner until the algorithms stops and gcd(N,M) has been found.

49551835