Montrons d’abord que, si a et b sont des entiers, $a + b$ est un entier. Procédons par récurrence sur b. La proposition est vraie pour $b = 0$, car $a + 0 = a$. Si $a + b$ est entier, il en est de même de $(a + b) + 1$ (III, p. 31, prop. 1); mais $(a + b) + 1 = a + (b + 1)$ (III, p. 27, corollaire), donc $a + (b + 1)$ est entier, et par suite $a + b$ est un entier pour tout entier b.

Montrons maintenant, par récurrence sur $n = \mathrm{Card}\,(I)$, que $\sum_{i \in I} a_i$ est un entier. C’est évident si $n = 0$, car alors $I = \varnothing$ et $\sum_{i \in I} a_i = 0$. Si $\mathrm{Card}\,(I) = n + 1$, on a $I = J \cup \{k\}$, avec $\mathrm{Card}\,(J) = n$ et $k \notin J$; alors $\sum_{i \in I} a_i = a_k + \sum_{i \in J} a_i$ (III, p. 26, prop. 5). L’hypothèse de récurrence est que $\sum_{i \in J} a_i$ est un entier; il en est donc de même de $a_k + \sum_{i \in J} a_i$, d’après ce qui vient d’être démontré. Cela prouve que $\sum_{i \in I} a_i$ est entier pour tout $n$.

Comme le produit $ab$ de deux entiers a et b est la somme d’une famille finie d’entiers égaux à a (III, p. 27, cor. 2), $ab$ est un entier. Montrons, par récurrence sur $n = \mathrm{Card}\,(I)$, que $\prod_{i \in I} a_i$ est un entier. C’est vrai pour $n = 0$, car alors $\prod_{i \in I} a_i = 1$.

D'autre part, si Card (I) = n + 1, on a (avec les mêmes notations que ci-dessus),

donc l'hypothèse de récurrence entraîne que $\prod_{i \in I} a_i$ est un entier. Par suite, $\prod_{i \in I} a_i$ est un entier pour tout $n$.

En effet, l'ensemble somme S de la famille $(X_i)$ est fini. Comme il existe une application de S sur E (II, p. 30), l'ensemble E est fini (III, p. 32, cor. 3).

En effet, $a^b$ est le produit d'une famille finie d'entiers égaux à $a$ (III, p. 28, prop. 10).

En effet, son cardinal est $2^{\text{Card}(E)}$ (III, p. 29, prop. 12).

En effet, si $a < b$, on sait qu'il existe un cardinal $c \leq b$ (qui est donc un entier (III, p. 31, prop. 2)) tel que $b = a + c$ (III, p. 29, prop. 13); si $a \neq b$, on a nécessairement $c \neq 0$. Inversement, si $b = a + c$ et $c \neq 0$, on a $c \geq 1$, donc $a < a + 1 \leq a + c = b$.

Soit $j$ un indice tel que $a_j < b_j$, et posons $J = I - \{j\}$. On a $b_j = a_j + c_j$ avec $c_j > 0$ (prop. 2), donc (III, p. 30, prop. 14)

et comme $c_j > 0$, on en déduit la première assertion (prop. 2). De même or, comme $c_j$ et tous les $b_i$ sont $\neq 0$, le produit $c_j \prod_{i \in J} b_i$ est $\neq 0$ (III, p. 28, prop. 7); la seconde assertion en résulte, compte tenu de la prop. 2.

Il suffit d’exprimer $a^b$ et $a'^b$ comme produits de familles finies d’entiers (III, p. 28, prop. 10) et d’appliquer la prop. 3, en remarquant que la relation $a < a'$ implique $a' > 0$.

En effet, il existe un entier $c > 0$ tel que $b' = b + c$ (prop. 2); comme $c \geqslant 1$, on a $a^c \geqslant a > 1$; d’où $a^{b'} = a^b a^c > a^b$.

En effet, si $b \neq b'$, on a par exemple $b < b'$, et la prop. 3 montre que $a + b < a + b'$ et $ab < ab'$ (si $a > 0$).

L’existence de $c$ résulte de la prop. 13 de III, p. 29, et son unicité du cor. 3 ci-dessus.

L’entier $c$ tel que $b = a + c$ (pour $a \leqslant b$) s’appelle la différence des entiers $b$ et $a$, et se note $b - a$. On vérifie aussitôt que, si $a, b, a', b'$ sont des entiers tels que $a \leqslant b$ et $a' \leqslant b'$, on a

Il est clair que les relations $0 \leqslant x \leqslant b$ entraînent

l’application $x \mapsto a + x$ est strictement croissante (donc injective) en raison de la prop. 3 de III, p. 36. Enfin, les relations $a \leqslant y \leqslant a + b$ entraînent $y = a + x$ avec $x \geqslant 0$ et $a + x \leqslant a + b$, d’où $x \leqslant b$ (III, p. 36, prop. 3), ce qui achève la démonstration.

En vertu de la prop. 4, on peut se limiter au cas où $a = 0$. Démontrons la proposition par récurrence sur $b$. Elle est évidente pour $b = 0$. D’autre part, la relation $0 \leq x \leq b + 1$ équivaut à « $0 \leq x < b + 1$ ou $x = b + 1$ » et la relation $0 \leq x < b + 1$ équivaut à $0 \leq x \leq b$ (III, p. 31, prop. 2); autrement dit, l’intervalle $[0, b + 1]$ est réunion de $[0, b]$ et de $\{b + 1\}$, et ces deux ensembles ne se rencontrent pas; en vertu de l’hypothèse de récurrence, le nombre d’éléments de $[0, b + 1]$ est égal à $(b + 1) + 1$, ce qui établit la proposition.

Comme $E$ et $[1, n]$ sont bien ordonnés (III, p. 34, cor. 1), et ont même nombre d’éléments (prop. 5), la proposition résulte de III, p. 21, th. 3 et p. 31, cor. 2.

(1)

(2) (3)

pour tout $x \in E$.

Les conditions imposées sont équivalentes à $bq \leq a < b(q + 1)$ et $r = a - bq$ (III, p. 36, prop. 2). Tout revient donc à trouver q tel que $bq \leq a < b(q + 1)$; autrement dit, q doit être le plus petit entier tel que $a < b(q + 1)$, ce qui montre que q et $r = a - bq$ sont déterminés de façon unique. Pour montrer leur existence, remarquons qu’il existe des entiers p tels que $a < bp$, ne serait-ce que $a + 1$, puisque $b > 0$. Soit m le plus petit de ces entiers; on a $m \neq 0$, et on peut donc écrire $m = q + 1$ avec $q \leq m$ (III, p. 31, prop. 2); il en résulte que $bq \leq a < b(q + 1)$.

