CommeUnJeu · L1 PCSI

Algebraic computations

⌚ ~115 min ▢ 14 blocks ✓ 46 exercises ➣ Prerequisites : Logic, Binomial Theorem

This chapter is a workshop. We will not introduce a deep theory; we will train the calculus muscles needed for every chapter that follows. Three tools sharpen here. Sums (with the compact notation $\sum$): how to manipulate them, change of index, telescopic collapse, double sums. Products and factorial (with $\prod$): how the multiplicative analogue works, the factorial $n!$, telescopic products. Binomial coefficients: $\binom{n}{p}$, Pascal's triangle, and the famous formula $(a+b)^n$.
The plan opens with three movements, each independent of the others, each short. We will move fast on the parts that students have already met (in lycée: factorials, the binomial for small $n$); we will be deliberate on the genuinely new material (telescopic sums, double sums, the binomial formula). Many proofs in this chapter are by induction on $n$, or by careful index manipulation --- techniques mastered in the Logic chapter; we apply them here. A companion topic on the order side of $\mathbb{R}$ (inequalities, absolute value, floor function, supremum/infimum) is treated elsewhere. A pedagogical convention. When clarifying a $\sum$ identity, we will sometimes write both the formal form and the extended form (terms written out with \texttt{+}) on consecutive lines, so the reader can see what each term looks like.
A fourth section then folds in the basics of arithmetic in $\mathbb{Z}$, the toolkit on the integers $\mathbb{N}, \mathbb{Z}$ that we will use throughout the course: the divisibility relation $b \mid a$ and Euclidean division $a = bq + r$; the greatest common divisor $a \wedge b$ computed by Euclid's algorithm, and the least common multiple $a \vee b$; the prime numbers, the infinitude of $\mathbb{P}$, and the decomposition of an integer into a product of primes.

I Sums

The notation $\sum$ is shorthand: it abbreviates a sum that would be intractable to write out. We start by stating its rules: how the dummy index works, how to break a sum or shift the index, how two consecutive terms cancel. The five subsections of this section drill these mechanics on classical examples; later chapters will use them everywhere.

I.1 Sigma notation

Given a finite list of real numbers $a_m, a_{m+1}, \dots, a_n$, their sum $a_m + a_{m+1} + \dots + a_n$ is denoted $\sum_{k=m}^{n} a_k$. The variable $k$ is a dummy index: it ranges over the integers from $m$ to $n$ (inclusive), and the value of the sum does not depend on the letter chosen ($k$, $i$, $j$, $\ell$ all yield the same sum). Two basic rules govern how $\sum$ interacts with addition and scalar multiplication.

Definition — Sigma notation

For $m, n \in \mathbb{Z}$ and $(a_k)$ a family of real numbers indexed by integers, the sum $\sum_{k=m}^{n} a_k$ is defined as follows.

If $m \le n$: $$ \sum_{k=m}^{n} a_k = a_m + a_{m+1} + \dots + a_n. $$
If $m > n$ (the empty sum case): $$ \sum_{k=m}^{n} a_k = 0. $$

Example

$\sum_{k=1}^{5} k = 1 + 2 + 3 + 4 + 5 = 15$.

Proposition — Linearity of $\sum$

For $m, n \in \mathbb{Z}$ with $m \le n$, $\lambda, \mu \in \mathbb{R}$, and $(a_k)_{m \le k \le n}$, $(b_k)_{m \le k \le n}$ two finite families of real numbers: $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} (\lambda a_k + \mu b_k) &= \lambda \sum_{k=m}^{n} a_k + \mu \sum_{k=m}^{n} b_k \\ (\lambda a_m + \mu b_m) + \dots + (\lambda a_n + \mu b_n) &= \lambda(a_m + \dots + a_n) + \mu(b_m + \dots + b_n). \end{aligned}} $$ In particular, $\sum (a_k + b_k) = \sum a_k + \sum b_k$ and $\sum \lambda a_k = \lambda \sum a_k$.

Proposition — Splitting and Chasles relation

For $m, p, n \in \mathbb{Z}$ with $m \le p < n$, and $(a_k)_{m \le k \le n}$ a finite family of real numbers: $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} a_k &= \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k \\ a_m + \dots+ a_p + a_{p+1} +\dots+ a_n &= (a_m + \dots + a_p) + (a_{p+1} + \dots + a_n). \end{aligned}} $$

Skills to practice

Reading and evaluating $\sum$ sums

I.2 Change of index

The dummy index can be re-named (it stays an integer) or shifted by an additive or symmetric transformation. Two changes of index are everywhere: shift $j = k - p$ (renumbering by $p$) and reflection $j = n - k$ (counting backwards). Each preserves the sum --- it just reshapes the bounds.

Proposition — Change of index

Let $m \le n$ be integers (so the index set $\{m, m+1, \dots, n\}$ is non-empty).

Shift: for $p \in \mathbb{Z}$, with $j = k - p$ $$ \textcolor{colorprop}{ \sum_{k=m}^{n} a_k = \sum_{j=m-p}^{n-p} a_{j+p} } $$
Reflection: with $j = n - k$ (so $k = n - j$), which shifts the lower bound to $0$, $$ \textcolor{colorprop}{\begin{aligned}\sum_{k=m}^{n} a_k &= \sum_{j=0}^{n-m} a_{n-j}\\ a_m+a_{m+1}+\dots+a_{n-1}+a_n&=a_n+a_{n-1}+\dots+a_{m+1}+a_m \end{aligned} } $$ or, equivalently, in the bound-preserving form, with $j = n + m - k$ (so $k = n + m - j$), $$ \textcolor{colorprop}{ \sum_{k=m}^{n} a_k = \sum_{j=m}^{n} a_{n+m-j} } $$ which keeps the original bounds $m$ and $n$ unchanged.

Example

Rewrite $\sum_{k=3}^{n+3} k^2$ with summation index starting at $0$.

Answer

Set $j = k - 3$. Then $k = j + 3$, and as $k$ ranges from $3$ to $n+3$, $j$ ranges from $0$ to $n$. Hence $$ \sum_{k=3}^{n+3} k^2 = \sum_{j=0}^{n} (j+3)^2 = \sum_{j=0}^{n} (j^2 + 6j + 9). $$

Example

Show that $\sum_{k=0}^{n} a_k = \sum_{k=0}^{n} a_{n-k}$.

Answer

Apply the reflection $j = n - k$: $k = n - j$, and as $k$ ranges from $0$ to $n$, $j$ ranges from $n$ to $0$, i.e. $j$ takes the same values as $k$. Hence $$ \sum_{k=0}^{n} a_k = \sum_{j=0}^{n} a_{n-j} = \sum_{k=0}^{n} a_{n-k} $$ (the last equality just renames the dummy back to $k$).

Skills to practice

Translating and reflecting indices

I.3 Classical sums

Four sums must be at the fingertips: the sum of the first $n$ integers, the sum of their squares, the sum of their cubes, and the geometric sum. Plus one factorisation that is the algebraic dual of the geometric sum: $a^n - b^n$. These five formulas underpin every later computation.

Theorem — Classical sums

For $n \in \mathbb{N}$:

