Pgcd et algorithme d’Euclide

Plan du chapitre "Arithmétique dans ℤ"

Pgcd de {a,b} dans {\mathbb{N}} (avec {a\ne 0} ou {b\ne0})

On rappelle que la relation de divisibilité est une relation d’ordre (partiel) sur $\mathbb{N}$.

On rappelle également que {\mathcal{D}(0)=\mathbb{Z}} donc {\mathcal{D}(0)\cap\mathbb{N}=\mathbb{N}} : tous les entiers divisent $0$, donc {0} est l’élément maximum de $\mathbb{N}$ pour l’ordre défini par la divisibilité.

En revanche si {n>0}, alors {\mathcal{D}(n)\cap \mathbb{N}} est une partie fini non vide de {[1,n]} (qui contient d’ailleurs $1$ et $n$) de maximum $n$ à la fois pour l’ordre naturel et pour celui défini par la divisibilité.

Dans la suite, on considère deux entiers {a} et {b} de {\mathbb{N}} dont l’un au moins est non nul.

Il en résulte que {\mathcal{D}(a)\cap\mathcal{D}(b)\cap\mathbb{N}} est une partie finie non vide de {\mathbb{N}^{*}} (elle contient l’entier {1}).

Définition (pgcd de deux entiers naturels dont l'un au moins est non nul)
Soit {a} et {b} deux entiers naturels, dont l’un au moins est non nul.
Soit {\mathcal{D}(a)\cap\mathcal{D}(b)\cap\mathbb{N}} l’ensemble des diviseurs communs de {a} et {b} dans {\mathbb{N}}.
Cet ensemble, fini et inclus dans {\mathbb{N}^{*}}, possède un maximum {n\ge1} (pour l’ordre naturel).
Cet entier strictement positif {n} est appelé pgcd de {a} et de {b}. Il est noté {n=\text{pgcd}(a,b)}, ou {n=a\wedge b}.

Choix d’une notation

Ainsi {a\wedge b = \max\big(\mathcal{D}(a)\cap\mathcal{D}(b)\cap \mathbb{N}\bigr)}, où le “max” s’entend au sens de l’ordre naturel.

On verra bientôt (avec l’algorithme d’Euclide) que {a\wedge b} est aussi le maximum de {\mathcal{D}(a)\cap\mathcal{D}(b)\cap\mathbb{N}} au sens de l’ordre défini par la divisibilité. En d’autres termes, non seulement {d\le a\wedge b} pour tout diviseur positif {d} de {a} et {b}, mais on a mieux : {d\mid a\wedge b}.

Le nom “pgcd” est bien sûr une abréviation de “plus grand commun diviseur”.
En anglais, la dénomination est “gcd” (greatest common divisor).

Il faut mieux utiliser la notation {a\wedge b} qui a le mérite d’être universelle.
Le langage Python possède une fonction intégrée gcd, mais elle fait partie du module fractions.
De toutes façons, on verra qu’il est très simple de programmer soi-même cette fonction.

>>> from fractions import gcd
>>> gcd(1155,910)
35

Premières propriétés

Il est clair que {a\wedge b=b\wedge a}. De même, si {a>0}, la définition donne {a\wedge 0=a}.

Pour tout {a} de {\mathbb{N}}, on a : {\mathcal{D}(a)\cap\mathcal{D}(1)\cap\mathbb{N}=\{1\}} donc {a\wedge 1=1}.

Par définition, l’entier {a\wedge b} est un diviseur commun aux entiers {a} et {b}.
Les diviseurs de {a\wedge b} sont donc également des diviseurs communs à {a} et {b}.

On verra que la réciproque est vraie : les diviseurs communs à {a} et {b} sont aussi des diviseurs de {a\wedge b}.

On a l’égalité {a\wedge b=a} si et seulement si {a} est un diviseur de {b}.

Prolongement aux entiers relatifs

La définition {a\wedge b = \max\big(\mathcal{D}(a)\cap\mathcal{D}(b)\cap \mathbb{N}\bigr)}, est celle du programme de la classe de MPSI.

On pose {0\wedge 0=0}, ce qui prolonge l’égalité {a\wedge 0=a} quand {a\ge1}.

Attention : poser {0\wedge 0=0} ne cadre pas avec la définition {a\wedge b = \max\big(\mathcal{D}(a)\cap\mathcal{D}(b)\cap \mathbb{N}\bigr)} si on considère le {\max} au sens de l’ordre naturel, mais ça marche encore si le {\max} est celui de l’ordre défini par la divisibilité dans {\mathbb{N}} (en effet {\mathcal{D}(0)\cap\mathcal{D}(0)\cap \mathbb{N}=\mathbb{N}} dont le maximum pour la divisibilité est {0}).

Par ailleurs, on rappelle que {\mathcal{D}(a)=\mathcal{D}(-a)} pour tout {a} de {\mathbb{Z}}.
On peut donc étendre la définition du pgcd aux entiers relatifs en posant {a\wedge b=\left|a\right|\wedge\left|b\right|}.

Dans la mesure où les propriétés relatives à la divisibilité (donc aux calculs de pgcd) ne dépendent pas du signe des entiers {a} et {b}, on supposera essentiellement que {a} et {b} sont des entiers naturels.

Algorithme d’Euclide

Proposition
Soit {a}, {b} et {q} trois entiers relatifs. Alors {\mathcal{D}(a)\cap\mathcal{D}(b)=\mathcal{D}(b)\cap\mathcal{D}(a-qb)}.
Autrement dit, les diviseurs communs de {a} et {b} sont exactement ceux de {b} et {a-qb}.

Ce résultat a une conséquence immédiate qui est la clef de l’algorithme d’Euclide :

Proposition (pgcd et division euclidienne)
Soit {a}, {b} deux entiers naturels, avec {b>0}.
Soit {a=qb+r} la division euclidienne de {a} par {b}. Alors {\mathcal{D}(a)\cap\mathcal{D}(b)=\mathcal{D}(b)\cap\mathcal{D}(r)}

Un application répétée de ce principe conduit au célèbre algorithme d’Euclide.

Proposition (algorithme d'Euclide)
Soit {a} et {b} deux entiers naturels strictement positifs. On veut calculer {a\wedge b}.
On forme une suite finie d’entiers {r_{k}}, à commencer par {r_{0}=a} et {r_{1}=b}.
Soit {k\ge1}. On suppose que {r_{k-1}} et {r_{k}} sont connus.
Si {r_{k}>0}, on note {r_{k-1}=q_{k}r_{k}+r_{k+1}} la division euclidienne de {r_{k-1}} par {r_{k}}.
Sous l’hypothèse {r_{k}>0}, on a donc défini {r_{k+1}}, avec {0\le r_{k+1}\lt r_{k}}.
La suite d’entiers naturels {(r_{k})_{k\ge1}} est finie car elle est strictement décroissante.
Il existe donc {n\in\mathbb{N}} tel que {r_n>0} et {r_{n+1}=0}. Avec ces notations, on a : {a\wedge b=r_n}.
Ainsi {a\wedge b} est le dernier reste non nul dans cette succession de divisions.

Exemples

  • Voici les huit divisions successives qui aboutissent à {14938\wedge 9471=77} : {\begin{array}{|rl|rl|}14938&=1*9471+5467&9471&=1*5467+4004\\5467&=1*4004+1463&4004&=2*1463+1078\\1463&=1*1078+385&1078&=2*385+308&\\385&=1*308+77&308&=4*77\end{array}}
  • Le nombre de divisions est parfois bien moindre (tout dépend bien sûr des quotients successifs) : la méthode est d’autant plus rapide que les quotients sont très supérieurs à {1}…)

    Voici par exemple le pcgd de {a=267914296} et de {b=317811} en seulement trois divisions : {\begin{array}{rl}267914296&=842*317811+317434\\ 317811&=1*317434+377\\3117434&=842*377+0\end{array}}

  • Voici un dernier exemple, plus théorique.
    On va montrer que {(n^{a}-1)\wedge(n^{b}-1)=n^{a\wedge b}-1}.
    Soit {a=qb+r} la division euclidienne de {a} par {b} (avec {a,b} dans {\mathbb{N}^{*}}).
    Pour tout {n} de {\mathbb{N}^{*}}, on a : {\begin{array}{rl}n^{a}-1&=n^{qb+r}-1=(n^{b})^{q}n^{r}-1\\\\&=((n^{b})^{q}-1)n^{r}+n^{r}-1\end{array}}
    Mais l’entier {(n^{b})^{q}-1} est factorisable (donc divisible) par {n^{b}-1}.
    Ainsi {n^{a}-1=q'(n^{b}-1)+r'}, avec {0\le r'=n^{r}-1\lt n^{b}-1}.
    Le reste dans la division de {n^{a}-1} par {n^{b}-1} est donc {n^{r}-1}.
    Il en découle facilement (algorithmes d’Euclide en parallèle), que : {(n^{a}-1)\wedge(n^{b}-1)=n^{a\wedge b}-1}
    Par exemple : {(2^{30}-1)\wedge(2^{24}-1)=2^{30\wedge 24}-1=2^{6}-1=63}.

Un peu de programmation Python

On écrit une fonction Python très simple qui calcule le pgcd par l’algorithme d’Euclide :

def pgcd1(a, b):
while b :
(a, b) = (b, a % b) # tant que b non nul, remplace (a,b) par (b,r)
return a # renvoie le dernier reste non nul (le pcgd)

On vérifie que ça marche sur les trois exemples précédents :

>>> pgcd1(14938,9471)
77
>>> pgcd1(267914296,317811)
377
>>> pgcd1(2**30-1,2**24-1)
63

Avec un petit effort de programmation, on modifie la fonction pgcd1 pour qu’elle renvoie non seulement le pcgd, mais aussi la description des étapes de l’algorithme d’Euclide :

def pgcd2(a, b):
e = []
while b:
(q, r) = (a // b, a % b)
e.append(‘{}={}*{}+{}’.format(a, q, b, r))
(a, b) = (b, r)
return (a, e)

Voici ce que renvoie la fonction pgcd2, toujours sur les exemples précédents :

>>> pgcd2(14938,9471)
(77, [‘14938=1*9471+5467’, ‘9471=1*5467+4004’, ‘5467=1*4004+1463’,
‘4004=2*1463+1078’, ‘1463=1*1078+385’, ‘1078=2*385+308’,
‘385=1*308+77’, ‘308=4*77+0’])
>>> pgcd2(267914296,317811)
(377, [‘267914296=842*317811+317434’, ‘317811=1*317434+377’,
‘317434=842*377+0’])
>>> pgcd2(2**30-1,2**24-1)
(63, [‘1073741823=64*16777215+63’, ‘16777215=266305*63+0’])

L’algorithme d’Euclide est par nature récursif (calculer le pgcd de {a} et {b}, c’est calculer celui de {b} et {r}, à moins que {b} soit nul auquel cas c’est fini). Voici une fonction Python qui utilise la récursivité :

def pgcd3(a, b) :
if b : return pgcd3(b, a % b)
else : return a

On peut même écrire une version encore plus compacte (avec lambda et le “if ternaire”) :

pgcd4 = lambda a, b  : pgcd4(b, a % b) if b else a

Voici maintenant une fonction Python qui renvoie l’ensemble des diviseurs d’un entier {n>0}.

On initialise l’ensemble {d=\mathcal{D}(n)} à la valeur {d=\emptyset}.
On utilise un compteur {k} qu’on incrémente à partir de {1}, sans jamais atteindre {\sqrt{n}}.
À chaque diviseur {k} de {n}, on ajoute à la fois {k} et {n/k} à l’ensemble {d} (on a {1\le k\lt \sqrt{n}\lt n/k\le n}).

À la sortie de la boucle, il faut vérifier si la dernière valeur de {k} vaut exactement {\sqrt{n}} (ce qui se produit si {n} est un carré parfait) car alors {n/k} et {k} sont égaux (et il suffit d’ajouter {k} à l’ensemble {d}).

def diviseurs(n) :
d = set(); k = 1
while k*k < n :
if n % k == 0 : d |= {k, n//k}
k += 1
if k*k == n : d.add(k)
return sorted(d)

Voici par exemple la liste des diviseurs de l’entier {210}

>>> diviseurs(210)
[1,2,3,5,6,7,10,14,15,21,30,35,42,70,105,210]

Quelques propriétés du pgcd

On peut considérer que l’algorithme d’Euclide constitue une nouvelle définition du pgcd (c’est le dernier reste non nul dans la succession des divisions).
Les propriétés suivantes sont alors des conséquences de cette définition algorithmique du pgcd.

On sait par exemple (depuis la toute première définition) que l’entier {a\wedge b} divise {a} et {b}.
Mais l’algorithme d’Euclide donne la réciproque : si un entier divise {a} et {b}, alors il divise leur pgcd.
Ceci constitue une caractérisation de l’entier strictement positif {n=a\wedge b}.

Proposition (caractérisation du pgcd)
Soit {a} et {b} deux entiers naturels, dont l’un au moins est non nul. Soit {n=a\wedge b}.
L’entier strictement positif {n=a\wedge b} est caractérisé par l’égalité {\mathcal{D}(n)=\mathcal{D}(a)\cap\mathcal{D}(b)}.

Interprétation et exemple

Soit {a} et {b} deux entiers naturels, dont l’un au moins est non nul. Soit {n=a\wedge b}.

  • d’une part {n} est le maximum de {\mathcal{D}(a)\cap\mathcal{D}(b)} au sens de la relation {\le} sur {\mathbb{N}}.
  • d’autre part {n} est le maximum de {\mathcal{D}(a)\cap\mathcal{D}(b)} au sens de la relation de divisibilité {\mid} sur {\mathbb{N}}.

Prenons l’exemple des deux entiers {a=210} et {b=330}.

Avec la fonction diviseurs définie précécemment, on forme la liste des diviseurs de {a} puis celle de {b}.
On vérifie que le pgcd de {a} et {b} vaut {30}.

On forme l’ensemble des diviseurs communs aux deux entiers {a} et {b}.
On vérifie qu’on obtient la même chose en demandant directement la liste des diviseurs de {30}.

Dans cette liste, l’entier {30} est à la fois le maximum pour l’ordre habituel dans {\mathbb{N}}, mais il est aussi le maximum en terme de divisibilité car il est multiple de chacun des éléments de la liste.

>>> diviseurs(210)
[1,2,3,5,6,7,10,14,15,21,30,35,42,70,105,210]
>>> diviseurs(330)
[1,2,3,5,6,10,11,15,22,30,33,55,66,110,165,330]
>>> pgcd1(210,330)
30
>>> set(diviseurs(210)) & set(diviseurs(330))
{1,2,3,5,6,10,15,30}
>>> diviseurs(30)
[1,2,3,5,6,10,15,30]

La proposition suivant montre qu’il est possible d’effectuer une mise en facteur (ou de diviser par un facteur commun) dans un calcul de pgcd.

Proposition (mise en facteur dans un calcul de pgcd)
Soit {a} et {b} deux entiers naturels, dont l’un au moins est non nul.
Pour tout entier strictement positif {k}, on a l’égalité : {(ka)\wedge(kb)=k\,(a\wedge b)}.
De même, si {k} est un diviseur commun à {a} et {b}, on a : {\dfrac{a}{k}\wedge\dfrac{b}{k}=\dfrac{a\wedge b}{k}}

Relation de Bézout

Proposition (relation de Bézout entre deux entiers)
Soit {a} et {b} deux entiers naturels, dont l’un au moins est non nul.
Alors il existe des entiers relatifs {u_{0}} et {v_{0}} tels que {a\wedge b=au_{0}+bv_{0}}.
Un telle égalité s’appelle une relation de Bézout entre {a} et {b}.
On dit que le couple {(u_{0},v_{0})} constitue un couple de coefficients de Bézout de {a} et {b}.
Proposition (combinaisons linéaires de deux entiers)
Soit {a} et {b} deux entiers naturels, dont l’un au moins est non nul.
L’ensemble {\{au+bv,\;u\in\mathbb{Z},\;v\in\mathbb{Z}\}} est exactement égal à l’ensemble des multiples de {a\wedge b}.

Recherche d’un couple de coefficients de Bézout

Pour trouver un couple de coefficients de Bézout de deux entiers strictement positifs {a} et {b}, il suffit de “remonter les calculs” dans l’algorithme d’Euclide.

Voici comment procéder avec {a=14938} et {b=9471}.

On commence par applique l’algorithme d’Eulcide au calcul de {a\wedge b=77} :

{\begin{array}{rl}14938=&1\cdot9471+5467\\9471=&1\cdot5467+4004\\5467=&1\cdot4004+1463\\4004=&2\cdot1463+1078\\1463=&1\cdot1078+385\\1078=&2\cdot385+308\\385=&1\cdot308+77\\308=&4\cdot77&&~&\end{array}}

Ensuite, on “remonte” les calculs pour obtenir l’égalité {26a-41b=77}.

{\begin{array}{rl}77=&385-308\\77=&385-(1078-2\cdot385)=3\cdot385-1078\\77=&3(1463-1078)-1078=-4\cdot1078+3\cdot1463\\77=&-4\cdot(4004-2\cdot1463)+3\cdot1463=11\cdot1463-4\cdot4004\\77=&11\cdot(5467-4004)-4\cdot4004=-15\cdot4004+11\cdot5467\\77=&-15\cdot(9471-5467)+11\cdot5467=26\cdot5467-15\cdot9471\\77=&26\cdot(14938-9471)-15\cdot9471=26\cdot14938-41\cdot9471\end{array}}

Programmation d’une méthode récursive

Soit {a=bq+r} la division euclidienne de {a} par {b}.
On sait que {a\wedge b=b\wedge r}.

Supposons connu un couple {(x,y)} de coefficients de Bézout de {b} et {r}.
Autrement dit {bx+ry=b\wedge r}, et il en résulte :{a\wedge b=b\wedge r=bx+(a-bq)y=ay+b(x-qy)}

Ainsi {(x'=y,y'=x-qy)} est un couple de coefficients de Bézout de {a} et {b}
Le problème se résout donc par des appels récursifs, qui finissent par aboutir au cas de base {b=0} pour lequel une solution {(x,y)} de l’équation {ax+by=a\wedge b=a} est {(1,0)} :

def recbezout(a,b):
if b == 0 : return (1,0) # si b=0, alors (x,y)=(1,0)
else : # sinon
(q, r) = divmod(a, b) # division euclidienne a=bq+r
(x, y) = recbezout(b, r) # coeffs de Bézout de (b,r)
return (y, x-q*y) # on en déduit des coeffs de Bézout de (a,b)

On vérifie que ça marche, en reprenant l’exemple {a=14938}, {b=9471}.

>>> recbezout(14938, 9471)
(26, -41)

Programmation d’une méthode itérative

Notons {(E_d)} l’équation {ax+by=d}, où {d} est dans {\mathbb{Z}}.

Soit {\alpha} et {\beta} dans {\mathbb{Z}}, avec {\beta\ne0}, et soit {\alpha=q\beta+r} la division euclidienne de {\alpha} par {\beta}.

Soit {(x_1,y_1)} une solution de {(E_\alpha)} et {(x_2,y_2)} une solution de {(E_\beta)}.

Les égalités {ax_1+by_1=\alpha} et {ax_2+by_2=\beta} impliquent :{a(x_1-qx_2)+b(y_1-qy_2)=\alpha-q\beta=r}
Le couple {(x_3=x_1-qx_2,\,y_3=y_1-qy_2)} est donc solution de {E_r}.

On remarque que {(1,0)} est solution de {(E_a)} et que {(0,1)} est solution de {(E_b)}.

Si on applique cette idée tout au long de l’algorithme d’Euclide de {(a,b)}, on forme, pour chacun des restes successifs {r_k}, une solution {(x_k,y_k)} de {(E_{r_k})}. À la fin, avec {r_n=a\wedge b}, on obtient une solution {(x_n,y_n)} de l’équation {(E_{r_n})}, c’est-à-dire de l’équation {ax+by=a\wedge b}.

Voici une fonction Python utilisant cette méthode :

def iterbezout(a,b):
(x1, y1, x2, y2) = (1, 0, 0, 1)
while b:
(q, r) = divmod(a, b); (a, b) = (b, r)
(x1, y1, x2, y2) = (x2, y2, x1-q*x2, y1-q*y2)
return (x1,y1)

On vérifie, en reprenant l’exemple {a=14938} et {b=9471} :

>>> iterbezout(14938,9471)
(26, -41)

Ppcm de deux entiers

Dans la suite, on considère deux entiers strictement positifs {a} et {b}.

L’intersection {a\mathbb{Z}\cap b\mathbb{Z}\cap\mathbb{N}^{*}} désigne l’ensemble des multiples communs strictement positifs de {a} et {b}. Cet ensemble est non vide, car il contient le produit {ab}. Il possède donc un plus petit entier strictement positif, ce qui conduit à la définition suivante :

Définition (ppcm de deux entiers strictement positifs)
Soit {a} et {b} deux entiers naturels strictement positifs. Soit {n} le minimum de l’ensemble {a\mathbb{Z}\cap b\mathbb{Z}\cap\mathbb{N}^{*}} des multiples communs strictement positifs de {a} et {b}.
L’entier {n\gt0} est appelé ppcm de {a} et {b}. Il est noté {n=\text{ppcm}(a,b)}, ou {n=a\vee b}.

Remarque sur le caractère minimum du ppcm

Le nom “ppcm est bien sûr une abréviation de “plus petit commun multiple.
En anglais, la dénomination est “lcm” (least common multiple). On utilisera la notation {a\vee b}.

On va voir que l’entier {a\vee b} est non seulement le minimum de {a\mathbb{Z}\cap b\mathbb{Z}\cap\mathbb{N}^{*}} au sens de l’ordre naturel, mais qu’il en est aussi le minimum au sens de l’ordre défini par la divisibilité.

En d’autres termes, non seulement {a\vee b\le m} pour tout multiple commun strictement positif {m} des entiers {a} et {b}, mais on a mieux : {a\vee b\mid m}.

Premières propriétés

Il est clair qu’on a les égalités {a\vee b=b\vee a}, et {a\vee 1=a}.

Par définition, l’entier {a\vee b} est un multiple commun aux entiers {a} et {b}.
On verra que la réciproque est vraie : les multiples communs à {a} et {b} sont aussi des multiples de {a\vee b}.

On a l’égalité {a\vee b=a} si et seulement si {a} est un multiple de {b}.

Un exemple

On forme la liste {m_{12}} des cinquante premiers multiples de l’entier {12} dans {\mathbb{N}^{*}}.
On crée ensuite la liste {m_{15}} des cinquante premiers multiples de l’entier {15} dans {\mathbb{N}^{*}}.

On forme enfin l’intersection ordonnée de ces deux listes. On obtient alors une liste de dix entiers strictement positifs, qui sont donc les dix premiers multiples communs de {12} et {15} dans {\mathbb{N}^{*}}.

On constate que le plus petit d’entre eux est l’entier {60} (donc {12\vee15=60}), et qu’il est effectivement un diviseur de tous les entiers de cette liste.

>>> m12 = list(12*k for k in range(1,51)); m12
[12,24,36,48,60,72,84,96,108,120,132,144,156,168,
180,192,204,216,228,240,252,264,276,288,300,312,
324,336,348,360,372,384,396,408,420,432,444,456,
468,480,492,504,516,528,540,552,564,576,588,600]
>>> m15 = list(15*k for k in range(1,51)); m15
[15,30,45,60,75,90,105,120,135,150,165,180,195,210,
225,240,255,270,285,300,315,330,345,360,375,390,
405,420,435,450,465,480,495,510,525,540,555,570,585,
600,615,630,645,660,675,690,705,720,735,750]
>>> sorted(set(m12)&set(m15))
[60,120,180,240,300,360,420,480,540,600]

On en vient à une caractérisation du ppcm de deux entiers strictement positifs.

Proposition (caractérisation du ppcm de deux entiers)
Soit {a,b} dans {\mathbb{N}^{*}}.
Le ppcm de {a} et {b} est l’unique entier strictement positif {n} tel que {a\mathbb{Z}\cap b\mathbb{Z}=n\mathbb{Z}}.
Autrement dit, les multiples communs de {a} et {b} sont exactement ceux de leur ppcm.

Extension aux entiers relatifs

Si {a=0} ou {b=0} on pose {a\vee b=0}, ce qui est compatible avec la caractérisation {a\mathbb{Z}\cap b\mathbb{Z}=(a\vee b)\mathbb{Z}}, mais ne cadre pas avec la première définition (car {0} est le seul multiple commun de {a} et {b}).

Enfin, si {a} et {b} sont dans {\mathbb{Z}}, on peut encore appeler ppcm de {a} et {b} celui de {\left|a\right|} et de {\left|b\right|}, c’est-à-dire l’unique entier naturel {n} tel que {a\mathbb{Z}\cap b\mathbb{Z}=(a\vee b)\mathbb{Z}}.

Dans la pratique, on ne perd pas grand-chose à se limiter aux cas {a>0} et {b>0}.

Quelques propriétés du ppcm

Proposition (mise en facteur ou simplification dans un calcul de ppcm)
Soit {a,b,k} trois entiers naturels strictement positifs.
Alors on a l’égalité : {(ka)\vee(kb)=k(a\vee b)}.
De même, si {k} est un diviseur commun de {a} et {b}, on a l’égalité : {\dfrac{a}{k}\vee\dfrac{b}{k}=\dfrac{a\vee b}{k}}.

La proposition suivante est admise pour l’instant. Elle sera démontrée après le “Lemme de Gauss” :

Proposition (lien entre le pgcd et le ppcm)
Soit {a,b} deux entiers naturels strictement positifs. Alors : {(a\wedge b)(a\vee b)=ab}

Il suffit donc de calculer {a\wedge b} (par l’algorithme d’Euclide) pour obtenir le ppcm par : {a\vee b=\dfrac{ab}{a\wedge b}}.

Voici comment faire avec Python :

def pgcd(a, b) :
return pgcd(b, a % b) if b else a
def ppcm(a,b) :
return a*b // pgcd(a,b)

Et voici un exemple d’utilisation :

>>> ppcm(240,350)
8400

Page précédente : divisibilité et division euclidienne
Page suivante : entiers premiers entre eux