Diviseurs

Plus grand commun diviseur

Définition

Notation : Soit \(a\) un entier naturel. On note \(D(a)\) l'ensemble des diviseurs positifs de l'entier \(a\).

Remarque

Si \(a = 0\), \(D(0) =\mathbb{N}\). Si \(a {\neq}0\), \(D(a)\) n'est pas vide en effet \(1\) et \(a\) appartiennent à \(D(a)\).

On a vu que si \(d\) est un diviseur de \(a\) alors \(d {\leqslant} a\) donc \(D (a)\) admet un plus grand élément qui est \(a\).

Notation : Soient \(a\) et \(b\) deux entiers naturels. On note \(D (a;b)\) l'ensemble des diviseurs positifs communs à \(a\) et \(b\).

Remarque

\(D (0;0) = \mathbb{N}\). Regardons ce qui se passe si \(a\) et \(b\) sont différents de \(0\).

Il vient immédiatement que \(D(a;b) = D(a) \cap  D(b)\).

\(D(a;b)\) est lui aussi non vide. En effet \(1\) divise \(a\) et \(b\) donc \(1\) est un diviseur commun à \(a\) et \(b\).

De plus les diviseurs de \(a\) étant inférieurs à \(a\) et ceux de \(b\) inférieurs à \(b\) les diviseurs communs à \(a\) et \(b\) sont inférieurs au plus petit des deux entiers \(a\) et \(b\). Donc \(D(a;b)\) contient un plus grand élément.

On retiendra le schéma suivant :

Notation : le plus grand élément de \(D (a;b)\) est le plus grand diviseur commun à \(a\) et \(b\).

On le note \(pgcd(a;b)\) ou de manière plus synthétique \(a \wedge b\).

Définition

on dit que deux entiers \(a\) et \(b\) sont premiers entre eux lorsque leur pgcd vaut \(1\). ( \(a \wedge b=1\) ).

Conséquences

On remarquera que \(pgcd(a ; b) = pgcd(b ; a)\) et \(pgcd(a ; 0) = a\)  la démonstration de ces deux résultats est triviale et passe par la simple définition. Mais ces résultats vont avoir une certaine importance plus tard.

Théorème

soient \(a\) et \(b\) deux entiers tels que \(b\) divise \(a\) alors \(pgcd(a;b) = b\)

Remarque

En particulier on aura \(pgcd(a ; 1) = 1\) et \(pgcd(a ; a) = a\) .

Preuve

\(D (a;b) = D (a) \cap  D (b)\) or comme \(b\) divise \(a\), \(b\) appartient à \(D (a)\). De plus \(b\) est le plus grand élément de \(D (b)\). Donc le plus grand élément en commun à \(D (a)\) et \(D (b)\) est forcément \(b\). Donc le plus grand élément de \(D (a ; b)\) est \(b\). D'où le résultat.

Recherche du PGCD

Résultats préliminaires

On suppose ici que \(a\) et \(b\) sont deux entiers différent de \(0\) tels que \(a>b\).

Car si \(a = 0\), \(pgcd(a ; b) = b\), si \(b = 0\) \(pgcd(a ; b) = a\) et si \(a = b\) alors \(pgcd(a ; b) = a\).

Dans le cas où \(a < b\) il suffira alors d'intervertir le rôle de a et b.

Théorème

\(pgcd(a ; b) = pgcd(b ; a - b)\) .

Preuve

On va utiliser un nouveau principe de démonstration appelé double inclusion. Pour cela on va montrer que \(D (a;b) \subset  D (b;a - b)\) puis que \(D (b; a - b) \subset D(a;b)\). Le signe \(\subset\)  se lit "inclus dans".

On considère un entier \(d \in D(a;b)\), alors \(d\) divise \(a\) et \(b\) donc toute combinaison linéaire de \(a\) et \(b\), en particulier \(d\) divise \(a - b\). Comme \(d\) divise \(b\) et \(a - b\) alors \(d \in D (b;a - b)\). On vient de démontrer que n'importe quel élément de \(D (a;b)\) appartient aussi à \(D (b;a - b)\).

