Let $\mathrm{a}, \mathrm{b}$ and $\mathrm{c}$ be three integers. Find all pairs of integers $x, y$ (possibly with a - sign in front) such that $a x+b y=c$.


We still reason by analysis and synthesis. Let $d=a \wedge b$. If $a x+b y=c$ then $d \mid c$. We deduce that if $d \nmid c$, then there is no solution.

Otherwise, by dividing everything by $d$, we can assume without loss of generality that $a \wedge b=1$. We now start by looking for a particular solution. Let $u$ and $v$, given by the extended Euclidean algorithm, be such that $a u+b v=1$. Then, by setting $x_{0}=c u$ and $y_{0}=c v$, we have indeed $a x_{0}+b y_{0}=c$.

Now let $x$ and $y$ be any solution. By subtracting $a x+b y=c$ and $a x_{0}+b y_{0}=c$, we get

$$
a\left(x-x_{0}\right)=b\left(y_{0}-y\right)
$$

Since $a \wedge b=1$, by the lemma of Gauss, $a \mid y_{0}-y$, so there exists an integer $k$ such that $y=y_{0}-k a$. We then find that necessarily $x=x_{0}+k b$.

Conversely, for any integer $k$, the pairs $x=x_{0}+k b, y=y_{0}-k a$ are indeed solutions.

## 2 Second Course

The subject of this course was an introduction to congruences.

## 3 First Practical Session

## - Statements -