Sum of integers. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k &= \frac{n(n+1)}{2} \\ 1 + 2 + 3 + \dots + n &= \frac{n(n+1)}{2}. \end{aligned}} $$
Sum of squares. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k^2 &= \frac{n(n+1)(2n+1)}{6} \\ 1^2 + 2^2 + 3^2 + \dots + n^2 &= \frac{n(n+1)(2n+1)}{6}. \end{aligned}} $$
Sum of cubes. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k^3 &= \left(\frac{n(n+1)}{2}\right)^2 \\ 1^3 + 2^3 + 3^3 + \dots + n^3 &= \left(\frac{n(n+1)}{2}\right)^2. \end{aligned}} $$

Geometric sum. For $x \in \mathbb{R}$ with $x \ne 1$ and $n \in \mathbb{N}$: $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} x^k &= \frac{1 - x^{n+1}}{1 - x} = \frac{x^{n+1} - 1}{x - 1} \\ 1 + x + x^2 + \dots + x^n &= \frac{1 - x^{n+1}}{1 - x}. \end{aligned}} $$ For $x = 1$: $\sum_{k=0}^{n} 1 = n+1$.

Proof

The proofs use two recurring ideas: change of index (for the sum of integers) and telescoping of a difference $u_{k+1} - u_k$ followed by polynomial expansion (for the sums of squares and cubes, and for the geometric sum). We use telescoping here in anticipation: it is stated and proved in full as the telescoping Proposition of the next subsection (Telescopic sums below); only its conclusion $\sum_{k=m}^{n}(u_{k+1}-u_k) = u_{n+1} - u_m$ is invoked here.

Sum of integers --- change of index. Let $S = \sum_{i=0}^{n} i$. With the change of index $i \mapsto n - i$, the same sum can also be written $S = \sum_{i=0}^{n} (n - i)$. Add the two expressions of $S$: $$ \begin{aligned} 2S &= \sum_{i=0}^{n} i + \sum_{i=0}^{n} (n - i) \\ &= \sum_{i=0}^{n} \big(i + (n - i)\big) && \text{(linearity)} \\ &= \sum_{i=0}^{n} n && \text{(simplification: } i + (n-i) = n\text{)} \\ &= n \sum_{i=0}^{n} 1 && \text{(linearity)} \\ &= n (n+1) && \text{(} \sum_{i=0}^{n} 1 = n+1 \text{)}. \end{aligned} $$ Hence $\displaystyle\sum_{k=0}^{n} k = \frac{n(n+1)}{2}$.
Sum of squares --- telescoping with cubes. Apply telescoping to $u_k = k^3$ and chain the operations: $$ \begin{aligned} \sum_{k=0}^{n} \big((k+1)^3 - k^3\big) &= (n+1)^3 && \text{(telescoping, } u_k = k^3 \text{)} \\ \sum_{k=0}^{n} (3k^2 + 3k + 1) &= (n+1)^3 && \text{(expand } (k+1)^3 - k^3\text{)} \\ 3 \sum_{k=0}^{n} k^2 + 3 \sum_{k=0}^{n} k + \sum_{k=0}^{n} 1 &= (n+1)^3 && \text{(linearity)} \\ 3 \sum_{k=0}^{n} k^2 + 3 \cdot \frac{n(n+1)}{2} + (n+1) &= (n+1)^3 && \text{(known sums)} \\ 3 \sum_{k=0}^{n} k^2 &= (n+1)^3 - \frac{3n(n+1)}{2} - (n+1) && \text{(isolate)} \\ 6 \sum_{k=0}^{n} k^2 &= 2(n+1)^3 - 3n(n+1) - 2(n+1) && \text{(}\times 2\text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)\big[2(n+1)^2 - 3n - 2\big] && \text{(factor } (n+1) \text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)\big[2n^2 + 4n + 2 - 3n - 2\big] && \text{(expand } 2(n+1)^2 = 2n^2 + 4n + 2 \text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)(2n^2 + n) && \text{(collect terms inside the bracket)} \\ 6 \sum_{k=0}^{n} k^2 &= n(n+1)(2n+1) && \text{(factor } n \text{).} \end{aligned} $$ Hence $\displaystyle\sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$.
Sum of cubes --- same trick with $(k+1)^4 - k^4$. Apply telescoping to $u_k = k^4$, expand $(k+1)^4 - k^4 = 4k^3 + 6k^2 + 4k + 1$, and reuse $\sum k$ and $\sum k^2$: $$ \begin{aligned} \sum_{k=0}^{n} \big((k+1)^4 - k^4\big) &= (n+1)^4 && \text{\doublecolumnscriptsize (telescoping, } u_k = k^4 \text{)} \\ \sum_{k=0}^{n} (4k^3 + 6k^2 + 4k + 1) &= (n+1)^4 && \text{\doublecolumnscriptsize (expand)} \\ 4 \sum k^3 + 6 \sum k^2 + 4 \sum k + \sum 1 &= (n+1)^4 && \text{\doublecolumnscriptsize (linearity)} \\ 4 \sum k^3 + n(n+1)(2n+1) \\ \quad + 2n(n+1) + (n+1) &= (n+1)^4 && \text{\doublecolumnscriptsize (known sums)} \\ 4 \sum k^3 &= (n+1)^4 - n(n+1)(2n+1) \\ &\quad - 2n(n+1) - (n+1) && \text{\doublecolumnscriptsize (isolate)} \\ 4 \sum k^3 &= (n+1)\big[(n+1)^3 - n(2n+1) - 2n - 1\big] && \text{\doublecolumnscriptsize (factor } (n+1) \text{)} \\ 4 \sum k^3 &= (n+1)\big[n^3 + 3n^2 + 3n + 1 \\ &\quad - 2n^2 - n - 2n - 1\big] && \text{\doublecolumnscriptsize (expand } (n+1)^3, n(2n+1)\text{)} \\ 4 \sum k^3 &= (n+1)(n^3 + n^2) && \text{\doublecolumnscriptsize (collect bracket terms)} \\ 4 \sum k^3 &= n^2(n+1)^2 && \text{\doublecolumnscriptsize (factor } n^2 \text{).} \end{aligned} $$ Hence $\displaystyle\sum_{k=0}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$.
Geometric sum --- telescoping after multiplying by $(1-x)$. For $x \ne 1$: $$ \begin{aligned} (1 - x) \sum_{k=0}^{n} x^k &= \sum_{k=0}^{n} x^k - x \sum_{k=0}^{n} x^k && \text{(distribute)} \\ &= \sum_{k=0}^{n} x^k - \sum_{k=0}^{n} x^{k+1} && \text{(factor inside the sum)} \\ &= \sum_{k=0}^{n} (x^k - x^{k+1}) && \text{(linearity)} \\ &= x^0 - x^{n+1} && \text{(telescoping, } u_k = x^k \text{)} \\ &= 1 - x^{n+1}. \end{aligned} $$ Divide by $1 - x$: $\displaystyle\sum_{k=0}^{n} x^k = \frac{1 - x^{n+1}}{1 - x}$.

Example

Compute $\displaystyle \sum_{k=1}^{100} k$.

Answer

$\sum_{k=1}^{100} k = 100 \cdot 101 / 2 = 5050$.

