Calcul du PGCD de deux nombres entiers en Python

Fiche méthode

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

Introduction :

Nous avons appris en cours à déterminer le $\text{PGCD}$ de deux nombres entiers $a$ et $b$ en nous servant de l’algorithme d’Euclide.
Dans cette fiche, nous allons tout simplement voir comment programmer cet algorithme en Python. Bien sûr, votre calculatrice dispose déjà d’une fonction qui calcule directement le $\text{PGCD}$ de deux entiers, mais cela nous permettra de bien comprendre l’algorithme d’Euclide et de programmer un algorithme simple en 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 :

	Division	Dividende	Diviseur	Reste
$\scriptsize 1$	$\footnotesize{a=bq_1+r_1}$	$\footnotesize a$	$\footnotesize b$	$\footnotesize{r_1}$	$\scriptsize{\text{PGCD}(a\ ;\,b)=\text{PGCD}(b\ ;\,r_1)}$
$\scriptsize 2$	$\footnotesize{b=r_1q_2+r_2}$	$\footnotesize b$	$\footnotesize{r_1}$	$\footnotesize{r_2}$	$\scriptsize{\text{PGCD}(b\ ;\,r_1)=\text{PGCD}(r_1\ ;\,r_2)}$
$\scriptsize 3$	$\footnotesize{r_1=r_2q_3+r_3}$	$\footnotesize{r_1}$	$\footnotesize{r_2}$	$\footnotesize{r_3}$	$\scriptsize{\text{PGCD}(r_1\ ;\,r_2)=\text{PGCD}(r_2\ ;\,r_3)}$
…	…	…	…	…	…
$\scriptsize{n-1}$	$\footnotesize{r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}}$	$\footnotesize{r_{n-3}}$	$\footnotesize{r_{n-2}}$	$\footnotesize{r_{n-1}}$	$\scriptsize{\text{PGCD}(r_{n-3}\ ;\,r_{n-2})=\text{PGCD}(r_{n-2}\ ;\,r_{n-1})}$
$\scriptsize n$	$\footnotesize{r_{n-2}=r_{n-1}q_{n}+0}$	$\footnotesize{r_{n-2}}$	$\footnotesize{r_{n-1}}$	$\footnotesize{r_{n}=0}$	$\begin{aligned} \scriptsize \text{PGCD}(r_{n-2}\ ;\,r_{n-1})&\scriptsize =\text{PGCD}(r_{n-1}\ ;\,0) \\ &\scriptsize=r_{n-1} \end{aligned}$

$\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}}$ :

$\text{def pgcd(a, 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}}$ :

$\text{while a \% b != 0:}$

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}}$ :

$\text{a, b = b, a \% 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 :

$\text{print(b)}$

À 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)}}$$