Dans cet article, l’objectif est d’aboutir à la propriété suivante, traduisant la multiplicité du $\mathrm{PGCD}$ :
\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \forall m\in \N^{*}, \mathrm{PGCD}(ma,mb) = m\times \mathrm{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 $\mathrm{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 $\mathrm{PGCD}$ des entiers $a$ et $b$ est bien défini et :
\mathrm{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)$ le $\mathrm{PGCD}$ des entiers $ma$ et $mb$ est bien défini et :
\mathrm{PGCD}(ma,mb) = \max\{n\in\N^{*}, n\mid ma \text{ et }n\mid mb\}.Passez à la démonstration
Notez $d = \mathrm{PGCD}(a,b).$
Alors $d\mid a$ et $d\mid b.$
En multipliant par $m$, il vient :
$md\mid ma$ et $md \mid mb.$
Comme $d$ et $m$ sont non nuls, vous déduisez que $md$ est 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 \mathrm{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 \mathrm{PGCD}(a,b) \leq \mathrm{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 = \mathrm{PGCD}(ma,mb).$
Alors :
\left\{\begin{align*}
u&\mid ma\\
u&\mid mb.
\end{align*}
\right.Vous notez encore $d = \mathrm{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é, il vient :
d\times \mathrm{PGCD}(a',b') \leq \mathrm{PGCD}(da',db').Cela s’écrit :
d\times \mathrm{PGCD}(a',b') \leq \mathrm{PGCD}(a,b).C’est-à-dire :
d\times \mathrm{PGCD}(a',b') \leq d.Comme $d\neq 0$ il vient :
\mathrm{PGCD}(a',b') \leq 1.Or, $\mathrm{PGCD}(a’,b’)$ est un entier non nul, donc :
\boxed{\mathrm{PGCD}(a',b') = 1.}Ramenez-vous au théorème de Gauss
Comme
\left\{\begin{align*}
u&\mid mda'\\
u&\mid mdb'
\end{align*}
\right.Il existe 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 : $a’ \neq 0.$ Comme :
a' \mid a''b'
et comme $\mathrm{PGCD}(a’,b’)=1$ le théorème de Gauss (dont une preuve directe se trouve dans le contenu rédigé dans l'article 310) fournit :
a' \mid a''.
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 : $a’ = 0.$ Comme $(a’,b’)\neq (0,0)$ il vient $b’\neq 0.$
Vous utilisez le fait que :
b'\mid a'b''.
Comme $\mathrm{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 positifs, cela entraîne :
u\leq md
donc :
\boxed{ \mathrm{PGCD}(ma,mb)\leq m\times \mathrm{PGCD}(a,b) .}Concluez
Compte tenu des deux inégalités précédentes, le caractère multiplicatif du $\mathrm{PGCD}$ est établi.
\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \forall m\in \N^{*}, \mathrm{PGCD}(ma,mb) = m\times \mathrm{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 = \mathrm{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=\mathrm{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$, nécessairement premiers entre eux, d’après la première inégalité démontrée ci-dessus, tels que :
\left\{\begin{align*}
u &=du'\\
m &= dm'.
\end{align*}
\right.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.Notez que $u=du’$ avec $u\neq 0$ impose $u’\neq 0.$ Comme $\mathrm{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 $\mathrm{PGCD}$ avec $u’\in\NN$ il vient :
u'\leq \mathrm{PGCD}(a,b).Vous multipliez par $d$ qui est positif :
du'\leq d\times \mathrm{PGCD}(a,b).Comme $u=du’$ :
u\leq d\times \mathrm{PGCD}(a,b).Or, $d = \mathrm{PGCD}(u,m)$, donc $d\mid m.$ Or $d\in\NN$ et $m\in\NN$ donc $d\leq m.$
Ainsi :
u\leq m\times \mathrm{PGCD}(a,b).Cela s’écrit :
\boxed{ \mathrm{PGCD}(ma,mb)\leq m\times \mathrm{PGCD}(a,b) .}Partagez maintenant !
Aidez vos amis à découvrir cet article et à mieux comprendre le sujet.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !