Exercise 9. Determine the smallest integer $n \geqslant 2$ such that there exist strictly positive integers $a_{1}, \ldots, a_{n}$ such that

$$
a_{1}^{2}+\ldots+a_{n}^{2} \mid\left(a_{1}+\ldots+a_{n}\right)^{2}-1
$$
Solution to Exercise 9 Let's analyze the problem. In this problem, we are looking for the smallest integer $\mathrm{n}$ satisfying a certain property. Suppose we want to show that the smallest integer sought is the integer $c$. To show that it is indeed the smallest integer, we must on the one hand show that if an integer $n$ satisfies the property, then $\mathrm{n} \geqslant \mathrm{c}$, and on the other hand, we must show that we can find $\mathrm{c}$ integers satisfying the divisibility relation.

Since there is a divisibility relation, we can expect to use various ideas:

- If $a \mid \mathrm{b}$ then $a$ divides the linear combinations of $\mathrm{a}$ and $\mathrm{b}$
- If $a \mid b$ and $a$ and $b$ are strictly positive, then $a \mid b$
- If $a \mid \mathrm{b}$, the divisors of $a$ also divide $b$

Once this initial analysis is done, we can start by looking for integers $a_{i}$ satisfying the property for small values of $n$, for example for $n=2,3$ or even 4 if we are brave, before realizing that this method will not allow us to determine $n$.

However, having searched for $a_{i}$ for small values of $n$ allows us to find potential properties that the $a_{i}$ must satisfy. For example, we may have noticed that the integers $a_{i}$ cannot all be even, since in that case the sum of the $a_{i}^{2}$ would be even but $\left(a_{1}+\ldots+a_{n}\right)^{2}-1$ is odd. We then realize that what matters in this argument is not the parity of the $a_{i}$ but the parity of the sum.

We obtain that $a_{1}+a_{2}+\ldots+a_{n}$ is odd. Otherwise, since $a_{1}^{2}+a_{2}^{2}+\ldots+a_{n}^{2} \equiv a_{1}+a_{2}+\ldots+a_{n} \bmod 2, a_{1}+\ldots+a_{n}$ is also even, but then $a_{1}^{2}+\ldots+a_{n}^{2}$ is even and divides $\left(a_{1}+a_{2}+\ldots+a_{n}\right)^{2}-1$ which is odd, which is absurd.

We deduce that $\left(a_{1}+\ldots+a_{n}\right)^{2}-1$ is even. The previous parity argument invites us to refine this study. We will therefore look to see if $\left(a_{1}+\ldots+a_{n}\right)^{2}-1$ is divisible by $4,8 \ldots$ The presence of multiple squares invites us to look at each term with well-chosen moduli.

For example, modulo $4,\left(a_{1}+\ldots+a_{n}\right)^{2} \equiv 1$ so 4 divides $\left(a_{1}+\ldots+a_{n}\right)^{2}-1$. Let's not stop here; we also know that the squares of odd numbers can only be 1 modulo 8. Thus, $\left(a_{1}+\ldots+a_{n}\right)^{2}-1$ is divisible by 8. Since 8 is coprime with $a_{1}^{2}+\ldots+a_{n}^{2}$ which is odd, we deduce from all this that

$$
8\left(a_{1}^{2}+\ldots+a_{n}^{2}\right) \mid\left(a_{1}+\ldots+a_{n}\right)^{2}-1
$$

Another remark that we can make about the statement is that it involves the sum of squares of numbers on one side and the square of the sum of numbers on the other side. This makes one think of the Cauchy-Schwarz inequality, or the inequality of arithmetic and quadratic means. We can therefore try to compare the quantities $8\left(a_{1}^{2}+\ldots+a_{n}^{2}\right)$ and $\left(a_{1}+\ldots+a_{n}\right)^{2}-1$.

This idea of comparing the terms is consistent with what we are trying to show. The divisibility obtained gives that $8\left(a_{1}^{2}+\ldots+a_{n}^{2}\right) \leqslant\left(a_{1}+\ldots+a_{n}\right)^{2}-1$. In the arithmetic and quadratic means inequality, the square of the sum is smaller than the sum of the squares of the elements multiplied by the number of variables. We therefore suspect that the inequality obtained will be false for $n$ too small, which will provide the desired bound. More precisely,

$$
8\left(a_{1}^{2}+\ldots+a_{n}^{2}\right) \leqslant\left(a_{1}+\ldots+a_{n}\right)^{2}-1 \leqslant n\left(a_{1}^{2}+\ldots+a_{n}^{2}\right)-18$ so $\mathrm{n} \geqslant 9$.

Conversely, we are looking for 9 integers satisfying the property. We can expect that small integers will work. We can therefore look for $a_{i}$ equal to 1 or 2. Finally, we find that by taking $a_{1}=\cdots=a_{7}=1$ and $a_{8}=a_{9}=2$, we indeed have 15 dividing $11^{2}-1=120=15 \times 8$.

The expected answer is therefore $\mathrm{n}=9$.

Comment from the graders: The problem was solved by only one student. This is an instructive and very complete exercise, involving both arithmetic arguments and inequalities.

## Senior Exercises