Cela revient à dire que \(D(a;b) \subset D(b;a-b)\).

On prend ensuite un entier \(d \in D (b; a - b)\) alors \(d\) divise \(b\) et \(a - b\) donc toute combinaison linéaire de \(b\) et \(a - b\), en particulier \(d\) divise \(b + a - b\), c'est à dire \(a\). Comme \(d\) divise \(b\) et \(a\) alors \(d \in D (a;b)\). Donc \(D (b; a - b) \subset D (a;b)\).

Les deux ensembles étant inclus l'un dans l'autres on a \(D (b; a - b) = D (a;b)\). Ils ont donc le même plus grand élément d'où \(pgcd(a ; b) = pgcd(b ; a - b)\).

Remarque

l'avantage de ce théorème est que la recherche du pgcd de \(a\) et \(b\) est ramenée à celle des nombres \(b\) et \(a - b\) qui sont plus petits que \(a\) et \(b\).

Exercice :

Démontrer que pour tout entier naturel \(n\) non nul, les entiers \(n\) et \(2n + 1\) sont premiers entre eux.

Théorème

\(q\) et \(r\) désignent respectivement le quotient et le reste de la division Euclidienne de \(a\) par \(b\). Alors \(pgcd(a ; b) = pgcd(b ; r)\).

Preuve

On a : \(a = bq + r\) avec \(0 \leqslant r < b\).

Supposons que l'entier \(c \in D(a;b)\), alors \(c\) divise \(a\) et \(b\) donc toute combinaison linéaire de \(a\) et \(b\), en particulier \(c\) divise \(a - bq\) c'est à dire \(r\). Comme \(c\) divise \(b\) et \(r\) alors \(c \in  D (b;r)\).

Donc \(D (a;b) \subset D (b;r)\).

Supposons maintenant que l'entier \(c \in D (b; r)\) alors \(c\) divise \(b\) et \(r\) donc toute combinaison linéaire de \(b\) et \(r\), en particulier \(c\) divise \(bq +r\) c'est-à-dire \(a\). Comme \(c\) divise \(b\) et \(a\) alors \(c \in  D (a;b)\).

Donc \(D (b; r) \subset  D (a;b)\).

Les deux ensembles étant inclus l'un dans l'autre on a \(D (b;r) = D (a;b)\). Ils ont donc le même plus grand élément d'où \(pgcd(a ; b) = pgcd(b ; r)\).

Remarque

là encore \(b\) et \(r\) sont deux nombres plus petit que \(a\) et \(b\) ils sont même encore plus petits que \(b\) et \(a - b\) dès que \(q > 1\).

Exercice :

Montrer que si \(6\) divise l'entier \(n - 1\) alors \(pgcd(n - 1 ; 2n + 4) = 6\)

Algorithme d'Euclide

Si \(b\) divise \(a\) on sait que \(pgcd(a ; b) = b\). On suppose ici que \(b\) ne divise pas \(a\).

Théorème

On définit la suite \((r_n)\) de la façon suivante :

\(r_0 = b\) et \(r_1\) est le reste de la division euclidienne de \(a\) par \(b\).

Pour \(n \geqslant 1\) : si \(r_n = 0\) alors \(r_{n+1} = 0\)

Si \(r_n \neq 0\) alors \(r_{n+1}\) est le reste de la division euclidienne de \(r_{n-1}\) par \(r_n\).

Alors il existe un rang \(n_0\) tel que \(r_{n_0} \neq 0\) et pour tout \(n > n_0\), \(r_{n} = 0\). De plus \(pgcd(a ; b) = r_{n_0}\).

Remarque

C'est l'algorithme de recherche du pgcd que l'on connaît depuis la classe de 3ème.

Mais même s'il doit son nom au Mathématicien grec Euclide ce n'est pas tout à fait cet algorithme qu'Euclide présente dans l'ouvrage "Les Éléments". Il utilise la méthode des soustractions successives qui découle du théorème \(pgcd(a ; b) = pgcd(b ; a - b)\).

La seule nouveauté est que nous allons en donner une démonstration.

