Divisibilité et algorithme d'Euclide

Divisibilité dans $\mathbb{Z}$

1. Définitions

$a$ divise $b$ ($a\mid b$) si $\exists k\in\mathbb{Z}$, $b=ka$.

Propriétés :
- $a\mid a$, $1\mid a$, $a\mid0$
- $a\mid b$ et $b\mid c$ $\Rightarrow$ $a\mid c$ (transitivité)
- $a\mid b$ et $a\mid c$ $\Rightarrow$ $a\mid(\lambda b+\mu c)$ (combinaison linéaire)
- $a\mid b$ et $b\mid a$ $\Rightarrow$ $a=\pm b$

2. Division euclidienne

Pour $a\in\mathbb{Z}$, $b\in\mathbb{N}^*$ : il existe un unique couple $(q,r)$ avec $r\in\{0,\ldots,b-1\}$ tel que :

3. PGCD et algorithme d'Euclide

$\text{pgcd}(a,b)$ est le plus grand entier $d>0$ divisant $a$ et $b$.

Algorithme d'Euclide : répéter $a=bq+r$ et remplacer $(a,b)$ par $(b,r)$ jusqu'à $r=0$.

4. Théorème de Bézout

$d=\text{pgcd}(a,b)$ $\Leftrightarrow$ il existe $u,v\in\mathbb{Z}$ tels que $au+bv=d$.

Corollaire : $a$ et $b$ sont premiers entre eux ($\text{pgcd}=1$) $\Leftrightarrow$ $\exists u,v: au+bv=1$.

Lemme de Gauss : si $a\mid bc$ et $\text{pgcd}(a,b)=1$, alors $a\mid c$.

5. PPCM

$\text{ppcm}(a,b)=\frac{|ab|}{\text{pgcd}(a,b)}$.

6. Nombres premiers

$p\geq2$ est premier si ses seuls diviseurs positifs sont $1$ et $p$.

Théorème fondamental : tout entier $n\geq2$ s'écrit de façon unique (à l'ordre près) comme produit de nombres premiers.