313. Le PGCD est multiplicatif

Dans ce contenu, l’objectif est d’aboutir à la propriété suivante, qui traduit le caractère multiplicatif du $\pgcd$ vis-à-vis d’un facteur commun :

\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \forall m\in \N^{*}, \pgcd(ma,mb) = m\times \pgcd(a,b).

Note. L’algorithme d’Euclide permet de démontrer ce résultat. Néanmoins, une autre approche sera utilisée, de façon à manipuler les autres propriétés du $\pgcd.$

Démontrez une première inégalité

Fixez le contexte

Soient $a$ et $b$ deux entiers non simultanément nuls et soit $m$ un entier naturel non nul.

Comme $(a,b)\neq (0,0)$ le $\pgcd$ des entiers $a$ et $b$ est bien défini et :

\pgcd(a,b) = \max\{n\in\N^{*}, n\mid a \text{ et }n\mid b\}.

Comme $m$ est non nul, vous avez aussi $(ma,mb)\neq (0,0)\comma$ donc le $\pgcd$ des entiers $ma$ et $mb$ est bien défini et :

\pgcd(ma,mb) = \max\{n\in\N^{*}, n\mid ma \text{ et }n\mid mb\}.

Passez à la démonstration

Notez $d = \pgcd(a,b).$

Alors $d\mid a$ et $d\mid b.$

En multipliant par $m\comma$ il vient $md\mid ma$ et $md \mid mb.$

Comme $d$ et $m$ sont des entiers naturels non nuls, vous déduisez que $md$ est un entier naturel non nul. Par conséquent :

md\in \{n\in\N^{*}, n\mid ma \text{ et }n\mid mb\}.

Du coup, vous déduisez :

md \leq \pgcd(ma,mb).

Il a donc été démontré que :

\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \forall m\in \N^{*}, m\times \pgcd(a,b) \leq \pgcd(ma,mb).}

Démontrez une seconde inégalité

Cet autre passage est plus délicat, dans la mesure où il est choisi volontairement de ne pas utiliser l’algorithme d’Euclide.

Soient $a$ et $b$ deux entiers non simultanément nuls et soit $m$ un entier naturel non nul.

Vous posez $u = \pgcd(ma,mb).$

Alors :

