Let $a$ and $b$ be two non-zero integers, $d=\operatorname{GCD}(a, b)$. Find all integers $u$ and $v$ such that:

$$
a u+b v=d
$$
Let $(u, v)$ and $\left(u^{\prime}, v^{\prime}\right)$ be two solution pairs.

Then we have $a u+b v=a u^{\prime}+b v^{\prime}=d$, which means $a\left(u-u^{\prime}\right)+b\left(v-v^{\prime}\right)=0$. By dividing $a$ and $b$ by $d$, assume $d=1$ and $a$ and $b$ are coprime.

Then, since $a\left|a\left(u-u^{\prime}\right), a\right| b\left(v^{\prime}-v\right)$. Since $a$ and $b$ are coprime, it follows that $a \mid v^{\prime}-v$. Similarly, we have $b \mid u-u^{\prime}$. Therefore, there exist integers $k$ and $l$ such that $v^{\prime}-v=k a$ and $u-u^{\prime}=l b$. The equation can then be rewritten as $l a b=k a b$. Since $a b$ is non-zero, this implies $k=l$. Thus, we have $v^{\prime}=v+k a$ and $u^{\prime}=u-k b$.

Considering $\left(u_{0}, v_{0}\right)$ as a solution pair given by the Euclidean algorithm, the solutions to the equation will be pairs of the form $\left(u_{0}-k b, v_{0}+k a\right)$ where $k$ is an integer. Conversely, these pairs are indeed valid.

## 2 Pigeonhole Principle (Theo)

To be added...

## 3 Prime Numbers (Jean)

The course is available in the POFM resources.