CommeUnJeu · L1 PCSI

Compléments de calcul algébrique

⌚ ~115 min ▢ 14 blocs ✓ 46 exercices ➣ Prérequis : Logique, Formule du binôme de Newton

Ce chapitre est un atelier. On n'y introduit pas une théorie profonde ; on y muscle les outils de calcul nécessaires à tous les chapitres qui suivent. Trois outils s'aiguisent ici. Sommes (avec la notation compacte $\sum$) : comment les manipuler, changement d'indice, simplification télescopique, sommes doubles. Produits et factorielle (avec $\prod$) : comment fonctionne l'analogue multiplicatif, la factorielle $n!$, les produits télescopiques. Coefficients binomiaux : $\binom{n}{p}$, le triangle de Pascal, et la fameuse formule $(a+b)^n$.
Le plan s'ouvre sur trois mouvements, chacun indépendant des autres, chacun court. On ira vite sur ce que les étudiants ont déjà rencontré au lycée (factorielles, binôme pour les petits $n$) ; on prendra son temps sur le matériel vraiment nouveau (sommes télescopiques, sommes doubles, formule du binôme). De nombreuses démonstrations de ce chapitre se font par récurrence sur $n$, ou par manipulation soignée d'indices --- techniques maîtrisées au chapitre de logique ; on les applique ici. Le versant ordonné de $\mathbb{R}$ (inégalités, valeur absolue, partie entière, borne supérieure/inférieure) est traité ailleurs. Convention pédagogique. Pour clarifier une identité avec $\sum$, on écrira parfois la forme formelle et la forme développée (termes écrits avec des \texttt{+}) sur deux lignes consécutives, afin que le lecteur voie à quoi ressemble chaque terme.
Une quatrième section replie ensuite les bases de l'arithmétique dans $\mathbb{Z}$, la boîte à outils sur les entiers $\mathbb{N}, \mathbb{Z}$ dont on se servira tout au long du cours : la relation de divisibilité $b \mid a$ et la division euclidienne $a = bq + r$ ; le plus grand commun diviseur $a \wedge b$ calculé par l'algorithme d'Euclide, et le plus petit commun multiple $a \vee b$ ; les nombres premiers, l'infinitude de $\mathbb{P}$, et la décomposition d'un entier en produit de nombres premiers.

I Sommes

La notation $\sum$ est un raccourci : elle abrège une somme qu'il serait pénible d'écrire en extension. On commence par poser ses règles : comment fonctionne l'indice muet, comment éclater une somme ou décaler l'indice, comment deux termes consécutifs se télescopent. Les cinq sous-sections de cette section exercent ces mécaniques sur des exemples classiques ; les chapitres ultérieurs s'en serviront partout.

I.1 Notation sigma

Étant donné une liste finie de réels $a_m, a_{m+1}, \dots, a_n$, leur somme $a_m + a_{m+1} + \dots + a_n$ se note $\sum_{k=m}^{n} a_k$. La variable $k$ est un indice muet : elle parcourt les entiers de $m$ à $n$ (inclus), et la valeur de la somme ne dépend pas du nom de la lettre ($k$, $i$, $j$, $\ell$ donnent la même somme). Deux règles élémentaires régissent l'interaction de $\sum$ avec l'addition et la multiplication par un scalaire.

Définition — Notation sigma

Pour $m, n \in \mathbb{Z}$ et $(a_k)$ une famille de réels indexée par les entiers, la somme $\sum_{k=m}^{n} a_k$ est définie comme suit.

Si $m \le n$ : $$ \sum_{k=m}^{n} a_k = a_m + a_{m+1} + \dots + a_n. $$
Si $m > n$ (cas de la somme vide) : $$ \sum_{k=m}^{n} a_k = 0. $$

Exemple

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

Proposition — Linéarité de $\sum$

Pour $m, n \in \mathbb{Z}$ avec $m \le n$, $\lambda, \mu \in \mathbb{R}$, et $(a_k)_{m \le k \le n}$, $(b_k)_{m \le k \le n}$ deux familles finies de réels : $$ \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}} $$ En particulier, $\sum (a_k + b_k) = \sum a_k + \sum b_k$ et $\sum \lambda a_k = \lambda \sum a_k$.

Proposition — Découpage et relation de Chasles

Pour $m, p, n \in \mathbb{Z}$ avec $m \le p < n$, et $(a_k)_{m \le k \le n}$ une famille finie de réels : $$ \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_n &= (a_m + \dots + a_p) + (a_{p+1} + \dots + a_n). \end{aligned}} $$

Compétences à pratiquer

Lire et évaluer une somme avec $\sum$

I.2 Changement d'indice

L'indice muet peut être renommé (il reste un entier) ou décalé par une transformation additive ou symétrique. Deux changements d'indice sont omniprésents : le décalage $j = k - p$ (renumérotation par $p$) et la réflexion $j = n - k$ (compter en sens inverse). Chacun préserve la somme --- il ne fait que reformuler les bornes.

Proposition — Changement d'indice

Soient $m \le n$ deux entiers (l'ensemble d'indices $\{m, m+1, \dots, n\}$ est donc non vide).

Décalage : pour $p \in \mathbb{Z}$, avec $j = k - p$ $$ \textcolor{colorprop}{\sum_{k=m}^{n} a_k = \sum_{j=m-p}^{n-p} a_{j+p}}. $$
Réflexion : avec $j = n - k$ (soit $k = n - j$), qui ramène la borne inférieure à $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}} $$ ou, de façon équivalente, sous la forme qui préserve les bornes, avec $j = n + m - k$ (soit $k = n + m - j$), $$ \textcolor{colorprop}{ \sum_{k=m}^{n} a_k = \sum_{j=m}^{n} a_{n+m-j} } $$ qui laisse les bornes initiales $m$ et $n$ inchangées.

Exemple

Réécrire $\sum_{k=3}^{n+3} k^2$ avec un indice de sommation commençant à $0$.

Correction

Posons $j = k - 3$. Alors $k = j + 3$, et lorsque $k$ parcourt $3$ à $n+3$, $j$ parcourt $0$ à $n$. D'où $$ \sum_{k=3}^{n+3} k^2 = \sum_{j=0}^{n} (j+3)^2 = \sum_{j=0}^{n} (j^2 + 6j + 9). $$

Exemple

Montrer que $\sum_{k=0}^{n} a_k = \sum_{k=0}^{n} a_{n-k}$.

Correction

On applique la réflexion $j = n - k$ : $k = n - j$, et lorsque $k$ parcourt $0$ à $n$, $j$ parcourt $n$ à $0$, donc $j$ prend les mêmes valeurs que $k$. D'où $$ \sum_{k=0}^{n} a_k = \sum_{j=0}^{n} a_{n-j} = \sum_{k=0}^{n} a_{n-k} $$ (la dernière égalité renomme l'indice muet en $k$).

