 Euclid game

A Euclid game is an impartial game based on subtraction steps of the Euclidean algorithm.^[ref] Here use the following normal-play convention: a position is an ordered pair $0\le a\le b$; if $a>0$, remove a positive multiple $ka\le b$ from $b$ and reorder. A position with $a=0$ has no legal move and is losing. Thus moving to a zero coordinate wins; variants that instead stop at equal positive coordinates require a different endpoint convention.

The sum of the coordinates strictly decreases, so every play terminates. If $a$ divides $b$, subtract $b$ and win immediately. If $a<b<2a$, there is only one move, to $(b-a,a)$, so the position has the opposite winning status from that successor.

If $b=qa+r$ with $q\ge 2$ and $0<r<a$, two legal choices leave $(r,a)$ or $(a,a+r)$. The latter has exactly one move, to the former, so exactly one of these two successors is losing. Choose it. For example, $(2,3)$ is losing because its only move reaches $(1,2)$, where the opponent takes the whole larger coordinate. From $(2,5)$, subtract $2$ to leave that losing position. These cases give a recursive strategy without exploring every subtraction amount.