Nous démontrerons la proposition par récurrence sur $k$; elle découle aussitôt des définitions pour $k = 1$. Pour tout $r = (r_0, \ldots, r_{k-1}, r_k) \in E_{k+1}$, posons $\varphi(r) = (r_0, \ldots, r_{k-1}) \in E_k$; l’application $r \mapsto (\varphi(r), r_k)$ est un isomorphisme de $E_{k+1}$ sur le produit lexicographique de $E_k$ et de $J = (0, b-1)$, comme il résulte des définitions. On peut écrire $f_{k+1}(r) = b \cdot f_k(\varphi(r)) + r_k$; montrons que la relation $r < r'$ dans $E_{k+1}$ entraîne $f_{k+1}(r) < f_{k+1}(r')$. En effet, on a alors, ou bien $\varphi(r) < \varphi(r')$, ou bien $\varphi(r) = \varphi(r')$ et $r_k < r'_k$. Dans le premier cas, l’hypothèse de récurrence entraîne que $f_k(\varphi(r)) < f_k(\varphi(r'))$, donc (III, p. 31, prop. 2) $f_k(\varphi(r')) \geq f_k(\varphi(r)) + 1$; par suite $f_{k+1}(r') \geq b \cdot f_k(\varphi(r)) + b > f_{k+1}(r)$, puisque $r_k \leq b-1$ (III, p. 36, prop. 3). Si au contraire $\varphi(r) = \varphi(r')$ et $r_k < r'_k$, il est immédiat que $f_{k+1}(r) < f_{k+1}(r')$. D’autre part, l’hypothèse de récurrence montre que $f_k(\varphi(r)) \leq b^k - 1$, d’où $f_{k+1}(r) \leq b(b^k - 1) + b - 1 = b^{k+1} - 1$. On en conclut que $f_{k+1}$ est un isomorphisme de $E_{k+1}$ sur une partie de l’intervalle $(0, b^{k+1} - 1)$; mais comme cet intervalle et $E_{k+1}$ ont le même nombre d’éléments $b^{k+1}$ (III, p. 38, prop. 5), $f_{k+1}$ est une bijection (III, p. 32, cor. 4), ce qui achève la démonstration.

Remarquons maintenant que, pour tout entier $a$, on a $a < b^a$: il suffit de raisonner par récurrence sur $a$, la proposition étant évidente pour $a = 0$, et l’hypothèse $a < b^a$ entraînant $a + 1 \leq b^a < b \cdot b^a = b^{a+1}$ (III, p. 36, prop. 3 et p. 31, prop. 2). Il existe donc un plus petit entier $k$ tel que $a < b^k$, et la prop. 8 prouve alors qu’il existe une suite finie et une seule $(r_h)_{0 \leq h \leq k-1}$ telle que $0 \leq r_h \leq b-1$ pour $0 \leq h \leq k-1$ et $a = \sum_{h=0}^{k-1} r_h b^{k-h-1}$; en outre, on a nécessairement $r_0 > 0$, sans quoi on déduirait de la prop. 8 que $a < b^{k-1}$. On dit que $\sum_{h=0}^{k-1} r_h b^{k-h-1}$ est le développement de base $b$ du nombre entier $a$.

\* Dans toutes les parties des mathématiques où on n’a pas en vue le calcul numérique, la prop. 8 sera surtout utile lorsqu’elle sera appliquée à un entier $b$ premier.\*

Lorsque l’entier $b$ est assez petit pour que cela soit praticable, on peut représenter chaque entier $< b$ par un symbole distinctif appelé chiffre, les chiffres représentant 0 et 1 étant en général 0 et 1. Soient $a$ un entier et $\sum_{h=0}^{k-1} r_h b^{k-h-1}$ son développement de base $b$; si l’entier $k$ figurant dans ce développement est assez petit pour que ce soit praticable, on convient d’associer à l’entier $a$ la succession de symboles obtenue en écrivant de gauche à droite $r_0 r_1 \ldots r_{k-2} r_{k-1}$ et en remplaçant chaque entier $r_i$ par le chiffre qui le représente; le symbole ainsi obtenu est appelé le symbole numérique associé à $a$. On remplace alors souvent $a$ par son symbole numérique dans les termes ou relations où il figure.

Par exemple, si $C, Q, F, D$ sont des chiffres, les symboles numériques $CQ, CQF, CQFD$ sont respectivement associés à $Cb + Q, Cb^2 + Qb + F, Cb^3 + Qb^2 + Fb + D$.

Il résulte de la prop. 8 que le symbole numérique associé à un entier $a$ est unique, et que, si $a < b^k$, il contient $k$ chiffres au plus. On notera que le symbole numérique associé à l’entier $b^k$ est formé du chiffre 1 suivi de $k$ chiffres 0.

Ce système de représentation des entiers par des symboles numériques s’appelle le système de numération de base $b$. Dans la pratique du Calcul numérique, on utilise les systèmes suivants : $a)$ le système de base 2 ou système dyadique, où les chiffres sont 0 et 1 ; $b)$ le système décimal, dans lequel les chiffres sont 0, 1, 2, 3, 4, 5 = 4 + 1, 6 = 5 + 1, 7 = 6 + 1, 8 = 7 + 1, 9 = 8 + 1, et où $b$ est l’entier 9 + 1 (dont le symbole numérique est donc 10 dans ce système).

Depuis le Moyen Age, le système décimal est traditionnellement utilisé dans le Calcul numérique, et c’est celui dont nous nous servirons lorsque nous aurons à écrire un entier explicité dans la suite de cet ouvrage. Nous renvoyons à la partie de ce Traité consacrée au Calcul numérique pour l’exposé des méthodes qui permettent d’obtenir les symboles numériques associés à la somme, la différence, le produit ou la partie entière du quotient de deux entiers donnés par leurs symboles numériques.

En effet, la famille $(f^{-1}(y))_{y \in F}$ est une partition de $E$, dont chaque élément est un ensemble de cardinal $c$; d’où la proposition (III, p. 27, cor. 2).

Procédons par récurrence sur le nombre $m \leq n$ d’éléments de $A$. La proposition est évidente pour $m = 0$. Supposons que $m + 1 \leq n$, et soient $A$ un ensemble à $m + 1$ éléments, $A'$ une partie de $A$ ayant $m$ éléments, et $\{a\} = A - A'$. Soient $F$ et $F'$ les ensembles d’applications injectives de $A$ et $A'$ respectivement dans $B$, et soit $\varphi$ l’application $f \mapsto f|_{A'}$ qui, à toute fonction $f \in F$, fait correspondre sa restriction à $A'$. Pour toute fonction $f' \in F'$, un élément $f$ de $\varphi(f')$ est déterminé de façon unique par sa valeur $f(a)$; comme $f$ est injective, on doit avoir f(a) \in \mathbf{B} - f'(A'). Il en résulte $\varphi^{-1}(f')$ a même nombre d'éléments $n - m$ que $\mathbf{B} - f'(A')$; le principe des bergers montre alors que F possède

éléments, en vertu de l'hypothèse de récurrence, et cela démontre la proposition.

En effet, ce nombre est égal au nombre des injections de l'ensemble dans lui-même (III, p. 32, cor. 4).

Soient G l'ensemble des permutations de E, P l'ensemble des recouvrements $(X_i)_{1 \leq i \leq h}$ satisfaisant aux conditions de l'énoncé. Comme $\sum_{i=1}^{h} p_i = n$, P n'est pas vide. Soit $(A_i)_{1 \leq i \leq h}$ un élément de P. Pour toute permutation $f \in G$, la famille $(f(A_i))_{1 \leq i \leq h}$ appartient encore à P; désignons-la par $\varphi(f)$. Pour tout élément $(X_i)_{1 \leq i \leq h}$ de P, cherchons le nombre d'éléments $f \in G$ tels que $\varphi(f) = (X_i)$. Pour qu'il en soit ainsi, il faut et il suffit que, pour tout indice $i$, on ait $f(A_i) = X_i$; donc l'ensemble des permutations $f$ considérées est équipotent au produit des ensembles de bijections de $A_i$ sur $X_i$ (II, p. 29, prop. 8); par conséquent l'ensemble $\varphi^{-1}((X_i)_{1 \leq i \leq h})$ a $\prod_{i=1}^{h} p_i!$ éléments (cor. de la prop. 10). Comme G a $n!$ éléments, il suffit d'appliquer le principe des bergers pour obtenir la prop. 11.

Il suffit d'appliquer la prop. 11 au cas où $h = 2$, $p_1 = p$, $p_2 = n - p$.

Le nombre des parties à $p$ éléments d'un ensemble à $n$ éléments (si $p \leq n$) se note $\binom{n}{p}$ et s'appelle (pour des raisons qui apparaîtront en A, I, § 8, n° 2) le coefficient binomial d'indices n et p. De la relation $\binom{n}{p} = \frac{n!}{p!(n-p)!}$ résulte aussitôt que l'on a

Ceci résulte aussi du fait que, si E est un ensemble à n éléments, X ↦ E − X est une bijection de l’ensemble des parties à p éléments de E sur l’ensemble des parties à n − p éléments de E.

On pose $\binom{n}{p} = 0$ pour tout couple d’entiers naturels tels que $p > n$. Avec cette convention, le nombre des parties à p éléments d’un ensemble à n éléments est $\binom{n}{p}$ pour tout entier naturel $p$.

En effet, une telle application est une injection de E dans F et, comme E et F sont bien ordonnés (III, p. 34, cor. 1), pour toute partie X à p éléments de F, il existe une application strictement croissante de E sur X et une seule (III, p. 21, th. 3).

En effet, si E est un ensemble à n éléments, le premier membre est le nombre des parties de E et on applique III, p. 29, prop. 12.

Soient E un ensemble à $n + 1$ éléments, P l’ensemble des parties à $p + 1$ éléments de E, a un élément de E, et $E' = E - \{a\}$. Notons P’ (resp. P”) l’ensemble des parties à $p + 1$ éléments de E qui contiennent a (resp. qui ne contiennent pas a). L’ensemble P” est l’ensemble des parties à $p + 1$ éléments de E’, et a donc $\binom{n}{p+1}$ éléments. L’application $X \mapsto X \cap E'$ est une bijection de P’ sur l’ensemble des parties à p éléments de E’ ; P’ a donc $\binom{n}{p}$ éléments. La proposition résulte de ce que P est réunion des ensembles disjoints P’ et P”.

On peut démontrer la prop. 13 par un calcul facile utilisant la formule $\binom{n}{p} = \frac{n!}{p!(n-p)!}$ pour $p \leq n$.

En effet, $b_n$ est le nombre des parties à 2 éléments de $\{1, n\}$; donc $b_n = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2}$. On en déduit $a_n$ en remarquant que l’ensemble des couples $(i, j)$ tels que $1 \leq i \leq j \leq n$ est la réunion de l’ensemble des couples $(i, j)$ tels que $1 \leq i < j \leq n$ et de l’ensemble des couples $(i, i)$ où $1 \leq i \leq n$; d’où $a_n = n + b_n = \frac{n(n+1)}{2}$.

Dans l’ensemble $A$ des couples d’entiers $(i, j)$ tels que $1 \leq i \leq j \leq n$, notons $A_k$ l’ensemble des couples $(i, k)$, où $1 \leq i \leq k$ (pour un entier quelconque $k \leq n$); le nombre d’éléments de $A_k$ est $k$; d’autre part $(A_k)_{1 \leq k \leq n}$ est une partition de $A$, d’où le corollaire.