Problem

Source: INMO 2025/6

Tags: INMO 2025, quadratic residue, base system, construction



Let $b \geqslant 2$ be a positive integer. Anu has an infinite collection of notes with exactly $b-1$ copies of a note worth $b^k-1$ rupees, for every integer $k\geqslant 1$. A positive integer $n$ is called payable if Anu can pay exactly $n^2+1$ rupees by using some collection of her notes. Prove that if there is a payable number, there are infinitely many payable numbers. Proposed by Shantanu Nene