PGCD, théorèmes de Bézout et Gauss

Accueil » Cours et exercices » Mathématiques Expertes » PGCD, théorèmes de Bézout et Gauss

PGCD de deux entiers

PGCD

Notation : Pour tout entier relatif $a$, on notera $D_a$ ou $D(a)$ l’ensemble de ses diviseurs.

Soit $a$ et $b$ deux entiers relatifs non tous les deux nuls. On appelle plus grand diviseur commun (PGCD) de $a$ et $b$ le plus grand entier naturel qui divise $a$ et $b$.

On le note $PGCD(a;b)$ ou $a \wedge b$. On convient par ailleurs que $PGCD(0;0)=0$.

Exemple : Les diviseurs de 12 sont $-12$, $-6$, $-4$, $-3$, $-2$, $-1$, $1$, $2$, $3$, $4$, $6$ et $12$.

Les diviseurs de 18 sont $-18$, $-9$, $-6$, $-3$, $-2$, $-1$, $1$, $2$, $3$, $6$, $9$ et $18$.

Le plus grand diviseur commun de 12 et 18 est donc 6.

Calcul du PGCD

Soit $a$ et $b$ deux entiers relatifs, avec $b$ non nul.

Pour tout entier relatif $k$, $D(a) \cap D(b)=D(a-kb) \cap D(b)$.
En particulier, soit $r$ le reste de la division euclidienne de $a$ par $b$.
Alors $D(a) \cap D(b) = D(b) \cap D(r)$ : les diviseurs communs à $a$ et $b$ sont les diviseurs communs à $b$ et $r$.

Soit $a$ et $b$ deux entiers relatifs, avec $b$ non nul. Soit $k$ un entier relatif

Soit $d$ un diviseur commun de $a$ et $b$. $d$ divise alors toute combinaison linéaire de $a$ et $b$. En particulier, $d$ divise $a-bk$.
Soit $d$ un diviseur commun de $a-kb$ et $b$. $d$ divise alors toute combinaison linéaire de $a-kb$ et $b$. En particulier, $d$ divise $a-kb+kb$, c’est-à-dire $a$.

De cette propriété, il vient naturellement que…

Soit $a$ et $b$ deux entiers relatifs, avec $b$ non nul. Pour tout entier relatif $k$, $a \wedge b = (a-bk) \wedge b$.

En particulier, soit $r$ le reste de la division euclidienne de $a$ par $b$. Alors $a\wedge b = b \wedge r$

Exemple : Soit $n$ un entier naturel. On souhaite déterminer le PGCD de $2n+3$ et $n-4$.
D’après la propriété précédente, on a $(2n+3) \wedge (n-4) = (2n+3-2(n-4)) \wedge (n-4) = 11 \wedge n-4$.

Or, les diviseurs positifs de 11 sont 1 et 11. Ainsi,

Si $n-4$ est divisible par 11 (c’est-à-dire si $n \equiv 4 \, [11]$), alors $(2n+3) \wedge (n-4) = 11$.
Sinon, $(2n+3) \wedge (n-4) = 1$.

Algorithme d’Euclide
Soit $a$ et $b$ deux entiers naturels tous deux non nuls. On considère l’algorithme suivant

Tant que le reste $r$ de la division euclidienne de $a$ par $b$ n’est pas nul :
- Affecter à $a$ la valeur de $b$
- Affecter à $b$ la valeur de $r$

Le PGCD de $a$ et $b$ est égal à la dernière valeur non nulle de $r$.

Exemple : On souhaite déterminer le PGCD de 1824 et 432

$1824 = 4 \times 432 + 96$. Ainsi, $1824 \wedge 432 = 432 \wedge 96$
$432 = 4 \times 96 + 48$. Ainsi, $432 \wedge 96 = 96 \wedge 48$
$96 = 2 \times 48 + 0$. On atteint un reste nul.

Finalement, $1824 \wedge 432 = 48$.

Propriétés du PGCD

Soit $a$ et $b$ deux entiers relatifs. Alors $D(a) \cap D(b) = D(a\wedge b)$.

Quitte à considérer $|a|$ et $|b|$, on peut supposer que $a$ et $b$ sont tous deux positifs. On peut alors appliquer l’algorithme d’Euclide et on obtient que $D(a) \cap D(b) = D(a\wedge b)$.

Soit $a$, $b$ et $k$ trois entiers relatifs. Alors $(ka) \wedge (kb) = |k|(a \wedge b)$.