Compétences à pratiquer

Translater et réfléchir un indice

I.3 Sommes classiques

Quatre sommes doivent être au bout des doigts : la somme des premiers entiers, la somme de leurs carrés, la somme de leurs cubes, et la somme géométrique. Et une factorisation, duale algébrique de la somme géométrique : $a^n - b^n$. Ces cinq formules sous-tendent tout calcul ultérieur.

Theorem — Sommes classiques

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

Somme des entiers. $$ \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}} $$
Somme des carrés. $$ \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}} $$
Somme des 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}} $$

Somme géométrique. Pour $x \in \mathbb{R}$ avec $x \ne 1$ et $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}} $$ Pour $x = 1$ : $\sum_{k=0}^{n} 1 = n+1$.

Preuve

Les démonstrations utilisent deux idées récurrentes : le changement d'indice (pour la somme des entiers) et le télescopage d'une différence $u_{k+1} - u_k$ suivi du développement polynomial (pour les sommes des carrés et des cubes, et pour la somme géométrique). On utilise ici le télescopage par anticipation : il est énoncé et démontré en détail dans la Proposition de télescopage de la sous-section suivante (Sommes télescopiques ci-dessous) ; on n'invoque ici que sa conclusion $\sum_{k=m}^{n}(u_{k+1}-u_k) = u_{n+1} - u_m$.

Somme des entiers --- changement d'indice. Soit $S = \sum_{i=0}^{n} i$. Avec le changement d'indice $i \mapsto n - i$, la même somme s'écrit aussi $S = \sum_{i=0}^{n} (n - i)$. Additionnons les deux expressions de $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{(linéarité)} \\ &= \sum_{i=0}^{n} n && \text{(simplification : } i + (n-i) = n\text{)} \\ &= n \sum_{i=0}^{n} 1 && \text{(linéarité)} \\ &= n (n+1) && \text{(} \sum_{i=0}^{n} 1 = n+1 \text{)}. \end{aligned} $$ D'où $\displaystyle\sum_{k=0}^{n} k = \frac{n(n+1)}{2}$.
Somme des carrés --- télescopage avec les cubes. On applique le télescopage à $u_k = k^3$ et on enchaîne les opérations : $$ \begin{aligned} \sum_{k=0}^{n} \big((k+1)^3 - k^3\big) &= (n+1)^3 && \text{(télescopage, } u_k = k^3 \text{)} \\ \sum_{k=0}^{n} (3k^2 + 3k + 1) &= (n+1)^3 && \text{(développer } (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{(linéarité)} \\ 3 \sum_{k=0}^{n} k^2 + 3 \cdot \frac{n(n+1)}{2} + (n+1) &= (n+1)^3 && \text{(sommes connues)} \\ 3 \sum_{k=0}^{n} k^2 &= (n+1)^3 - \frac{3n(n+1)}{2} - (n+1) && \text{(isolation)} \\ 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{(factoriser } (n+1) \text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)\big[2n^2 + 4n + 2 - 3n - 2\big] && \text{(développer } 2(n+1)^2 = 2n^2 + 4n + 2 \text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)(2n^2 + n) && \text{(regrouper les termes du crochet)} \\ 6 \sum_{k=0}^{n} k^2 &= n(n+1)(2n+1) && \text{(factoriser } n \text{).} \end{aligned} $$ D'où $\displaystyle\sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$.
Somme des cubes --- même astuce avec $(k+1)^4 - k^4$. On applique le télescopage à $u_k = k^4$, on développe $(k+1)^4 - k^4 = 4k^3 + 6k^2 + 4k + 1$, et on réutilise $\sum k$ et $\sum k^2$ : $$ \begin{aligned} \sum_{k=0}^{n} \big((k+1)^4 - k^4\big) &= (n+1)^4 && \text{\doublecolumnscriptsize (télescopage, } u_k = k^4 \text{)} \\ \sum_{k=0}^{n} (4k^3 + 6k^2 + 4k + 1) &= (n+1)^4 && \text{\doublecolumnscriptsize (développement)} \\ 4 \sum k^3 + 6 \sum k^2 + 4 \sum k + \sum 1 &= (n+1)^4 && \text{\doublecolumnscriptsize (linéarité)} \\ 4 \sum k^3 + n(n+1)(2n+1) \\ \quad + 2n(n+1) + (n+1) &= (n+1)^4 && \text{\doublecolumnscriptsize (sommes connues)} \\ 4 \sum k^3 &= (n+1)^4 - n(n+1)(2n+1) \\ &\quad - 2n(n+1) - (n+1) && \text{\doublecolumnscriptsize (isolation)} \\ 4 \sum k^3 &= (n+1)\big[(n+1)^3 - n(2n+1) - 2n - 1\big] && \text{\doublecolumnscriptsize (factoriser } (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 (développer } (n+1)^3, n(2n+1)\text{)} \\ 4 \sum k^3 &= (n+1)(n^3 + n^2) && \text{\doublecolumnscriptsize (regrouper les termes du crochet)} \\ 4 \sum k^3 &= n^2(n+1)^2 && \text{\doublecolumnscriptsize (factoriser } n^2 \text{).} \end{aligned} $$ D'où $\displaystyle\sum_{k=0}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$.
Somme géométrique --- télescopage après multiplication par $(1-x)$. Pour $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{(distribution)} \\ &= \sum_{k=0}^{n} x^k - \sum_{k=0}^{n} x^{k+1} && \text{(faire entrer dans la somme)} \\ &= \sum_{k=0}^{n} (x^k - x^{k+1}) && \text{(linéarité)} \\ &= x^0 - x^{n+1} && \text{(télescopage, } u_k = x^k \text{)} \\ &= 1 - x^{n+1}. \end{aligned} $$ On divise par $1 - x$ : $\displaystyle\sum_{k=0}^{n} x^k = \frac{1 - x^{n+1}}{1 - x}$.

Exemple

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

Correction

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

Exemple

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

Correction

Somme géométrique avec $x = 2$ : $\sum_{k=0}^{n} 2^k = (2^{n+1} - 1)/(2 - 1) = 2^{n+1} - 1$.

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

Pour $a, b \in \mathbb{R}$ et $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})}. $$

Preuve

Posons $u_k = a^{n-k} b^k$. La distribution de $(a - b)$ sur la somme produit une somme télescopique : $$ (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. $$

Compétences à pratiquer

Reconnaître et appliquer les formules classiques
Combiner les sommes classiques par linéarité

I.4 Sommes télescopiques

Une somme télescopique est une somme de différences consécutives $u_{k+1} - u_k$, dans laquelle tous les termes intermédiaires se simplifient deux à deux --- seuls les bords subsistent. L'astuce est de reconnaître quand un terme s'écrit comme une telle différence, car alors la somme entière s'effondre à deux termes.

Proposition — Somme télescopique

Pour toute suite $(u_k)$ et entiers $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}} $$

