Variables aléatoires discrètes

Les deux membres valent le plus grand diviseur commun positif de \(a_1, \dots, a_k\). Pour le membre de droite : par la Proposition « Diviseurs communs et PGCD » plus haut, les diviseurs de \((a_1 \wedge \dots \wedge a_{k-1}) \wedge a_k\) sont exactement les diviseurs communs de \(a_1 \wedge \dots \wedge a_{k-1}\) et de \(a_k\), qui par la même proposition sont les diviseurs communs de \(a_1, \dots, a_{k-1}, a_k\).

Par récurrence sur \(k \geq 2\).

• Initialisation \(k = 2\). Déjà fait (Bézout pour deux entiers).
• Hérédité. Supposons le résultat pour \(k - 1\) entiers. Deux cas.
  • Si \(a_1 = \dots = a_{k-1} = 0\), alors \(a_1 \wedge \dots \wedge a_k = a_k \wedge 0 = |a_k|\), et l'identité de Bézout \(|a_k| = a_k \cdot \mathrm{sgn}(a_k)\) (avec tous les autres \(u_i = 0\)) est immédiate.
  • Sinon, posons \(d' = a_1 \wedge \dots \wedge a_{k-1}\) (bien défini car la famille n'est pas toute nulle) et \(d = d' \wedge a_k = a_1 \wedge \dots \wedge a_k\). Par Bézout à deux entiers, \(d = d' \alpha + a_k \beta\) pour certains \(\alpha, \beta \in \mathbb{Z}\). Par hypothèse de récurrence, \(d' = a_1 u'_1 + \dots + a_{k-1} u'_{k-1}\). En substituant, $$ d = \alpha (a_1 u'_1 + \dots + a_{k-1} u'_{k-1}) + a_k \beta = a_1 (\alpha u'_1) + \dots + a_{k-1} (\alpha u'_{k-1}) + a_k \beta. $$ Poser \(u_i = \alpha u'_i\) pour \(i \leq k-1\) et \(u_k = \beta\).

Posons \(d = a_1 \wedge \dots \wedge a_r\). On montre que \(|\lambda| d\) est un diviseur commun de \(\lambda a_1, \dots, \lambda a_r\), et réciproquement que tout diviseur commun de \(\lambda a_1, \dots, \lambda a_r\) divise \(|\lambda| d\).

• \(|\lambda| d\) divise chaque \(\lambda a_i\) : de \(d \mid a_i\), on obtient \(|\lambda| d \mid |\lambda| a_i\), et \(|\lambda| a_i = \pm \lambda a_i\), donc \(|\lambda| d \mid \lambda a_i\).
• Soit \(\delta\) un diviseur commun de \(\lambda a_1, \dots, \lambda a_r\). Par Bézout pour \(r\) entiers, \(d = a_1 u_1 + \dots + a_r u_r\) pour certains \(u_i \in \mathbb{Z}\). On multiplie par \(\lambda\) : \(\lambda d = (\lambda a_1) u_1 + \dots + (\lambda a_r) u_r\), donc \(\delta \mid \lambda d\), donc \(\delta \mid |\lambda| d\).

Par la caractérisation des diviseurs (Proposition « Diviseurs communs et PGCD » plus haut), \(|\lambda| d = (\lambda a_1) \wedge \dots \wedge (\lambda a_r)\).

Posons \(m = a \vee b\).

• \((\supset)\) \(m\) est un multiple commun de \(a\) et \(b\) par définition, donc tout multiple de \(m\) est aussi un multiple commun.
• \((\subset)\) Soit \(n\) un multiple commun de \(a\) et \(b\). Appliquer la division euclidienne de \(n\) par \(m\) : \(n = m q + r\) avec \(0 \leq r < m\). Alors \(r = n - m q\) est combinaison \(\mathbb{Z}\)-linéaire de deux multiples communs de \(a\) et \(b\), donc est un multiple commun de \(a\) et \(b\). Comme \(0 \leq r < m\) et que \(m\) est le plus petit multiple commun strictement positif, \(r\) ne peut être dans \(\mathbb{N}^*\) ; donc \(r = 0\). Donc \(n = m q \in m \mathbb{Z}\).

• \((\Rightarrow)\) Si \(a \wedge b = 1\), l'identité de Bézout (Proposition « Identité de Bézout » plus haut) donne \(u, v \in \mathbb{Z}\) avec \(a u + b v = a \wedge b = 1\).
• \((\Leftarrow)\) Supposons \(a u + b v = 1\) pour certains \(u, v \in \mathbb{Z}\). Soit \(\delta\) un diviseur commun de \(a\) et \(b\). Par la propriété des combinaisons linéaires, \(\delta \mid (a u + b v) = 1\), donc \(\delta \in \{\pm 1\}\). Donc les seuls diviseurs communs sont \(\pm 1\), donc \(a \wedge b = 1\).