Example

Compute $\displaystyle \sum_{k=0}^{n} 2^k$.

Answer

Geometric sum with $x = 2$: $\sum_{k=0}^{n} 2^k = (2^{n+1} - 1)/(2 - 1) = 2^{n+1} - 1$.

Proposition — Factorisation of $a^n - b^n$

For $a, b \in \mathbb{R}$ and $n \in \mathbb{N}^*$: $$ \textcolor{colorprop}{a^n - b^n = (a - b)\sum_{k=0}^{n-1} a^{n-1-k} b^{k} = (a-b)(a^{n-1} + a^{n-2}b + \dots + a b^{n-2} + b^{n-1})}. $$

Proof

Set $u_k = a^{n-k} b^k$. Distributing $(a - b)$ on the sum produces a telescoping sum: $$ (a - b) \sum_{k=0}^{n-1} a^{n-1-k} b^k = \sum_{k=0}^{n-1} \big( a^{n-k} b^k - a^{n-1-k} b^{k+1} \big) = \sum_{k=0}^{n-1} (u_k - u_{k+1}) = u_0 - u_n = a^n - b^n. $$

Skills to practice

Recognising and applying closed forms
Combining classical sums by linearity

I.4 Telescopic sums

A telescopic sum is a sum of consecutive differences $u_{k+1} - u_k$, in which all middle terms cancel pairwise --- only the endpoints survive. The trick is to recognize when a summand can be written as such a difference, because then the entire sum collapses to two terms.

Proposition — Telescopic sum

For any sequence $(u_k)$ and integers $m \le n$: $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} (u_{k+1} - u_k) &= u_{n+1} - u_m \\ (u_{m+1}-u_m) + (u_{m+2}-u_{m+1}) + \dots + (u_{n+1}-u_n) &= u_{n+1} - u_m \end{aligned}} $$

Proof

Three perspectives on the same result: two formal proofs and one visual.

Proof 1 --- induction on $n$ (with $m$ fixed). Initialization. For $n = m$, the sum has one term: $\sum_{k=m}^{m} (u_{k+1} - u_k) = u_{m+1} - u_m$, which equals $u_{n+1} - u_m$ at $n=m$. $\checkmark$ Heredity. Assume the formula at rank $n$. At rank $n+1$: $$ \begin{aligned} \sum_{k=m}^{n+1} (u_{k+1} - u_k) &= \sum_{k=m}^{n} (u_{k+1} - u_k) + (u_{n+2} - u_{n+1}) && \text{(Chasles, split off the last term)} \\ &= (u_{n+1} - u_m) + (u_{n+2} - u_{n+1}) && \text{(induction hypothesis)} \\ &= u_{n+2} - u_m && \text{(simplify).} \end{aligned} $$ Heredity holds; the result follows for all $n \ge m$.
Proof 2 --- change of index. $$ \begin{aligned} \sum_{k=m}^{n} (u_{k+1} - u_k) &= \sum_{k=m}^{n} u_{k+1} - \sum_{k=m}^{n} u_k && \text{(linearity)} \\ &= \sum_{j=m+1}^{n+1} u_j - \sum_{k=m}^{n} u_k && \text{(change of index } j = k+1 \text{)} \\ &= u_{n+1} + \sum_{j=m+1}^{n} u_j - \sum_{k=m}^{n} u_k && \text{(Chasles, peel off } j=n+1\text{)} \\ &= u_{n+1} + \sum_{j=m+1}^{n} u_j - u_m - \sum_{k=m+1}^{n} u_k && \text{(Chasles, peel off } k=m\text{)} \\ &= u_{n+1} - u_m && \text{(the two inner sums are equal --- dummy index).} \end{aligned} $$
Visual idea --- expand and watch terms cancel. Writing the sum out term by term: $$ \sum_{k=m}^{n} (u_{k+1} - u_k) = (u_{m+1} - u_m) + (u_{m+2} - u_{m+1}) + \dots + (u_{n+1} - u_n). $$ Every $u_j$ with $m+1 \le j \le n$ appears exactly twice --- once with a $+$ sign, once with a $-$ sign --- and the two occurrences cancel. Only $-u_m$ at the start and $+u_{n+1}$ at the end survive: the sum collapses to $u_{n+1} - u_m$.

Example

Compute $\displaystyle \sum_{k=1}^{n} \frac{1}{k(k+1)}$.

Answer

Decompose: $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$. Setting $u_k = -\frac{1}{k}$, the summand is $u_{k+1} - u_k$. By the telescopic formula $$ \sum_{k=1}^{n} \frac{1}{k(k+1)} = u_{n+1} - u_1 = -\frac{1}{n+1} + 1 = \frac{n}{n+1}. $$

Example

Compute $\displaystyle \sum_{k=1}^{n} \ln\!\left(1 + \frac{1}{k}\right)$.

Answer

$\ln(1 + 1/k) = \ln((k+1)/k) = \ln(k+1) - \ln(k)$. Setting $u_k = \ln(k)$, the summand is $u_{k+1} - u_k$. Hence $$ \sum_{k=1}^{n} \ln\!\left(1 + \frac{1}{k}\right) = \ln(n+1) - \ln(1) = \ln(n+1). $$

Method — Recognize a telescopic sum

Look for the pattern $u_{k+1} - u_k$ (a single-step difference). Two frequent triggers:

Rational fraction $\dfrac{1}{k(k+1)}$: partial-fraction decomposition gives $\dfrac{1}{k(k+1)} = \dfrac{1}{k} - \dfrac{1}{k+1}$, a single-step difference of $u_k = -\dfrac{1}{k}$. (For wider gaps $\dfrac{1}{k(k+a)}$ with $a \ge 2$, the decomposition produces an $a$-step difference --- handled in the going-further section of the exercises.)
Logarithm of a ratio: $\ln\!\big(f(k+1)/f(k)\big) = \ln f(k+1) - \ln f(k)$.

Once the summand is recognised as $u_{k+1} - u_k$, the formula collapses the sum to two terms: $u_{n+1} - u_m$.

Skills to practice

Decomposing then collapsing

I.5 Double sums

A double sum $\sum_{i,j}$ runs over a rectangle (or a triangle) of pairs $(i, j)$. Three simplifications: when the rectangle is full and the summand factors, the sum is a product of two simple sums; the order of summation can be permuted (Fubini for sums); for triangles, one swaps the roles of the inner and outer variables.

Proposition — Double-sum identities

Permutation (Fubini): $$ \textcolor{colorprop}{\sum_{i=m}^{n} \sum_{j=p}^{q} a_{i,j} = \sum_{j=p}^{q} \sum_{i=m}^{n} a_{i,j}}. $$
Factorisation (separable summand): if $a_{i,j} = b_i c_j$ $$ \textcolor{colorprop}{\sum_{i=m}^{n} \sum_{j=p}^{q} b_i c_j = \left(\sum_{i=m}^{n} b_i\right)\!\left(\sum_{j=p}^{q} c_j\right)}. $$
Triangle: swap inside and outside: $$ \textcolor{colorprop}{\sum_{1 \le i \le j \le n} a_{i,j} = \sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j} = \sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}}. $$

Proof

