Le plus grand diviseur commun - L'univers des mathématiques

Que ce soit pour simplifier une fraction ou pour résoudre un problème d’arithmétique, il est souvent utile de calculer le plus grand diviseur commun de deux nombres entiers $a$ et $b$ . Le plus grand diviseur commun de $a$ et $b$ est noté $a\wedge b$ et on rappelle ci-dessous l’algorithme d’Euclide qui permet de le calculer.

Pour calculer par exemple $158\wedge 34$ on réalise des divisions euclidiennes successives, le premier quotient est la partie entière de $158/34$ c’est à dire $q_0=[158/34]=4$ et le premier reste est alors $158-4\times 34=22$ , on obtient en continuant ainsi :

$\displaystyle q_0=\left[\frac{158}{34}\right]=4 ; q_1=\left[\frac{34}{22}\right]=1 ; q_2=\left[\frac{22}{12}\right]=1 ; q_3=\left[\frac{12}{10}\right]=1 ; q_4=\frac{10}{2}=5$

Il faut s’arrêter lorsque le quotient à calculer donne un nombre entier, dans l’exemple étudié c’est le quotient $q_4=10/2$ qui donne un nombre entier et qui signale alors la fin de l’algorithme. De plus le dénominateur du quotient $q_4$ est le plus grand diviseur commun $158\wedge 34=2$ qui était recherché. La suite des quotients $(q_0,q_1,q_2,q_3,q_4)$ est indicée jusqu’au rang $p=4$ et elle peut nous permettre de déterminer des entiers $u$ et $v$ tels que $134u+58v=134\wedge58$ . Pour cela, on considère la suite de nombres entiers $c$ dont les premières valeurs sont $c_{-2}=1$ et $c_{-1}=0$ définie par récurrence à l’aide de la formule suivante :

$\displaystyle \forall n \in\mathbb{N}\cap[0,p],c_{n}=c_{n-2}+q_{p-n}c_{n-1}=\begin{pmatrix} 1 & q_{p-n} \end{pmatrix}\begin{pmatrix} c_{n-2} \\ c_{n-1}\end{pmatrix}$

Dans notre exemple, on obtient les calculs ci-dessous :

$\displaystyle c_0= \begin{pmatrix} 1 & q_{4} \end{pmatrix}\begin{pmatrix} 1 \\ 0\end{pmatrix}=1 \\ c_1= \begin{pmatrix} 1 & q_{3} \end{pmatrix}\begin{pmatrix} 0 \\ c_0\end{pmatrix}=q_3=1 \\ c_2= \begin{pmatrix} 1 & q_{2} \end{pmatrix}\begin{pmatrix} c_0 \\ c_1\end{pmatrix}=c_0+q_2c_1=1+1\times1=2 \\ c_3= \begin{pmatrix} 1 & q_{1} \end{pmatrix}\begin{pmatrix} c_1 \\ c_2\end{pmatrix}=c_1+q_1c_2=1+1\times2=3 \\ c_4= \begin{pmatrix} 1 & q_{0} \end{pmatrix}\begin{pmatrix} c_2 \\ c_3\end{pmatrix}=c_2+q_0c_3=2+4\times 3=14$

On ne peut pas continuer les calculs puisque la formule de récurrence ne peut plus fonctionner. Les valeurs absolues des entiers relatifs $u$ et $v$ sont alors données respectivement par les deux derniers coefficients calculés et il faut juste retenir que les nombres $u$ et $v$ sont opposés pour pouvoir conclure que $(u,v)=(-3,14)$ . Nous avons ainsi obtenu une égalité $-3\times 158+14\times 34=158\wedge 34$ que l’on appelle l’identité de Bachet-Bézout. On peut à présent énoncer le théorème suivant :

Théorème de Bachet-Bézout : Si $a$ et $b$ sont deux entiers relatifs alors il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=a\wedge b$ .

Le plus grand diviseur commun de $a$ et $b$ nous permet aussi de calculer si on le souhaite le plus petit multiple commun de $a$ et $b$ . Ce dernier nombre noté $a\vee b$ vérifie en effet la propriété suivante :

Propriété : Si $a$ et $b$ sont deux entiers relatifs alors on a $(a\wedge b) \times (a\vee b) = |ab|$ .

En reprenant l’exemple de cet article on trouve ainsi $158\vee 34= 158\times 34 / 2=2686$ . Deux nombres entiers $a$ et $b$ sont dits premiers entre eux lorsque $a\wedge b=1$ , à ce propos le théorème de Bachet-Bézout permet de démontrer un autre théorème important utile dans divers problèmes de divisibilité :

Théorème de Gauss : Si $a, b$ et $c$ sont des entiers relatifs non nuls tels que $a \wedge b=1$ et $a$ divise $bc$ alors $a$ divise $c$ .

Preuve : On peut noter $u$ et $v$ des entiers relatifs tels que $au+bv=1$ d’après le théorème de Bachet-Bézout, de plus si $k$ est un entier relatif tel que $ak=bc$ alors on a $auc+bvc=c$ donc $auc+akv=c$ puis $a(uc+kv)=c$ ce qui prouve que $a$ divise $c$ .

Partager :

Laisser un commentaire Annuler la réponse