(i) Diviseurs premiers entre eux. De \(a \mid n\), écrire \(n = a k\) pour un certain \(k \in \mathbb{Z}\). Alors \(b \mid a k\). Comme \(a \wedge b = 1\), le lemme de Gauss donne \(b \mid k\), soit \(k = b k'\), donc \(n = a b k'\), donc \(a b \mid n\).
(ii) Premier à un produit. De \(a \wedge n = 1\), prendre \(a u + n v = 1\). De \(b \wedge n = 1\), prendre \(b u' + n v' = 1\). On multiplie : $$ 1 = (a u + n v)(b u' + n v') = a b (u u') + n (a u v' + b v u' + n v v'). $$ C'est une identité de Bézout pour \(a b\) et \(n\), donc par le théorème de Bézout \((a b) \wedge n = 1\).

L'ensemble \(D = \{d \in \mathbb{N} : d \geq 2 \text{ et } d \mid n\}\) est non vide (il contient \(n\)) et minoré par \(2\), donc admet un plus petit élément \(p_0 \in D\).
Affirmation : \(p_0\) est premier. Si \(p_0\) était composé, il aurait un diviseur \(d\) avec \(1 < d < p_0\). Alors \(d\) divise aussi \(n\) (transitivité), donc \(d \in D\) avec \(d < p_0\) --- ce qui contredit la minimalité de \(p_0\).
Donc \(p_0\) est premier, et \(p_0 \mid n\).

Démonstration classique d'Euclide, par l'absurde. Supposons par l'absurde que \(\mathbb{P}\) soit fini, disons \(\mathbb{P} = \{p_1, p_2, \dots, p_r\}\). On considère l'entier $$ N = p_1 \, p_2 \cdots p_r + 1. $$ Comme \(N \geq 2\), par la proposition précédente \(N\) admet un diviseur premier, disons \(p_k\) pour un certain \(k \in \{1, \dots, r\}\). Alors \(p_k\) divise à la fois \(N\) et \(p_1 \cdots p_r\), donc \(p_k\) divise leur différence \(N - p_1 \cdots p_r = 1\). Mais un nombre premier est \(\geq 2\), donc ne peut pas diviser \(1\) --- contradiction. Donc \(\mathbb{P}\) est infini.

Les diviseurs de \(p\) dans \(\mathbb{N}^*\) sont seulement \(1\) et \(p\). Donc \(a \wedge p \in \{1, p\}\).

• Si \(p \mid a\), alors \(p \in \operatorname{div}(a) \cap \operatorname{div}(p)\), donc \(a \wedge p = p\).
• Si \(p \nmid a\), alors \(p \notin \operatorname{div}(a) \cap \operatorname{div}(p)\), donc \(a \wedge p = 1\).

Les deux cas sont exclusifs et exhaustifs, donnant l'équivalence.

\((\Leftarrow)\) Immédiat par la propriété de divisibilité des produits.
\((\Rightarrow)\) Supposer \(p \mid a b\). Si \(p \mid a\), c'est fait. Sinon \(p \nmid a\), donc par la proposition précédente \(a \wedge p = 1\). Appliquer le lemme de Gauss à \(p \mid a b\) avec \(p \wedge a = 1\) : \(p \mid b\).

Par récurrence forte sur \(n \geq 1\).

• Initialisation \(n = 1\). Le produit vide (avec \(s = 0\)) donne \(1\), donc l'énoncé est vrai.
• Hérédité. Soit \(n \geq 2\), et on suppose l'énoncé vrai pour tout entier \(1 \leq k < n\). Deux cas :
  • Si \(n\) est premier, on écrit \(n = n\) (produit à un terme), et c'est fait.
  • Si \(n\) est composé, on écrit \(n = a b\) avec \(1 < a, b < n\) (par définition de composé). Par l'hypothèse de récurrence, \(a = q_1 \cdots q_s\) et \(b = q'_1 \cdots q'_t\) sont des produits de nombres premiers. En concaténant, \(n = q_1 \cdots q_s \, q'_1 \cdots q'_t\) est un produit de nombres premiers.