Exemple : $8100 \wedge 600 = 100 \times (81 \wedge 6) = 100 \times 3 = 300$.

Nombres premiers entre eux et théorème de Bézout

Nombres premiers entre eux

Soit $a$ et $b$ deux entiers relatifs. On dit que $a$ et $b$ sont premiers entre eux si $a \wedge b = 1$.

Exemple : 17 et 24 sont premiers entre eux.

Soit $a$ et $b$ deux entiers relatifs non nuls et $d$ un entier naturel.

Alors $d= a \wedge b$ si et seulement s’il existe deux entiers relatifs $a’$ et $b’$ premiers entre eux tels que $a=da’$ et $b=db’$.

On raisonne par double implication

Supposons que $d=a \wedge b$. Alors $d|a$ et $d|b$. Il existe donc des entiers relatifs $a’$ et $b’$ tels que $a=da’$ et $b=db’$. Par ailleurs, $a \wedge b = (da’) \wedge (db’) = d \times a’ \wedge b’ = d$. Ainsi, $a’ \wedge b’=1$. $a$ et $b$ sont donc premiers entre eux.
Supposons qu’il existe deux entiers relatifs $a’$ et $b’$ premiers entre eux tels que $a=da’$ et $b=db’$. alors $a \wedge b = (da’) \wedge (db’) = d \times a’ \wedge b’ = d \times 1 = d$. Ainsi, $d = a \wedge b$.

Exemple : Pour tout nombre rationnel $q$, il existe des entiers $a$ et $b$ premiers entre eux tels que $q = \dfrac{a}{b}$.

Exemple : Cherchons deux nombres entiers naturels $a$ et $b$ tels que $a \wedge b = 20$ et $ab=30800$.

Il existe alors deux entiers $a’$ et $b’$ premiers entre eux tels que $a=20a’$ et $b=20b’$. Ainsi, $ab=20a’ \times 20b’ = 30800 = 400a’b’$ et il en vient que $a’b’=77$. Les couples $(a’,b’)$ possibles sont donc $(1,77)$, $(7,11)$, $(11,7)$ et $(77,1)$. Les couples $(a,b)$ possibles sont donc $(20,1540)$, $(140, 220)$, $(220,140)$ et $(1540, 20)$.

Réciproquement, on vérifie facilement que ces couples répondent bien au problème posé.

Théorème de Bézout

Identité de Bézout

Soit $a$ et $b$ deux entiers relatifs non nuls.

Il existe des entiers relatifs $u$ et $v$ tels que $au+bv = a \wedge b$.

Soit $\mathcal{E}$ l’ensemble des entiers naturels non nuls $n$ pour lesquels il existe des entiers relatifs $u$ et $v$ tels que $n=au+bv$.

