Calcul du PGCD de deux nombres entiers (par l'algorithme d'Euclide) - Python

Algorithme d’Euclide

Rappelons avant tout en quoi consiste l’algorithme d’Euclide.

Commençons par nous souvenir de cette propriété.

Propriété

Pour tout entier relatif $a$, nous avons :

$\text{PGCD}(a\ ;\, 0)=\vert a\vert$

Nous avons aussi appris et démontré la propriété suivante.

Propriété

Soit $a$ et $b$ deux entiers naturels non nuls, et $r$ le reste de la division euclidienne de $a$ par $b$.

• Nous avons alors : $\text{PGCD}(a\ ;\, b)=\text{PGCD}(b\ ;\, r)$.

Voici en quoi consiste l’algorithme d’Euclide :

• nous effectuons d’abord la division euclidienne de $a$ par $b$, obtenons le reste $r_1$ ;
• ensuite, pour chaque division suivante et tant que le reste obtenu est différent de $0$ :
• le diviseur de la division précédente devient dividende,
• le reste de la division précédente devient diviseur.
• Le $\text{PGCD}$ de $a$ et $b$ sera égal au dernier reste non nul.

Illustrons par un petit tableau cet algorithme :

• $\text{PGCD}(a\ ;\, b)=r_{n-1}$.

Exemple

Prenons un exemple et déterminons le $\text{PGCD}$ de $2\,070$ et $368$ :

	Division	Dividende	Diviseur	Reste
$\scriptsize 1$	$\footnotesize{2\,070=368\times 5+230}$	$\footnotesize{2\,070}$	$\footnotesize{368}$	$\footnotesize{230}$	$\scriptsize{\text{PGCD}(2\,070\ ;\,368)=\text{PGCD}(368\ ;\,230)}$
$\scriptsize 2$	$\footnotesize{368=230\times 1 + 138}$	$\footnotesize{368}$	$\footnotesize{230}$	$\footnotesize{138}$	$\scriptsize{\text{PGCD}(368\ ;\,230)=\text{PGCD}(230\ ;\,138)}$
$\scriptsize 3$	$\footnotesize{230=138\times 1 + 92}$	$\footnotesize{230}$	$\footnotesize{138}$	$\footnotesize{92}$	$\scriptsize{\text{PGCD}(230\ ;\,138)=\text{PGCD}(138\ ;\,92)}$
$\scriptsize 4$	$\footnotesize{138=92\times 1+46}$	$\footnotesize{138}$	$\footnotesize{92}$	$\footnotesize{46}$	$\scriptsize{\text{PGCD}(138\ ;\,92)=\text{PGCD}(92\ ;\,46)}$
$\scriptsize 5$	$\footnotesize{92=46\times 2+0}$	$\footnotesize{92}$	$\footnotesize{46}$	$\footnotesize{0}$	$\begin{aligned} \scriptsize \text{PGCD}(92\ ;\,46)&\scriptsize =\text{PGCD}(46\ ;\,0) \ &\scriptsize =46 \end{aligned}$

• $\text{PGCD} (2\,070\ ;\, 368) = 46$.

Algorithme Python

Une fois la logique de l’algorithme Python bien compris, le programme Python correspondant devient assez simple à réaliser.

• Nous créons la fonction $\purple{\text{pgcd}}$, qui prendra pour paramètres les deux entiers strictement positifs $\purple{\text{a}}$ et $\purple{\text{b}}$ :

• Nous allons effectuer les divisions successives tant que le reste obtenu est non nul.
• C’est donc notre condition pour notre boucle $\purple{\text{while}}$ :

Rappel

Opérateurs Python pour la division euclidienne :

