Determine the strictly positive integers $n$ such that for any integer $k$, there exists an integer $a$ such that $n$ divides $a^{3}+a-k$.
Let $p$ be a prime divisor of $n$, we obtain that the polynomial $X^{3}+X-k$ has a root for any $p$. In particular, modulo $p$ the function that maps $x$ to $x^{3}+x$ is surjective, and thus also injective by cardinality: $c^{\prime}$ is a bijection modulo $p$. Thus, since $0^{3}+0 \equiv 0(\bmod p)$, we know that $\left\{x^{3}+x \mid x \in\{1, \ldots, p-1\}\right\}$ viewed modulo $p$ is $\{1, \ldots, p-1\}$. Note that this is false if $p=2$, so we will assume $p \geqslant 3$.

By taking the product, $(p-1)!\equiv \prod_{x=1}^{p-1} x\left(x^{2}+1\right)(\bmod p)$, so $\prod_{x=1}^{p-1}\left(x^{2}+1\right) \equiv 1(\bmod p)$.

It is known that $\prod_{a=1}^{\frac{p-1}{2}}\left(X-a^{2}\right)=X^{\frac{p-1}{2}}-1$. Indeed, there are $\frac{p-1}{2}$ quadratic residues modulo $p$, which are all roots of $X^{\frac{p-1}{2}}-1$ which is monic, so it factors as $\prod_{a=1}^{\frac{p-1}{2}}\left(X-a^{2}\right)$ (since the $a^{2}$ modulo $p$ are distinct as $a$ varies from 1 to $\frac{p-1}{2}$).

Now modulo $p, \prod_{a=1}^{\frac{p-1}{2}}\left(X-a^{2}\right)=\prod_{a=\frac{p+1}{2}}^{p-1}\left(X-a^{2}\right)$, so modulo $p, \prod_{a=1}^{p-1}\left(X-a^{2}\right)=\left(X^{\frac{p-1}{2}}-1\right)^{2}$. Evaluating at $-1, \prod_{a=1}^{p-1}\left(-1-a^{2}\right) \equiv\left((-1)^{\frac{p-1}{2}}-1\right)^{2}(\bmod p)$, so

$$
1 \equiv \prod_{x=1}^{p-1}\left(x^{2}+1\right) \equiv(-1)^{p-1}\left((-1)^{\frac{p-1}{2}}-1\right)^{2} \quad(\bmod p)
$$

The right-hand side is 0 or 4 modulo $p$, so $p$ divides -1 or 3. Thus $p=3$. We then obtain that every prime factor of $n$ is 3, so $n$ is a power of 3.

Conversely, if $n=1$ the result is clear, if $n=3$, the polynomial $P(X)=X^{3}+X$ is indeed surjective modulo 3 because $P(0)=0, P(1)=2$ and $P(2)=1$ modulo 3. Thus, for any integer $k$, the equation $P(a) \equiv k(\bmod 3)$ has a solution, and this solution satisfies $P^{\prime}(a) \equiv 3 a^{2}+1 \equiv 1 \equiv 0(\bmod 3)$, so by Hensel's lemma, the equation $P(x) \equiv k$ has a solution modulo $3^{j}$ for all $j \geqslant 1$: thus any power of 3 is indeed a solution.

The solutions $n$ are therefore exactly the powers of 3.

## 4 Inequalities (Martin)

One of the major challenges in algebra problems encountered in Olympiads is being able to estimate quantities and compare quantities with each other. This can be explicit in the statement ("prove the following inequality") or implicit, i.e., the search for a solution leads to comparing quantities. The tools at our disposal are the following.

- Classical inequalities: mean inequality, Cauchy-Schwarz, rearrangement, convexity.
- The triangle inequality: $|x-y| \leqslant|x-z|+|z-y|$.
- $x-1<\lfloor x\rfloor \leqslant x$.
- Algebraic manipulations: telescoping, adding/removing a quantity, in the case of a sum, grouping certain well-chosen terms of the sum together.

In Olympiad problems, knowledge of these inequalities alone is not enough. Success in a problem often depends on the ability to estimate an expression without being "too greedy". Let's illustrate this point with an example:

Take $x \in[0,1]$. To estimate $x^{2}$, there are several possibilities. For example, we can upper bound $x^{2}$ by 1, but we can also upper bound $x^{2}$ by $x$, which is more precise and allows us to retain "information" (for example, if the variables are related by a hypothesis). Thus, in addition to classical inequalities, one must learn to detect which upper/lower bound will be the most precise for the problem at hand.

A good indicator of whether you are being too greedy is the equality case of the inequality you are trying to estimate. Once you have the equality case in mind, ask yourself if the inequality you are applying preserves this equality case. If not, you are being too greedy. Thus, there is no point in lower bounding $x+1 / x$ by 2 if the equality case does not correspond to $x=1$.

Moreover, many problems asking to determine the reals satisfying an equality are in fact hidden inequalities! In this case, one must apply inequalities to our reals and show that the reals satisfy the equality case of the inequality you have applied.

Finally, it is not uncommon for a combinatorial or arithmetic argument to be necessary in the problem. One must be sensitive to this.

These abstract tips find their illustration in the exercises that follow (which are not ranked by difficulty).

## Exercises