The three identities all rest on commutativity and associativity of addition on $\mathbb{R}$ --- which let us re-order any finite sum freely --- combined with linearity of $\sum$.

Permutation (Fubini) --- expand and re-collect. The rectangular double sum enumerates every cell $(i,j)$ of the $(n - m + 1) \times (q - p + 1)$ index rectangle exactly once. Both nested orderings list the same cells; the resulting finite sums of the same numbers are equal: $$ \sum_{i=m}^{n} \sum_{j=p}^{q} a_{i,j} = \sum_{\substack{m \le i \le n \\ p \le j \le q}} a_{i,j} = \sum_{j=p}^{q} \sum_{i=m}^{n} a_{i,j}. $$
Factorisation (separable summand). Fix $i$ in the inner sum and apply linearity ($b_i$ is constant with respect to $j$): $$ \begin{aligned} \sum_{i=m}^{n} \sum_{j=p}^{q} b_i c_j &= \sum_{i=m}^{n} \left[ b_i \sum_{j=p}^{q} c_j \right] && \text{(linearity, } b_i \text{ does not depend on } j\text{)} \\ &= \left(\sum_{j=p}^{q} c_j\right) \sum_{i=m}^{n} b_i && \text{(linearity, the parenthesised factor does not depend on } i\text{)} \\ &= \left(\sum_{i=m}^{n} b_i\right) \left(\sum_{j=p}^{q} c_j\right). \end{aligned} $$
Triangle: swap inside and outside. The set $\{(i,j) : 1 \le i \le j \le n\}$ partitions in two equivalent ways:
- ordering on $j$ outside: for each $j \in \{1, \dots, n\}$, the inner index $i$ runs over $\{1, \dots, j\}$, giving $\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$;
- ordering on $i$ outside: for each $i \in \{1, \dots, n\}$, the inner index $j$ runs over $\{i, \dots, n\}$, giving $\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}$.
Both partitions enumerate each pair $(i,j)$ with $1 \le i \le j \le n$ exactly once, so the two double sums equal $\sum_{1 \le i \le j \le n} a_{i,j}$.

Example

Compute $\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} ij$.

Answer

The summand $ij$ is separable. Factorisation: $$ \sum_{i=1}^{n} \sum_{j=1}^{n} ij = \left(\sum_{i=1}^{n} i\right)\!\left(\sum_{j=1}^{n} j\right) = \left(\frac{n(n+1)}{2}\right)^2. $$

Example

Compute $\displaystyle \sum_{1 \le i \le j \le n} 1$.

Answer

Triangle of pairs $(i, j)$ with $1 \le i \le j \le n$. Sum of $1$ over this triangle = number of pairs = $n(n+1)/2$. Verify by ordering on $j$: $\sum_{j=1}^{n} \sum_{i=1}^{j} 1 = \sum_{j=1}^{n} j = n(n+1)/2$.

Method — Compute a double sum

Three reflexes, in order:

Separable summand: if $a_{i,j} = b_i c_j$, factor $\sum_{i,j} b_i c_j = \bigl(\sum_i b_i\bigr)\bigl(\sum_j c_j\bigr)$ --- two single sums.
Triangular range: choose the inner sum so the bounds of the inner variable are visible. With $1 \le i \le j \le n$, ordering on $j$ outside gives $\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$; ordering on $i$ outside gives $\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}$. Pick whichever makes the inner sum a known classical sum.
Stuck rectangle: if neither of the above helps, swap the order of summation (Fubini) and try again --- often the swapped form reveals a separable structure or a recognisable inner sum.

Skills to practice

Swapping and splitting double indices

II Products

The notation $\prod$ is the multiplicative cousin of $\sum$. The same machinery applies: dummy index, change of index, telescopic collapse. The only structural change is the convention for the empty product (it is $1$, not $0$). The most useful product is the factorial.

II.1 Pi notation and factorial

The factorial $n!$ counts the number of orderings of $n$ objects. Algebraically, it is the product of the first $n$ positive integers. It will appear everywhere: in binomial coefficients, in Taylor expansions, in counting problems.

Definition — Pi notation$\virgule$ factorial

For $m, n \in \mathbb{Z}$ and a family $(a_k)$ of real numbers indexed by integers, the product $\prod_{k=m}^{n} a_k$ is defined as follows.
- If $m \le n$: $$ \prod_{k=m}^{n} a_k = a_m \cdot a_{m+1} \cdot \dots \cdot a_n. $$
- If $m > n$ (the empty product case): $\prod_{k=m}^{n} a_k = 1$.
For $n \in \mathbb{N}$, the factorial of $n$ is $$ \textcolor{colordef}{n!} = \prod_{k=1}^{n} k = 1 \cdot 2 \cdot 3 \cdots n. $$ By convention, $\textcolor{colordef}{0!} = 1$ (empty product).

Example

$0! = 1$, $1! = 1$, $2! = 2$, $3! = 6$, $4! = 24$, $5! = 120$.
$10! = 3628800$ (already large).

Proposition — Recurrence and ratios of factorials

For $n \in \mathbb{N}$: $$ \textcolor{colorprop}{(n+1)! = (n+1) \cdot n!}. $$ For $n \ge p \ge 0$: $$ \textcolor{colorprop}{\frac{n!}{p!} = (p+1)(p+2)\cdots n = \prod_{k=p+1}^{n} k}. $$

Skills to practice

Manipulating products and factorials

II.2 Telescopic products

The multiplicative analogue of the telescopic sum: a product of ratios $u_{k+1}/u_k$ collapses to two endpoint terms. Useful when a fraction can be rewritten as such a ratio.

Proposition — Telescopic product

For a sequence $(u_k)$ of nonzero real numbers and $m \le n$: $$ \textcolor{colorprop}{\prod_{k=m}^{n} \frac{u_{k+1}}{u_k} = \frac{u_{n+1}}{u_m}}. $$

Example

Compute $\displaystyle \prod_{k=1}^{n} \frac{k+1}{k}$.

Answer

Setting $u_k = k$, the term is $u_{k+1}/u_k$. By the telescopic product $$ \prod_{k=1}^{n} \frac{k+1}{k} = \frac{u_{n+1}}{u_1} = \frac{n+1}{1} = n+1. $$

Method — Recognize a telescopic product

Look for the pattern $u_{k+1}/u_k$. Common triggers:

Explicit ratio of consecutive values: $\dfrac{f(k+1)}{f(k)}$ for some sequence $(f(k))$.
Ratio of consecutive factorials: $\dfrac{(k+1)!}{k!} = k+1$, so $\prod_{k=1}^{n}\dfrac{(k+1)!}{k!} = (n+1)!$.
Logarithmic fall-back: when the factors are positive, take $\ln$ to convert the product into a telescopic sum of $\ln u_{k+1} - \ln u_k$, then re-exponentiate.

Once recognised, the product collapses to $u_{n+1}/u_m$ --- only the boundary values survive.

Skills to practice

Collapsing multiplicative chains

III Binomial coefficients

The binomial coefficient $\binom{n}{k}$ counts the number of ways to choose $k$ objects out of $n$ (without order). The same number appears as the coefficient of $a^{n-k}b^k$ in the expansion of $(a+b)^n$. The two faces --- combinatorial and algebraic --- are equivalent, and we will use whichever is most convenient. The chapter culminates in the binomial formula, the most famous algebraic identity in elementary mathematics.

