Avancer

Section 11.1 Présentation

Rappelons qu'on désigne par \(\mathbb{Z}\) l'ensemble des entiers relatifs, et par \(\mathbb{N}\) celui des entiers naturels.

Définition 11.1.1.

Soit \(a, b\in\mathbb{Z}\text{.}\)

S'il existe \(q\in\mathbb{Z}\) tel que

\begin{equation*} a=b\cdot q \end{equation*}

alors on dit, de manière équivalente, que

  • \(a\) est un multiple de \(b\text{,}\)

  • \(a\) est divisible par \(b\text{,}\)

  • \(b\) divise \(a\text{,}\)

  • \(b\) est un diviseur de \(a\text{,}\)

et on note cela de la façon suivante :

\begin{equation*} b\vert a. \end{equation*}

  • \(15\) est un multiple de \(3\) car \(15=3\cdot 5\text{.}\)

  • \(15\) est divisible par \(-5\) car \(15=(-5)\cdot (-3)\text{.}\)

  • \(3\) divise \(-15\) car \(-15=3\cdot(-5)\text{.}\)

  • \(-5\) est un diviseur de \(-15\) car \(-15=(-5)\cdot 3\text{.}\)

  • \(5\vert 15\) car \(15=5\cdot 3\text{.}\)

Remarque 11.1.3.

Les critères de divisibilité suivants sont parfois bien utiles.

  • Un entier est divisible par \(2\) si et seulement s'il se termine par un chiffre pair, c'est-à-dire \(0, 2, 4, 6\) ou \(8\text{.}\)

  • Un entier est divisible par \(5\) si et seulement s'il se termine par \(0\) ou \(5\text{.}\)

  • Un entier est divisible par \(3\) si et seulement si la somme de ses chiffres est divisible par \(3\text{.}\)

  • Un entier est divisible par \(9\) si et seulement si la somme de ses chiffres est divisible par \(9\text{.}\)

  • L'entier \(1234\) est divisible par \(2\) mais pas par \(5\text{,}\) car il se termine par \(4\text{.}\)

  • L'entier \(1235\) est divisible par \(5\) mais pas par \(2\text{,}\) car il se termine par \(5\text{.}\)

  • L'entier \(1236\) est divisible par \(3\) mais pas par \(9\text{,}\) car \(1+2+3+6=12\) est divisible par \(3\) mais pas par \(9\text{.}\)

  • L'entier \(7236\) est divisible par \(3\) et par \(9\) car \(7+2+3+6=18\) est divisible par \(3\) et par \(9\text{.}\)

Les algorithmes Python ci-dessous prouvent l'existence de \((q,r)\text{.}\)

La preuve de son unicité est laissée en exercice.

  • Lorsqu'on effectue la division de \(100\) par \(35\text{,}\) on trouve que le quotient vaut \(q=2\) et le reste \(r=30\text{.}\)

    Et on a bien

    \begin{equation*} 100=35\cdot 2+30\qquad\text{et}\qquad 0\leq 30<35. \end{equation*}

  • Lorsqu'on effectue la division de \(-100\) par \(35\text{,}\) on trouve que le quotient vaut \(q=-3\) et le reste \(r=5\text{.}\)

    Et on a bien

    \begin{equation*} -100=35\cdot (-3)+5\qquad\text{et}\qquad 0\leq 5<35. \end{equation*}

  • Lorsqu'on effectue la division de \(432\) par \(18\text{,}\) on trouve que le quotient vaut \(q=24\) et le reste \(r=0\text{.}\)

    Et on a bien

    \begin{equation*} 432=18\cdot 24+0\qquad\text{et}\qquad 0\leq 0<18. \end{equation*}
Remarque 11.1.7.

Pour obtenir le reste \(r\) de la division euclidienne de \(a\) par \(b\) en Python, on utilise la commande a % b.

Notez qu'on a

\begin{equation*} b\vert a\quad\Leftrightarrow\quad a\;\%\;b=0. \end{equation*}

L'algorithme qui suit renvoie le quotient et le reste de la division euclidienne de \(a\) par \(b\text{.}\) Il fonctionne pour tout couple d'entiers positifs \((a;b)\text{.}\)

Généralisons maintenant cet algorithme de façon à inclure tous les cas \((a;b)\in\mathbb{Z}\times\mathbb{Z}^*\text{.}\)

Nous allons maintenant nous intéresser à l'ensemble des diviseurs d'un entier relatif donné.

