Using parity to determine the answer for the given problem

Let $n$ be an integer greater than 0. The numbers $1, 2, 3, \ldots, n$ are written on a blackboard. We decide to erase from the blackboard any two numbers, and replace them with their nonnegative difference. After this is done several times, a single number remains on the blackboard. For which values of $n$ can this number equal 0?

Trying on small cases, I think that the last number that remains can be 0 only when n is a multiple of 4. I tried using parity to prove that the last number that remains and n are of the same parity. Can someone help me out with it?

• Unless I don't understand something, the list 1,2,3 can have 2 and 3 erased and replaced with 1. Then 1 and 1 are erased to give 0. This would be a counterexample to your claim $n$ must be a multiple of 4. – Laars Helenius Jun 5 '16 at 2:14
• Yes you are correct. I realize my mistake now. Thank you. – Gayatri Jun 5 '16 at 3:41

Key Observation

Parity of the sum of the numbers written on the board stays unchanged. Because, at each step you are turning $x,y$ into $|x-y|$ and $x+y\equiv x-y\equiv y-x\pmod2$ .

Necessary condition

In order to have the last number to be $0$, you need the sum of the numbers written in the beginning to be even. So, we want $$1+2+\ldots+n=\frac{n(n+1)}2$$ to be even. Notice, this happens iff $n\equiv 0,3\pmod4$.

To see this condition is sufficient, try to play with the numbers to get $0$ at the end. You said you did it for $4$. For $3$, $$1,(2,3)\mapsto1,(1)\mapsto 0$$ works.

Suppose you can get $0$ for $n$. Then, you can get $0$ for $n+4$ by repeating the same steps for the first $n$ numbers to get $$0,n+1,n+2,n+3,n+4$$ and then making $$n+4,n+2\mapsto 2\qquad n+3,n+1\mapsto 2\qquad 2,2\mapsto 0\qquad 0,0\mapsto 0$$

So, by induction, you can do it for any $n\equiv 0,3\pmod4$

• Pair the numbers $(2,3)$, $(4,5)$ etc. to get $(n+1)/2$ ones or the numbers $(1,2)$, $(3,4)$ etc. to get $n/2$ ones. If $(n+1)/2$ or $n/2$ is an even natural number, you can thus get zero. – Aravind Jun 5 '16 at 2:19