I solved these two problems from a programming challenge website: numgame and numgame2.
These two problems are very similar. In the first one, the position is a number $n$ and each player can subtract from $n$ a divisor $d$ of $n$ with $1 \leq d < n$. Players Alice and Bob alternate with Alice going first and the first person unable to move loses. The second problem is similar except each player can subtract a prime number $p$, or 1, from the current position $n$, with $p < n$ ($p$ is not necessarily a divisor of $n$). We assume that the players play optimally and, as usual, ask who the winner is given the initial value of $n$.
The claim is that in the first game Alice wins if $n \equiv 0 \pmod{2}$ and Bob wins if $n \equiv 1 \pmod{2}$, while in the second game Alice wins if $n \equiv 1 \pmod{4}$ and Bob wins otherwise.
I'm looking for someone to give me a proof of these answers, or some hints to start.