Find the positive integers $n$ such that $n^{2}+1 \mid n+1$.

 untranslated text has been translated while preserving the original formatting and structure.
If $n^{2}+1 \mid n+1$, we have $n+1 \geq n^{2}+1$ (according to Proposition 8), hence $n=0$ or $n=1$. We verify that these solutions work.

Definition 114. An integer $p>1$ is said to be prime if its only positive divisors are 1 and itself.

## Examples

7 is prime

1 is not prime

The only even prime number is 2.

## - Euclidean Division -

Theorem 115. Let $a \in \mathbb{Z}$ and $b \in \mathbb{N}, b>0$.

There exists a unique pair $(q, r)$ such that

$$
\left\{\begin{array}{l}
a=b q+r \\
0 \leq r<b
\end{array}\right.
$$

This is the Euclidean division you are familiar with; $q$ is called the quotient and $r$ the remainder of the division.

## Reminder

For any $x \in \mathbb{R}$, the floor function, denoted $\lfloor x\rfloor$, is the unique integer $n$ such that $n \leq x<n+1$. If we write $q=\left\lfloor\frac{a}{b}\right\rfloor$ and $r=a-b q$, we indeed have $a=b q+r$ and $0 \leq r<b$. The uniqueness of the quotient and the remainder is shown by contradiction.

## Example

Euclidean division of 135 by $17: 135=17 \times 7+16$

Euclidean division of $2 x^{2}+3 x-5$ by $x+7: 2 x^{2}+3 x-5=(x+7)(2 x-1)-30$

## - GCD and Euclidean Algorithm -

Definition 116. Let $a, b \in \mathbb{Z}$.

The GCD of $a$ and $b$, denoted $a \wedge b$, is the greatest common divisor of $a$ and $b$, i.e., the greatest integer $d$ such that $d \mid a$ and $d \mid b$.

The LCM of two integers $a$ and $b$, denoted $a \vee b$, is the least common multiple of $a$ and $b$, i.e., the smallest integer $m$ such that $a \mid m$ and $b \mid m$.

Remark 117. Two integers $a$ and $b$ are coprime if $a \wedge b=1$. In general, if $a$ and $b$ are any integers, and if we set $d=a \wedge b$, then we can write $a=d \times a^{\prime}$ and $b=d \times b^{\prime}$ where $a^{\prime}$ and $b^{\prime}$ are coprime integers.

## Examples

$9 \wedge 12=3$

$9 \vee 12=36$

Proposition 118. $a \wedge b=a \wedge(a+b)$

More generally, for any integer $k \in \mathbb{Z}$, we have $a \wedge b=b \wedge(a+k b)$.

Proof. Let $k \in \mathbb{Z}$. We denote $d=a \wedge b$ and $d^{\prime}=b \wedge(a+k b)$.

On the one hand, $d \mid a$ and $d \mid b$ so $d \mid a+k b$ and $d \leq d^{\prime}$ (since $d^{\prime}$ is the greatest common divisor of $b$ and $a+k b$).

On the other hand, $d^{\prime} \mid a+k b$ and $d^{\prime} \mid b$ hence $d^{\prime} \mid a$ and $d^{\prime} \leq d$.

Thus, $d=d^{\prime}$.

Definition 119. Given integers $a=r_{0}$ and $b=r_{1}$, the Euclidean algorithm at step $k$ consists of performing the Euclidean division of $r_{k-1}$ by $r_{k}: r_{k-1}=r_{k} \times q_{k}+r_{k+1}$, etc.

$$
\begin{aligned}
r_{0} & =r_{1} q_{1}+r_{2} \\
r_{1} & =r_{2} q_{2}+r_{3} \\
\vdots & \vdots \\
r_{l-2} & =r_{l-1} q_{l-1}+r_{l} \\
r_{l-1} & =r_{l} q_{l}+0
\end{aligned}
$$

According to the previous proposition, at each step $k$, we have $r_{k} \wedge r_{k+1}=r_{k+1} \wedge r_{k+2}$.

The sequence of $r_{k}$ is a strictly decreasing sequence of integers, so it must eventually become zero. The last non-zero remainder (here $r_{l}$) is then the GCD of $a$ and $b$.

Theorem 120. Bézout's Theorem

Let $a, b \in \mathbb{Z}$ and $d=a \wedge b$. Then there exist $u, v \in \mathbb{Z}$ such that $a u+b v=d$.

In particular, if $a$ and $b$ are coprime, there exist $u, v \in \mathbb{Z}$ such that $a u+b v=1$.

To find the Bézout relation between two integers $a$ and $b$ (i.e., the $u$ and $v$), we can trace back the Euclidean algorithm: we start from the last non-zero remainder $r_{l}$, equal to $d$, and express it in terms of $r_{l-1}$ and $r_{l-2}$. We then express the $r_{k}$ successively in terms of the previous terms until we obtain an expression of $r_{l}$ solely in terms of $r_{0}$ and $r_{1}$.

## Example

Using the Euclidean algorithm to find the GCD of 153 and 71 and the associated Bézout relation:

$$
\begin{aligned}
153 & =71 \times 2+11 \\
71 & =11 \times 6+5 \\
11 & =5 \times 2+1 \\
5 & =1 \times 5+0
\end{aligned}
$$

We thus obtain $153 \wedge 71=1$. Moreover, by tracing back:

$$
\begin{aligned}
& 1=11-5 \times 2 \\
& 1=11-(71-11 \times 6) \times 2 \\
& 1=(153-71 \times 2)-(71-(153-71 \times 2) \times 6) \times 2 \\
& 1=153 \times(1+6 \times 2)+71 \times(-2-(1+2 \times 6) \times 2)
\end{aligned}
$$

We finally get $1=153 \times 13+71 \times(-28)$.

Corollary 121. Gauss's Lemma

If $a \mid b c$ and $a \wedge b=1$, then $a \mid c$.

Proof. $a \wedge b=1$ so by Bézout's theorem there exist $u, v \in \mathbb{Z}$ such that $a u+b v=1$, hence $c a u+c b v=c$. Since $a \mid c a u$ and $a \mid b c$, it follows that $a \mid c . \quad \square$ This text has not yet been integrated.

## 2 Monday morning, April 24: Julien Portier

## - Congruences -

Definition 122 (Congruences). We say that $a$ and $b$ are congruent modulo $n$ and we write $a \equiv b \bmod n$ if $a$ and $b$ have the same remainder in the Euclidean division by $n$, i.e., if $n$ divides $a-b$.

The congruence relation satisfies the following properties:

- if $a \equiv b \bmod n$ and $c \equiv d \bmod n$, then $a+c \equiv b+d \bmod n$,

- if $a \equiv b \bmod n$ and $c \equiv d \bmod n$, then $a c \equiv b d \bmod n$.

- if $a \equiv b \bmod n$ and $q$ is a natural integer, then $a^{q} \equiv b^{q} \bmod n$.

Proofs: 1st point: $a \equiv b \bmod n$ means there exist integers $k, k^{\prime}$ and $r$ such that $a=n k+r$ and $b=n k^{\prime}+r$. Similarly, since $c \equiv d \bmod n$, there exist integers $q, q^{\prime}$ and $r^{\prime}$ such that $c=q n+r^{\prime}$ and $d=q^{\prime} n+r^{\prime}$, so $a+c=n(k+q)+\left(r+r^{\prime}\right)$ and $b+d=n\left(k