# Describe a strategy that lets you win this game of common divisors every time

I have this question in one of my assignments of a course(MIT 6042) that I am pursuing online. Question is as follows:

Here is a very, very fun game. We start with two distinct, positive integers written on a blackboard. Call them x and y. You and I now take turns. (I’ll let you decide who goes first.) On each player’s turn, he or she must write a new positive integer on the board that is a common divisor of two numbers that are already there. If a player can not play, then he or she loses. For example, suppose that 12 and 15 are on the board initially. Your first play can be 3 or 1. Then I play 3 or 1, whichever one you did not play. Then you can not play, so you lose.

(a) [6 pts] Show that every number on the board at the end of the game is either x, y, or a positive divisor of gcd(x, y).

(b) [6 pts] Show that every positive divisor of gcd(x, y) is on the board at the end of the game.

(c) [6 pts] Describe a strategy that lets you win this game every time.

I was able to solve part (a) as game involves writing only common divisors of x and y on the board, and gcd(x,y) is the smallest positive linear combination of x and y and thus can be expressed as sx+ty. Further, a common divisor of x and y divides all linear combinations of x and y and thus divides gcd(x,y).

Part(b) was rather trivial I suppose, though I am not sure, as game involves writing all common divisors of x and y and they divide gcd(x,y) as well as proved in part(a).

Main issue is with part (c). Solution I proposed is that if number of common divisors of x and y is even then let the other player start the game and if it is odd then I should start the game. However this solution seems too trivial as well and I suppose they wouldn't put it in the assignment if it was that simple.

Can anyone tell if there is anything wrong with any of my solutions and if there is a more refined solution to part(c).

In principle, your answer to part (c) is correct. However, it can be simplified and expressed more nicely: The number of divisors of a natural number $n$ is odd if and only if $n$ is a perfect square (because all divisors $\ne\sqrt n$ come in pairs). Therefore, your winning strategy consists in deciding who makes the first move based on whether or not $\gcd(x,y)$ is a perfect square.