two elementary games in number theory 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.
 A: Hint for the first problem: If the current position $n$ is even and it's Alice's turn, can she always make a move into an odd position? If the current position $n>1$ is odd and it's Bob's turn, what can you prove about the parity of the position he must move into?
A: Second Problem:
Bob can never change a number of the form $4k+1$ into a number of the same form (primes and 1 tend to be not divisible by 4).
Alice can always change a number not of this form  into a number of this form by substracting 1,2 or 3 as needed.
A: Hint for the first problem: Who wins if $n=2$, who wins if $n=1$? If $n$ is even, can Alice assure that after 2 turns (one turn by Alice and one by Bob) the number is still even?
A: 1st Game
1) let n = value of current position.
2) n = 1 x n, so n is always divisible by 1
3) if n is even, Alice can always subtract 1 leaving Bob with odd value n
4) an odd number has no even divisors since if n/2a = b, then n = 2ab and is even.
5) if n is odd, Bob must always leave Alice with an even value n since all divisors are odd and he must subtract an odd number from n, while the difference between 2 odd numbers must always be even ((2x+1)-(2y+1) = 2(x-y)).
6) thus, by 3) & 5) with each subsequent pair of turns, Alice can always leave Bob with a smaller odd number position n.
7) This strategy leads to a descent that eventually must leave Bob with the odd position n = 1, and he loses.  The descent could be hastened by Alice if she chose the largest odd divisor to subtract instead of 1 (which is the smallest) when it was her turn.