Preuve

Trois perspectives sur le même résultat : deux démonstrations formelles et une visuelle.

Démonstration 1 --- récurrence sur $n$ (avec $m$ fixé). Initialisation. Pour $n = m$, la somme se réduit à un seul terme : $\sum_{k=m}^{m} (u_{k+1} - u_k) = u_{m+1} - u_m$, ce qui vaut $u_{n+1} - u_m$ pour $n=m$. $\checkmark$ Hérédité. On suppose la formule au rang $n$. Au rang $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, isoler le dernier terme)} \\ &= (u_{n+1} - u_m) + (u_{n+2} - u_{n+1}) && \text{(hypothèse de récurrence)} \\ &= u_{n+2} - u_m && \text{(simplification).} \end{aligned} $$ L'hérédité est établie ; le résultat suit pour tout $n \ge m$.
Démonstration 2 --- changement d'indice. $$ \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{(linéarité)} \\ &= \sum_{j=m+1}^{n+1} u_j - \sum_{k=m}^{n} u_k && \text{(changement d'indice } j = k+1 \text{)} \\ &= u_{n+1} + \sum_{j=m+1}^{n} u_j - \sum_{k=m}^{n} u_k && \text{(Chasles, isoler } 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, isoler } k=m\text{)} \\ &= u_{n+1} - u_m && \text{(les deux sommes intérieures sont égales --- indice muet).} \end{aligned} $$
Idée visuelle --- développer et regarder les termes se simplifier. En écrivant la somme terme à terme : $$ \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). $$ Tout $u_j$ avec $m+1 \le j \le n$ apparaît exactement deux fois --- une fois avec un signe $+$, une fois avec un signe $-$ --- et les deux occurrences se compensent. Seuls $-u_m$ au début et $+u_{n+1}$ à la fin survivent : la somme se réduit à $u_{n+1} - u_m$.

Exemple

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

Correction

On décompose : $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$. En posant $u_k = -\frac{1}{k}$, le terme général est $u_{k+1} - u_k$. Par la formule télescopique $$ \sum_{k=1}^{n} \frac{1}{k(k+1)} = u_{n+1} - u_1 = -\frac{1}{n+1} + 1 = \frac{n}{n+1}. $$

Exemple

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

Correction

$\ln(1 + 1/k) = \ln((k+1)/k) = \ln(k+1) - \ln(k)$. En posant $u_k = \ln(k)$, le terme général est $u_{k+1} - u_k$. D'où $$ \sum_{k=1}^{n} \ln\!\left(1 + \frac{1}{k}\right) = \ln(n+1) - \ln(1) = \ln(n+1). $$

Méthode — Reconnaître une somme télescopique

Repérer le motif $u_{k+1} - u_k$ (différence d'un seul pas). Deux déclencheurs fréquents :

Fraction rationnelle $\dfrac{1}{k(k+1)}$ : décomposition en éléments simples qui donne $\dfrac{1}{k(k+1)} = \dfrac{1}{k} - \dfrac{1}{k+1}$, différence d'un pas avec $u_k = -\dfrac{1}{k}$. (Pour des écarts plus larges $\dfrac{1}{k(k+a)}$ avec $a \ge 2$, la décomposition donne une différence à $a$ pas --- traité dans le « pour aller plus loin » des exercices.)
Logarithme d'un rapport : $\ln\!\big(f(k+1)/f(k)\big) = \ln f(k+1) - \ln f(k)$.

Une fois le terme général reconnu sous la forme $u_{k+1} - u_k$, la formule effondre la somme à deux termes : $u_{n+1} - u_m$.

Compétences à pratiquer

Décomposer puis télescoper

I.5 Sommes doubles

Une somme double $\sum_{i,j}$ parcourt un rectangle (ou un triangle) de couples $(i \,;\, j)$. Trois simplifications : quand le rectangle est plein et que le terme général se factorise, la somme est un produit de deux sommes simples ; on peut permuter l'ordre des sommations (Fubini pour les sommes) ; pour les triangles, on échange les rôles des variables interne et externe.

Proposition — Identités sur les sommes doubles

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 (terme séparable) : si $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 : échange interne/externe : $$ \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}}. $$

Preuve

Les trois identités reposent toutes sur la commutativité et l'associativité de l'addition sur $\mathbb{R}$ --- qui permettent de réordonner une somme finie librement --- combinées à la linéarité de $\sum$.

Permutation (Fubini) --- développer et re-collecter. La somme double rectangulaire énumère chaque case $(i,j)$ du rectangle d'indices $(n - m + 1) \times (q - p + 1)$ exactement une fois. Les deux imbrications listent les mêmes cases ; les sommes finies des mêmes nombres sont égales : $$ \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 (terme séparable). Fixons $i$ dans la somme interne et appliquons la linéarité ($b_i$ est constant par rapport à $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{(linéarité, } b_i \text{ ne dépend pas de } j\text{)} \\ &= \left(\sum_{j=p}^{q} c_j\right) \sum_{i=m}^{n} b_i && \text{(linéarité, le facteur entre parenthèses ne dépend pas de } i\text{)} \\ &= \left(\sum_{i=m}^{n} b_i\right) \left(\sum_{j=p}^{q} c_j\right). \end{aligned} $$
Triangle : échange interne/externe. L'ensemble $\{(i,j) : 1 \le i \le j \le n\}$ se partitionne de deux manières équivalentes :
- en ordonnant sur $j$ à l'extérieur : pour chaque $j \in \{1, \dots, n\}$, l'indice interne $i$ parcourt $\{1, \dots, j\}$, donnant $\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$ ;
- en ordonnant sur $i$ à l'extérieur : pour chaque $i \in \{1, \dots, n\}$, l'indice interne $j$ parcourt $\{i, \dots, n\}$, donnant $\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}$.
Les deux partitions énumèrent chaque couple $(i,j)$ avec $1 \le i \le j \le n$ exactement une fois, donc les deux sommes doubles sont égales à $\sum_{1 \le i \le j \le n} a_{i,j}$.

Exemple

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

Correction

Le terme $ij$ se sépare. 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. $$

Exemple

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

Correction

Triangle des couples $(i \,;\, j)$ avec $1 \le i \le j \le n$. Somme de $1$ sur ce triangle = nombre de couples = $n(n+1)/2$. Vérification en ordonnant sur $j$ : $\sum_{j=1}^{n} \sum_{i=1}^{j} 1 = \sum_{j=1}^{n} j = n(n+1)/2$.

Méthode — Calculer une somme double

Trois réflexes, dans cet ordre :