Preuve

Supposons que pour tout entier \(n\), \(r_n \neq 0\).

D'après l'encadrement de la division Euclidienne \(r_0 < b\) donc \(r_0 \leqslant b-1\).

Et pour tout \(n\), \(r_{n+1} < r_n\) donc \(r_2 < r_1\) d'où \(r_2 \leqslant r1 - 1\) et en utilisant l'inégalité ci-dessus \(r_2 \leqslant b-2\).

On montre par une récurrence immédiate que pour tout \(n\), \(r_n \leqslant b-n\).

On a donc en particulier si \(n = b + 1\), \(r_{b+1} \leqslant b - (b + 1)\) c'est à dire \(r_{b+1} \leqslant -1\) or pour tout \(n\), \(r_n \in \mathbb{N}\) . On a donc une absurdité. Notre hypothèse de départ est donc fausse.

Il existe un rang \(n_0\) tel que \(r_{n_0} = 0\).

Notons \(E\) l'ensemble des entiers \(n\) tel que \(r_n = 0\).

\(E\) étant une partie non vide de \(\mathbb{N}\) , elle admet un plus petit élément que l'on note \(n_1\).

On a donc \(r_{n_1} = 0\) et d'après la définition de la suite pour tout \(n \geqslant n_1\), \(r_n = 0\).

Posons \(n_0 = n_1-1\).

Comme \(n_0 < n_1\), \(n_0\) n'appartient pas à \(E\) donc \(r_{n_0} \neq 0\), et si \(n > n_0\) alors \(n \geqslant n_1\) et donc \(r_n = 0\).

On a vu que \(pgcd(a ; b) = pgcd(b ; r)\). En appliquant cette propriété aux éléments de la suite \((r_n)\) on obtient :

\(pgcd(a ; b) = pgcd(b ; r_0) = pgcd(r_0 ; r_1) = pgcd(r_1 ; r_2) = \dots = pgcd(r_{n_0} ; r_{n_1}) = pgcd(r_{n_0} ; 0) = r_{n_0}\).

Exercice :

Déterminer pgcd(1 414 ; 666).

Théorème de Bezout et conséquences

Théorème de Bezout

Théorème

\(a\) et \(b\) sont deux entiers naturels non nuls.

\(pgcd(a ; b) = 1 \Leftrightarrow\)  il existe deux entiers \(u\) et \(v\) tels que \(au + bv = 1\).

Remarque

\(u\) et \(v\) sont des entiers relatifs.

Ce n'est pas parce qu'il existe deux entiers u et v tels que \(au + bv\) \({\neq}\) 1 que \(pgcd(a ; b) \neq 1\).

Il suffit de voir que \(7 \times 4+2 \times (-13)=2\) et pourtant \(pgcd(7 ; 2)= 1\).

Preuve

Supposons qu'il existe deux entiers \(u\) et \(v\) tels que \(au + bv = 1\).

Notons \(d\) le pgcd de \(a\) et \(b\).

\(d\) divise \(a\) et \(d\) divise \(b\) donc \(d\) divise toute combinaison linéaire de \(a\) et \(b\) en particulier \(d\) divise \(au + bv\). Donc \(d\) divise \(1\). Mais le seul diviseur positif de \(1\) est \(1\) lui-même donc \(d = 1\). Finalement \(pgcd(a ; b) = 1\).

Supposons maintenant que \(pgcd(a ; b) = 1\).

Notons \(E\) l'ensemble de tous les entiers strictement positifs de la forme \(au + bv\) où u et v décrivent \(\mathbb{Z}\) .

\(a\) appartient à \(E\) car \(a\) est strictement positif et l'on peut écrire a sous la forme \(a \times 1+b \times 0\).

Donc \(E\) est une partie non vide de \(\mathbb{N}\) . Elle admet donc un plus petit élément.

Notons \(d\) ce plus petit élément.

Il existe donc deux entiers \(u_1\) et \(v_1\) tels que \(d = au_1 + bv_1\).

Effectuons la division euclidienne de \(a\) par \(d\).

