Sauter au contenu
Logo image

Algèbre abstraite Théorie et applications

Thomas W. Judson

Section 2.2 L’algorithme de la division

Une application du principe du bon ordre que nous utiliserons souvent est l’algorithme de la division.
🔗

Démonstration.

C’est un exemple parfait de démonstration d’existence et d’unicité. Nous devons d’abord prouver que les entiers \(q\) et \(r\) existent effectivement. Puis nous devons montrer que si \(q'\) et \(r'\) sont deux autres tels entiers, alors \(q = q'\) et \(r = r'\text{.}\)
🔗

Existence de \(q\) et \(r\).

Posons
\begin{equation*} S = \{ a - bk : k \in {\mathbb Z} \text{ et } a - bk \geq 0 \}\text{.} \end{equation*}
Si \(0 \in S\text{,}\) alors \(b\) divise \(a\text{,}\) et nous pouvons poser \(q = a/b\) et \(r = 0\text{.}\) Si \(0 \notin S\text{,}\) nous pouvons utiliser le principe du bon ordre. Montrons d’abord que \(S\) est non vide. Si \(a \gt 0\text{,}\) alors \(a - b \cdot 0 \in S\text{.}\) Si \(a \lt 0\text{,}\) alors \(a - b(2a) = a(1 - 2b) \in S\text{.}\) Dans l’un ou l’autre cas, \(S \neq \emptyset\text{.}\) Par le principe du bon ordre, \(S\) possède un plus petit élément, disons \(r = a - bq\text{.}\) Donc \(a = bq + r\text{,}\) \(r \geq 0\text{.}\) Montrons maintenant que \(r \lt b\text{.}\) Supposons que \(r \gt b\text{.}\) Alors
\begin{equation*} a - b(q + 1)= a - bq - b = r - b \gt 0\text{.} \end{equation*}
Dans ce cas, \(a - b(q + 1)\) appartiendrait à l’ensemble \(S\text{.}\) Mais alors \(a - b(q + 1) \lt a - bq\text{,}\) ce qui contredirait le fait que \(r = a - bq\) est le plus petit élément de \(S\text{.}\) Donc \(r \leq b\text{.}\) Puisque \(0 \notin S\text{,}\) \(r \neq b\) et donc \(r \lt b\text{.}\)
🔗
🔗

Unicité de \(q\) et \(r\).

