## Problem 10.3. (Problem for the Atanas Radev award)

Find all natural numbers $n$ such that: If $a$ and $b$ are natural numbers and $n$ divides $a^{2} b+1$, then $n$ divides $a^{2}+b$.


Solution: Obviously the condition holds for $n=1$ and suppose $n \geq 2$. Let $a$ be a natural number coprime to $n$. It follows from Bezout's Theorem that there exists a natural number $b$ such that $a^{2} b+1$ is divisible by $n$. Further, $n$ divides $a^{2}+b$ and since $a^{4}-1=$ $a^{2}\left(a^{2}+b\right)-\left(a^{2} b+1\right)$, it follows that $n$ divides $a^{4}-1$.

Let $n=2^{\alpha} k$, where $k$ is an odd number and $\alpha \geq 0$. Suppose $k \geq 3$. Then $n$ and $k-2$ are coprime and therefore $2^{\alpha} k$ divides $(k-2)^{4}-1$, so $k$ divides 15 . Hence $n$ is of the form $n=2^{\alpha} \cdot 3^{\beta} \cdot 5^{\gamma}$, where $\alpha \geq 0,0 \leq \beta, \gamma \leq 1$. Consequently $n$ divides $11^{4}-1$ and we conclude that $\alpha \leq 4$.

It is easy to see now that $n$ divides $2^{4} \cdot 3 \cdot 5=240$.

Conversely, let $n$ be a divisor of 240 . Then $n$ satisfies the condition of the problem. Indeed, if 3 divides $a^{2} b+1$, then 3 divides both $a^{2}-1$ and $a^{2}+1$ and therefore 3 divides $a^{2}+b$. Similarly, if 5 divides $a^{2} b+1$, then 5 divides $a^{2}+b$. If we can show that the
same property holds for $2,4,8$ and 16 , we will be done. Assume $2^{k}$ divides $a^{2} b+1$, where $1 \leq k \leq 3$. Then $a$ is an odd integer number and therefore $a^{2}-1$ is divisible by 8 . Consequently $b+1$ is divisible by $2^{k}$ and thus $a^{2}+b$ is divisible by $2^{k}$ as well. Assume 16 divides $a^{2} b+1$. Then $a$ is an odd integer number and it is easy to verify that $a^{2}$ is congruent to 1 or 9 modulo 16 . Further, $b$ should be congruent to 15 or 7 modulo 16 correspondingly and again $a^{2}+b$ is divisible by 16 .

The required numbers are all divisors of 240 .