Remarque 11.1.8.

  1. Pour tout \(n\in\mathbb{Z}\text{,}\)

    • \(1\vert n\) car \(n=1\cdot n\text{;}\)

    • \(n\vert n\) car \(n=n\cdot 1\text{.}\)

    Tout entier relatif \(n\) admet donc au moins \(\pm 1\) et \(\pm n\) comme diviseurs.

  2. Pour tout \(n\in\mathbb{Z}^*\text{,}\) on a

    \begin{equation*} d\vert n\quad\Rightarrow\quad |d|\leq |n|. \end{equation*}

Tout entier relatif non nul \(n\) possède donc un nombre fini de diviseurs dont le plus petit et le plus grand, parmi ceux qui sont positifs, sont \(1\) et \(|n|\text{.}\)

Dressons la liste de tous les diviseurs positifs de \(15\text{.}\)

On sait déjà que \(1\) et \(15\) sont le plus petit et le plus grand élément de cette liste.

Passons ensuite en revue tous les entiers de \(2\) à \(14\) et gardons ceux qui divisent \(15\text{.}\)

Finalement, on trouve que les diviseurs positifs de \(15\) sont

\begin{equation*} 1,\; 3,\; 5,\; 15. \end{equation*}

Voici comment coder l'exemple précédent en utilisant la même approche naïve, qui consiste à tester la divisibilité de \(15\) par tous les entiers compris entre \(1\) et \(15\text{,}\) afin de dresser la liste de tous les diviseurs positifs de \(15\text{.}\)

Si on fait appel au concept de nombre premier, on peut être plus efficace quand on cherche à dresser la liste de tous les diviseurs d'un entier relatif.

Définition 11.1.10.

On appelle nombre premier tout entier plus grand que \(1\) qui n'admet pas d'autre diviseur positif que \(1\) et lui-même.

Dans l'ordre croissant, la liste des nombres premiers commence ainsi :

\begin{equation*} 2,\; 3,\; 5,\; 7,\; 11,\; 13,\; 17,\; 19,\; 23,\; 29,\; 31,\;\ldots \end{equation*}
Remarque 11.1.11.

La première chose non triviale à dire sur les nombres premiers, c'est qu'il en existe une infinité.

Ce théorème est attribué à Euclide et il en existe toutes sortes de démonstrations.

On a

\begin{equation*} 15=1\cdot 15\quad\text{et}\quad 15=3\cdot 5. \end{equation*}

Il n'y a pas d'autre façon de factoriser \(15\) comme produit de deux entiers positifs car \(3\) et \(5\) sont des nombres premiers.

Les nombres \(1, 3, 5\) et \(15\) constituent donc la liste de tous les diviseurs positifs de \(15\text{.}\)

Remarque 11.1.13.

La deuxième chose non triviale à dire sur les nombres premiers, c'est que tout entier naturel se décompose comme produit de nombres premiers et que cette factorisation est unique si on range les facteurs premiers dans l'ordre croissant.

Ce théorème est assez important pour qu'on l'appelle Théorème fondamental de l'arithmétique.

Dressons la liste de tous les diviseurs positifs de \(18\text{.}\)

On commence par décomposer \(18\) en produit de facteurs premiers :

\begin{equation*} 18=2\cdot 3\cdot 3. \end{equation*}

Ses diviseurs positifs sont donc

\begin{equation*} 1,\; 2,\; 3,\; 2\cdot 3,\; 3\cdot 3,\; 2\cdot 3\cdot 3 \end{equation*}

c'est-à-dire

\begin{equation*} 1,\; 2,\; 3,\; 6,\; 9,\; 18. \end{equation*}

Dressons la liste de tous les diviseurs positifs de \(60\text{.}\)

On commence par décomposer \(60\) en produit de facteurs premiers :

\begin{equation*} 60=2\cdot 2\cdot 3\cdot 5. \end{equation*}

Ses diviseurs positifs sont donc

\begin{equation*} 1,\; 2,\; 3,\; 5,\; 2\cdot 2,\; 2\cdot 3,\; 2\cdot 5,\; 3\cdot 5,\; 2\cdot 2\cdot 3,\; 2\cdot 2\cdot 5,\; 2\cdot 3\cdot 5,\; 2\cdot 2\cdot 3\cdot 5 \end{equation*}

c'est-à-dire

\begin{equation*} 1,\; 2,\; 3,\; 5,\; 4,\; 6,\; 10,\; 15,\; 12,\; 20,\; 30,\; 60 \end{equation*}

et dans l'ordre