Unicité de \(q\) et \(r\text{.}\) Supposons qu’il existe des entiers \(r\text{,}\) \(r'\text{,}\) \(q\) et \(q'\) tels que
\begin{equation*} a = bq + r, 0 \leq r \lt b \quad \text{et}\quad a = bq' + r', 0 \leq r' \lt b\text{.} \end{equation*}
Alors \(bq + r = bq' + r'\text{.}\) Supposons que \(r' \geq r\text{.}\) La dernière équation donne \(b(q - q') = r' - r\) ; donc \(b\) divise \(r' - r\) et \(0 \leq r'- r \leq r' \lt b\text{.}\) Ceci n’est possible que si \(r' - r = 0\text{.}\) Donc \(r = r'\) et \(q = q'\text{.}\)
🔗
🔗
🔗
Soient \(a\) et \(b\) des entiers. Si \(b = ak\) pour un certain entier \(k\text{,}\) on écrit \(a \mid b\text{.}\) Un entier \(d\) est appelé un diviseur commun de \(a\) et \(b\) si \(d \mid a\) et \(d \mid b\text{.}\) Le plus grand commun diviseur des entiers \(a\) et \(b\) est un entier positif \(d\) tel que \(d\) est un diviseur commun de \(a\) et \(b\) et si \(d'\) est un autre diviseur commun de \(a\) et \(b\text{,}\) alors \(d' \mid d\text{.}\) On note \(d = \gcd(a, b)\) ; par exemple, \(\gcd( 24, 36) = 12\) et \(\gcd(120, 102) = 6\text{.}\) On dit que deux entiers \(a\) et \(b\) sont premiers entre eux si \(\gcd( a, b ) = 1\text{.}\)
🔗

Démonstration.

Posons
\begin{equation*} S = \{ am + bn : m, n \in {\mathbb Z} \text{ et } am + bn \gt 0 \}\text{.} \end{equation*}
Il est clair que l’ensemble \(S\) est non vide ; donc, par le principe du bon ordre, \(S\) possède un plus petit élément, disons \(d = ar + bs\text{.}\) Nous affirmons que \(d = \gcd( a, b)\text{.}\) Écrivons \(a = dq + r'\) où \(0 \leq r' \lt d\text{.}\) Si \(r' \gt 0\text{,}\) alors
\begin{align*} r'& = a - dq\\ & = a - (ar + bs)q\\ & = a - arq - bsq\\ & = a( 1 - rq ) + b( -sq )\text{,} \end{align*}
qui appartient à \(S\text{.}\) Mais cela contredirait le fait que \(d\) est le plus petit élément de \(S\text{.}\) Donc \(r' = 0\) et \(d\) divise \(a\text{.}\) Un argument analogue montre que \(d\) divise \(b\text{.}\) Par conséquent, \(d\) est un diviseur commun de \(a\) et \(b\text{.}\)
🔗
Supposons que \(d'\) soit un autre diviseur commun de \(a\) et \(b\text{,}\) et montrons que \(d' \mid d\text{.}\) En posant \(a = d'h\) et \(b = d'k\text{,}\) on obtient
\begin{equation*} d = ar + bs = d'hr + d'ks = d'(hr + ks)\text{.} \end{equation*}
Donc \(d'\) divise \(d\text{.}\) Ainsi, \(d\) est bien l’unique plus grand commun diviseur de \(a\) et \(b\text{.}\)
🔗
🔗

Sous-section 2.2.1 L’algorithme d’Euclide

Entre autres choses, le Théorème 2.2.2 nous permet de calculer le plus grand commun diviseur de deux entiers.
🔗

Exemple 2.2.4.

Calculons le plus grand commun diviseur de \(945\) et \(2415\text{.}\) Observons d’abord que
\begin{align*} 2415 & = 945 \cdot 2 + 525\\ 945 & = 525 \cdot 1 + 420\\ 525 & = 420 \cdot 1 + 105\\ 420 & = 105 \cdot 4 + 0\text{.} \end{align*}
En remontant les étapes, \(105\) divise \(420\text{,}\) \(105\) divise \(525\text{,}\) \(105\) divise \(945\text{,}\) et \(105\) divise \(2415\text{.}\) Donc \(105\) divise à la fois \(945\) et \(2415\text{.}\) Si \(d\) était un autre diviseur commun de \(945\) et \(2415\text{,}\) alors \(d\) devrait aussi diviser \(105\text{.}\) Par conséquent, \(\gcd( 945, 2415 ) = 105\text{.}\)
🔗
En remontant la suite d’équations ci-dessus, nous pouvons aussi trouver des entiers \(r\) et \(s\) tels que \(945 r + 2415 s = 105\text{.}\) Observons que
\begin{align*} 105 & = 525 + (-1) \cdot 420\\ & = 525 + (-1) \cdot [945 + (-1) \cdot 525]\\ & = 2 \cdot 525 + (-1) \cdot 945\\ & = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945\\ & = 2 \cdot 2415 + (-5) \cdot 945\text{.} \end{align*}
Donc \(r = -5\) et \(s= 2\text{.}\) Remarquons que \(r\) et \(s\) ne sont pas uniques, puisque \(r = 41\) et \(s = -16\) conviendraient également.
🔗
🔗
Pour calculer \(\gcd(a,b) = d\text{,}\) nous effectuons des divisions successives pour obtenir une suite décroissante d’entiers positifs \(r_1 \gt r_2 \gt \cdots \gt r_n = d\) ; c’est-à-dire,
\begin{align*} b & = a q_1 + r_1\\ a & = r_1 q_2 + r_2\\ r_1 & = r_2 q_3 + r_3\\ & \vdots\\ r_{n - 2} & = r_{n - 1} q_{n} + r_{n}\\ r_{n - 1} & = r_n q_{n + 1}\text{.} \end{align*}
Pour trouver \(r\) et \(s\) tels que \(ar + bs = d\text{,}\) nous partons de cette dernière équation et substituons les résultats obtenus à partir des équations précédentes :
\begin{align*} d & = r_n\\ & = r_{n - 2} - r_{n - 1} q_n\\ & = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )\\ & = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2}\\ & \vdots\\ & = ra + sb\text{.} \end{align*}
L’algorithme que nous venons d’utiliser pour trouver le plus grand commun diviseur \(d\) de deux entiers \(a\) et \(b\) et pour écrire \(d\) comme combinaison linéaire de \(a\) et \(b\) est connu sous le nom d’ algorithme d’Euclide.
🔗
🔗

Sous-section 2.2.2 Les nombres premiers

Soit \(p\) un entier tel que \(p \gt 1\text{.}\) On dit que \(p\) est un nombre premier, ou simplement que \(p\) est premier, si les seuls entiers positifs qui divisent \(p\) sont \(1\) et \(p\) lui-même. Un entier \(n \gt 1\) qui n’est pas premier est dit composé.
🔗

Démonstration.

Supposons que \(p\) ne divise pas \(a\text{.}\) Nous devons montrer que \(p \mid b\text{.}\) Puisque \(\gcd( a, p ) = 1\text{,}\) il existe des entiers \(r\) et \(s\) tels que \(ar + ps = 1\text{.}\) Donc
\begin{equation*} b = b(ar + ps) = (ab)r + p(bs)\text{.} \end{equation*}
Puisque \(p\) divise à la fois \(ab\) et lui-même, \(p\) divise \(b = (ab)r + p(bs)\text{.}\)
🔗
🔗

Démonstration.

Nous allons démontrer ce théorème par l’absurde. Supposons qu’il n’existe qu’un nombre fini de nombres premiers, disons \(p_1, p_2, \ldots, p_n\text{.}\) Posons \(P = p_1 p_2 \cdots p_n + 1\text{.}\) Alors \(P\) doit être divisible par un certain \(p_i\) pour \(1 \leq i \leq n\text{.}\) Dans ce cas, \(p_i\) diviserait \(P - p_1 p_2 \cdots p_n = 1\text{,}\) ce qui est une contradiction. Donc soit \(P\) est premier, soit il existe un nombre premier supplémentaire \(p \neq p_i\) qui divise \(P\text{.}\)
🔗
🔗

Démonstration.

Unicité.
Pour montrer l’unicité, nous allons procéder par récurrence sur \(n\text{.}\) Le théorème est certainement vrai pour \(n = 2\) car dans ce cas \(n\) est premier. Supposons maintenant que le résultat est vrai pour tout entier \(m\) tel que \(1 \leq m \lt n\text{,}\) et que
\begin{equation*} n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l\text{,} \end{equation*}
où \(p_1 \leq p_2 \leq \cdots \leq p_k\) et \(q_1 \leq q_2 \leq \cdots \leq q_l\text{.}\) D’après le Lemme 2.2.5, \(p_1 \mid q_i\) pour un certain \(i = 1, \ldots, l\) et \(q_1 \mid p_j\) pour un certain \(j = 1, \ldots, k\text{.}\) Puisque tous les \(p_i\) et \(q_i\) sont premiers, \(p_1 = q_i\) et \(q_1 = p_j\text{.}\) Donc \(p_1 = q_1\) puisque \(p_1 \leq p_j = q_1 \leq q_i = p_1\text{.}\) Par hypothèse de récurrence,
\begin{equation*} n' = p_2 \cdots p_k = q_2 \cdots q_l \end{equation*}
admet une factorisation unique. Donc \(k = l\) et \(q_i = p_i\) pour \(i = 1, \ldots, k\text{.}\)
🔗
🔗
Existence.
Pour montrer l’existence, supposons qu’il existe un entier qui ne peut pas s’écrire comme produit de nombres premiers. Soit \(S\) l’ensemble de tous ces entiers. Par le principe du bon ordre, \(S\) possède un plus petit élément, disons \(a\text{.}\) Si les seuls facteurs positifs de \(a\) sont \(a\) et \(1\text{,}\) alors \(a\) est premier, ce qui est une contradiction. Donc \(a = a_1 a_2\) où \(1 \lt a_1 \lt a\) et \(1 \lt a_2 \lt a\text{.}\) Ni \(a_1\in S\) ni \(a_2 \in S\text{,}\) puisque \(a\) est le plus petit élément de \(S\text{.}\) Donc
\begin{align*} a_1 & = p_1 \cdots p_r\\ a_2 & = q_1 \cdots q_s\text{.} \end{align*}
Par conséquent,
\begin{equation*} a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s\text{.} \end{equation*}
Donc \(a \notin S\text{,}\) ce qui est une contradiction.
🔗
🔗
🔗
🔗

Sous-section 2.2.3 Note historique

Les nombres premiers ont été étudiés pour la première fois par les Grecs de l’Antiquité. Deux résultats importants de l’Antiquité sont la démonstration d’Euclide qu’il existe une infinité de nombres premiers et le crible d’Ératosthène, une méthode pour calculer tous les nombres premiers inférieurs à un entier positif fixé \(n\text{.}\) Un problème de la théorie des nombres est de trouver une fonction \(f\) telle que \(f(n)\) soit premier pour chaque entier \(n\text{.}\) Pierre de Fermat (1601?–1665) conjectura que \(2^{2^n} + 1\) était premier pour tout \(n\text{,}\) mais Leonhard Euler (1707–1783) montra plus tard que
\begin{equation*} 2^{2^5} + 1 = 4{,}294{,}967{,}297 \end{equation*}
est un nombre composé. L’une des nombreuses conjectures non démontrées sur les nombres premiers est la conjecture de Goldbach. Dans une lettre à Euler en 1742, Christian Goldbach énonça la conjecture que tout entier pair à l’exception de \(2\) semblait être la somme de deux nombres premiers : \(4 = 2 + 2\text{,}\) \(6 = 3 + 3\text{,}\) \(8 =3 + 5\text{,}\) \(\ldots\text{.}\) Bien que la conjecture ait été vérifiée pour les entiers jusqu’à \(4 \times 10^{18}\text{,}\) elle n’a pas encore été démontrée en général. Puisque les nombres premiers jouent un rôle important en cryptographie à clé publique, on s’intéresse actuellement beaucoup à déterminer si un grand nombre est premier ou non.
🔗
🔗
🔗
PrécédentTopSuivant