# Arithmétique/PGCD
## Diviseurs communs à deux entiers naturels

Deux entiers naturels non tous deux nuls ont toujours un nombre fini de diviseurs et donc de diviseurs communs (dont –1 et 1). Il existe donc un diviseur commun à ces deux nombres plus grand que les autres.
Le PGCD de deux entiers naturels a et b non tous deux nuls, noté pgcd(a, b), est leur plus grand diviseur commun.
Conséquence : $b\mid a\Leftrightarrow \operatorname {pgcd} \left(a,b\right)=b$.

## Lemme pour l'algorithme d'Euclide

Soient $b,r\in \mathbb {N} ^{*}$ et $q\in \mathbb {N}$, alors : $\operatorname {pgcd} \left(bq+r,b\right)=\operatorname {pgcd} \left(b,r\right)$.
Il suffit de démontrer que $bq+r$ et $b$ ont mêmes diviseurs communs que $b$ et $r$.
Soit $d$ un diviseur de $bq+r$ et $b$, alors $d$ divise $(bq+r)-bq=r$.
Réciproquement, soit $d$ un diviseur de $b$ et $r$, alors $d$ divise $bq+r$.

## Algorithme d'Euclide

Soient $a$ et $b$ deux entiers naturels tels que $b\neq 0$.
| Opération | Reste $r$ | Commentaire |
| on divise $a$ par $b$ | $r_{0}$ | $0\leq r_{0}<b{\text{ et }}\operatorname {pgcd} (a,b)=\operatorname {pgcd} (b,r_{0})$ |
| si $r_{0}\neq 0$, on divise $b$ par $r_{0}$ | $r_{1}$ | $0\leq r_{1}<r_{0}{\text{ et }}\operatorname {pgcd} (b,r_{0})=\operatorname {pgcd} (r_{0},r_{1})$ |
| si $r_{n}\neq 0$, on divise $r_{n-1}$ par $r_{n}$ | $0$ | $\operatorname {pgcd} (r_{n-1},r_{n})=r_{n}$ |
Lorsque b ne divise pas a, le PGCD des entiers naturels non nuls a et b est égal au dernier reste non nul obtenu par l'algorithme d'Euclide.
Les diviseurs communs à deux entiers naturels a et b non tous deux nuls sont les diviseurs de pgcd(a, b).
Ceci fournit une définition alternative du PGCD.

## Propriétés du PGCD

$\operatorname {pgcd} (ka,kb)=k\times \operatorname {pgcd} (a,b)$
L'entier k divise ka et kb donc aussi leur PGCD. L'entier d > 0 défini par pgcd(ka, kb) = kd vérifie alors :
$\forall n\in \mathbb {Z} \quad n\mid a,b\iff kn\mid ka,kb\iff kn\mid pgcd(ka,kb)\iff n\mid d$
donc
$\operatorname {pgcd} (a,b)=d=\operatorname {pgcd} (ka,kb)/k$
$\operatorname {pgcd} (12000,32000)$
    $12000=12\times 1000$ et $32000=32\times 1000$
donc $\operatorname {pgcd} (12000,32000)=1000\times \operatorname {pgcd} (12,32)=4000$.
Conséquence : si $k$ est un entier naturel non nul, diviseur commun à $a$ et $b$, alors $\operatorname {pgcd} \left({\frac {a}{k}},{\frac {b}{k}}\right)={\frac {1}{k}}\times \operatorname {pgcd} (a,b)$.

## Extension du PGCD aux entiers relatifs

Le PGCD de deux entiers relatifs non nuls $a$ et $b$ est le PGCD de leurs valeurs absolues, c'est-à-dire $\operatorname {pgcd} (a,b)=\operatorname {pgcd} (|a|,|b|)$.
* $\forall k\in \mathbb {Z} ^{*}\quad \operatorname {pgcd} (ka,kb)=|k|\operatorname {pgcd} (a,b)$
* Les diviseurs communs à $a$ et $b$ sont encore les diviseurs de $\operatorname {pgcd} (a,b)$

## Nombres premiers entre eux

Deux entiers relatifs $a$ et $b$ non tous deux nuls sont dits premiers entre eux si $\operatorname {pgcd} (a,b)=1$.
$35$ et $26$ sont premiers entre eux, car leur seul diviseur commun positif est $1$.
Soient $a$ et $b$ deux entiers relatifs non tous deux nuls, $d$ leur PGCD, et $a',b'$ les entiers définis par $a=da'$ et $b=db'$. Alors, $a'$ et $b'$ sont premiers entre eux.
$d$ est non nul et divise $a$ et $b$ donc :
* $a':={\frac {a}{d}}$ et $b':={\frac {b}{d}}$ sont bien définis et sont bien des entiers ;
* $\operatorname {pgcd} (a',b')={\frac {\operatorname {pgcd} (da',db')}{d}}={\frac {\operatorname {pgcd} (a,b)}{d}}=1$.
| Divisibilité et congruences dans Z | Théorèmes de Bézout et Gauss |