Terme séparable : si $a_{i,j} = b_i c_j$, on factorise $\sum_{i,j} b_i c_j = \bigl(\sum_i b_i\bigr)\bigl(\sum_j c_j\bigr)$ --- deux sommes simples.
Domaine triangulaire : on choisit la somme interne de sorte que les bornes de la variable interne soient visibles. Avec $1 \le i \le j \le n$, ordonner sur $j$ à l'extérieur donne $\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$ ; ordonner sur $i$ à l'extérieur donne $\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}$. Choisir celle qui rend la somme interne reconnaissable parmi les sommes classiques.
Rectangle bloqué : si aucun des deux points précédents ne suffit, on permute l'ordre de sommation (Fubini) et on réessaie --- souvent la forme permutée révèle une structure séparable ou une somme interne reconnaissable.

Compétences à pratiquer

Permuter et factoriser des sommes doubles

II Produits

La notation $\prod$ est la cousine multiplicative de $\sum$. La même machinerie s'applique : indice muet, changement d'indice, simplification télescopique. Le seul changement structurel est la convention du produit vide (qui vaut $1$, pas $0$). Le produit le plus utile est la factorielle.

II.1 Notation pi et factorielle

La factorielle $n!$ compte le nombre d'ordres distincts de $n$ objets. Algébriquement, c'est le produit des $n$ premiers entiers strictement positifs. Elle apparaîtra partout : coefficients binomiaux, développements de Taylor, dénombrement.

Définition — Notation pi$\virgule$ factorielle

Pour $m, n \in \mathbb{Z}$ et une famille $(a_k)$ de réels indexée par les entiers, le produit $\prod_{k=m}^{n} a_k$ est défini comme suit.
- Si $m \le n$ : $$ \prod_{k=m}^{n} a_k = a_m \cdot a_{m+1} \cdot \dots \cdot a_n. $$
- Si $m > n$ (cas du produit vide) : $\prod_{k=m}^{n} a_k = 1$.
Pour $n \in \mathbb{N}$, la factorielle de $n$ est $$ \textcolor{colordef}{n!} = \prod_{k=1}^{n} k = 1 \cdot 2 \cdot 3 \cdots n. $$ Par convention, $\textcolor{colordef}{0!} = 1$ (produit vide).

Exemple

$0! = 1$, $1! = 1$, $2! = 2$, $3! = 6$, $4! = 24$, $5! = 120$.
$10! = 3628800$ (déjà grand).

Proposition — Récurrence et rapports de factorielles

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

Compétences à pratiquer

Manipuler produits et factorielles

II.2 Produits télescopiques

Analogue multiplicatif de la somme télescopique : un produit de rapports $u_{k+1}/u_k$ s'effondre à deux termes aux bornes. Utile lorsqu'une fraction se réécrit comme un tel rapport.

Proposition — Produit télescopique

Pour une suite $(u_k)$ de réels non nuls et $m \le n$ : $$ \textcolor{colorprop}{\prod_{k=m}^{n} \frac{u_{k+1}}{u_k} = \frac{u_{n+1}}{u_m}}. $$

Exemple

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

Correction

En posant $u_k = k$, le terme général est $u_{k+1}/u_k$. Par le produit télescopique $$ \prod_{k=1}^{n} \frac{k+1}{k} = \frac{u_{n+1}}{u_1} = \frac{n+1}{1} = n+1. $$

Méthode — Reconnaître un produit télescopique

Repérer le motif $u_{k+1}/u_k$. Cas fréquents :

Rapport explicite de valeurs consécutives : $\dfrac{f(k+1)}{f(k)}$ pour une suite $(f(k))$.
Rapport de factorielles consécutives : $\dfrac{(k+1)!}{k!} = k+1$, donc $\prod_{k=1}^{n}\dfrac{(k+1)!}{k!} = (n+1)!$.
Détour logarithmique : lorsque les facteurs sont positifs, on passe au $\ln$ pour convertir le produit en une somme télescopique de $\ln u_{k+1} - \ln u_k$, puis on ré-exponentie.

Une fois reconnu, le produit s'effondre en $u_{n+1}/u_m$ --- seuls les bords subsistent.

Compétences à pratiquer

Téléscoper un produit

III Coefficients binomiaux

Le coefficient binomial $\binom{n}{k}$ compte le nombre de façons de choisir $k$ objets parmi $n$ (sans ordre). Le même nombre apparaît comme coefficient de $a^{n-k}b^k$ dans le développement de $(a+b)^n$. Les deux visages --- combinatoire et algébrique --- sont équivalents, et l'on utilisera celui qui convient. La section culmine sur la formule du binôme, l'identité algébrique la plus célèbre des mathématiques élémentaires.

III.1 Définition et propriétés

On définit $\binom{n}{k}$ par sa formule factorielle, puis on observe ses trois propriétés fondamentales : il apparaîtra (dans la formule du binôme prouvée plus bas) comme coefficient de $a^{n-k} b^k$ dans le polynôme symétrique $(a+b)^n$, il est symétrique en $k$ et $n-k$, et il satisfait une relation de récurrence qui donne le triangle de Pascal.

Définition — Coefficient binomial

Pour $n \in \mathbb{N}$ et $k \in \mathbb{Z}$, le coefficient binomial $\binom{n}{k}$ est défini par : $$ \textcolor{colordef}{\binom{n}{k}} = \begin{cases} \dfrac{n!}{k!\,(n-k)!} & \text{si } 0 \le k \le n, \\ 0 & \text{sinon.} \end{cases} $$ On lit « $k$ parmi $n$ ». L'expression factorielle ci-dessus est la définition ; le fait que ce nombre soit aussi égal au nombre de parties à $k$ éléments d'un ensemble à $n$ éléments est l'interprétation combinatoire, établie séparément par un argument de dénombrement (elle ne fait pas partie de la définition).

Proposition — Valeurs standards des coefficients binomiaux

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

$\textcolor{colorprop}{\binom{n}{0} = \binom{n}{n} = 1}$ (une façon de ne rien choisir ou tout choisir) ;
$\textcolor{colorprop}{\binom{n}{1} = \binom{n}{n-1} = n}$ ($n$ singletons ou $n$ parties auxquelles il manque un élément) ;
pour $n \ge 2$, $\textcolor{colorprop}{\binom{n}{2} = \binom{n}{n-2} = \dfrac{n(n-1)}{2}}$.

Exemple

$\binom{5}{2} = \dfrac{5!}{2!\,3!} = \dfrac{5 \cdot 4}{2} = 10$ --- il y a dix façons de choisir une paire dans un ensemble à $5$ éléments.

Proposition — Symétrie$\virgule$ Pascal$\virgule$ absorption

Pour $n \in \mathbb{N}$ et $k \in \mathbb{Z}$ avec $0 \le k \le n$ :

