augustin_p wrote: Numbers $1, 2,\ldots, n$ are written on the board. By one move, we replace some two numbers $ a, b$ with the number $a^2-b{}$. Find all $n{}$ such that after $n-1$ moves it is possible to obtain $0$. $\color{blue}\boxed{\textbf{Answer: n}\equiv \textbf{0(mod 4) and n}\equiv \textbf{3(mod 4)}}$ $\color{blue}\boxed{\textbf{Proof:}}$ $\color{blue}\rule{24cm}{0.3pt}$ Let us first note that: $$a^2-b\equiv a-b\equiv a+b \pmod{2}$$$$\Rightarrow \text{The sum is maintained in modulo 2}$$$$\Rightarrow 1+2+3+\ldots +n\equiv 0 \pmod{2}$$$$\Rightarrow 2|\frac{n(n+1)}{2}$$$$\Rightarrow 4|n(n+1)$$$$\Rightarrow n\equiv 0 \pmod{4} \text{ or } n\equiv 3\pmod{4}$$Now we will prove by induction that all $n\equiv 0 \pmod{4} \text{ or }n\equiv 3 \pmod{4}$ satisfy: $\boxed{\text{Base cases:}}$ $\boxed{n=3}:$ $$1 \text{ , }2\text{ , }3$$$$1 \text{ , }2^2-3$$$$1\text{ , }1$$$$1^2-1$$$$0 _\surd$$$\boxed{n=4}:$ $$1\text{ , }2\text{ , }3\text{ , }4$$$$1\text{ , }2\text{ , }3^2-4$$$$1\text{ , }2\text{ , }5$$$$1\text{ , }2^2-5$$$$1\text{ , }-1$$$$(-1)^2-1$$$$0_\surd$$$\boxed{\text{Inductive hypothesis:}}$ Suppose that it is possible up to $n=4k$ for multiples of $4$ and up to $n=4k-1$ for multiples of $4$ plus $3$, $\forall k\le t$ $\boxed{\text{Inductive step:}}$ it is enough to prove that it is possible to go from $4n \to 4n+4$ $$n\text{ , }n-1\text{ , }n-2\text{ , }n-3\text{ , }n-4\text{ , }\ldots$$$$(n-1)^2-n\text{ , }n-2\text{ , }n-3\text{ , }n-4\text{ , }\ldots$$$$n^2-3n+1\text{ , }n-2\text{ , }n-3\text{ , }n-4\text{ , }\ldots$$$$(n-2)^2-(n^2-3n+1)\text{ , }n-3\text{ , }n-4\text{ , }\ldots$$$$-n+3\text{ , }n-3\text{ , }n-4\text{ , }\ldots$$$$(-n+3)^2-(n-3)\text{ , }n-4\text{ , }\ldots$$$$(n-3)(n-4)\text{ , }n-4\text{ , }\ldots$$$$(n-4)^2-(n-3)(n-4)\text{ , }\ldots$$$$n-4\text{ , }\ldots$$$$\Rightarrow \text{Induction is complete}$$ $$\Rightarrow \boxed{n\equiv 0 \pmod{4} \textbf{ and } n\equiv 3\pmod{4} \textbf{are the only solutions}}_\blacksquare$$$\color{blue}\rule{24cm}{0.3pt}$