There are $10^7$ stones on the desk. Two people take turns at taking out stones and they can take out any number of stones as long as the number is the format of $P^n$. Here $P$ is any prime number, and $n$ is any nonnegative integer. The person who takes the last stone wins. Is there a winning strategy for the first player?
I have tried the following:
(1) Per the $P^n$ rule, each player can take out 1, 2, 3, 4, or 5, but not 6 stones every time (the player can also take 7, 9, 11, 13, … stones).
(2)If there are just 1, 2, 3, 4, or 5 stones left, the player who moves next wins simply by taking all the stones.
(3) With 6 stones left, the player who moves next must leave 1, 2, 3, 4, or 5 stones in the pile and the current player (the one just moved) will be able to win. So leaving 6 stones to the opponent is a winning strategy for the current player.
(4) With 12 stones left, the player who moves next must leave 1, 3, 5, 7, 8, 9, 10, or 11 stones in the pile by taking 1, 2, 3, 4, 5, 7, 9, or 11 stones. The current player can then win by taking all stones (if there are less than 6 stones left) or by moving to the position with 6 stones left.
(5) So to win the game, we like to move into the target positions of leaving 0, 6 or 12 stones.
(6) How can I theorize that the winning strategy is to leave a multiple of 6 stones?
Hint
In order to prove that the winning strategy is to always leave a multiple of six stones, you need to show two things:
If the current number of stones is not a multiple of six, then there exists a move which makes it a multiple of six.
If the current number of stones is a multiple of six, then every move will leave a heap which is not a multiple of six.
This shows that a player who follows the strategy is never without a move, and therefore wins.
I think you should be able to prove both of these facts on your own. I've included a proof of the first bullet behind a spoiler block in case you get stuck. For the second bullet, all you need is some light number theory.