Discrete random variables

Both sides equal the largest common positive divisor of \(a_1, \dots, a_k\). For the right side: by the Proposition « Common divisors and the gcd » above, the divisors of \((a_1 \wedge \dots \wedge a_{k-1}) \wedge a_k\) are exactly the common divisors of \(a_1 \wedge \dots \wedge a_{k-1}\) and \(a_k\), which by the same proposition again are the common divisors of \(a_1, \dots, a_{k-1}, a_k\).

By induction on \(k \geq 2\).

• Base \(k = 2\). Already done (Bézout for two integers).
• Heredity. Assume the result for \(k - 1\) integers. Two cases.
  • If \(a_1 = \dots = a_{k-1} = 0\), then \(a_1 \wedge \dots \wedge a_k = a_k \wedge 0 = |a_k|\), and the Bézout identity \(|a_k| = a_k \cdot \mathrm{sgn}(a_k)\) (with all other \(u_i = 0\)) is immediate.
  • Otherwise, set \(d' = a_1 \wedge \dots \wedge a_{k-1}\) (well-defined since the family is not all zero) and \(d = d' \wedge a_k = a_1 \wedge \dots \wedge a_k\). By Bézout for two integers, \(d = d' \alpha + a_k \beta\) for some \(\alpha, \beta \in \mathbb{Z}\). By induction hypothesis, \(d' = a_1 u'_1 + \dots + a_{k-1} u'_{k-1}\). Substituting, $$ 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. $$ Set \(u_i = \alpha u'_i\) for \(i \leq k-1\) and \(u_k = \beta\).

Set \(d = a_1 \wedge \dots \wedge a_r\). We show that \(|\lambda| d\) is a common divisor of \(\lambda a_1, \dots, \lambda a_r\), and conversely that any common divisor of \(\lambda a_1, \dots, \lambda a_r\) divides \(|\lambda| d\).

• \(|\lambda| d\) divides each \(\lambda a_i\): from \(d \mid a_i\), we get \(|\lambda| d \mid |\lambda| a_i\), and \(|\lambda| a_i = \pm \lambda a_i\), so \(|\lambda| d \mid \lambda a_i\).
• Let \(\delta\) be a common divisor of \(\lambda a_1, \dots, \lambda a_r\). By Bézout for \(r\) integers, \(d = a_1 u_1 + \dots + a_r u_r\) for some \(u_i \in \mathbb{Z}\). Multiply by \(\lambda\): \(\lambda d = (\lambda a_1) u_1 + \dots + (\lambda a_r) u_r\), so \(\delta \mid \lambda d\), hence \(\delta \mid |\lambda| d\).

By the divisor characterization (Proposition « Common divisors and the gcd » above), \(|\lambda| d = (\lambda a_1) \wedge \dots \wedge (\lambda a_r)\).

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

• \((\supset)\) \(m\) is a common multiple of \(a\) and \(b\) by definition, so every multiple of \(m\) is also a common multiple.
• \((\subset)\) Let \(n\) be a common multiple of \(a\) and \(b\). Apply Euclidean division to \(n\) by \(m\): \(n = m q + r\) with \(0 \leq r < m\). Then \(r = n - m q\) is a \(\mathbb{Z}\)-linear combination of two common multiples of \(a\) and \(b\), hence a common multiple of \(a\) and \(b\). Since \(0 \leq r < m\) and \(m\) is the smallest positive common multiple, \(r\) cannot be in \(\mathbb{N}^*\); therefore \(r = 0\). So \(n = m q \in m \mathbb{Z}\).

• \((\Rightarrow)\) If \(a \wedge b = 1\), Bézout's identity (Proposition « Bézout's identity » above) gives \(u, v \in \mathbb{Z}\) with \(a u + b v = a \wedge b = 1\).
• \((\Leftarrow)\) Suppose \(a u + b v = 1\) for some \(u, v \in \mathbb{Z}\). Let \(\delta\) be a common divisor of \(a\) and \(b\). By the linear-combination property, \(\delta \mid (a u + b v) = 1\), so \(\delta \in \{\pm 1\}\). Hence the only common divisors are \(\pm 1\), so \(a \wedge b = 1\).

