Division euclidienne

Théorème : Pour tous $a \in \mathbb{Z}$ et $b \in \mathbb{Z}$ avec $b > 0$, il existe un unique couple $(q, r) \in \mathbb{Z}^2$ tel que : $a = bq + r \quad \text{avec} \quad 0 \leq r < b$

$q$ est le quotient et $r$ est le reste de la division de $a$ par $b$.

Divisibilité : $b$ divise $a$ (noté $b \mid a$) si et seulement si $r = 0$, i.e. $\exists k \in \mathbb{Z},\; a = kb$.

Propriétés de la divisibilité :

• Réflexivité : $a \mid a$
• Transitivité : $a \mid b$ et $b \mid c \Rightarrow a \mid c$
• Linéarité : $a \mid b$ et $a \mid c \Rightarrow a \mid (bx + cy)$ pour tous $x, y \in \mathbb{Z}$

Le PGCD (plus grand commun diviseur) de $a$ et $b$ est le plus grand entier divisant à la fois $a$ et $b$, noté $\pgcd(a, b)$.

Algorithme d'Euclide : repose sur la propriété fondamentale : $\pgcd(a, b) = \pgcd(b,\; a \bmod b)$

On itère en remplaçant $(a, b)$ par $(b, r)$ jusqu'à ce que $r = 0$. Le dernier reste non nul est le PGCD.

PPCM (plus petit commun multiple) : $\text{ppcm}(a, b) = \frac{|a \times b|}{\pgcd(a, b)}$

Théorème de Bézout : Il existe $u, v \in \mathbb{Z}$ (coefficients de Bézout) tels que : $au + bv = \pgcd(a, b)$

Corollaire : $a$ et $b$ sont premiers entre eux ($\pgcd(a,b) = 1$) si et seulement si $\exists u, v,\; au + bv = 1$.

Un entier $p \geq 2$ est premier s'il n'admet aucun diviseur autre que 1 et $p$.

Premiers nombres premiers : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots$

Théorème fondamental de l'arithmétique : Tout entier $n \geq 2$ s'écrit de façon unique (à l'ordre près) comme produit de nombres premiers : $n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$

Lemme d'Euclide : Si $p$ est premier et $p \mid ab$, alors $p \mid a$ ou $p \mid b$.

Infinité des nombres premiers : Euclide a montré qu'il existe une infinité de nombres premiers.

Critère pratique : Pour tester si $n$ est premier, il suffit de tester la divisibilité par tous les premiers $p \leq \sqrt{n}$.

PGCD via décomposition : Si $a = \prod p_i^{\alpha_i}$ et $b = \prod p_i^{\beta_i}$, alors : $\pgcd(a,b) = \prod p_i^{\min(\alpha_i, \beta_i)} \qquad \text{ppcm}(a,b) = \prod p_i^{\max(\alpha_i, \beta_i)}$

Soit $n \geq 1$. On dit que $a$ et $b$ sont congrus modulo $n$, noté $a \equiv b \pmod{n}$, si $n \mid (a - b)$.

Autrement dit, $a$ et $b$ ont le même reste dans la division par $n$.

Propriétés (stabilité des opérations) : Si $a \equiv a' \pmod{n}$ et $b \equiv b' \pmod{n}$, alors : $a + b \equiv a' + b' \pmod{n} \qquad a \times b \equiv a' \times b' \pmod{n}$

Petit théorème de Fermat : Si $p$ est premier et $\gcd(a, p) = 1$, alors : $a^{p-1} \equiv 1 \pmod{p}$

Inverse modulaire : $a$ admet un inverse modulo $n$ (i.e. $\exists x,\; ax \equiv 1 \pmod{n}$) si et seulement si $\pgcd(a, n) = 1$.