Il existe deux entiers naturels \(q\) et \(r\) tels que \(a = dq + r\) et \(0 \leqslant r < d\). Supposons que \(r \neq 0\).

Donc \(a=dq+r=(au_1+bv_1)q+r \Rightarrow r= a \times (1-qu_1)+b\times (-qv_1)\)  

Or \(1-qu_1\) et \(-qv_1\)  sont des éléments de \(\mathbb{Z}\).

Donc \(r\) appartient à \(E\). Mais comme \(r < d\) cela contredit le fait que \(d\) est le plus petit élément de \(E\).

Donc \(r\) est forcément nul.

On vient donc de démontrer que \(d\) divise \(a\). On montre de même que \(d\) divise \(b\).

Donc \(d\) divise le \(pgcd\) de \(a\) et \(b\) qui vaut \(1\). Donc \(d\) divise \(1\). Finalement, on a montré que \(d = 1\).

Comme \(1\) appartient à \(E\), il existe deux entiers \(u\) et \(v\) tels que \(au + bv = 1\).

Exercice :

\(a\), \(b\) et \(c\) sont trois entiers naturels non nuls tels que : \(a\) et \(b\) sont premiers entre eux et \(a\) et \(c\) sont premiers entre eux.

Démontrer que \(a\) et \(bc\) sont premiers entre eux.

Caractérisation du pgcd

Théorème

\(a\), \(b\) et \(d\) sont trois entiers naturels non nuls. Les trois propositions suivantes sont équivalentes :

1. \(d\) est le pgcd de \(a\) et \(b\).

2. \(d\) est un diviseur de \(a\) et \(b\) et les quotients \(a'=\dfrac{a}{d}\) et \(b'=\dfrac{b}{d}\)  sont premiers entre eux.

3. \(d\) est un diviseur de \(a\) et de \(b\) et il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = d\).

Preuve

Pour démontrer ce théorème il faut démontrer que \(1 \Leftrightarrow 2\) ; \(1 \Leftrightarrow 3\) ; \(2 \Leftrightarrow 3\). Si l'on démontre chaque équivalence par double implication cela fait 6 démonstrations à faire. Nous allons former une "boucle" d'implication, en démontrant que \(1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 1\). Ce qui ne nous fait que trois démonstrations...

Supposons que \(d\) est le pgcd de \(a\) et \(b\), \(d\) est bien un diviseur de \(a\) et \(b\). Considérons \(a'=\dfrac{a}{d}\) et \(b'=\dfrac{b}{d}\).

Soit \(d'\) un diviseur commun de \(a'\) et \(b'\), alors \(a' = d'p\) et \(b' = d'q\) avec \(p\) et \(q\) deux entier naturels.

On a donc \(a = dd'p\) et \(b = dd'q\). Donc \(dd'\) est un diviseur commun à \(a\) et \(b\). Or le plus grand des diviseurs communs à \(a\) et \(b\) est \(d\) donc \(d' = 1\). Cela signifie que \(a'\) et \(b'\) sont premier entre eux.

On a démontré que \(1 \Rightarrow 2\).

Supposons que \(d\) est un diviseur de \(a\) et \(b\) et les quotients \(a'=\dfrac{a}{d}\) et \(b'=\dfrac{b}{d}\)  sont premiers entre eux.

D'après le théorème de Bezout, il existe deux entiers relatifs \(u\) et \(v\) tels que \(a'u + b'v = 1\), c'est à dire . Donc on a montré qu'il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = d\).

On a démontré que \(2 \Rightarrow 3\).

Supposons que : \(d\) est un diviseur de \(a\) et de \(b\) et il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = d\).

Notons \(d'\) le pgcd de \(a\) et \(b\). Comme \(d\) divise \(a\) et \(b\) alors \(d\) divise \(d'\). De plus \(d'\) divise \(a\) et \(b\) donc \(d'\) divise toute combinaison linéaire de \(a\) et \(b\).

En particulier : \(d'\) divise \(au + bv\). Donc \(d'\) divise \(d\).