III.1 Definition and properties

We define $\binom{n}{k}$ by its factorial formula and observe its three fundamental properties: it will appear (in the binomial formula proved below) as the coefficient of $a^{n-k} b^k$ in the symmetric polynomial $(a+b)^n$, it is symmetric in $k$ and $n-k$, and it satisfies a recurrence relation that gives Pascal's triangle.

Definition — Binomial coefficient

For $n \in \mathbb{N}$ and $k \in \mathbb{Z}$, the binomial coefficient $\binom{n}{k}$ is defined by: $$ \textcolor{colordef}{\binom{n}{k}} = \begin{cases} \dfrac{n!}{k!\,(n-k)!} & \text{if } 0 \le k \le n, \\ 0 & \text{otherwise.} \end{cases} $$ It reads « $n$ choose $k$ ». The factorial expression above is the definition; the fact that this number also equals the count of subsets of size $k$ in a set of $n$ elements is the combinatorial interpretation, established separately by a counting argument (it is not part of the definition).

Proposition — Standard values of binomial coefficients

For $n \in \mathbb{N}$:

$\textcolor{colorprop}{\binom{n}{0} = \binom{n}{n} = 1}$ (one way to choose nothing or everything);
$\textcolor{colorprop}{\binom{n}{1} = \binom{n}{n-1} = n}$ ($n$ singletons or $n$ subsets missing one element);
for $n \ge 2$, $\textcolor{colorprop}{\binom{n}{2} = \binom{n}{n-2} = \dfrac{n(n-1)}{2}}$.

Example

$\binom{5}{2} = \dfrac{5!}{2!\,3!} = \dfrac{5 \cdot 4}{2} = 10$ --- there are ten ways to choose a pair from a $5$-element set.

Proposition — Symmetry$\virgule$ Pascal$\virgule$ absorption

For $n \in \mathbb{N}$ and $k \in \mathbb{Z}$ with $0 \le k \le n$:

Symmetry: $\textcolor{colorprop}{\binom{n}{k} = \binom{n}{n-k}}$.
Pascal's identity: for $1 \le k \le n-1$, $\textcolor{colorprop}{\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}$.
Absorption: for $1 \le k \le n$, $\textcolor{colorprop}{k\binom{n}{k} = n\binom{n-1}{k-1}}$.

Proof

The core of all three proofs is the same: put the fractions on a common denominator using the factorial identities $k \cdot (k-1)! = k!$ and $(n-k) \cdot (n-k-1)! = (n-k)!$.

Symmetry. Apply the factorial formula and simplify the second factor: $$ \begin{aligned} \binom{n}{n-k} &= \frac{n!}{(n-k)! \, \big(n - (n-k)\big)!} && \text{(factorial formula at index } n-k \text{)} \\ &= \frac{n!}{(n-k)! \, k!} && \text{(simplification: } n - (n-k) = k\text{)} \\ &= \frac{n!}{k! \, (n-k)!} && \text{(swap factors in the denominator)} \\ &= \binom{n}{k} && \text{(factorial formula at index } k\text{).} \end{aligned} $$
Pascal. The common denominator we aim for is $k!\,(n-k)!$. We multiply each fraction by $1$ in a way that lets the factorials extend to it: $$ \begin{aligned} \binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (factorial formula)} \\ &= \frac{k \cdot (n-1)!}{k \cdot (k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (multiply 1st fraction by } k/k \text{)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (}k \cdot (k-1)! = k! \text{ in 1st denom.)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} \\ &\quad + \frac{(n-k) \cdot (n-1)!}{k!\,(n-k) \cdot (n-k-1)!} && \text{\doublecolumnscriptsize (multiply 2nd fraction by } (n-k)/(n-k) \text{)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} + \frac{(n-k) \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}(n-k) \cdot (n-k-1)! = (n-k)! \text{ in 2nd denom.)} \\ &= \frac{k \cdot (n-1)! + (n-k) \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (common denominator reached)} \\ &= \frac{(n-1)! \, \big[k + (n-k)\big]}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (factor } (n-1)! \text{)} \\ &= \frac{n \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}k + (n-k) = n\text{)} \\ &= \frac{n!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}n \cdot (n-1)! = n!\text{)} \\ &= \binom{n}{k}. \end{aligned} $$
Absorption. Same idea, simpler: pull a factor in or out of a factorial. $$ \begin{aligned} k \binom{n}{k} &= \frac{k \cdot n!}{k! \, (n-k)!} && \text{(factorial formula)} \\ &= \frac{k \cdot n!}{k \cdot (k-1)! \, (n-k)!} && \text{(}k! = k \cdot (k-1)!\text{)} \\ &= \frac{n!}{(k-1)! \, (n-k)!} && \text{(cancel the factor } k\text{)} \\ &= \frac{n \cdot (n-1)!}{(k-1)! \, (n-k)!} && \text{(}n! = n \cdot (n-1)!\text{)} \\ &= n \binom{n-1}{k-1}. \end{aligned} $$

Skills to practice

Proving identities by calculation

III.2 Pascal's triangle

Pascal's identity gives a recursive procedure to compute $\binom{n}{k}$: each entry is the sum of the two entries above. The resulting array is Pascal's triangle, a fixture of elementary combinatorics.

Example

The first seven rows of Pascal's triangle. Row $n$ contains $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$. Each entry equals the sum of the two diagonal entries above (Pascal's identity).

Method — Build Pascal's triangle row by row

To compute $\binom{n}{k}$ for small $n$, use Pascal's recurrence:

start with row $0$: $\binom{0}{0} = 1$;
each new row begins and ends with $1$;
interior entries are the sum of the two entries diagonally above (above-left and above-right).

For larger $n$ or specific entries, prefer the factorial formula.

Skills to practice

Building and exploiting the triangle

III.3 Binomial formula

The binomial formula expresses $(a+b)^n$ as an explicit linear combination of monomials $a^{n-k}b^k$ with coefficients exactly the binomial coefficients. It is the key identity that links combinatorics, algebra, and analysis: it underlies Taylor expansions and many counting arguments.

Theorem — Binomial formula (Newton)