Symétrie : $\textcolor{colorprop}{\binom{n}{k} = \binom{n}{n-k}}$.
Identité de Pascal : pour $1 \le k \le n-1$, $\textcolor{colorprop}{\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}$.
Absorption : pour $1 \le k \le n$, $\textcolor{colorprop}{k\binom{n}{k} = n\binom{n-1}{k-1}}$.

Preuve

Le c\oe ur des trois démonstrations est le même : mettre les fractions au même dénominateur à l'aide des identités factorielles $k \cdot (k-1)! = k!$ et $(n-k) \cdot (n-k-1)! = (n-k)!$.

Symétrie. On applique la formule factorielle et on simplifie le second facteur : $$ \begin{aligned} \binom{n}{n-k} &= \frac{n!}{(n-k)! \, \big(n - (n-k)\big)!} && \text{(formule factorielle à l'indice } n-k \text{)} \\ &= \frac{n!}{(n-k)! \, k!} && \text{(simplification : } n - (n-k) = k\text{)} \\ &= \frac{n!}{k! \, (n-k)!} && \text{(échange des facteurs au dénominateur)} \\ &= \binom{n}{k} && \text{(formule factorielle à l'indice } k\text{).} \end{aligned} $$
Pascal. Le dénominateur commun visé est $k!\,(n-k)!$. On multiplie chaque fraction par $1$ de manière à étendre les factorielles : $$ \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 (formule factorielle)} \\ &= \frac{k \cdot (n-1)!}{k \cdot (k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (multiplier la 1\textsuperscript{re} fraction par } 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{ au 1\textsuperscript{er} dénom.)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} \\ &\quad + \frac{(n-k) \cdot (n-1)!}{k!\,(n-k) \cdot (n-k-1)!} && \text{\doublecolumnscriptsize (multiplier la 2\textsuperscript{e} fraction par } (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{ au 2\textsuperscript{e} dénom.)} \\ &= \frac{k \cdot (n-1)! + (n-k) \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (dénominateur commun atteint)} \\ &= \frac{(n-1)! \, \big[k + (n-k)\big]}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (factoriser } (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. Même idée, plus simple : faire entrer ou sortir un facteur dans une factorielle. $$ \begin{aligned} k \binom{n}{k} &= \frac{k \cdot n!}{k! \, (n-k)!} && \text{(formule factorielle)} \\ &= \frac{k \cdot n!}{k \cdot (k-1)! \, (n-k)!} && \text{(}k! = k \cdot (k-1)!\text{)} \\ &= \frac{n!}{(k-1)! \, (n-k)!} && \text{(simplifier le facteur } 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} $$

Compétences à pratiquer

Démontrer des identités par calcul

III.2 Triangle de Pascal

L'identité de Pascal donne une procédure récursive pour calculer $\binom{n}{k}$ : chaque entrée est la somme des deux au-dessus. Le tableau obtenu est le triangle de Pascal, monument de combinatoire élémentaire.

Exemple

Les sept premières lignes du triangle de Pascal. La ligne $n$ contient $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$. Chaque entrée est la somme des deux entrées diagonales au-dessus (identité de Pascal).

Méthode — Construire le triangle de Pascal ligne par ligne

Pour calculer $\binom{n}{k}$ pour de petits $n$, utiliser la récurrence de Pascal :

commencer avec la ligne $0$ : $\binom{0}{0} = 1$ ;
chaque nouvelle ligne commence et finit par $1$ ;
les entrées intérieures sont la somme des deux entrées diagonalement au-dessus.

Pour de plus grands $n$ ou des entrées précises, préférer la formule factorielle.

Compétences à pratiquer

Construire et exploiter le triangle

III.3 Formule du binôme

La formule du binôme exprime $(a+b)^n$ comme combinaison linéaire explicite des monômes $a^{n-k}b^k$ avec coefficients exactement les coefficients binomiaux. C'est l'identité-clef qui relie combinatoire, algèbre et analyse : elle sous-tend les développements de Taylor et de nombreux arguments de dénombrement.

Theorem — Formule du binôme (Newton)

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

Preuve

Récurrence sur $n$.

Initialisation. Pour $n = 0$ : $(a+b)^0 = 1$ et $\sum_{k=0}^{0} \binom{0}{k} a^{0-k} b^k = \binom{0}{0} = 1$. $\checkmark$
Hérédité. On suppose la formule au rang $n$. On calcule $(a+b)^{n+1}$ étape par étape : $$ \begin{aligned} (a+b)^{n+1} &= (a+b)\,(a+b)^n && \text{\doublecolumnscriptsize (isoler un facteur)} \\ &= (a+b) \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k && \text{\doublecolumnscriptsize (d'après l'hypothèse de récurrence)} \\ &= 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 (distribuer)} \\ &= \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 (faire entrer dans les sommes)} \\ &= \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 (changement d'indice } k \to k+1\text{ dans la 2e somme)} \\ &= 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 (isoler } k=0 \text{ dans la 1re somme)} \\ &= 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 (isoler } k=n+1 \text{ dans la 2e somme)} \\ &= 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 (combiner les deux sommes sur } 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 (identité de Pascal)} \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (réabsorber }a^{n+1}\text{ et }b^{n+1}\text{).} \end{aligned} $$ L'hérédité est établie. Le résultat suit pour tout $n \in \mathbb{N}$.

Exemple

Développer $(a+b)^4$.

Correction

Lire la ligne $n=4$ du triangle de Pascal : $1, 4, 6, 4, 1$. D'où $$ (a+b)^4 = a^4 + 4 a^3 b + 6 a^2 b^2 + 4 a b^3 + b^4. $$

Exemple

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

Correction

On applique la formule du binôme avec $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}. $$ Avec $a = 1, b = -1$, pour $n \ge 1$ : $$ 0 = (1-1)^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k. $$

Méthode — Appliquer la formule du binôme

Pour un développement $(a+b)^n$ :

lire les coefficients binomiaux dans le triangle de Pascal (petits $n$) ou les calculer par la formule factorielle ;
écrire chaque terme $\binom{n}{k} a^{n-k} b^k$ pour $k = 0, \dots, n$.

Pour une identité de somme faisant intervenir $\binom{n}{k}$, essayer d'évaluer $(a+b)^n$ en des valeurs astucieuses : $a = b = 1$ donne $\sum \binom{n}{k} = 2^n$ ; $a = 1, b = -1$ donne la somme alternée.

Compétences à pratiquer

Appliquer et inverser la formule de Newton

IV Arithmétique dans $\mathbb{Z}$

On clôt l'atelier par les bases de l'arithmétique sur les entiers. Les ensembles $\mathbb{N}$ et $\mathbb{Z}$ sont supposés connus ; leur construction est hors de notre champ. On développe quatre outils, chacun élémentaire et chacun utilisé constamment par la suite. D'abord la relation de divisibilité $b \mid a$ et la division euclidienne $a = b q + r$, l'outil algorithmique qui convertit « $b$ divise-t-il $a$ ? » en « le reste est-il nul ? ». Puis le plus grand commun diviseur $a \wedge b$, calculé par les divisions euclidiennes itérées de l'algorithme d'Euclide, et le plus petit commun multiple $a \vee b$, relié au PGCD par $(a \wedge b)(a \vee b) = |ab|$. Enfin les nombres premiers : leur définition, l'infinitude de $\mathbb{P}$ (Euclide), le crible d'Ératosthène, et la décomposition de tout $n \geq 2$ en produit de nombres premiers --- les briques de $\mathbb{N}^*$ pour la multiplication.
Convention permanente. Tout au long de cette section, un diviseur est toujours un entier non nul : chaque fois qu'on écrit « $d \mid a$ », on suppose tacitement $d \in \mathbb{Z}^*$. On utilise $\mathbb{N} = \{0, 1, 2, \dots\}$ et $\mathbb{N}^* = \mathbb{N} \setminus \{0\}$. Les notations $a \wedge b$ (PGCD) et $a \vee b$ (PPCM) sont standard.

IV.1 Divisibilité et division euclidienne

Deux définitions, un théorème. La définition de la divisibilité est le point d'entrée ; la division euclidienne est l'outil algorithmique qui convertit « $b \mid a$ ? » en « le reste est-il nul ? ». Le lycée couvre déjà les deux de façon informelle ; on les énonce formellement et on étend la division euclidienne aux dividendes négatifs.

Définition — Divisibilité

Soient $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$. On dit que $b$ divise $a$, et on note $b \mid a$, s'il existe $k \in \mathbb{Z}$ tel que $a = b k$. On dit aussi que $a$ est un multiple de $b$, ou que $b$ est un diviseur de $a$.
Notations :

$a \mathbb{Z} = \{a k : k \in \mathbb{Z}\}$ est l'ensemble des multiples de $a$ ;
$\operatorname{div}(a) = \{d \in \mathbb{Z}^* : d \mid a\}$ est l'ensemble des diviseurs de $a$.

Exemple

$\operatorname{div}(12) = \{\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12\}$. $\operatorname{div}(0) = \mathbb{Z}^*$ car tout entier non nul $d$ vérifie $0 = d \cdot 0$. L'ensemble des multiples de $5$ est $5 \mathbb{Z} = \{\dots, -10, -5, 0, 5, 10, \dots\}$.

Proposition — Propriétés de la divisibilité

Soient $a, b, c, d \in \mathbb{Z}$ et $u, v \in \mathbb{Z}$, avec la convention permanente qu'un diviseur est non nul (le diviseur figurant dans chaque énoncé ci-dessous appartient à $\mathbb{Z}^*$).

Réflexivité et transitivité. Pour tout $a \in \mathbb{Z}^*$, $a \mid a$. Si $a \mid b$ et $b \mid c$ (avec $a, b \in \mathbb{Z}^*$), alors $a \mid c$.
Entiers associés. Pour $a, b \in \mathbb{Z}^*$, $a \mid b \text{ et } b \mid a \iff |a| = |b|$. En particulier, restreint à $\mathbb{N}^*$ ceci redonne l'antisymétrie de $\mid$ : $a \mid b$ et $b \mid a \iff a = b$.
Combinaisons linéaires. Si $d \mid a$ et $d \mid b$, alors $d \mid (a u + b v)$ pour tout $u, v \in \mathbb{Z}$.
Produit. Si $a \mid b$ et $c \mid d$ (avec $a, c \in \mathbb{Z}^*$), alors $a c \mid b d$. En particulier $a^k \mid b^k$ pour tout $k \in \mathbb{N}^*$ lorsque $a \mid b$.

Preuve

Réflexivité / transitivité. $a = a \cdot 1$ donne $a \mid a$. Si $b = a k$ et $c = b k'$, alors $c = a (k k')$ avec $k k' \in \mathbb{Z}$, donc $a \mid c$.
Entiers associés. Si $a \mid b$ et $b \mid a$, écrire $b = a k$ et $a = b k'$. Alors $a = a (k k')$, donc $k k' = 1$ (car $a \neq 0$). Avec $k, k' \in \mathbb{Z}$, cela force $k = k' = \pm 1$, donc $|a| = |b|$. Réciproquement si $|a| = |b|$ alors $a = \pm b$, donc chacun divise l'autre.
Combinaisons linéaires. De $a = d k$ et $b = d k'$, $a u + b v = d (k u + k' v) \in d \mathbb{Z}$.
Produit. De $b = a k$ et $d = c k'$, $b d = (a c)(k k')$, donc $a c \mid b d$.