\begin{equation*} 1,\; 2,\; 3,\; 4,\; 5,\; 6,\; 10,\; 12,\; 15,\; 20,\; 30,\; 60. \end{equation*}

Intéressons-nous maintenant aux diviseurs que deux entiers relatifs ont en commun.

Quels sont les diviseurs positifs communs à \(15\) et \(18\text{?}\)

Diviseurs positifs de 15 : \(1,\; 3,\; 5,\; 15\text{.}\)

Diviseurs positifs de 18 : \(1,\; 2,\; 3,\; 6,\; 9,\; 18\text{.}\)

Diviseurs positifs communs : \(1,\; 3\text{.}\)

Quels sont les diviseurs positifs communs à \(15\) et \(60\text{?}\)

Diviseurs positifs de 15 : \(1,\; 3,\; 5,\; 15\text{.}\)

Diviseurs positifs de 60 : \(1,\; 2,\; 3,\; 4,\; 5,\; 6,\; 10,\; 12,\; 15,\; 20,\; 30,\; 60\text{.}\)

Diviseurs positifs communs : \(1,\; 3,\; 5,\; 15\text{.}\)

Quels sont les diviseurs positifs communs à \(18\) et \(60\text{?}\)

Diviseurs positifs de 18 : \(1,\; 2,\; 3,\; 6,\; 9,\; 18\text{.}\)

Diviseurs positifs de 60 : \(1,\; 2,\; 3,\; 4,\; 5,\; 6,\; 10,\; 12,\; 15,\; 30,\; 60\text{.}\)

Diviseurs positifs communs : \(1,\; 2,\; 3,\; 6\text{.}\)

Quels sont les diviseurs positifs communs à \(-120\) et \(77\text{?}\)

Diviseurs positifs de -120 : \(1,\;2,\;3,\;4,\;5,\;6,\;8,\;10,\;12,\;15,\;20,\;24,\;30,\;40,\;60,\;120\text{.}\)

Diviseurs positifs de 77 : \(1,\;7,\;11,\;77\text{.}\)

Diviseurs positifs communs : \(1\text{.}\)

Quels sont les diviseurs positifs communs à \(77\) et \(0\text{?}\)

Diviseurs positifs de 77 : \(1,\;7,\;11,\;77\text{.}\)

Diviseurs positifs de 0 : tous les entiers positifs, car on a

\begin{equation*} 0=0\cdot n\quad\Rightarrow\quad n\vert 0 \end{equation*}

pour tout entier \(n\text{.}\)

Diviseurs positifs communs : \(1,\;7,\;11,\;77\text{.}\)

Remarque 11.1.21.

L'ensemble des diviseurs positifs communs à deux entiers relatifs est

  • fini dès que l'un d'eux est non nul,

  • et non vide car il contient toujours \(1\text{.}\)

Cet ensemble admet donc un plus grand élément.

Autrement dit, deux entiers relatifs qui ne sont pas nuls tous les deux admettent toujours un diviseur positif commun qui est plus grand que tous les autres.

Définition 11.1.22.

On appelle Plus Grand Commun Diviseur de deux entiers relatifs \((a;b)\neq(0;0)\) le plus grand nombre parmi leurs diviseurs positifs communs.

On le note \(\text{PGCD}(a;b)\text{.}\)

On déduit des exemples 11.1.16, 11.1.17, 11.1.18, 11.1.19 et 11.1.20 que

  • \(\text{PGCD}(15;18)=3\text{,}\)

  • \(\text{PGCD}(15;60)=15\text{,}\)

  • \(\text{PGCD}(18;60)=6\text{,}\)

  • \(\text{PGCD}(-120;77)=1\text{,}\)

  • \(\text{PGCD}(77;0)=77\text{.}\)

Notons qu'on retrouve rapidement ces quatre premiers résultats à partir des décompositions en facteurs premiers :

\begin{align*} 15=3\cdot 5\quad\text{et}\quad 18=2\cdot 3^2\quad&\Rightarrow\quad\text{PGCD}(15;18)=3.\\ 15=3\cdot 5\quad\text{et}\quad 60=2^2\cdot 3\cdot 5\quad&\Rightarrow\quad\text{PGCD}(15;60)=3\cdot 5=15.\\ 18=2\cdot 3^2\quad\text{et}\quad 60=2^2\cdot 3\cdot 5\quad&\Rightarrow\quad\text{PGCD}(15;60)=2\cdot 3=6.\\ -120=-2^3\cdot 3\cdot 5\quad\text{et}\quad 77=7\cdot 11\quad&\Rightarrow\quad\text{PGCD}(-120;77)=1. \end{align*}