(i) Coprime divisors. From \(a \mid n\), write \(n = a k\) for some \(k \in \mathbb{Z}\). Then \(b \mid a k\). Since \(a \wedge b = 1\), Gauss's lemma gives \(b \mid k\), i.e.\ \(k = b k'\), so \(n = a b k'\), i.e.\ \(a b \mid n\).
(ii) Coprime to a product. From \(a \wedge n = 1\), take \(a u + n v = 1\). From \(b \wedge n = 1\), take \(b u' + n v' = 1\). Multiply: $$ 1 = (a u + n v)(b u' + n v') = a b (u u') + n (a u v' + b v u' + n v v'). $$ This is a Bézout identity for \(a b\) and \(n\), so by Bézout's theorem \((a b) \wedge n = 1\).

The set \(D = \{d \in \mathbb{N} : d \geq 2 \text{ and } d \mid n\}\) is non-empty (it contains \(n\)) and bounded below by \(2\), so admits a smallest element \(p_0 \in D\).
Claim: \(p_0\) is prime. If \(p_0\) were composite, it would have a divisor \(d\) with \(1 < d < p_0\). Then \(d\) also divides \(n\) (transitivity), so \(d \in D\) with \(d < p_0\) --- contradicting the minimality of \(p_0\).
Hence \(p_0\) is prime, and \(p_0 \mid n\).

Euclid's classical proof, by contradiction. Suppose for contradiction that \(\mathbb{P}\) is finite, say \(\mathbb{P} = \{p_1, p_2, \dots, p_r\}\). Consider the integer $$ N = p_1 \, p_2 \cdots p_r + 1. $$ Since \(N \geq 2\), by the previous proposition \(N\) admits a prime divisor, say \(p_k\) for some \(k \in \{1, \dots, r\}\). Then \(p_k\) divides both \(N\) and \(p_1 \cdots p_r\), so \(p_k\) divides their difference \(N - p_1 \cdots p_r = 1\). But a prime is \(\geq 2\), so cannot divide \(1\) --- contradiction. Hence \(\mathbb{P}\) is infinite.

The divisors of \(p\) in \(\mathbb{N}^*\) are only \(1\) and \(p\). Therefore \(a \wedge p \in \{1, p\}\).

• If \(p \mid a\), then \(p \in \operatorname{div}(a) \cap \operatorname{div}(p)\), so \(a \wedge p = p\).
• If \(p \nmid a\), then \(p \notin \operatorname{div}(a) \cap \operatorname{div}(p)\), so \(a \wedge p = 1\).

The two cases are exclusive and exhaustive, giving the equivalence.

\((\Leftarrow)\) Immediate from the divisibility-of-products property.
\((\Rightarrow)\) Suppose \(p \mid a b\). If \(p \mid a\), done. Else \(p \nmid a\), so by the previous proposition \(a \wedge p = 1\). Apply Gauss's lemma to \(p \mid a b\) with \(p \wedge a = 1\): \(p \mid b\).

By strong induction on \(n \geq 1\).

• Base \(n = 1\). The empty product (with \(s = 0\)) gives \(1\), so the claim holds.
• Heredity. Let \(n \geq 2\), and assume the claim holds for every integer \(1 \leq k < n\). Two cases:
  • If \(n\) is prime, write \(n = n\) (a single-term product), and we are done.
  • If \(n\) is composite, write \(n = a b\) with \(1 < a, b < n\) (by definition of composite). By the inductive hypothesis, \(a = q_1 \cdots q_s\) and \(b = q'_1 \cdots q'_t\) are products of primes. Concatenating, \(n = q_1 \cdots q_s \, q'_1 \cdots q'_t\) is a product of primes.

Set \(\alpha = v_p(a)\) and \(\beta = v_p(b)\). By definition, \(a = p^{\alpha} a'\) with \(p \nmid a'\), and \(b = p^{\beta} b'\) with \(p \nmid b'\). Then $$ a b = p^{\alpha + \beta} (a' b'). $$ By Euclid's lemma (contrapositive), \(p \nmid a'\) and \(p \nmid b'\) imply \(p \nmid a' b'\). Hence the largest power of \(p\) dividing \(a b\) is exactly \(p^{\alpha + \beta}\), i.e.\ \(v_p(a b) = \alpha + \beta = v_p(a) + v_p(b)\).

Existence. By the existence theorem above, \(n = q_1 q_2 \cdots q_s\) is a product of primes. Group equal primes together: \(n = \prod_p p^{\alpha_p}\) with \(\alpha_p = \) number of \(i\) such that \(q_i = p\). The family \((\alpha_p)_{p \in \mathbb{P}}\) has finite support.
Uniqueness. Suppose \(n = \prod_p p^{\alpha_p} = \prod_p p^{\beta_p}\) for two such families. Apply \(v_q\) (for an arbitrary prime \(q\)) to \(n = \prod_p p^{\alpha_p}\) using the additivity of \(v_q\): $$ v_q(n) = \sum_p \alpha_p \, v_q(p) = \alpha_q, $$ since \(v_q(p) = 1\) if \(p = q\) and \(0\) otherwise. The same argument applied to \(n = \prod_p p^{\beta_p}\) gives \(v_q(n) = \beta_q\). Hence \(\alpha_q = \beta_q = v_q(n)\) for every prime \(q\), so the two families coincide.

Divisibility. If \(a \mid b\), then \(b = a k\) for some \(k \in \mathbb{Z}^*\), so \(v_p(b) = v_p(a) + v_p(k) \geq v_p(a)\) by additivity. Conversely, assume \(v_p(a) \leq v_p(b)\) for every prime \(p\). Write $$ |a| = \prod_p p^{\alpha_p}, \qquad |b| = \prod_p p^{\beta_p}, $$ with \(\alpha_p \leq \beta_p\) for every \(p\) by hypothesis. Then $$ |b| = |a| \cdot \prod_p p^{\beta_p - \alpha_p}, $$ where the product on the right is an integer of \(\mathbb{N}^*\). Hence \(|a| \mid |b|\), so \(a \mid b\).
gcd via valuations. Set \(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)\) for every \(p\), so \(d \mid a\) by the divisibility characterization. Similarly \(d \mid b\).
• \(d\) is the largest such: suppose \(\delta \mid a\) and \(\delta \mid b\). Then \(v_p(\delta) \leq v_p(a)\) and \(v_p(\delta) \leq v_p(b)\) for every \(p\), so \(v_p(\delta) \leq \min(v_p(a), v_p(b)) = v_p(d)\). Hence \(\delta \mid d\), so \(|\delta| \leq d\).