Posons \(\alpha = v_p(a)\) et \(\beta = v_p(b)\). Par définition, \(a = p^{\alpha} a'\) avec \(p \nmid a'\), et \(b = p^{\beta} b'\) avec \(p \nmid b'\). Alors $$ a b = p^{\alpha + \beta} (a' b'). $$ Par le lemme d'Euclide (contraposée), \(p \nmid a'\) et \(p \nmid b'\) entraînent \(p \nmid a' b'\). Donc la plus grande puissance de \(p\) divisant \(a b\) est exactement \(p^{\alpha + \beta}\), soit \(v_p(a b) = \alpha + \beta = v_p(a) + v_p(b)\).

Existence. Par le théorème d'existence ci-dessus, \(n = q_1 q_2 \cdots q_s\) est un produit de nombres premiers. Regrouper les premiers égaux : \(n = \prod_p p^{\alpha_p}\) avec \(\alpha_p = \) nombre d'indices \(i\) tels que \(q_i = p\). La famille \((\alpha_p)_{p \in \mathbb{P}}\) est à support fini.
Unicité. Supposons \(n = \prod_p p^{\alpha_p} = \prod_p p^{\beta_p}\) pour deux telles familles. Appliquer \(v_q\) (pour un premier \(q\) quelconque) aux deux membres ; par additivité de \(v_q\), $$ v_q(n) = \sum_p \alpha_p \, v_q(p) = \alpha_q, $$ puisque \(v_q(p) = 1\) si \(p = q\) et \(0\) sinon. Donc \(\alpha_q = v_q(n)\) pour tout premier \(q\), et de même \(\beta_q = v_q(n)\). Donc \(\alpha_q = \beta_q\) pour tout \(q\), soit l'unicité.

Divisibilité. Si \(a \mid b\), alors \(b = a k\) pour un certain \(k \in \mathbb{Z}^*\), donc \(v_p(b) = v_p(a) + v_p(k) \geq v_p(a)\) par additivité. Réciproquement, supposer \(v_p(a) \leq v_p(b)\) pour tout premier \(p\). On écrit $$ |a| = \prod_p p^{\alpha_p}, \qquad |b| = \prod_p p^{\beta_p}, $$ avec \(\alpha_p \leq \beta_p\) pour tout \(p\) par hypothèse. Alors $$ |b| = |a| \cdot \prod_p p^{\beta_p - \alpha_p}, $$ où le produit de droite est un entier de \(\mathbb{N}^*\). Donc \(|a| \mid |b|\), donc \(a \mid b\).
PGCD via valuations. Posons \(d = \prod_p p^{\min(v_p(a), v_p(b))}\).

• \(d \mid a\) : \(v_p(d) = \min(v_p(a), v_p(b)) \leq v_p(a)\) pour tout \(p\), donc \(d \mid a\) par la caractérisation de la divisibilité. De même \(d \mid b\).
• \(d\) est le plus grand : supposer \(\delta \mid a\) et \(\delta \mid b\). Alors \(v_p(\delta) \leq v_p(a)\) et \(v_p(\delta) \leq v_p(b)\) pour tout \(p\), donc \(v_p(\delta) \leq \min(v_p(a), v_p(b)) = v_p(d)\). Donc \(\delta \mid d\), donc \(|\delta| \leq d\).

Comme \(d \in \mathbb{N}^*\) et qu'il est le plus grand diviseur commun au sens de \(\leq\), \(d = a \wedge b\).
PPCM via valuations. Argument symétrique avec \(\max\) à la place de \(\min\).
Relation PGCD-PPCM. Pour tout premier \(p\), \(\min(v_p(a), v_p(b)) + \max(v_p(a), v_p(b)) = v_p(a) + v_p(b)\). En multipliant \(a \wedge b\) et \(a \vee b\) puis en prenant \(v_p\) : $$ v_p((a \wedge b)(a \vee b)) = v_p(a) + v_p(b) = v_p(a b) = v_p(|a b|). $$ Les deux membres sont des entiers positifs de mêmes valuations en tout premier, donc par unicité de la décomposition \((a \wedge b)(a \vee b) = |a b|\).

Déjà démontré dans le chapitre Relations binaires. En bref : \(a - a = 0 = n \cdot 0\) (réflexive) ; si \(n \mid (a - b)\) alors \(n \mid (b - a) = -(a - b)\) (symétrique) ; si \(n \mid (a - b)\) et \(n \mid (b - c)\), alors \(n \mid (a - c) = (a - b) + (b - c)\) par combinaison linéaire (transitive).

On applique la division euclidienne de \(a\) par \(n\) (Théorème « Division euclidienne » de la section sur la division euclidienne plus haut) : il existe un unique \((q, r) \in \mathbb{Z} \times \mathbb{N}\) avec \(a = n q + r\) et \(0 \leq r < n\). Alors \(a - r = n q\), soit \(a \equiv r \pmod n\), avec \(r \in \{0, 1, \dots, n-1\}\) unique.
Pour \(r, r' \in \{0, 1, \dots, n-1\}\) distincts, \(|r - r'| < n\) donc \(n \nmid (r - r')\), soit \(r \not\equiv r' \pmod n\). Les classes de \(0, 1, \dots, n-1\) sont donc deux à deux distinctes, et elles recouvrent \(\mathbb{Z}\). Donc \(|\mathbb{Z}/n\mathbb{Z}| = n\).

• \((\Leftarrow)\) Supposer \(a \wedge n = 1\). Par le théorème de Bézout, \(a u + n v = 1\) pour certains \(u, v \in \mathbb{Z}\). Alors \(a u = 1 - n v \equiv 1 \pmod n\), donc \(u\) est un inverse de \(a\) modulo \(n\).
• \((\Rightarrow)\) Supposer \(a u \equiv 1 \pmod n\), soit \(a u - 1 = n v\) pour un certain \(v\), donc \(a u + n (-v) = 1\). Par la réciproque du théorème de Bézout, \(a \wedge n = 1\).