received_3926786850970758.jpeg

# Prérequis ## Définitions ### Définition 1 : Congruences Soient $a, b, n \in \mathbb{Z}$ avec $n \geq 1$. On dit que $a$ est congru à $b$ modulo $n$, et on écrit $a \equiv b[n]$, si $n$ divise $b-a$. ### Définition 2 : PGCD Soient $a, b \in \mathbb{Z}$. On appelle PGCD (plus grand diviseur com...

# Prérequis ## Définitions ### Définition 1 : Congruences Soient $a, b, n \in \mathbb{Z}$ avec $n \geq 1$. On dit que $a$ est congru à $b$ modulo $n$, et on écrit $a \equiv b[n]$, si $n$ divise $b-a$. ### Définition 2 : PGCD Soient $a, b \in \mathbb{Z}$. On appelle PGCD (plus grand diviseur commun) de $a$ et $b$, noté $a \wedge b$, le plus grand entier positif qui divise à la fois $a$ et $b$. ### Définition 3 : Nombres premiers entre eux Deux entiers $a$ et $b$ sont dits premiers entre eux lorsque $a \wedge b = 1$. ### Définition 4 : Indicatrice d'Euler Pour $n \geq 1$, on note $\varphi(n)$ le nombre d'entiers compris entre 1 et $n$ qui sont premiers avec $n$. La fonction $\varphi$ est appelée indicatrice d'Euler. ## Théorèmes ### Théorème 1 : Petit théorème de Fermat Soit $p$ un nombre premier. Alors, pour tout entier $a$, on a $a^p \equiv a[p]$. De plus, si $p$ ne divise pas $a$, alors $a^{p-1} \equiv 1[p]$. ### Théorème 2 : Théorème d'Euler Soient $a$ et $n$ deux entiers premiers entre eux. Alors $a^{\varphi(n)} \equiv 1[n]$. ### Théorème 3 Soient $a, b, c, n \in \mathbb{Z}$ avec $n \geq 1$. Si $a \equiv b[n]$, alors $a + c \equiv b + c[n]$ et $ac \equiv bc[n]$. ### Théorème 4 Soient $a, b, n \in \mathbb{Z}$ avec $n \geq 1$. Si $d = a \wedge n$, alors l'équation $ax \equiv b[n]$ admet des solutions si et seulement si $d$ divise $b$. Dans ce cas, il y a exactement $d$ solutions modulo $n$. ### Théorème 5 : Lemme chinois Soient $m, n \in \mathbb{N}^*$ premiers entre eux. Alors, pour tous $a, b \in \mathbb{Z}$, le système de congruences $\begin{cases} x \equiv a[m] \\ x \equiv b[n] \end{cases}$ admet une solution unique modulo $mn$.