Game theory: power and mod

Question

Given two non negative integers $a, b$. Two players alternate turns. If at any state of the game the two integers are $a\le b$ then the player with the turn can either replace $b$ with $b\bmod a$ or $b-a^k\ge 0$ where $k$ is any positive integer chosen at that turn. The first player to yield a $0$ wins (if one of initial values is $0$ the player $1$ wins). Under what conditions on $a, b$ shall player $1$ have a winning strategy?

Answer 1

Firstly, let me say that for consistency, it would make sense if player 1 loses if one of the initial values is $0$. Imagine the position were, say, "$1,5$" and Alice is to move, then Alice could win by replacing $5$ with $5\text{ mod }1=0$. If we allowed the game to go on for one more step, then Alice's opponent could be faced with $0,1$ and would have lost. I will follow the convention that player 1 loses if the game starts with a $0$ in the discussion below.

Well, the important thing about simple combinatorial games like this is that the position is a win for the second player precisely if all of the pairs the player can move to are wins for the first player. Since there are no pairs to move to if 0 is in the pair, those are "wins for second" (not wins for first). Since a positive pair with a 1 in it, or with both numbers the same, necessarily has a move to a position with a 0, those are all wins for first, etc.

Using white squares to mark wins for the second player and black squares to mark wins for the first player, we get something like this for small pairs: $$\begin{matrix} &0&1&2&3&4&5&6&7&8&9\\ 0& \square & \square & \square & \square & \square & \square & \square & \square & \square & \square \\ 1& \square & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ 2& \square & \blacksquare & \blacksquare & \square & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \square \\ 3& \square & \blacksquare & \square & \blacksquare & \square & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ 4& \square & \blacksquare & \blacksquare & \square & \blacksquare & \square & \square & \blacksquare & \blacksquare & \blacksquare \\ 5& \square & \blacksquare & \blacksquare & \blacksquare & \square & \blacksquare & \square & \square & \square & \blacksquare \\ 6& \square & \blacksquare & \blacksquare & \blacksquare & \square & \square & \blacksquare & \square & \square & \square \\ 7& \square & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \square & \square & \blacksquare & \square & \square \\ 8& \square & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \square & \square & \square & \blacksquare & \square \\ 9& \square & \blacksquare & \square & \blacksquare & \blacksquare & \blacksquare & \square & \square & \square & \blacksquare \\ \end{matrix}$$ The rows for 0 and 1 and the main diagonal are what I described, but the rest is a little complicated. To get a broader picture of what's going on, we can use a computer, telling it what the moves are for a pair, and that a move is a win for the second player if all the moves are to first player wins, and a win for first player otherwise.

Here is a computer-generated table for pairs with max up to 100:

This looks pretty complicated. For fun, here's up to 1000:

Since these images are complicated, I doubt there's going to be a very nice formula/characterization. They remind me of Whythoff's game, where the corresponding image is basically two lines of dots that hug lines with irrational slopes.