Méthode — Décider si $b \mid a$

Deux tests équivalents pour $b \in \mathbb{Z}^*$, $a \in \mathbb{Z}$ :

Test direct du quotient. Calculer $a / b$ dans $\mathbb{Q}$ ; vérifier si le résultat est entier.
Test du reste (préféré pour $a, b$ grands). Calculer la division euclidienne $a = b q + r$ avec $0 \leq r < |b|$ ; alors $b \mid a \iff r = 0$ (théorème suivant).

Theorem — Division euclidienne

Pour tout $a \in \mathbb{Z}$ et tout $b \in \mathbb{Z}^*$, il existe un unique couple $(q, r) \in \mathbb{Z} \times \mathbb{N}$ tel que $$ \textcolor{colorprop}{a = b q + r \quad \text{et} \quad 0 \leq r < |b|.} $$ L'entier $a$ est le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste de la division euclidienne de $a$ par $b$. Lorsque $b > 0$, le quotient est $q = \lfloor a / b \rfloor$, où $\lfloor \cdot \rfloor$ désigne la partie entière (le plus grand entier inférieur ou égal à un réel, vue dans le matériel sur les propriétés de $\mathbb{R}$).

Preuve

On traite d'abord le cas $b > 0$, puis on ramène le cas général à celui-ci.
Existence ($b > 0$). Posons $R = \{a - b k : k \in \mathbb{Z}\} \cap \mathbb{N}$. L'ensemble $R$ est non vide : si $a \geq 0$, alors $a = a - b \cdot 0 \in R$ ; si $a < 0$, alors $k = a$ donne $a - b a = a (1 - b) \geq 0$ car $1 - b \leq 0$ et $a < 0$, donc $a - b a \in R$. Comme partie non vide de $\mathbb{N}$, $R$ admet un plus petit élément ; notons-le $r$, et écrivons $r = a - b q$ pour un certain $q \in \mathbb{Z}$, soit $a = b q + r$ avec $r \geq 0$. Il reste à montrer $r < b$. Supposons par l'absurde $r \geq b$. Alors $r - b \in \mathbb{N}$ et $r - b = a - b (q + 1) \in R$, ce qui contredit la minimalité de $r$. Donc $r < b = |b|$.
Unicité ($b > 0$). Supposons $a = b q + r = b q' + r'$ avec $0 \leq r, r' < b$. Alors $b (q - q') = r' - r$, donc $|b (q - q')| = |r' - r| < b$, ce qui force $|q - q'| < 1$. Comme $q - q' \in \mathbb{Z}$, $q = q'$, et donc $r = r'$.
Cas général $b \in \mathbb{Z}^*$. On applique le cas déjà démontré au diviseur positif $|b|$ : il existe un unique $(q_0, r) \in \mathbb{Z} \times \mathbb{N}$ avec $a = |b| q_0 + r$ et $0 \leq r < |b|$. Si $b > 0$, on prend $(q, r) = (q_0, r)$ ; si $b < 0$, alors $|b| = -b$ et $a = b(-q_0) + r$, donc on prend $(q, r) = (-q_0, r)$. Dans les deux cas $a = b q + r$ avec $0 \leq r < |b|$, et l'unicité de $r$ (donc de $q$) découle de l'unicité pour $|b|$.
Formule pour $q$ lorsque $b > 0$. De $a / b = q + r / b$ avec $0 \leq r/b < 1$, on obtient $q = \lfloor a / b \rfloor$.

