Problem 3. Vasya wants to find all integers $a$ such that the expression $10 n^{3}+3 n^{5}+7 a n$ is divisible by 15 for all integers $n$. What remainders can the number $a$ give when divided by 15? Provide all possible answers or prove that there are no such integers $a$.
Answer: 11.

Solution. First, let's show that $n^{3} \equiv n(\bmod 3)$ and $n^{5} \equiv n(\bmod 5)$ for any natural $n$. This can be done in several ways. We will present only three of them.

First method. We will divide all natural numbers into groups based on their remainders when divided by 3 and 5:

| $n$ | $n^{3}$ | $n^{3} \bmod 3$ |
| :---: | :---: | :---: |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 8 | 2 |


| $n$ | $n^{5}$ | $n^{5} \bmod 5$ |
| :---: | :---: | :---: |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 32 | 2 |
| 3 | 243 | 3 |
| 4 | 1024 | 4 |

From the table, it is clear that the statement to be proved is true.

Second method. Note that $n^{3}-n=(n-1) n(n+1)-$ is the product of three consecutive integers, and

$$
n^{5}-n=(n-1) n(n+1)\left(n^{2}+1\right) \equiv(n-1) n(n+1)\left(n^{2}-4\right)=(n-2)(n-1) n(n+1)(n+2) \quad(\bmod 5)
$$

- is the product of five consecutive integers. In the first case, the expression is always divisible by 3, and in the second case, by 5, which is what we needed to prove.

The third method is to say that these statements are special cases of Fermat's Little Theorem for $3$ and $5$.

Now let's look at the original expression modulo 3:

$$
10 n^{3}+3 n^{5}+7 a n \equiv 10 n+7 a n \equiv(a+1) \cdot n \quad(\bmod 3)
$$

This expression is divisible by 3 for any integer $n$ if and only if $a+1$ is divisible by 3, i.e., when $a$ gives a remainder of 2 when divided by 3. Similarly, $10 n^{3}+3 n^{5}+7 a n \equiv(2 a+3) \cdot n(\bmod 5)$, i.e., $2 a+3$ is divisible by 5, so $a$ gives a remainder of 1 when divided by 5.

Thus, $a \equiv 2(\bmod 3)$ and $a \equiv 1(\bmod 5)$, i.e., $a \equiv 11(\bmod 15)$.

Another solution. Substitute $n=1$ and we get that if such an $a$ exists, then $13+7 a$ must be divisible by 15, i.e., $a$ must give a remainder of 11 when divided by 15. It remains to check that if $a \equiv 11(\bmod 15)$, then the given expression is divisible by 15 for any natural $n$. This can be done in many ways (see, for example, the first solution). Here we will present another one.

We will prove this statement by induction on $n$ (for $n=0$ the divisibility is obvious, for negative $n$ it is proved similarly or reduced to the case of positive $n$ by replacing $n \rightarrow-n$). If $n=1$, the statement is already verified. Suppose now that we have already proved that $10 n^{3}+3 n^{5}+7 a n$ is divisible by 15 and we will prove that $10(n+1)^{3}+3(n+1)^{5}+7 a(n+1)$ is also divisible by 15. Let's look at the difference between these two expressions:

$10\left((n+1)^{3}-n^{3}\right)+3\left((n+1)^{5}-n^{5}\right)+7 a((n+1)-n)=10\left(3 n^{2}+3 n+1\right)+3\left(5 n^{4}+10 n^{3}+10 n^{2}+5 n+1\right)+7 a$.

After expanding the brackets, all terms on the right side, except for $10+3+7 a$, are divisible by 15, but $13+7 a$ is divisible by 15, since $a \equiv 11(\bmod 15)$.