Problem
Alice and Bob play the following game.They choose a number N to play with.The runs are as follows :
1.Bob plays first and the two players alternate.
2.In his/her turn ,a player can subtract from $N$ any prime number less than $N$ or the number 1. The result thus obtained is the new $N$.
3.The person who cannot make a move in his/her turn loses the game.
Assuming both play optimally, who wins the game?
The answer is if $N \equiv 1 \pmod{4}$, then "Alice" will win, otherwise Bob. But I couldn't prove it mathematically correct. The way I obtain this answer is just bruteforce for some particular $N$. I noticed several rules but I just can't find a way to deduce from there. Here is what I have:
If $N = P + 1$, where $P$ is prime, then whoever take this turn will win.
If $N = 5$, then whoever takes this turn will lose.
The biggest problem I'm facing is primes
because there is no general rule to generate one. I wonder could anyone shed me some light on this problem? Any suggestion would be greatly appreciated.