Since \(d \in \mathbb{N}^*\) and is the largest common divisor in \(\leq\), \(d = a \wedge b\).
lcm via valuations. Symmetric argument with \(\max\) in place of \(\min\).
gcd-lcm relation. For every prime \(p\), \(\min(v_p(a), v_p(b)) + \max(v_p(a), v_p(b)) = v_p(a) + v_p(b)\). Multiplying \(a \wedge b\) and \(a \vee b\) then taking \(v_p\): $$ v_p((a \wedge b)(a \vee b)) = v_p(a) + v_p(b) = v_p(a b) = v_p(|a b|). $$ Both sides are positive integers with equal valuations at every prime, so by uniqueness of the factorization \((a \wedge b)(a \vee b) = |a b|\).

Already shown in the chapter Binary relations. In short: \(a - a = 0 = n \cdot 0\) (reflexive); if \(n \mid (a - b)\) then \(n \mid (b - a) = -(a - b)\) (symmetric); if \(n \mid (a - b)\) and \(n \mid (b - c)\), then \(n \mid (a - c) = (a - b) + (b - c)\) by linear combinations (transitive).

Apply the Euclidean division of \(a\) by \(n\) (Theorem « Euclidean division » from the section on Euclidean division above): there exists a unique \((q, r) \in \mathbb{Z} \times \mathbb{N}\) with \(a = n q + r\) and \(0 \leq r < n\). Then \(a - r = n q\), i.e.\ \(a \equiv r \pmod n\), with \(r \in \{0, 1, \dots, n-1\}\) unique.
For \(r, r' \in \{0, 1, \dots, n-1\}\) distinct, \(|r - r'| < n\) so \(n \nmid (r - r')\), hence \(r \not\equiv r' \pmod n\). The classes of \(0, 1, \dots, n-1\) are therefore pairwise distinct, and they cover \(\mathbb{Z}\). Hence \(|\mathbb{Z}/n\mathbb{Z}| = n\).

• \((\Leftarrow)\) Assume \(a \wedge n = 1\). By Bézout's theorem, \(a u + n v = 1\) for some \(u, v \in \mathbb{Z}\). Then \(a u = 1 - n v \equiv 1 \pmod n\), so \(u\) is an inverse of \(a\) modulo \(n\).
• \((\Rightarrow)\) Assume \(a u \equiv 1 \pmod n\), i.e.\ \(a u - 1 = n v\) for some \(v\), hence \(a u + n (-v) = 1\). By the converse of Bézout's theorem, \(a \wedge n = 1\).