Comme \(d\) divise \(d'\) et \(d'\) divise \(d\) alors \(d = d'\). \(d\) est bien le pgcd de \(a\) et \(b\).

On a démontré que \(3 \Rightarrow 1\).

Dans la pratique comment trouver les entiers \(u\) et \(v\) tels que \(au + bv = d\) ?

Il suffit de calculer \(d\) avec l'algorithme d'Euclide puis de remonter les égalités... un petit exemple.

Exemple 1

Trouver deux entiers \(u\) et \(v\) tels que \(388u + 156v = 4\).

On commence par vérifier si le pgcd de \(388\) et \(156\) ne serait pas égal à \(4\), ce qui nous assurerait l'existence des deux entiers \(u\) et \(v\).

On a:

\(388 = 156 \times 2 + 76\)

\(156 = 76 \times 2+4\)

\(76 = 4 \times 19+0\)

Ces égalités impliquent :

\(388 - 156 \times 2 = 76\)

\(156-76 \times 2=4\)

En remplaçant on a \(156 - (388 - 156 \times 2) \times 2 = 4\) c'est à dire, après calculs, \(388 \times (-2) + 156 \times 5 = 4\) .

Donc \(u = -2\) et \(v = 5\) conviennent.

Exemple 2 : Méthode de Lamé-Lucas

ici, \(a= 388\) et \(b=156\)

Restes	u	v	Calcul
388	1	0	\(388=1 \times 388+0 \times 156\)
156	0	1	\(156=0 \times 388+1 \times 156\)
76	1	-2	\(76=1 \times 388+(-2) \times 156\)
4	-2	5	\(4=1 \times 156 + (-2) \times 76\)

On retrouve les coefficients \(u = -2\) et \(v = 5\).

Théorème

Toute fraction est égale à une fraction irréductible.

Exercice : Démontrer le théorème ci-dessus.

Propriétés du pgcd

Théorème

si \(d\) est le pgcd des deux entiers naturel \(a\) et \(b\) alors, pour tout entier naturel non nul \(c\), \(dc\) est le pgcd de \(ac\) et \(bc\).

Preuve

Nous allons utiliser la 3ème assertion du théorème précédent.

\(d\) divise \(a\) et \(b\) donc \(dc\) divise \(ac\) et \(bc\).

Comme \(d = pgcd(a ; b)\) alors il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = d\) et donc \(acu + bcv = dc\).

D'où d'après le théorème précédent \(dc = pgcd(ac ; bc)\).

Remarque

on appelle parfois cette propriété la propriété multiplicative du pgcd.

Exercice :

Pour tous entiers \(m\) et \(n\) non nuls déterminer \(pgcd(mn ; n(2m+1))\).

Théorème de Gauss

Théorème

\(a\), \(b\) et \(c\) sont des entiers strictement positifs.

Si \(a\) divise \(bc\) et \(a\) et \(b\) sont premiers entre eux alors \(a\) divise \(c\).

Preuve

Puisque \(a\) et \(b\) sont premiers entre eux alors, d'après le théorème de Bezout :

il existe \(u\) et \(v\) entiers relatifs tels que \(au + bv = 1\).

Donc il existe \(u\) et \(v\) entiers relatifs tels que \(acu + bcv = c\).

Comme \(a\) divise \(bc\) alors \(a\) divise \(bcv\) et trivialement \(a\) divise \(acu\).

Finalement \(a\) divise \(acu + bcv\) c'est à dire \(c\).

Exercice :

Trouver tous les couples d'entiers relatifs \((x ; y)\) tels que \(7x = 5y\).

Corollaire

Si \(n\) est divisible par \(a\) et \(b\) et que \(pgcd(a ; b) = 1\) alors \(n\) est divisible par \(ab\).

Preuve

Comme \(n\) est divisible par \(a\) et \(b\) il existe deux entiers naturels \(p\) et \(q\) tels que \(n = ap = bq\).

Donc \(b\) divise \(ap\) et \(pgcd(a ; b) = 1\), d'après le théorème de Gauss \(b\) divise \(p\).

Donc il existe un entier \(p'\) tel que \(p = bp'\).

