. A lighthouse emits a yellow signal every 15 seconds and a red signal every 28 seconds. The yellow signal is seen 2 seconds after midnight and the red signal 8 seconds after midnight. At what time will we see both signals emitted at the same time for the first time
. We start by formulating the problem into equations. We denote $x$ as the times, in seconds, since midnight, when the two headlights are turned on at the same moment. Using the data from the problem, we can say that $x$ is a solution to the system: $(S)\left\{\begin{array}{l}x \equiv 2(\bmod 15) \\ x \equiv 8(\bmod 28)\end{array}\right.$. We are looking for the smallest natural number $x$ that is a solution to this system. We notice that 15 and 28 are coprime. We can then apply the method given by the previous remark to find the solutions to this system. Let's find a Bézout relation between 15 and 28.

We have: $28=15 \times 1+13 \quad ; \quad 15=13 \times 1+2 \quad ; \quad 13=2 \times 6+1$.

By retracing the calculations, we get:

$1=13-2 \times 6=13-6 \times(15-13)=-6 \times 15+7 \times 13=-6 \times 15+7(28-15)=$ $-13 \times 15+7 \times 28$.

Thus, the relation: $-13 \times 15+7 \times 28=1$ is a Bézout relation between 15 and 28. We then set (as in the previous remark): $a_{1}=2, a_{2}=8$, $m_{1}=15, m_{2}=28, u=-13$ and $v=7$. We then calculate $a=\left(a_{2}-a_{1}\right) m_{1} u+a_{1}=$ $a_{2} m_{1} u+a_{1} m_{2} v=(8-2) \times 15 \times(-13)+2=-1168$ and we can deduce that $x \equiv a$ $\left(\bmod m_{1} m_{2}\right)($ i.e $: x \equiv-1168(\bmod 15 \times 28))$. Thus, $x \equiv-1168(\bmod 420)$. The solutions to this system are then the integers congruent to $\tilde{A}-1168$ modulo 420, i.e., the integers of the form: $420 k-1168, k \in \mathbb{Z}$. We are looking for the smallest natural number that is a solution to this system. For $k=2,420 k-11680$ and we have: $420 \times 3-1168=92$. Therefore, the smallest natural number solution to this system is 92.

Thus, the two headlights will be turned on at the same time, for the first time, 1 minute and 32 seconds after midnight.

## 3 Monday 25th afternoon: Arsène Pierrot

## Introduction

This course aims to present the Chinese Remainder Theorem to students, but also to serve as an arithmetic tutorial, as a significant portion of the time will be devoted to solving exercises using all the arithmetic tools that students will have acquired during this workshop.

## The Chinese Remainder Theorem

Theorem. Let $n_{1}, \ldots, n_{k}$ be integers that are pairwise coprime, and $a_{1}, \ldots, a_{k}$ be integers. Let $n=\prod_{i=1}^{k} n_{i}$. Then there exists an integer $a$ such that for any integer $x$,

$$
\begin{aligned}
& x \equiv a_{1}\left[n_{1}\right] \\
& \ldots \quad \Leftrightarrow \quad x \equiv a[n] \\
& x \equiv a_{k}\left[n_{k}\right]
\end{aligned}
$$

Proof. We prove the result for $k=2$. The general case then follows from an easy induction.

Keeping the notation from the theorem, we have $x \equiv a_{1}\left[n_{1}\right]$, from which we deduce that: $\exists m \in \mathbb{Z}, x=m n_{1}+a_{1}$. Thus, $n_{2} x=m n_{1} n_{2}+a_{1} n_{2}$. Similarly, $\exists m^{\prime} \in \mathbb{Z}, n_{1} x=$
$m^{\prime} n_{1} n_{2}+a_{2} n_{1}$.

Since $n_{1}$ and $n_{2}$ are coprime, $\exists(i, j) \in \mathbb{Z}^{2}, i n_{1}+j n_{2}=1$ by Bézout's theorem. We then obtain by multiplying the first equality by $j$, the second by $i$, and summing the two, that: $1 \times x=\left(j m+i m^{\prime}\right) n_{1} n_{2}+\left(j a_{1} n_{2}+\right.$ $\left.i a_{2} n_{1}\right)$. Setting $M=j m+i m^{\prime}$ and $a=j a_{1} n_{2}+i a_{2} n_{1}$, we find that $x=M n+a$, which is equivalent to the desired congruence.

Knowing the value of the sought $a$, we easily obtain the converse by noting that $j n_{2} \equiv 1\left[n_{1}\right]$ by Bézout's identity.

Example. On an island, 25 pirates decide to share a freshly plundered treasure. They distribute the same number of gold coins to each of them, and at the end, they have 2 left over, which they set aside. But some pirates, greedier than others, organize a mutiny and kill 9 of their former comrades. When they redistribute the treasure equitably again, they have 1 gold coin left over at the end. Meanwhile, on the ship, the cook (who was not counted until then) decides to poison the remaining crew and keep the entire treasure for himself. What is the minimum number of coins the cook can hope to get after betraying his comrades?

In this example, calling $x$ the number of coins in the treasure, we have the following system of congruences:

$$
x \equiv 2[25]
$$

$$
\ldots \quad \Leftrightarrow \quad x \equiv a[n]
$$

$x \equiv 1[16]$

Thus, $\exists k \in \mathbb{Z}, x=25 k+2$ and passing to the congruence modulo 16, we have that $25 k+2 \equiv 1[16]$, i.e., $9 k \equiv-1[16]$; hence finally $k \equiv 7[16]$.

We then have $\exists k^{\prime} \in \mathbb{Z}, k=16 k^{\prime}+7$. Expressing $n$ in terms of $k^{\prime}$, we get $n=400 k^{\prime}+177$. Since $n \geq 0$, the cook can hope for a minimum of $n_{\text {min }}=177$ gold coins.

## Exercises