# Euclid's Game on a Square Grid

The game starts with two integers selected randomly on a square grid. The players (of which the computer is one) take turns picking up two of the already selected numbers and marking the difference between the larger and the smaller of the two, provided of course that number has not been marked previously. The player unable to move loses the game.

As you play against the computer, you may force it to make the first move by pressing "You start" button.

(This is a reincarnation of Euclid's Game, as proposed at Let's Play Math blog.)

What if applet does not run? |

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

The underlying idea of the game is Euclid's algorithm for finding the greatest common divisor (or factor) of two positive integers. It can be expressed in algorithmic form:

function gcd(N, M) { if M is 0 return N otherwise return gcd(M, N mod M) } |

For example, let N = 40 and M = 12. Euclid's algorithm is expressed in terms of modulo arithmetic.

Then, on the first step, 40 ≡ 4 (mod 12), giving

On the second step, 12 ≡ 0 (mod 4), giving

With M = 0, the algorithm returns 4 as the gcd of 12 and 4 and of 40 and 12.

How this relates to the game. Assume it starts with 40 and 12 marked. Whoever plays now has only one choice - the difference

4 is the smallest number to appear on the board and, when the game is over, all its multiples below 40 will be marked.

A longer way to implement Euclid's algorithm is to keep subtracting the smaller of the two numbers from the larger one until one of them becomes 0, at which point the remaining non-zero number is the greatest common factor of the original pair.

function gcd(N, M) { if N is greater than M return gcd(N - M, M) else if M is greater than N return gcd(M - N, N) otherwise return M } |

So, almost as in the game, with N = 40 and M = 12, we have successively

gcd(40, 12) | = gcd(28, 12) = gcd(16, 12) = gcd(12, 4) | |

= gcd(8, 4) = gcd(4, 4) = 4. |

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

63219126 |