Finalement on a démontré l'existence d'un entier \(p'\) tel que \(n = abp'\). Ce qui signifie que \(ab\) divise \(n\).

Équations diophantiennes

Le but est de résoudre dans \(\mathbb{Z}\)  les équations du type \(ax + by = c\) où \(a\), \(b\) et \(c\) sont trois entiers relatifs fixés et \(x\) et \(y\) les inconnues.

Ces équations sont appelées équations diophantiennes.

C'est le mathématicien grec Diophante d'Alexandrie qui vécu au Ier ou au IIIème siècle qui étudia ce type d'équations, et plus généralement l'arithmétique.

Théorème

L'équation \(ax + by = c\) admet des solutions si et seulement si \(pgcd(a ; b)\) divise \(c\).

Preuve

Supposons que cette l'équation \(ax + by = c\) admet une solution, notée \((x_0 ; y_0)\).

Alors \(ax_0 + by_0 = c\) comme \(pgdc(a ; b)\) divise \(a\) et \(b\) alors \(pgcd(a ; b)\) divise \(ax_0 + by_0\) donc \(pgcd(a ; b)\) divise \(c\).

Supposons maintenant que pgcd(a ; b) divise c. Notons d = pgcd(a ; b).

Il existe donc trois entier \(a'\),\(b'\) et \(c'\) tels que \(a = a'd\), \(b = b'd\) et \(c = c'd\).

Donc l'équation \(ax + by = c\)  est équivalente à l'équation \(a'x + b'y = c'\).

Or comme \(d = pgcd(a ; b)\) on sait que \(a'\) et \(b'\) sont premiers entre eux.

D'après le théorème de Bezout il existe deux entiers \(u\) et \(v\) tels que \(a'u+b'v = 1\) et donc \(a'c'u + b'c'v = c'\).

Le couple \((x_0 ; y_0) = (c'u ; c'v)\) est donc solution de l'équation \(a'x + b'y = c'\) et donc de l'équation \(ax + by = c\).

Corollaire

Si l'équation \(ax + by = c\) admet une solution notée \((x_0 ; y_0)\) alors elle en admet une infinité.

L'ensemble de tous les couples solutions est l'ensemble des couples \(\left(x_0-k\dfrac{b}{d};y_0-k\dfrac{a}{d}\right)\) avec \(k \in \mathbb{Z}\) et \(d = pgcd(a ; b)\).

Preuve

Soit \((x ; y)\) une solution de ax + by = c , montrons qu'il existe \(k \in \mathbb{Z}\) tel que \((x; y) = (x_0-k\dfrac{b}{d};y_0-k\dfrac{a}{d})\) .

Comme \((x_0 ; y_0)\) est aussi une solution on obtient par soustraction membre à membre \(a(x - x_0) + b(y - y_0) = 0\).

C'est-à-dire \(a(x - x_0) = -b(y - y_0)\). En divisant chaque membre de l'égalité par d on obtient \(a'(x - x_0) = -b'(y - y_0)\) où \(a'\) et \(b'\) sont deux entiers premiers entre eux.