For $a, b \in \mathbb{R}$ (or $\mathbb{C}$) and $n \in \mathbb{N}$: $$ \textcolor{colorprop}{(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k}. $$

Proof

Induction on $n$.

Initialization. For $n = 0$: $(a+b)^0 = 1$ and $\sum_{k=0}^{0} \binom{0}{k} a^{0-k} b^k = \binom{0}{0} = 1$. $\checkmark$
Heredity. Assume the formula at rank $n$. Compute $(a+b)^{n+1}$ step by step: $$ \begin{aligned} (a+b)^{n+1} &= (a+b)\,(a+b)^n && \text{\doublecolumnscriptsize (split off one factor)} \\ &= (a+b) \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k && \text{\doublecolumnscriptsize (by induction hypothesis)} \\ &= a \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k \\ &\quad + b \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k && \text{\doublecolumnscriptsize (distribute)} \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k+1} && \text{\doublecolumnscriptsize (factor inside the sums)} \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n+1} \binom{n}{k-1} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (change of index } k \to k+1\text{ in the 2nd sum)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n+1} \binom{n}{k-1} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (peel } k=0 \text{ off the 1st sum)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n} \binom{n}{k-1} a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (peel } k=n+1 \text{ off the 2nd sum)} \\ &= a^{n+1} + \sum_{k=1}^{n} \Big[\binom{n}{k} + \binom{n}{k-1}\Big] a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (combine the two sums on } k=1\text{..}n\text{)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k} a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (Pascal's identity)} \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (reabsorb }a^{n+1}\text{ and }b^{n+1}\text{).} \end{aligned} $$ Heredity holds. The result follows for all $n \in \mathbb{N}$.

Example

Expand $(a+b)^4$.

Answer

Read the row $n=4$ of Pascal's triangle: $1, 4, 6, 4, 1$. Hence $$ (a+b)^4 = a^4 + 4 a^3 b + 6 a^2 b^2 + 4 a b^3 + b^4. $$

Example

Compute $\sum_{k=0}^{n} \binom{n}{k}$ and $\sum_{k=0}^{n} (-1)^k \binom{n}{k}$.

Answer

Apply the binomial formula with $a = b = 1$: $$ 2^n = (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k = \sum_{k=0}^{n} \binom{n}{k}. $$ With $a = 1, b = -1$, for $n \ge 1$: $$ 0 = (1-1)^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k. $$

Method — Apply the binomial formula

For an expansion $(a+b)^n$:

read the binomial coefficients from Pascal's triangle (small $n$) or compute them by the factorial formula;
write each term as $\binom{n}{k} a^{n-k} b^k$ for $k = 0, \dots, n$.

For a sum identity involving $\binom{n}{k}$, try evaluating $(a+b)^n$ at clever values: $a = b = 1$ gives $\sum \binom{n}{k} = 2^n$; $a = 1, b = -1$ gives the alternating sum.

Skills to practice

Applying and inverting Newton's formula

IV Arithmetic in $\mathbb{Z}$

We close the workshop with the basics of arithmetic on the integers. The sets $\mathbb{N}$ and $\mathbb{Z}$ are assumed known; their construction is beyond our scope. We develop four tools, each elementary and each used constantly later. First the divisibility relation $b \mid a$ and Euclidean division $a = b q + r$, the algorithmic device that turns « does $b$ divide $a$? » into « is the remainder zero? ». Then the greatest common divisor $a \wedge b$, computed by the iterated Euclidean divisions of Euclid's algorithm, and the least common multiple $a \vee b$, tied to the gcd by $(a \wedge b)(a \vee b) = |ab|$. Finally the prime numbers: their definition, the infinitude of $\mathbb{P}$ (Euclid), the sieve of Eratosthenes, and the decomposition of every $n \geq 2$ into a product of primes --- the building blocks of $\mathbb{N}^*$ for multiplication.
Standing convention. Throughout this section, a divisor is always a non-zero integer: whenever we write « $d \mid a$ » we tacitly assume $d \in \mathbb{Z}^*$. We use $\mathbb{N} = \{0, 1, 2, \dots\}$ and $\mathbb{N}^* = \mathbb{N} \setminus \{0\}$. The notations $a \wedge b$ (gcd) and $a \vee b$ (lcm) are standard.

IV.1 Divisibility and Euclidean division

Two definitions, one theorem. The definition of divisibility is the entry point; Euclidean division is the algorithmic tool that turns « $b \mid a$? » into « is the remainder zero? ». The lycée baseline already covers both informally; we state them formally and extend Euclidean division to negative dividends.

Definition — Divisibility

Let $a \in \mathbb{Z}$ and $b \in \mathbb{Z}^*$. We say that $b$ divides $a$, and we write $b \mid a$, if there exists $k \in \mathbb{Z}$ such that $a = b k$. We then also say that $a$ is a multiple of $b$, or that $b$ is a divisor of $a$.
Notations:

$a \mathbb{Z} = \{a k : k \in \mathbb{Z}\}$ is the set of multiples of $a$;
$\operatorname{div}(a) = \{d \in \mathbb{Z}^* : d \mid a\}$ is the set of divisors of $a$.

Example

$\operatorname{div}(12) = \{\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12\}$. $\operatorname{div}(0) = \mathbb{Z}^*$ since every non-zero integer $d$ satisfies $0 = d \cdot 0$. The set of multiples of $5$ is $5 \mathbb{Z} = \{\dots, -10, -5, 0, 5, 10, \dots\}$.

Proposition — Properties of divisibility

Let $a, b, c, d \in \mathbb{Z}$ and $u, v \in \mathbb{Z}$, with the standing convention that a divisor is non-zero (the divisor appearing in each statement below lies in $\mathbb{Z}^*$).

Reflexivity and transitivity. For every $a \in \mathbb{Z}^*$, $a \mid a$. If $a \mid b$ and $b \mid c$ (with $a, b \in \mathbb{Z}^*$), then $a \mid c$.
Associated integers. For $a, b \in \mathbb{Z}^*$, $a \mid b \text{ and } b \mid a \iff |a| = |b|$. In particular, restricted to $\mathbb{N}^*$ this gives the antisymmetry of $\mid$: $a \mid b$ and $b \mid a \iff a = b$.
Linear combinations. If $d \mid a$ and $d \mid b$, then $d \mid (a u + b v)$ for every $u, v \in \mathbb{Z}$.
Product. If $a \mid b$ and $c \mid d$ (with $a, c \in \mathbb{Z}^*$), then $a c \mid b d$. In particular $a^k \mid b^k$ for every $k \in \mathbb{N}^*$ when $a \mid b$.

Proof

Reflexivity / transitivity. $a = a \cdot 1$ gives $a \mid a$. If $b = a k$ and $c = b k'$, then $c = a (k k')$ with $k k' \in \mathbb{Z}$, so $a \mid c$.
Associated integers. If $a \mid b$ and $b \mid a$, write $b = a k$ and $a = b k'$. Then $a = a (k k')$, so $k k' = 1$ (since $a \neq 0$). With $k, k' \in \mathbb{Z}$, this forces $k = k' = \pm 1$, hence $|a| = |b|$. Conversely if $|a| = |b|$ then $a = \pm b$, so each divides the other.
Linear combinations. From $a = d k$ and $b = d k'$, $a u + b v = d (k u + k' v) \in d \mathbb{Z}$.
Product. From $b = a k$ and $d = c k'$, $b d = (a c)(k k')$, so $a c \mid b d$.

Method — Decide whether $b \mid a$

Two equivalent tests for $b \in \mathbb{Z}^*$, $a \in \mathbb{Z}$:

Direct quotient test. Compute $a / b$ in $\mathbb{Q}$; check whether the result is an integer.
Remainder test (preferred when $a, b$ are large). Compute the Euclidean division $a = b q + r$ with $0 \leq r < |b|$; then $b \mid a \iff r = 0$ (next theorem).

Theorem — Euclidean division

