IMO Team Selection Test 2

If $n=1$, all choices of $a$ and $b$ are solutions. Now suppose that $n>1$ and let $p$ be a prime divisor of $n$. Let $k$ be the number of factors of $p$ in $n$. We give a condition for $a$ and $b$ modulo $p^k$ which guarantees that $p^k\mid 4a^2+9b^2-1$. By doing this for every prime divisor of $n$, we get a system of conditions for $a$ and $b$ modulo the various prime powers. Then, by the Chinese remainder theorem, there exist $a$ and $b$ satisfying all conditions simultaneously.

If $p\ne 2$, then we consider the condition that $2a\equiv 1(\mathrm{mod}{p}^k)$ and $b\equiv 0(\mathrm{mod}{p}^k)$. As $2$ has a multiplicative inverse modulo $p^k$, this condition can be satisfied. We then have $$4a^2+9b^2-1=(2a{)}^2+9b^2-1\equiv 1^2+9\cdot 0-1=0(\mathrm{mod}{p}^k).$$ Therefore all $a$ and $b$ satisfying this condition are solutions.

If $p=2$, then we consider the condition that $a\equiv 0(\mathrm{mod}{2}^k)$ and $3b\equiv 1(\mathrm{mod}{2}^k)$. As $3$ has a multiplicative inverse modulo $2^k$, this condition can be satisfied. We then have $$4a^2+9b^2-1=4a^2+(3b{)}^2-1\equiv 4\cdot 0+1^2-1=0(\mathrm{mod}{2}^k).$$ Therefore all $a$ and $b$ satisfying this condition are solutions. $\square$