D'après le théorème de Gauss \(a'\) divise \(y - y_0\) donc il existe un entier \(k\) tel que \(y - y_0 = ka'\).

C'est-à-dire qu'il existe un entier k tel que \(y = y0 +ka'\). En substituant on trouve que \(x = x_0-kb'\).

Vérifions maintenant que pour tout entier k le couple \((x_0-k\dfrac{b}{d};y_0-k\dfrac{a}{d})\)  est solution de l'équation \(ax + by = c\).

\(a(x_0-k\dfrac{b}{d})+b(y_0-k\dfrac{a}{d})=ax_0+by_0+k\dfrac{ab}{d}-k\dfrac{ab}{d}=0\) car \((x_0 ; y_0)\) est une solution.

Exercice :

Résoudre dans \(\mathbb{Z}^2\) l'équation \((E)\) : \(7x - 11y = 3\).

On commencera par trouver une solution particulière de l'équation \(7x - 11y = pgcd(7 ; 11)\), on en déduira une solution particulière de \((E)\) puis toutes les solutions.

Plus petit commun multiple

Définition

Définition

On note \(ppcm(a ; b)\) le plus petit multiple commun à \(a\) et \(b\).

Remarque

si on considère \(E\) l'ensemble des multiples communs à \(a\) et \(b\). Alors \(E\) est une partie de \(\mathbb{N}\)  et \(E\) n'est pas vide en effet l'entier \(ab\) appartient à \(E\). Donc \(E\) admet un plus petit élément. La définition a bien un sens.

Lien avec le pgcd

Théorème

\(a\) et \(b\) sont deux entiers naturels non nuls. On note \(d\) leur pgcd et \(m\) leur ppcm. Alors \(md = ab\) et tout multiple commun à \(a\) et \(b\) est un multiple de \(m\).

Preuve

Comme \(d = pgcd(a ; b)\) il existe deux entier \(a'\) et \(b'\) tels que \(a = da'\) et \(b = db'\) avec \(a'\) et \(b'\) premiers entre eux.

Notons \(M\) un multiple commun à \(a\) et \(b\). Il existe deux entiers \(p\) et \(q\) tels que \(M = ap = bq\).

Donc \(M = da'p = db'q\) et \(a'p = b'q\). Comme \(a'\) et \(b'\) sont premiers entre eux et que \(a'\) divise \(b'q\) d'après le théorème de Gauss \(a'\) divise \(q\). Donc il existe un entier \(k\) tel que \(q = ka'\) et d'après l'égalité \(a'p = b'q\), \(p = kb'\). Donc en remplaçant on obtient \(M = kda'b'\).

Réciproquement : montrons que tout nombre \(M\) qui s'écrit \(M = kda'b'\) est un multiple commun à \(a\) et \(b\).

On a \(M = k(da')b'=akb'\) donc \(M\) est un multiple de \(a\). De même \(M = bka'\) donc \(M\) est un multiple de \(b\).

On a donc montré que les multiples communs à \(a\) et \(b\) sont les multiples de \(da'b'\). Le plus petit multiple commun à \(a\) et \(b\) est donc \(da'b'\), lui-même.

Ainsi \(m = da'b' \Leftrightarrow md = da'db' \Leftrightarrow md = ab\), et, tous les multiples communs à \(a\) et \(b\) étant des multiples de \(da'b'\) ce sont des multiples de \(m\).

Remarque

on a une expression explicite du ppcm(a ; b), c'est \(da'b'\) où \(a'\) et \(b'\) sont les entiers tels que \(a = da'\) et \(b= db'\).

Exercice :

\(n\) est un entier naturel non nul, on pose \(a = n^2 + 3n\) et \(b = (2n + 1)(n + 3)\).

Déterminer \(ppcm(a ; b)\).

Caractérisation du ppcm

Théorème

\(a\), \(b\) et \(m\) sont trois entiers strictement positifs.

\(m\) est le ppcm de \(a\) et \(b\) \(\Leftrightarrow\)  \(m\) est un multiple de \(a\) et \(b\) et les entiers \(\dfrac{m}{a}\) et \(\dfrac{m}{b}\) sont premiers entre eux

Preuve

Soit \(m = ppcm(a ; b)\). On a vu que \(m = da'b'\). Donc \(m = ab' = ba'\) d'où \(a'=\dfrac{m}{b}\)  et \(b'=\dfrac{m}{a}\) . Or on sait que a' et b' sont premiers entre eux, d'où le résultat.

Réciproquement

Considérons \(M\) est un multiple commun à \(a\) et \(b\) tel que \(\dfrac{M}{a}\)  et \(\dfrac{M}{b}\) soient premiers entre eux.

D'après le théorème précédent on sait que \(M\) est un multiple de \(m\).

Il existe donc un entier \(k\) tel que \(M = km\).

D'après la remarque précédente \(M = kda'b' = kab' = ka'b\) ainsi  \(\dfrac{M}{a}= kb'\) et  \(\dfrac{M}{b}= ka'\).

Par hypothèse ka' et kb' sont premiers entre eux d'où \(k = 1\). Finalement \(M = m\).