For every $a \in \mathbb{Z}$ and every $b \in \mathbb{Z}^*$, there exists a unique pair $(q, r) \in \mathbb{Z} \times \mathbb{N}$ such that $$ \textcolor{colorprop}{a = b q + r \quad \text{and} \quad 0 \leq r < |b|.} $$ The integer $a$ is the dividend, $b$ the divisor, $q$ the quotient and $r$ the remainder of the Euclidean division of $a$ by $b$. When $b > 0$, the quotient is $q = \lfloor a / b \rfloor$, where $\lfloor \cdot \rfloor$ denotes the floor (the integer part of a real, from the Properties-of-$\mathbb{R}$ material).

Proof

We first treat the case $b > 0$, then reduce the general case to it.
Existence ($b > 0$). Set $R = \{a - b k : k \in \mathbb{Z}\} \cap \mathbb{N}$. The set $R$ is non-empty: if $a \geq 0$, then $a = a - b \cdot 0 \in R$; if $a < 0$, then $k = a$ gives $a - b a = a (1 - b) \geq 0$ since $1 - b \leq 0$ and $a < 0$, hence $a - b a \in R$. As a non-empty subset of $\mathbb{N}$, $R$ has a smallest element; call it $r$, and write $r = a - b q$ for some $q \in \mathbb{Z}$, i.e.\ $a = b q + r$ with $r \geq 0$. It remains to show $r < b$. Suppose for contradiction $r \geq b$. Then $r - b \in \mathbb{N}$ and $r - b = a - b (q + 1) \in R$, contradicting the minimality of $r$. Hence $r < b = |b|$.
Uniqueness ($b > 0$). Suppose $a = b q + r = b q' + r'$ with $0 \leq r, r' < b$. Then $b (q - q') = r' - r$, so $|b (q - q')| = |r' - r| < b$, forcing $|q - q'| < 1$. Since $q - q' \in \mathbb{Z}$, $q = q'$, and then $r = r'$.
General $b \in \mathbb{Z}^*$. Apply the case just proved to the positive divisor $|b|$: there is a unique $(q_0, r) \in \mathbb{Z} \times \mathbb{N}$ with $a = |b| q_0 + r$ and $0 \leq r < |b|$. If $b > 0$, take $(q, r) = (q_0, r)$; if $b < 0$, then $|b| = -b$ and $a = b(-q_0) + r$, so take $(q, r) = (-q_0, r)$. In both cases $a = b q + r$ with $0 \leq r < |b|$, and uniqueness of $r$ (hence of $q$) follows from the uniqueness for $|b|$.
Formula for $q$ when $b > 0$. From $a / b = q + r / b$ with $0 \leq r/b < 1$, we get $q = \lfloor a / b \rfloor$.

Example

For $a = 23$, $b = 5$: $23 = 5 \cdot 4 + 3$, so $q = 4$ and $r = 3$. Indeed $\lfloor 23 / 5 \rfloor = 4$.

Example — Negative dividend --- a classical trap

For $a = -23$, $b = 5$: not $-23 = 5 \cdot (-4) - 3$, because the remainder would then be $-3 < 0$. The correct Euclidean division is $$ \textcolor{colorprop}{-23 = 5 \cdot (-5) + 2,} $$ so $q = -5$ and $r = 2$. Check: $\lfloor -23 / 5 \rfloor = -5$ (not $-4$). The remainder is always in $\{0, 1, \dots, |b| - 1\}$.

Skills to practice

Divisibility and Euclidean division

IV.2 gcd, Euclid's algorithm and lcm

The greatest common divisor (gcd) of two integers is the largest integer dividing both. It is defined here as the greatest element, for the natural order $\leq$ on $\mathbb{N}^*$, of the set of common divisors; it is computed effectively by Euclid's algorithm, an iterated Euclidean division. The least common multiple (lcm) is the dual notion, and the relation $(a \wedge b)(a \vee b) = |ab|$ ties the two together.

Definition — Greatest common divisor (gcd)

Let $a, b \in \mathbb{Z}$ not both zero. The greatest common divisor of $a$ and $b$, denoted $a \wedge b$, is the largest element of $\{d \in \mathbb{N}^* : d \mid a \text{ and } d \mid b\}$ for the natural order $\leq$ on $\mathbb{N}^*$. By convention, $0 \wedge 0 = 0$.
The set $\{d \in \mathbb{N}^* : d \mid a \text{ and } d \mid b\}$ is non-empty (it contains $1$) and finite (every common divisor is bounded above by $\max(|a|, |b|)$), so its maximum exists.

Example

$12 \wedge 18 = 6$: divisors of $12$ in $\mathbb{N}^*$ are $\{1, 2, 3, 4, 6, 12\}$, divisors of $18$ are $\{1, 2, 3, 6, 9, 18\}$, common divisors are $\{1, 2, 3, 6\}$, max is $6$. Also $a \wedge 1 = 1$ for every $a \in \mathbb{Z}$, and $a \wedge 0 = |a|$ for every $a \in \mathbb{Z}^*$.

Proposition — Fundamental idea

For all $a \in \mathbb{Z}$ and $b \in \mathbb{N}^*$, if $a = b q + r$ is the Euclidean division of $a$ by $b$, then $$ \textcolor{colorprop}{a \wedge b = b \wedge r.} $$

Proof

We show that the set of common divisors of $a$ and $b$ equals the set of common divisors of $b$ and $r$; the gcd, defined as the maximum of this set, is therefore the same.

$(\subset)$ If $d \mid a$ and $d \mid b$, then by linear combinations $d \mid (a - b q) = r$. So $d$ divides $b$ and $r$.
$(\supset)$ If $d \mid b$ and $d \mid r$, then $d \mid (b q + r) = a$. So $d$ divides $a$ and $b$.

The two sets coincide; their maxima do too: $a \wedge b = b \wedge r$.

Theorem — Existence of the gcd via Euclid's algorithm

Let $a, b \in \mathbb{N}$ with $0 < b \leq a$. Define a sequence of remainders by $r_0 = a$, $r_1 = b$, and $r_{k+2} = $ Euclidean remainder of $r_k$ divided by $r_{k+1}$ as long as $r_{k+1} > 0$. The sequence terminates: there exists $N \geq 1$ with $r_N = 0$, and the gcd is the last non-zero remainder: $$ \textcolor{colorprop}{a \wedge b = r_{N - 1}.} $$

Proof

Termination. As long as $r_{k+1} > 0$, the construction yields $0 \leq r_{k+2} < r_{k+1}$, so the strictly positive remainders $r_1, r_2, \dots$ form a strictly decreasing sequence in $\mathbb{N}^*$, which must be finite; some $r_N = 0$.
Correctness. By the « fundamental idea » applied at each step, $r_k \wedge r_{k+1} = r_{k+1} \wedge r_{k+2}$. Chaining, $$ a \wedge b = r_0 \wedge r_1 = r_1 \wedge r_2 = \cdots = r_{N-1} \wedge r_N = r_{N-1} \wedge 0 = r_{N-1}. $$

Method — Compute $a \wedge b$ by Euclid's algorithm