Exemple

Pour $a = 23$, $b = 5$ : $23 = 5 \cdot 4 + 3$, donc $q = 4$ et $r = 3$. En effet $\lfloor 23 / 5 \rfloor = 4$.

Exemple — Dividende négatif --- piège classique

Pour $a = -23$, $b = 5$ : non $-23 = 5 \cdot (-4) - 3$, car le reste vaudrait alors $-3 < 0$. La division euclidienne correcte est $$ \textcolor{colorprop}{-23 = 5 \cdot (-5) + 2,} $$ donc $q = -5$ et $r = 2$. Vérification : $\lfloor -23 / 5 \rfloor = -5$ (pas $-4$). Le reste est toujours dans $\{0, 1, \dots, |b| - 1\}$.

Compétences à pratiquer

Divisibilité et division euclidienne

IV.2 PGCD$\virgule$ algorithme d'Euclide et PPCM

Le plus grand commun diviseur (PGCD) de deux entiers est le plus grand entier qui les divise tous les deux. On le définit ici comme le plus grand élément, pour l'ordre naturel $\leq$ sur $\mathbb{N}^*$, de l'ensemble des diviseurs communs ; il se calcule effectivement par l'algorithme d'Euclide, une suite itérée de divisions euclidiennes. Le plus petit commun multiple (PPCM) est la notion duale, et la relation $(a \wedge b)(a \vee b) = |ab|$ relie les deux.

Définition — Plus grand commun diviseur (PGCD)

Soient $a, b \in \mathbb{Z}$ non tous deux nuls. Le plus grand commun diviseur de $a$ et $b$, noté $a \wedge b$, est le plus grand élément de $\{d \in \mathbb{N}^* : d \mid a \text{ et } d \mid b\}$ pour l'ordre naturel $\leq$ sur $\mathbb{N}^*$. Par convention, $0 \wedge 0 = 0$.
L'ensemble $\{d \in \mathbb{N}^* : d \mid a \text{ et } d \mid b\}$ est non vide (il contient $1$) et fini (tout diviseur commun est majoré par $\max(|a|, |b|)$), donc son maximum existe.

Exemple

$12 \wedge 18 = 6$ : les diviseurs de $12$ dans $\mathbb{N}^*$ sont $\{1, 2, 3, 4, 6, 12\}$, les diviseurs de $18$ sont $\{1, 2, 3, 6, 9, 18\}$, les diviseurs communs sont $\{1, 2, 3, 6\}$, le maximum est $6$. De plus $a \wedge 1 = 1$ pour tout $a \in \mathbb{Z}$, et $a \wedge 0 = |a|$ pour tout $a \in \mathbb{Z}^*$.

Proposition — Idée fondamentale

Pour tout $a \in \mathbb{Z}$ et tout $b \in \mathbb{N}^*$, si $a = b q + r$ est la division euclidienne de $a$ par $b$, alors $$ \textcolor{colorprop}{a \wedge b = b \wedge r.} $$

Preuve

On montre que l'ensemble des diviseurs communs à $a$ et $b$ est égal à l'ensemble des diviseurs communs à $b$ et $r$ ; le PGCD, défini comme le maximum de cet ensemble, est donc le même.

$(\subset)$ Si $d \mid a$ et $d \mid b$, alors par combinaison linéaire $d \mid (a - b q) = r$. Donc $d$ divise $b$ et $r$.
$(\supset)$ Si $d \mid b$ et $d \mid r$, alors $d \mid (b q + r) = a$. Donc $d$ divise $a$ et $b$.

Les deux ensembles coïncident ; leurs maxima aussi : $a \wedge b = b \wedge r$.

Theorem — Existence du PGCD par l'algorithme d'Euclide

Soient $a, b \in \mathbb{N}$ avec $0 < b \leq a$. Définir une suite de restes par $r_0 = a$, $r_1 = b$, et $r_{k+2} = $ reste de la division euclidienne de $r_k$ par $r_{k+1}$ tant que $r_{k+1} > 0$. La suite s'arrête : il existe $N \geq 1$ tel que $r_N = 0$, et le PGCD est le dernier reste non nul : $$ \textcolor{colorprop}{a \wedge b = r_{N - 1}.} $$

Preuve

Terminaison. Tant que $r_{k+1} > 0$, la construction donne $0 \leq r_{k+2} < r_{k+1}$, donc les restes strictement positifs $r_1, r_2, \dots$ forment une suite strictement décroissante dans $\mathbb{N}^*$, qui est nécessairement finie ; il existe $N$ tel que $r_N = 0$.
Correction. Par l'« idée fondamentale » appliquée à chaque étape, $r_k \wedge r_{k+1} = r_{k+1} \wedge r_{k+2}$. En enchaînant, $$ 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}. $$

Méthode — Calculer $a \wedge b$ par l'algorithme d'Euclide

Supposer $0 < b \leq a$. Tabuler les divisions euclidiennes successives $r_k = r_{k+1} \, q_{k+1} + r_{k+2}$ avec $0 \leq r_{k+2} < r_{k+1}$, en partant de $a = b \, q_1 + r_2$. S'arrêter dès qu'un reste est nul ; le dernier reste non nul est $a \wedge b$. Pour $a, b \in \mathbb{Z}$ généraux, les remplacer par $|a|, |b|$.

Exemple

Calculer $1542 \wedge 58$.

Correction

On applique l'algorithme d'Euclide : $$ \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} $$ Le dernier reste non nul est $2$, donc $1542 \wedge 58 = 2$.

Définition — Plus petit commun multiple (PPCM)