• $\purple{\text{a \% b}}$ renvoie le reste de la division euclidienne de $\purple{\text{a}}$ par $\purple{\text{b}}$ ;
• $\purple{\text{a // b}}$ renvoie le quotient (entier) de la division euclidienne de $\purple{\text{a}}$ par $\purple{\text{b}}$.

• Comme nous l’avons dit plus haut, le diviseur de la division précédente devient le dividende, et le reste de la division précédente devient le diviseur.
• Nous assignons donc à $\purple{\text{a}}$ la valeur de $\purple{\text{b}}$ et à $\purple{\text{b}}$ le reste de la division euclidienne de $\purple{\text{a}}$ par $\purple{\text{b}}$ :

Attention

Il ne faut surtout pas écrire :

$\begin{aligned} &\text{a = b} \ &\text{b = a \% b} \end{aligned}$

En effet, avec ce code, quand la nouvelle valeur de $\purple{\text{b}}$ est assignée, $\purple{\text{a}}$ a déjà sa nouvelle valeur, soit celle de $\purple{\text{b}}$, et nous obtiendrions systématiquement $\purple{\text{b}}=0$.
Pour résoudre ce problème, nous pouvons créer une variable intermédiaire :

$\begin{aligned} &\text{c = a} \ &\text{a = b} \ &\text{b = c \% b} \end{aligned}$

Toutefois, la solution que nous avons choisie plus haut est la plus directe et permet de ne pas créer inutilement une nouvelle variable.

• Lorsqu’on sortira de la boucle, $\purple{\text{b}}$ contiendra le dernier reste non nul.
• Nous l’affichons donc :

À retenir

L’algorithme est terminé :

\begin{aligned} \textcolor{#A9A9A9}{\text{1}}&\quad\text{def pgcd(a, b):} \ \textcolor{#A9A9A9}{\text{2}}&\quad\qquad\text{while a \% b != 0:} \ \textcolor{#A9A9A9}{\text{3}}&\quad\qquad\qquad\text{a, b = b, a \% b} \ \textcolor{#A9A9A9}{\text{4}}&\quad\qquad\text{print(b)} \end{aligned}

• Vous pouvez vérifier que vous trouvez le même résultat que dans la première partie pour le $\text{PGCD}$ de $2\,070$ et $368$.

Terminons par quelques remarques.

Que se passe-t-il si $\purple{\text{a}} < \purple{\text{b}}$ ?
Le reste de la division euclidienne de $\purple{\text{a}}$ par $\purple{\text{b}}$ sera égal à $\purple{\text{a}}$. Au premier tour de boucle, les valeurs de $\purple{\text{a}}$ et $\purple{\text{b}}$ seront inversées et nous aurons alors $\purple{\text{a}} > \purple{\text{b}}$.

• Ainsi, il est inutile de différencier les cas $\purple{\text{a}} > \purple{\text{b}}$ et $\purple{\text{a}} < \purple{\text{b}}$, puisqu’on se ramène toujours et rapidement au premier.

Nous avons en outre considéré que $\purple{\text{a}}$ et $\purple{\text{b}}$ étaient des entiers naturels non nuls.
Que se passe-t-il si $\purple{\text{a}}$ est nul ?
Eh bien, $0$ étant un multiple de tout nombre entier, le reste de la division euclidienne de $0$ par tout nombre entier $b$ sera égal à $0$.
Nous n’entrons ainsi pas dans la boucle et l’algorithme renverra la valeur intiale de $\purple{\text{b}}$.

• Ce qui est juste, puisque nous savons que, pour tout entier naturel $b$, $\text{PGCD}(0\ ;\, b)=b$.

Maintenant, que se passe-t-il si c’est $\purple{\text{b}}$ qui est nul ?
Ici, effectivement, notre programme ne va pas aimer cette tentative de division par $0$…

• À vous de compléter l’algorithme pour qu’il prenne en compte de ce cas particulier !

Enfin, nous avons travaillé avec $\purple{\text{a}}$ et $\purple{\text{b}}$ entiers naturels.
Nous pourrions aussi compléter l’algorithme pour qu’il fonctionne aussi pour des entiers relatifs, en renvoyant bien une valeur positive.

• Encore à vous de jouer ! Il suffit de se rappeler que, pour tout $a$ et $b$ entiers relatifs :

$\text{PGCD}(a\ ;\, b)=\text{PGCD}(\vert a\vert\ ;\, \vert b\vert)$

Astuce

Pour prendre la valeur absolue d’un nombre $\purple{\text{x}}$ en Python, on fait appel à la fonction $\purple{\text{abs}}$ :

$\purple{\text{abs(x)}}$