Suppose $0 < b \leq a$. Tabulate the successive Euclidean divisions $r_k = r_{k+1} \, q_{k+1} + r_{k+2}$ with $0 \leq r_{k+2} < r_{k+1}$, starting from $a = b \, q_1 + r_2$. Stop as soon as a remainder is zero; the last non-zero remainder is $a \wedge b$. For general $a, b \in \mathbb{Z}$, replace them by $|a|, |b|$.

Example

Compute $1542 \wedge 58$.

Answer

Apply Euclid's algorithm: $$ \begin{aligned} 1542 &= 26 \cdot 58 + 34, \\ 58 &= 1 \cdot 34 + 24, \\ 34 &= 1 \cdot 24 + 10, \\ 24 &= 2 \cdot 10 + 4, \\ 10 &= 2 \cdot 4 + 2, \\ 4 &= 2 \cdot 2 + 0. \end{aligned} $$ The last non-zero remainder is $2$, so $1542 \wedge 58 = 2$.

Definition — Least common multiple (lcm)

Let $a, b \in \mathbb{N}^*$. The least common multiple of $a$ and $b$, denoted $a \vee b$, is the smallest element of $\{m \in \mathbb{N}^* : a \mid m \text{ and } b \mid m\}$ for the natural order $\leq$ on $\mathbb{N}^*$. The set is non-empty (it contains $a b$). By convention $0 \vee b := 0$, and for $a, b \in \mathbb{Z}$, $a \vee b := |a| \vee |b|$.

Proposition — Common multiples are multiples of the lcm

For all $a, b \in \mathbb{N}^*$, $$ \textcolor{colorprop}{a \mathbb{Z} \cap b \mathbb{Z} = (a \vee b) \mathbb{Z},} $$ equivalently: $a \mid n$ and $b \mid n \iff (a \vee b) \mid n$. Hence $a \vee b$ is also the smallest common multiple for the divisibility order $\mid$.

Proof

Set $m = a \vee b$.

$(\supset)$ $m$ is a common multiple of $a$ and $b$, so every multiple of $m$ is a common multiple.
$(\subset)$ Let $n$ be a common multiple. Euclidean division gives $n = m q + r$ with $0 \leq r < m$. Then $r = n - m q$ is a common multiple of $a$ and $b$; since $0 \leq r < m$ and $m$ is the smallest positive common multiple, $r = 0$. So $n = m q \in m \mathbb{Z}$.

Proposition — gcd-lcm relation

For all $a, b \in \mathbb{Z}$, $$ \textcolor{colorprop}{(a \wedge b)(a \vee b) = |a b|.} $$ (The cleanest proof reads off the exponents in the prime factorization of $a$ and $b$ via the identity $\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$; we take the formula as established.)

Example

$12 \vee 18 = 36$, and $12 \cdot 18 = 216 = 6 \cdot 36 = (12 \wedge 18)(12 \vee 18)$.

Skills to practice

gcd, Euclid's algorithm and lcm

IV.3 Prime numbers

Prime numbers are the multiplicative atoms of $\mathbb{N}^*$: every $n \geq 2$ is a product of primes. We give the definition, prove Euclid's classical infinitude theorem, present the sieve of Eratosthenes, and state the existence and uniqueness of the prime factorization, whose proof is beyond our scope here. The factorization then yields a clean way to read off the gcd and lcm.

Definition — Prime number$\virgule$ composite number

A natural number $p \geq 2$ is called prime if its only divisors in $\mathbb{N}^*$ are $1$ and $p$ (equivalently, $\operatorname{div}(p) = \{\pm 1, \pm p\}$). We denote by $\mathbb{P}$ the set of prime numbers. A natural number $n \geq 2$ that is not prime is called composite: it admits a divisor $d$ with $1 < d < n$. The integer $1$ is, by convention, neither prime nor composite.

Example

The first prime numbers are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \dots$. The integer $4 = 2 \cdot 2$ is composite. (The exclusion of $1$ from the primes is required to keep the prime factorization unique: otherwise $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$, etc.)

Proposition — Existence of a prime divisor

Every integer $n \geq 2$ admits at least one prime divisor.

Proof

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$. If $p_0$ were composite, it would have a divisor $d$ with $1 < d < p_0$; then $d \mid n$ (transitivity), so $d \in D$ with $d < p_0$ --- contradicting minimality. Hence $p_0$ is prime, and $p_0 \mid n$.

Theorem — Infinitude of primes

The set $\mathbb{P}$ of prime numbers is infinite.

Proof

Euclid's classical proof, by contradiction. Suppose $\mathbb{P}$ is finite, say $\mathbb{P} = \{p_1, \dots, p_r\}$. Consider $N = p_1 \, p_2 \cdots p_r + 1$. Since $N \geq 2$, $N$ admits a prime divisor $p_k$. 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.

Method — Sieve of Eratosthenes

To list all prime numbers $\leq N$ (for some $N \geq 2$):
Step 1. Write the integers $2, 3, 4, \dots, N$ in a table.
Step 2. Take the smallest non-crossed integer $p$. Then $p$ is prime; cross out all proper multiples $2p, 3p, \dots \leq N$.
Step 3. Repeat until $p > \sqrt{N}$. Every remaining non-crossed integer $\leq N$ is then prime.
Why $\sqrt{N}$ suffices. If $n \leq N$ is composite, write $n = a b$ with $a \leq b$; then $a \leq \sqrt{n} \leq \sqrt{N}$, so $n$ is crossed out by a prime $\leq \sqrt{N}$.

Example — Primes $\leq 30$ by the sieve

$\sqrt{30} < 6$, so the primes used to cross out are $2, 3, 5$. After crossing the multiples of $2$, then of $3$, then of $5$, the survivors are $$ \textcolor{colorprop}{\mathbb{P} \cap [\![ 2, 30 ]\!] = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}.} $$ Total: $10$ primes $\leq 30$.

Theorem — Existence and uniqueness of the prime factorization

Every integer $n \geq 2$ writes as a product of prime numbers, $$ \textcolor{colorprop}{n = p_1^{\alpha_1} \, p_2^{\alpha_2} \cdots p_s^{\alpha_s},} $$ with $p_1 < p_2 < \cdots < p_s$ primes and $\alpha_1, \dots, \alpha_s \in \mathbb{N}^*$, and this writing is unique (the primes and their exponents are determined by $n$). We admit this theorem; its proof is beyond our scope.

Example

$360 = 2^3 \cdot 3^2 \cdot 5$ and $84 = 2^2 \cdot 3 \cdot 7$. These two writings are the only prime factorizations of $360$ and $84$.

Method — Compute the gcd and lcm via factorization

Write $a$ and $b$ in prime factorization over the same list of primes $p_1, \dots, p_s$ (using exponent $0$ where a prime is absent): $a = \prod_i p_i^{\alpha_i}$, $b = \prod_i p_i^{\beta_i}$. Then $$ \textcolor{colorprop}{a \wedge b = \prod_i p_i^{\min(\alpha_i, \beta_i)}, \qquad a \vee b = \prod_i p_i^{\max(\alpha_i, \beta_i)}.} $$ Example: $360 = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^0$ and $84 = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^1$ give $360 \wedge 84 = 2^2 \cdot 3^1 = 12$ and $360 \vee 84 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$, with $12 \cdot 2520 = 30240 = 360 \cdot 84$.

Skills to practice

Prime numbers