Enfin, l'exemple 11.1.20 permet de comprendre pourquoi on a

\begin{equation*} \text{PGCD}(a;0)=|a|\qquad\text{pour tout }a\in\mathbb{Z}^*. \end{equation*}

En particulier, ça donne \(\text{PGCD}(77;0)=77\text{.}\)

Remarque 11.1.24.

Dresser la liste des diviseurs communs à deux entiers relatifs ou les décomposer en produits de facteurs premiers sont des opérations qui prennent du temps.

Il existe une méthode plus simple pour déterminer leur PGCD : il s'agit de l'algorithme d'Euclide dont le principe itératif repose sur le fait suivant.

Montrer que \((a;b)\) et \((b;r)\) ont les mêmes diviseurs positifs communs revient à établir l'équivalence suivante, pour \(d\in\mathbb{N}^*\) :

\begin{equation*} d\vert a\text{ et }d\vert b\quad\Leftrightarrow\quad d\vert b\text{ et }d\vert r. \end{equation*}

Pour cela, nous allons démontrer chacune des deux implications concernées :

  1. \(d\vert a\) et \(d\vert b\quad\Rightarrow\quad d\vert r\;\text{;}\)

  2. \(d\vert b\) et \(d\vert r\quad\Rightarrow\quad d\vert a\;\text{.}\)

  • Commençons par l'implication 1. Supposons que \(d\vert a\) et \(d\vert b\text{,}\) de sorte qu'il existe deux entiers relatifs \(\alpha\) et \(\beta\) tels que

    \begin{equation*} a=\alpha\cdot d\qquad\text{et}\qquad b=\beta\cdot d. \end{equation*}

    Comme \(a=bq+r\text{,}\) on a

    \begin{align*} r&=a-bq\\ &=\alpha d-\beta dq\\ &=d\cdot(\alpha-\beta q)\\ &=d\cdot\rho\quad\text{avec }\rho=\alpha-\beta\cdot q\in\mathbb{Z}, \end{align*}

    donc \(d\vert r\text{.}\)

  • Passons maintenant à l'implication 2. Supposons que \(d\vert b\) et \(d\vert r\text{,}\) de sorte qu'il existe deux entiers relatifs \(\beta\) et \(\rho\) tels que

    \begin{equation*} b=\beta\cdot d\qquad\text{et}\qquad r=\rho\cdot d. \end{equation*}

    On a

    \begin{align*} a&=bq+r\\ &=\beta dq+\rho d\\ &=d\cdot(\beta q+\rho)\\ &=d\cdot\alpha\quad\text{avec }\alpha=\beta q+\rho\in\mathbb{Z}, \end{align*}

    donc \(d\vert a\text{.}\)

Les deux implications étant démontrées, nous avons prouvé que les couples \((a;b)\) et \((b;r)\) ont les mêmes diviseurs positifs communs.

Par définition du PGCD, il en découle que \(\text{PGCD}(a;b)=\text{PGCD}(b;r)\text{.}\)

Vérifions le théorème 11.1.25 dans le cas où \(a=40\) et \(b=16\text{.}\) La division euclidienne donne

\begin{equation*} 40=16\cdot 2+8. \end{equation*}

Pour \((a;b)=(40;16)\) :

  • Diviseurs positifs de 40 : \(1, 2, 4, 5, 8, 10, 20, 40\text{.}\)

  • Diviseurs positifs de 16 : \(1, 2, 4, 8, 16\text{.}\)

  • Donc les diviseurs positifs communs sont \(1, 2, 4, 8\) et

    \begin{equation*} \text{PGCD}(40;16)=8. \end{equation*}

Pour \((b;r)=(16;8)\) :

  • Diviseurs positifs de 16 : \(1, 2, 4, 8, 16\text{.}\)

  • Diviseurs positifs de 8 : \(1, 2, 4, 8\text{.}\)

  • Donc les diviseurs positifs communs sont \(1, 2, 4, 8\) et

    \begin{equation*} \text{PGCD}(16;8)=8. \end{equation*}

Vérifions le théorème 11.1.25 dans le cas où \(a=16\) et \(b=8\text{.}\) La division euclidienne donne

\begin{equation*} 16=8\cdot 2+0. \end{equation*}