L’ensemble $\mathcal{E}$ est un sous-ensemble non vide de $\mathbb{N}$ : il suffit de prendre $v=0$ et $u=\pm 1$ selon le signe de $a$. Ainsi, $|a| \in \mathcal{E}$. L’ensemble $\mathcal{E}$ admet donc un plus petit élément que l’on note $d$. Nous allons montrer que \(d = a \wedge b$

D’une part, puisque $a \wedge b$ divise $a$ et $b$, alors $a \wedge b$ divise $au+bv$ pour tout entier relatif $u$ et $v$. En particulier, $a\wedge b$ divise $d$. Ces deux nombres étant strictement positifs, il en vient que $a \wedge b \leqslant d$.
Par ailleurs, écrivons la division euclidienne de $a$ par $d$. Il existe des entiers relatifs $q$ et $r$ vérifiant $a=dq+r$, avec $0 \leqslant r < d$. Or, $d \in \mathcal{E}$, il existe donc des entiers $u$ et $v$ tels que $d=au+bv$ et donc $r = a-dq=a-(au+bv)q=a(1-uq)+b(-vq)$. On a écrit $r$ sous la forme $aU+bV$, avec $U$ et $V$ des entiers relatifs : on en déduit que $r \in \mathcal{E}$ ou $r=0$. Or, $r < d$, qui est le plus petit élément de $\mathcal{E}$. La seule possibilité est donc que $r=0$. Ainsi, $a=dq$ et donc $d$ divise $a$. De la même manière, on prouve que $d$ divise $b$.
$d$ est donc un diviseur commun à $a$ et à $b$ vérifiant $d \geqslant a \wedge b$. Puisque $a \wedge b$ est le plus grand diviseur commun à $a$ et $b$, il en vient que $d=a \wedge b$, et en particulier, $a\wedge b \in \mathcal{E}$.

Exemple : On souhaite déterminer deux entiers $u$ et $v$ tels que $46u+26v=2$. Ceci est possible car $46 \wedge 26 = 2$. Utilisons l’algorithme d’Euclide en isolant à chaque fois les restes des divisions euclidiennes

$46 = 1 \times 26 + 20$ soit $20 = 46 – 26$
$26 = 1 \times 20 + 6$ soit $6 = 26 – 20$
$20 = 3 \times 6 + 2$ soit $2 = 20-3 \times 6$
$6 = 3 \times 2 + 0$

L’idée générale est alors de « remonter » cet algorithme pour exprimer 2 en fonction des valeurs de départ

Puisque $2 = 20-3 \times 6$ et $6 = 26 – 20$, alors $2 = 20 – 3 \times (26-20) = 20 – 3 \times 26 + 3 \times 20 = 4 \times 20 -3\times 26$
Puisque $20=46-26$, on en déduit que $2 = 4 \times (46 – 26)-3 \times 26 = 4 \times 46 – 7 \times 26$

Le procédé utilisé ici porte le nom d’Algorithme d’Euclide étendu.

Soit $a$, $b$ et $c$ des entiers relatifs non nuls.

L’équation d’inconnues $x$ et $y$ entières $ax+by=c$ admet des solutions si et seulement si $c|a\wedge b$.

Exemple : Puisque $24\wedge 9 = 3$ et que 5 n’est pas un multiple de 3, il n’existe aucun couple $(u,v)$ d’entiers relatifs tels que $24u+9v=5$.

Théorème de Bézout

Soit $a$ et $b$ deux entiers relatifs

$a$ et $b$ sont premiers entre eux si et seulement s’il existe deux entiers $u$ et $v$ tels que $au+bv=1$.

On raisonne par double implication

Supposons que $a$ et $b$ sont premiers entre eux. D’après l’identité de Bézout, il existe deux entiers $u$ et $v$ tels que $au+bv=a \wedge b=1$
Réciproquement, soit $u$ et $v$ tels que $au+bv=1$. Soit $d$ un diviseur commun de $a$ et $b$. Alors $d$ divise $au+bv$ et donc $d$ divise 1. Il en vient que les seuls diviseurs commun de $a$ et $b$ sont $-1$ et $1$ et donc que $a\wedge b =1$.

Exemple : Pour tout entier naturel $n$, $3(2n+5)-2(3n+7)=1$. Ainsi, pour tout entier naturel $n$, $2n+5$ et $3n+7$ sont premiers entre eux.

Soit $n$ et $a$ deux entiers relatifs. On dit que $a$ est inversible modulo $n$ s’il existe un entier relatif $b$ tel que $ab \equiv 1\,[n]$.

Soit $n$ et $a$ deux entiers relatifs. $a$ est inversible modulo $n$ si et seulement si $a \wedge n =1$.

Raisonnons par équivalence en utilisant le théorème de Bézout.

$a$ est inversible modulo $n$	si et seulement s’il	existe un entier relatif $b$ tel que $ab \equiv 1\,[n]$.
	si et seulement s’il	existe un entier relatif $b$ tel que $ab-1$ est un multiple de $n$
	si et seulement s’il	existe deux entiers relatifs $b$ et $k$ tels que $ab-1=kn$
	si et seulement s’il	existe deux entiers relatifs $b$ et $k$ tels que $ab-kn=1$
	si et seulement si	$a$ et $n$ sont premiers entre eux (théorème de Bézout)

Exemple : Cherchons un entier $x$ tel que $7x \equiv 1\, [17]$. Cela revient à chercher deux entiers $u$ et $v$ tels que $7u+17v=1$. Appliquons l’algorithme d’Euclide étendu

$17 = 7 \times 2 + 3 \qquad 7 = 3 \times 2 + 1 \qquad 3 = 3 \times 1 + 0$.
Ainsi, $1=7-3 \times 2 = 7-(17-7\times 2) \times 2 = 5 \times 7 – 2 \times 17$

En particulier, $5 \times 7 \equiv 1 \,[17]$ – on aurait aussi pu déterminer directement un tel entier en testant les nombres..

Théorème de Gauss

Théorème de Gauss

Soit $a$, $b$ et $c$ trois entiers relatifs non nuls.

Si $a|bc$ et $a\wedge b =1$, alors $a|c$

Si $a|bc$, alors il existe un entier naturel $k$ tel que $bc=ka$. Par ailleurs, puisque $a\wedge b =1$, d’après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au+bv=1$.

En multipliant par $c$, on a $cau + bcv = c$, soit $cau + kav=c$ et donc $a(cu+kv)=c$. En particulier, $a|c$.

L’hypothèse que $a$ et $b$ sont premiers entre eux est primordiale ! En effet, $12$ divise $6 \times 10$, mais 12 ne divise ni 6, ni 10…

Couplé au théorème de Bézout, le théorème de Gauss permet de trouver l’ensemble des solutions des équations du type $ax+by=c$, d’inconnues entières. De telles équations sont appelés \textbf{équations diophantiennes du premier degré}.

Exemple : On souhaite déterminer l’ensemble des entiers $u$ et $v$ tels que $8u+11v=1$. Puisque $8 \wedge 11 = 1$, de tels entiers existent. Nous pouvons déterminer un couple particulier solution en utilisant l’algorithme d’Euclide étendu :

$11 = 1 \times 8 + 3$
$8 = 2 \times 3 + 2$
$3 = 1 \times 2 + 1$
$2 = 2 \times 1 + 0$

Ainsi, $1 = 3 – 1\times 2 = 3 – (8-2\times 3)=3 \times 3 – 8 = 3 \times (11-8)-8=3 \times 11 – 4 \times 8$. Le couple $(-4;3)$ est donc solution. Raisonnons alors par analyse-synthèse.

Analyse : Soit $u$ et $v$ des entiers solutions de l’équation $8u+11v=1$. On a de plus $8 \times (-4) + 11 \times 3 = 1$. En soustrayant ces deux équation, on obtient $8(u+4)+11(v-3)=0$, c’est-à-dire $8(u+4)=11(3-v)$.

Ainsi, $8|11(3-v)$, mais 8 est premier avec 11. D’après le théorème de Gauss, on en déduit que $8|3-v$. Il existe donc un entier $k$ tel que $3-v=8k$ et donc $v=3-8k$.

Remplaçons $v$ par $3-8k$ dans la première équation. On a donc $8u+11(3-8k)=1$ et donc $8u+33-88k=1$ et finalement \(u=11k-4$

Synthèse : Réciproquement, pour tout entier relatif $k$,
\[8 \times (11k-4)+11 \times (3-8k)=88k-32+33-88k=1\]

Ainsi, les solutions de l’équation $8u+11v=1$ dans $\mathbb{Z}^2$ sont les couples $(11k-4,3-8k)$, pour $k\in\mathbb{Z}$.

Ce théorème possède également d’autres applications plutôt pratiques

Corollaire du théorème de Gauss

Soit $a$, $b$ et $c$ trois entiers relatifs non nuls

Si $a \wedge b =1$, que $a|c$ et $b|c$, alors $ab|c$.

Puisque $a|c$, il existe un entier $k$ et $k’$ tel que $c=ka$. Or, $b|c$ et donc $b|ka$. Mais puisque $a\wedge b = 1$, alors, d’après le théorème de Gauss, $b|k$ : il existe donc un entier relatif $k’$ tel que $k=bk’$ et donc $c=k’ba$. Finalement, $ab | c$.

Division dans une congruence
Soit $a$, $b$, $m$ et $n$ des entiers relatifs non nuls. On suppose que $m \wedge n =1$.

Si $am \equiv bm\,[n]$, alors $a\equiv b\,[n]$.

Si $am \equiv bm\,[n]$, cela signifie que $n$ divise $am-bm$, c’est-à-dire $m(b-a)$. Or, puisque $m$ et $n$ sont premiers entre eux, d’après le théorème de Gauss, $n$ divise alors $b-a$, ce qui signifie que $a \equiv b\,[n]$.

Accueil » Cours et exercices » Mathématiques Expertes » PGCD, théorèmes de Bézout et Gauss

\(a\) est inversible modulo \(n\)	si et seulement s’il	existe un entier relatif \(b\) tel que \(ab \equiv 1\,[n]\).
	si et seulement s’il	existe un entier relatif \(b\) tel que \(ab-1\) est un multiple de \(n\)
	si et seulement s’il	existe deux entiers relatifs \(b\) et \(k\) tels que \(ab-1=kn\)
	si et seulement s’il	existe deux entiers relatifs \(b\) et \(k\) tels que \(ab-kn=1\)
	si et seulement si	\(a\) et \(n\) sont premiers entre eux (théorème de Bézout)

Mathoutils

Outils mathématiques pour le lycée

PGCD, théorèmes de Bézout et Gauss

PGCD de deux entiers