Soient $a, b \in \mathbb{N}^*$. Le plus petit commun multiple de $a$ et $b$, noté $a \vee b$, est le plus petit élément de $\{m \in \mathbb{N}^* : a \mid m \text{ et } b \mid m\}$ pour l'ordre naturel $\leq$ sur $\mathbb{N}^*$. L'ensemble est non vide (il contient $a b$). Par convention $0 \vee b := 0$, et pour $a, b \in \mathbb{Z}$, $a \vee b := |a| \vee |b|$.

Proposition — Les multiples communs sont les multiples du PPCM

Pour tout $a, b \in \mathbb{N}^*$, $$ \textcolor{colorprop}{a \mathbb{Z} \cap b \mathbb{Z} = (a \vee b) \mathbb{Z},} $$ de manière équivalente : $a \mid n$ et $b \mid n \iff (a \vee b) \mid n$. Donc $a \vee b$ est aussi le plus petit multiple commun pour l'ordre de divisibilité $\mid$.

Preuve

Posons $m = a \vee b$.

$(\supset)$ $m$ est un multiple commun de $a$ et $b$, donc tout multiple de $m$ est un multiple commun.
$(\subset)$ Soit $n$ un multiple commun. La division euclidienne donne $n = m q + r$ avec $0 \leq r < m$. Alors $r = n - m q$ 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 = 0$. Donc $n = m q \in m \mathbb{Z}$.

Proposition — Relation PGCD-PPCM

Pour tout $a, b \in \mathbb{Z}$, $$ \textcolor{colorprop}{(a \wedge b)(a \vee b) = |a b|.} $$ (La démonstration la plus propre lit les exposants dans la décomposition en facteurs premiers de $a$ et $b$ via l'identité $\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$ ; on admet la formule.)

Exemple

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

Compétences à pratiquer

PGCD$\virgule$ algorithme d'Euclide et PPCM

IV.3 Nombres premiers

Les nombres premiers sont les atomes multiplicatifs de $\mathbb{N}^*$ : tout $n \geq 2$ est un produit de nombres premiers. On donne la définition, on démontre le théorème classique d'infinitude d'Euclide, on présente le crible d'Ératosthène, et on énonce l'existence et l'unicité de la décomposition en facteurs premiers, dont la démonstration dépasse notre champ ici. La décomposition donne ensuite une façon nette de lire le PGCD et le PPCM.

Définition — Nombre premier$\virgule$ nombre composé

Un entier naturel $p \geq 2$ est dit premier si ses seuls diviseurs dans $\mathbb{N}^*$ sont $1$ et $p$ (de manière équivalente, $\operatorname{div}(p) = \{\pm 1, \pm p\}$). On note $\mathbb{P}$ l'ensemble des nombres premiers. Un entier naturel $n \geq 2$ qui n'est pas premier est dit composé : il admet un diviseur $d$ avec $1 < d < n$. L'entier $1$ n'est, par convention, ni premier ni composé.

Exemple

Les premiers nombres premiers sont $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \dots$. L'entier $4 = 2 \cdot 2$ est composé. (L'exclusion de $1$ des nombres premiers est nécessaire pour garder l'unicité de la décomposition en facteurs premiers : sinon $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$, etc.)

Proposition — Existence d'un diviseur premier

Tout entier $n \geq 2$ admet au moins un diviseur premier.

Preuve

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$. Si $p_0$ était composé, il aurait un diviseur $d$ avec $1 < d < p_0$ ; alors $d \mid n$ (transitivité), donc $d \in D$ avec $d < p_0$ --- ce qui contredit la minimalité. Donc $p_0$ est premier, et $p_0 \mid n$.

Theorem — Infinitude des nombres premiers

L'ensemble $\mathbb{P}$ des nombres premiers est infini.

Preuve

Démonstration classique d'Euclide, par l'absurde. Supposons $\mathbb{P}$ fini, disons $\mathbb{P} = \{p_1, \dots, p_r\}$. Considérons $N = p_1 \, p_2 \cdots p_r + 1$. Comme $N \geq 2$, $N$ admet un diviseur premier $p_k$. 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.

Méthode — Crible d'Ératosthène

Pour lister tous les nombres premiers $\leq N$ (pour un $N \geq 2$ donné) :
Étape 1. Écrire les entiers $2, 3, 4, \dots, N$ dans un tableau.
Étape 2. Prendre le plus petit entier non rayé $p$. Alors $p$ est premier ; rayer tous ses multiples propres $2p, 3p, \dots \leq N$.
Étape 3. Répéter jusqu'à $p > \sqrt{N}$. Tout entier $\leq N$ non rayé est alors premier.
Pourquoi $\sqrt{N}$ suffit. Si $n \leq N$ est composé, on écrit $n = a b$ avec $a \leq b$ ; alors $a \leq \sqrt{n} \leq \sqrt{N}$, donc $n$ est rayé par un premier $\leq \sqrt{N}$.

Exemple — Premiers $\leq 30$ par le crible

$\sqrt{30} < 6$, donc les nombres premiers servant à rayer sont $2, 3, 5$. Après avoir rayé les multiples de $2$, puis de $3$, puis de $5$, les survivants sont $$ \textcolor{colorprop}{\mathbb{P} \cap [\![ 2, 30 ]\!] = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}.} $$ Total : $10$ nombres premiers $\leq 30$.

Theorem — Existence et unicité de la décomposition en facteurs premiers

Tout entier $n \geq 2$ s'écrit comme produit de nombres premiers, $$ \textcolor{colorprop}{n = p_1^{\alpha_1} \, p_2^{\alpha_2} \cdots p_s^{\alpha_s},} $$ avec $p_1 < p_2 < \cdots < p_s$ premiers et $\alpha_1, \dots, \alpha_s \in \mathbb{N}^*$, et cette écriture est unique (les nombres premiers et leurs exposants sont déterminés par $n$). On admet ce théorème ; sa démonstration dépasse notre champ.

Exemple

$360 = 2^3 \cdot 3^2 \cdot 5$ et $84 = 2^2 \cdot 3 \cdot 7$. Ces deux écritures sont les seules décompositions en facteurs premiers de $360$ et $84$.

Méthode — Calculer le PGCD et le PPCM par la décomposition

Écrire $a$ et $b$ en décomposition sur la même liste de premiers $p_1, \dots, p_s$ (avec l'exposant $0$ là où un premier est absent) : $a = \prod_i p_i^{\alpha_i}$, $b = \prod_i p_i^{\beta_i}$. Alors $$ \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)}.} $$ Exemple : $360 = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^0$ et $84 = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^1$ donnent $360 \wedge 84 = 2^2 \cdot 3^1 = 12$ et $360 \vee 84 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$, avec $12 \cdot 2520 = 30240 = 360 \cdot 84$.

Compétences à pratiquer

Nombres premiers