Pour \((a;b)=(16;8)\) :

  • Diviseurs positifs de 16 : \(1, 2, 4, 8, 16\text{.}\)

  • Diviseurs positifs de 8 : \(1, 2, 4, 8\text{.}\)

  • Donc les diviseurs positifs communs sont \(1, 2, 4, 8\) et

    \begin{equation*} \text{PGCD}(16;8)=8. \end{equation*}

Pour \((b;r)=(8;0)\) :

  • Diviseurs positifs de 8 : \(1, 2, 4, 8\text{.}\)

  • Diviseurs positifs de 0 : \(\mathbb{N}^*\text{.}\)

  • Donc les diviseurs positifs communs sont \(1, 2, 4, 8\) et

    \begin{equation*} \text{PGCD}(8;0)=8. \end{equation*}
Algorithme d'Euclide : Calculer le PGCD de deux entiers par divisions euclidiennes successives.

  • Objectif : Calculer le PGCD de deux entiers \(a\in\mathbb{Z}^*\) et \(b\in\mathbb{Z}^*\text{.}\)

  • Principe :

    • Comme \(\text{PGCD}(a;b)=\text{PGCD}(|a|;|b|)\text{,}\) on peut toujours se ramener au cas où \(a\in\mathbb{N}^*\) et \(b\in\mathbb{N}^*\text{.}\)

    • Effectuer la division euclidienne de \(a\) par \(b\)

      \begin{equation*} a=b\cdot q+r\qquad\text{où}\qquad 0\leq r<b \end{equation*}

      et remplacer \((a;b)\) par \((b;r)\text{.}\)

    • Recommencer jusqu'à ce que \(r=0\text{.}\)

    • Le PGCD est alors le dernier \(r\neq 0\text{,}\) et c'est aussi le dernier \(b\text{.}\)

  • Voir aussi : Notes de cours de Jérôme.

Calculons \(\text{PGCD}(18;15)\) à l'aide de l'algorithme d'Euclide.

On a

\begin{equation*} \begin{array}{|c|c|c|c|} \hline a&b&\text{Division euclidienne}&r\\ \hline 18&15&18=15\cdot 1+3&3\\ 15&3&15=3\cdot 5+0&0\\ \hline \end{array} \end{equation*}

Donc \(\text{PGCD}(18;15)=3\text{.}\)

Calculons \(\text{PGCD}(60;15)\) à l'aide de l'algorithme d'Euclide.

On a

\begin{equation*} \begin{array}{|c|c|c|c|} \hline a&b&\text{Division euclidienne}&r\\ \hline 60&15&60=15\cdot 4+0&0\\ \hline \end{array} \end{equation*}

Donc \(\text{PGCD}(60;15)=15\text{.}\)

Calculons \(\text{PGCD}(120,77)\) à l'aide de l'algorithme d'Euclide.

On a

\begin{equation*} \begin{array}{|c|c|c|c|} \hline a&b&\text{Division euclidienne}&r\\ \hline 120&77&120=77\cdot 1+43&43\\ 77&43&77=43\cdot 1+34&34\\ 43&34&43=34\cdot 1+9&9\\ 34&9&34=9\cdot 3+7&7\\ 9&7&9=7\cdot 1+2&2\\ 7&2&7=2\cdot 3+1&1\\ 2&1&2=1\cdot 2+0&0\\ \hline \end{array} \end{equation*}

Donc \(\text{PGCD}(120;77)=1\text{.}\)

Calculons \(\text{PGCD}(2589;234)\) à l'aide de l'algorithme d'Euclide.

On a

\begin{equation*} \begin{array}{|c|c|c|c|} \hline a&b&\text{Division euclidienne}&r\\ \hline 2589&234&2589=234\cdot 11+15&15\\ 234&15&234=15\cdot 15+9&9\\ 15&9&15=9\cdot 1+6&6\\ 9&6&9=6\cdot 1+3&3\\ 6&3&6=3\cdot 2+0&0\\ \hline \end{array} \end{equation*}

Donc \(\text{PGCD}(2589;234)=3\text{.}\)

Remarque 11.1.32.

Les restes \(r\) obtenus successivement constituent une suite d'entiers strictement décroissante et minorée par \(0\text{.}\)

C'est pour cela que l'algorithme converge en un nombre fini d'étapes et qu'on finit par tomber sur \(r=0\text{.}\)

Peut-on estimer a priori le nombre d'étapes nécessaires à l'algorithme d'Euclide pour aboutir à \(\text{PGCD}(a;b)\text{?}\)

Le théorème de Lamé fait un bon pas dans cette direction.

Un jour peut-être.