\left\{\begin{align*} u&\mid ma\\ u&\mid mb. \end{align*} \right.

Vous notez encore $d = \pgcd(a,b).$

Il existe donc deux entiers $a’$ et $b’$ tels que :

\left\{\begin{align*} a&= da'\\ b&= db'. \end{align*} \right.

Remarquez que $(a’,b’)\neq (0,0)$ sinon vous auriez $(a,b)=(0,0)$ ce qui est exclu.

Démontrez que $a’$ et $b’$ sont premiers entre eux

D’après la première inégalité, appliquée aux entiers $a’$ et $b’$ et au facteur $d\comma$ il vient :

d\times \pgcd(a',b') \leq \pgcd(da',db').

Cela s’écrit :

d\times \pgcd(a',b') \leq \pgcd(a,b).

C’est-à-dire :

d\times \pgcd(a',b') \leq d.

Comme $d\gt 0$ il vient :

\pgcd(a',b') \leq 1.

Or, $\pgcd(a’,b’)$ est un entier naturel non nul, donc :

\boxed{\pgcd(a',b') = 1.}

Ramenez-vous au théorème de Gauss

Comme $ma = mda’$ et $mb = mdb’\comma$ vous avez :

\left\{\begin{align*} u&\mid mda'\\ u&\mid mdb'. \end{align*} \right.

Il existe donc deux entiers $a »$ et $b »$ tels que :

\left\{\begin{align*} mda' &= ua''\\ mdb' &= ub''. \end{align*} \right.

Ainsi :

\left\{\begin{align*} mda'b'' &= ua''b''\\ mdb'a'' &= ua''b''. \end{align*} \right.

Ainsi, il vient $mda’b » = mdb’a ».$ Comme $m\neq 0$ et comme $d\neq 0$ il vient :

a'b'' = a''b'.

Premier cas. Supposez $a’ \neq 0.$ Comme :

a' \mid a''b'

et comme $\pgcd(a’,b’)=1$ le théorème de Gauss fournit :

a' \mid a''.

Note. Une preuve directe du théorème de Gauss se trouve dans un autre article.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 310.

Il existe un entier $k$ tel que :

a'' = ka'.

L’égalité $mda’ = ua »$ fournit $mda’ = uka’.$ Comme $a’$ est non nul, vous obtenez $md = uk$ ce qui donne $u \mid md.$

Second cas. Supposez $a’ = 0.$ Comme $(a’,b’)\neq (0,0)$ il vient $b’\neq 0.$

D’après l’égalité $a’b » = a »b’\comma$ vous avez :

b'\mid a'b''.

Comme $\pgcd(a’,b’)=1$ le théorème de Gauss fournit :

b' \mid b''.

Il existe un entier $\ell$ tel que :

b'' = \ell b'.

L’égalité $mdb’ = ub »$ fournit $mdb’ = u\ell b’.$ Comme $b’\neq 0$ vous déduisez encore que $md = u\ell.$ Donc $u\mid md.$

Il a été démontré que dans tous les cas :

\boxed{u\mid md.}

Comme $u$ et $md$ sont des entiers strictement positifs, cela entraîne :

u\leq md

donc :

\boxed{ \pgcd(ma,mb)\leq m\times \pgcd(a,b).}

Concluez

Compte tenu des deux inégalités précédentes, le caractère multiplicatif du $\pgcd$ est établi.

\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \forall m\in \N^{*}, \pgcd(ma,mb) = m\times \pgcd(a,b).}

Bonus : une autre démonstration de la seconde inégalité

Soient $a$ et $b$ deux entiers non simultanément nuls et soit $m$ un entier naturel non nul.

Vous posez $u = \pgcd(ma,mb).$ Vous avez $u\in\NN.$

Il existe deux entiers $a’$ et $b’$ tels que :

\left\{\begin{align*} ma &= ua'\\ mb &= ub'. \end{align*} \right.

Vous allez considérer dans la suite le nombre $d=\pgcd(u,m)$ qui est bien défini puisque $m$ est non nul. Vous avez $d\in\NN.$

Alors il existe deux entiers $u’\in\NN$ et $m’\in\NN$ tels que :

\left\{\begin{align*} u &=du'\\ m &= dm'. \end{align*} \right.

Les entiers $u’$ et $m’$ sont premiers entre eux, par le même raisonnement que celui qui a montré plus haut que $a’$ et $b’$ sont premiers entre eux, en utilisant la première inégalité.

Vous obtenez alors :

\left\{\begin{align*} dm'a &= du'a'\\ dm'b &= du'b'. \end{align*} \right.

Du coup, en simplifiant par $d\neq 0$ vous obtenez :

\left\{\begin{align*} m'a &= u'a'\\ m'b &=u'b'. \end{align*} \right.

Et vous déduisez :

\left\{ \begin{align*} u'&\mid m'a\\ u'&\mid m'b. \end{align*} \right.

Comme $\pgcd(u’,m’)=1$ vous déduisez, par le théorème de Gauss :

\left\{ \begin{align*} u'&\mid a\\ u'&\mid b. \end{align*} \right.

Par définition du $\pgcd$ avec $u’\in\NN$ il vient :

u'\leq \pgcd(a,b).

Vous multipliez par $d$ qui est positif :

du'\leq d\times \pgcd(a,b).

Comme $u=du’\comma$ cela s’écrit :

u\leq d\times \pgcd(a,b).

Or, $d = \pgcd(u,m)\comma$ donc $d\mid m.$ Comme $d\in\NN$ et $m\in\NN$ vous avez $d\leq m.$

Ainsi :

u\leq m\times \pgcd(a,b).

Cela s’écrit :

\boxed{ \pgcd(ma,mb)\leq m\times \pgcd(a,b).}