We write on the board the equality:

$$
(x-1)(x-2) \ldots(x-2016)=(x-1)(x-2) \ldots(x-2016) .
$$

We want to erase some of the 4032 factors in such a way that the equation on the board has no real solutions. What is the minimum number of factors that must be erased to achieve this?

## Solution of the exercises

## Translation of the solution

To solve this problem, we need to ensure that the equation on the board has no real solutions after erasing some factors. Let's analyze the given equation:

$$
(x-1)(x-2) \ldots(x-2016) = (x-1)(x-2) \ldots(x-2016).
$$

This equation is always true for any \( x \) because both sides are identical. To make the equation have no real solutions, we need to ensure that the left-hand side (LHS) and the right-hand side (RHS) are never equal for any real \( x \).

One way to achieve this is to make the LHS and RHS different polynomials. We can do this by erasing different sets of factors from each side. Specifically, we need to ensure that the remaining polynomials on both sides do not have any common roots.

Consider the polynomial on the left-hand side:

$$
P(x) = (x-1)(x-2) \ldots (x-2016).
$$

If we erase \( k \) factors from \( P(x) \), the remaining polynomial will be:

$$
P_1(x) = (x-a_1)(x-a_2) \ldots (x-a_{2016-k}),
$$

where \( a_1, a_2, \ldots, a_{2016-k} \) are the roots that remain.

Similarly, if we erase \( k \) factors from the right-hand side, the remaining polynomial will be:

$$
P_2(x) = (x-b_1)(x-b_2) \ldots (x-b_{2016-k}),
$$

where \( b_1, b_2, \ldots, b_{2016-k} \) are the roots that remain.

To ensure that \( P_1(x) \neq P_2(x) \) for any real \( x \), we need to ensure that the sets of roots \( \{a_1, a_2, \ldots, a_{2016-k}\} \) and \( \{b_1, b_2, \ldots, b_{2016-k}\} \) are disjoint. This means that we need to erase at least 2016 factors in total (1008 from each side) to ensure that the remaining polynomials have no common roots.

Therefore, the minimum number of factors that must be erased is:

$$
\boxed{2016}
$$
If there remains a factor $x-1$ on the right and one on the left, then the equation admits 1 as a solution, and the same applies to the other factors. Therefore, at least one $x-1$ must be erased, at least one $x-2$, etc., which means at least 2016 factors must be erased.

It remains to show that it is possible to erase exactly 2016 numbers. One way to do this is to erase $x-i$ on the left if $i$ is congruent to 0 or 1 modulo 4, and on the right if $i$ is congruent to 2 or 3 modulo 4.

## 4 Group $\mathrm{D}$ : arithmetic

## 1 Wednesday 17 morning : Matthieu Lequesne

Definition 16. Let $x \in \mathbb{Z}$. We say that $x$ is a quadratic residue modulo $p$ (or that $\bar{x}$ is a quadratic residue in $\mathbb{Z} / p \mathbb{Z}$) if $x$ is not divisible by $p$ and if $\bar{x}$ is the square of an element of $\mathbb{Z} / p \mathbb{Z}$.

We denote $\left(\frac{x}{p}\right)=1$ if $x$ is a quadratic residue modulo $p$, $\left(\frac{x}{p}\right)=0$ if $p \mid x$, and $\left(\frac{x}{p}\right)=-1$ otherwise. The symbol $\left(\frac{x}{p}\right)$ is called the Legendre symbol.

Theorem 17 (Euler's Criterion). Let $p$ be an odd prime, and $x \in(\mathbb{Z} / p \mathbb{Z})^{*}$. Then $x$ is a quadratic residue if and only if $x^{\frac{p-1}{2}}=\overline{1}$. Otherwise, we have $x^{\frac{p-1}{2}}=-\overline{1}$.

Proof. Let's start by counting the quadratic residues of $(\mathbb{Z} / p \mathbb{Z})^{*}$. Let $x$ be a quadratic residue, say $x=y^{2}$ with $y \in(\mathbb{Z} / p \mathbb{Z})^{*}$. We then also have $x=(-y)^{2}$, but $y \neq -y$ since $p$ is odd, so $x$ is the square of at least two elements of $(\mathbb{Z} / p \mathbb{Z})^{*}$. In fact, it is the square of exactly two elements, because the polynomial $X^{2}-x$ is of degree 2, and thus has at most two roots in $\mathbb{Z} / p \mathbb{Z}$. Since $(\mathbb{Z} / p \mathbb{Z})^{*}$ has $p-1$ elements, and since each quadratic residue is the square of exactly two of these elements, we deduce that there are exactly $\frac{p-1}{2}$ quadratic residues.

All these quadratic residues satisfy $x^{\frac{p-1}{2}}=\overline{1}$, since writing $x=y^{2}$, we get $x^{\frac{p-1}{2}}=y^{p-1}=\overline{1}$, by Fermat's little theorem. It remains to show that these are the only ones. But the polynomial $X^{\frac{p-1}{2}}-\overline{1}$ has at most $\frac{p-1}{2}$ roots in $\mathbb{Z} / p \mathbb{Z}$, and all the quadratic residues, which are $\frac{p-1}{2}$ in number, are roots of it. Therefore, these are the only roots, which concludes the first part of the theorem.

To prove the second part, it suffices to show that the function $f(x)=x^{\frac{p-1}{2}}$ takes only the values $\overline{1}$ and $-\overline{1}$ when $x$ runs through $(\mathbb{Z} / p \mathbb{Z})^{*}$. But $f(x)^{2}=x^{p-1}=\overline{1}$, so the values taken by $f$ on $(\mathbb{Z} / p \mathbb{Z})^{*}$ are square roots of 1: these are $\overline{1}$ and $-\overline{1}$.

This proof, or at least the first paragraph, is worth knowing, as it provides information on the distribution of quadratic residues: their number, and the fact that each is the square of exactly two elements. From this, we can deduce, for example, that $1^{2}, 2^{2}, \ldots,\left(\frac{p-1}{2}\right)^{2}$ form a complete set of representatives of the quadratic residues of $\mathbb{Z} / p \mathbb{Z}$, because they are $\frac{p-1}{2}$ in number and are pairwise non-opposite.

Another important remark is that Euler's criterion can be reformulated as follows using the Legendre symbol: for any odd prime $p$ and any $x \in \mathbb{Z}$, we have $\left(\frac{x}{p}\right) \equiv x^{\frac{p-1}{2}} \bmod p$ (note that this works even if $p \mid x$). We immediately deduce that the Legendre symbol is completely multiplicative with respect to its upper argument, that is, for all $x, y \in \mathbb{Z}$, we have $\left(\frac{x}{p}\right)\left(\frac{y}{p}\right)=\left(\frac{x y}{p}\right)$. In particular, the product of two quadratic residues is a quadratic residue, and the inverse of a quadratic residue is a quadratic residue (we say that the set of quadratic residues is a subgroup of $\left.(\mathbb{Z} / p \mathbb{Z})^{*}\right)$, but also, the product of two non-quadratic residues is a quadratic residue, and the product of a quadratic residue and a non-quadratic residue is not a quadratic residue.