We define the $x_{i}$ by $x_{1}=a$ and $x_{i+1}=2 x_{i}+1$. We define the sequence $y_{i}=2^{x_{i}}-1$. Determine the largest integer $k$ such that it is possible for $y_{1}, \ldots, y_{k}$ to all be prime.

Theorem 46. $\left(\frac{p}{q}\right)=-1 \frac{(p-1)(q-1)}{4}\left(\frac{q}{p}\right)$

Theorem 47. $\left(\frac{2}{p}\right)=(-1)^{\frac{p^{2}-1}{8}}$
We will show that $k_{\max }=2$. If a prime number $p$ divides $x_{i}$, then a remarkable identity gives $2^{p}-1 \mid 2^{x_{i}}-1$. Consequently, for $y_{i}$ to be prime, $x_{i}$ must also be prime. In particular, if $k \neq 0, a$ is prime. We start by treating the case $a=2$. Since $2^{11}-1=23 * 89, k$ is at most 2 in this case. Otherwise, $a$ is odd of the form $2 n+1$, so $x_{1}=2 n+1, x_{2}=4 n+3$ and $x_{3}=8 n+7$. If $k>2$, then $y_{2}$ and $x_{3}$ are prime, so according to Theorem 3, 2 is a quadratic residue modulo $x_{3}$, and there exists $s$ such that $2 \equiv s^{2}$ $\bmod x_{3}$. We then have $y_{2} \equiv 2^{x_{2}}-1 \equiv 2^{\left(x_{3}-1\right) / 2}-1 \equiv s^{x_{3}-1}-1 \equiv 1-1 \equiv 0 \bmod x_{3}$, so $x_{3} \mid y_{2}$, which contradicts the primality assumption of $y_{2}$. Therefore, $k<3$, and the case $a=2$ shows that $k$ can reach 2.

Solution to exercise $11\left(\frac{3}{p}\right)=(-1)^{\frac{2(p-1)}{4}}\left(\frac{p}{3}\right)$.

$\left(\frac{p}{3}\right)$ is -1 if $p \equiv 2 \bmod 3$ and 1 if $p \equiv 1 \bmod 3$, and $(-1)^{\frac{2(p-1)}{4}}$ is -1 if $p \equiv 3 \bmod 4$ and 1 if $p \equiv 1 \bmod 4$. By examining the 4 values that $p$ can take modulo 12 (cases 2 and 3 are treated separately), we find that 3 is a quadratic residue modulo $p$ if and only if $p \equiv \pm 1$ $\bmod 12$.

For exercises 1 to 4, see the course on multiplicative order from the Grésillon 2011 olympic stage, page 15.

For exercises 5 to 9 and 12, see the first advanced arithmetic course from the Montpellier 2012 olympic stage, page 192.

For exercise 13, see the second advanced arithmetic course from the same course material, page 198.

## 3 Saturday afternoon, 19th

## Definitions and Elementary Properties

Definition 48. We introduce the imaginary number $i$ which satisfies:

$$
i^{2}=-1
$$

Definition 49. We call Gaussian integers the numbers of the form $a+i b$ with $a, b \in \mathbb{Z}$. We will denote this set as $Z[i]$.

On this set, we define addition and multiplication:

Definition 50. Addition and Multiplication:

$$
\begin{gathered}
(a+i b)+(c+i d)=(a+c)+i(b+d) \\
(a+i b)(c+i d)=(a c-b d)+i(b c+d a)
\end{gathered}
$$