Bases de numération

Le but de cette section est de définir un système d'écriture qui permette de manipuler aisément les nombres entiers, en particulier d'expliciter facilement les opérations addition et multiplication.

Pour simplifier les notations, la multiplication sur $\mathbb{N}$ sera notée $ab$ pour $a\times b$, le résultat de la multiplication de $a$ par $a$ itérée $n$ fois sera noté $a^n$ et l'inégalité stricte $a<b$ pour $a\leqslant b$ et $a\neq b$.

On décide de représenter les premiers entiers par un symbole unique appelé chiffre et on cherche un moyen d'utiliser ces symboles pour écrire tous les nombres entiers. Deux symboles ont déjà été définis : 0 pour le plus petit élément de $\mathbb{N}$ et $1$ pour $s(0)$. Traditionnellement on note $2$ pour $s(1)$, $3$ pour $s(2)$, $4$ pour $s(3)$, $5$ pour $s(4)$, $6$ pour $s(5)$, $7$ pour $s(6)$, $8$ pour $s(7)$, $9$ pour $s(8)$, $A$ pour $s(9)$, $B$ pour $s(A)$, $C$ pour $s(B)$, $D$ pour $s(C)$, $E$ pour $s(D)$, $F$ pour $s(E)$...

Etant donné un nombre entier $a>1$ appelé base, par exemple $2$, $8$, $A$, $C$ ou $G$, on peut proposer l'algorithme suivant pour dénombrer un ensemble :

on fait autant de paquets de $a$ éléments qu'il est possible, puis autant de paquets de $a$ paquets et ainsi de suite...

Remarquons qu'à la $n$-ième étape, on obtient des regroupements de $a^n$ éléments.

Par exemple pour $a=2$, considérons l'ensemble $E=\{\clubsuit\clubsuit\clubsuit\clubsuit\clubsuit\clubsuit\clubsuit\}$ et appliquons l'algorithme

$$\underbrace{\underbrace{\clubsuit\clubsuit} \underbrace{\clubsuit\clubsuit}}\underbrace{\clubsuit\clubsuit}\clubsuit$$

nous obtenons un paquet de $2$ paquets, qui regroupe donc $2^2$ éléments, plus un paquet de $2$ éléments, plus $1$ élément. Le nombre d'éléments de $E$ pourrait alors être représenté par le triple symbole $\overline{111}$, le premier 1 à gauche correspondant au nombre de paquets de paquets, le second $1$ au nombre de paquets restant et le dernier $1$ au nombre d'éléments distincts.

L'algorithme se formalise de la manière suivante : écrire un nombre entier $x$ sous la forme

$$x=x_n a^n+\dots+x_1 a+x_0, 0\leqslant x_i<a,$$

appelé développement de $x$ dans la base $a$. Si cette écriture est unique le nombre $x$ pourrait alors être représenté par le multi-symbole $\overline{x_n\dots x_1x_0}$.

Proposition 10   Si $a\in\mathbb{N}$ vérifie $1<a$, la suite de terme général $u_n=a^n$ est strictement croissante et non majorée.

Démonstration : Puisque $1<a$, la compatibilité de la relation d'ordre avec la multiplication implique $a^n<a^{n+1}$ car $a^n$ est non nul. La suite $(u_n)_{n\in\mathbb{N}}$ est donc croissante.

Nous devons prouver que pour tout $b\in\mathbb{N}$, il existe $n\in\mathbb{N}$ tel que $b<u_n$. Puisque $\mathbb{N}$ est archimédien (cf. Proposition 9), il suffit de montrer que $na\leqslant a^n$ pour tout $n$ tel que $1\leqslant n$.

Pour $n=1$ on a bien $a^1=a$. Supposons que $na\leqslant a^n$. Puisque $1\leqslant n$ et $1<a$, soit $2\leqslant a$, on a

$$(n+1)a\leqslant 2(na)\leqslant 2a^n\leqslant aa^n\leqslant a^{n+1}.$$

On a donc montré par récurrence que $na\leqslant a^n$ pour tout $n$ tel que $1\leqslant n$.$\square$

Théorème 2   Pour tout $a\in\mathbb{N}$ et tout $b\in\mathbb{N}^*$, il existe des entiers $q$ et $r$ uniques tels que

$$a=bq+r$$   et$$\quad 0\leqslant r<b.$$

Démonstration : On considère l'ensemble $A=b\mathbb{N}\cap\{x\in\mathbb{N} \vert x\leqslant a\}$, où $b\mathbb{N}=\{x\in\mathbb{N} \vert \exists n\in\mathbb{N}, x=bn\}$. L'ensemble $A$ contient 0 et est majoré par $a$, il possède donc un plus grand élément $bq$. L'élément $bq$ ainsi défini est unique et vérifie $bq\leqslant a<b(q+1)$. On note $r$ la solution de l'équation $bq+x=a$, qui existe puisque $bq\leqslant a$, elle vérifie $0\leqslant r<b$ puisque $a<b(q+1)$.$\square$

L'opération définie dans le théorème s'appelle la division euclidienne de $a$ par $b$, $q$ est le quotient de la division et $r$ le reste. Si $r=0$, on dit que $a$ est divisible par $b$.

Théorème 3   Si $a\in\mathbb{N}$ vérifie $1<a$, tout nombre entier $x$ s'écrit de manière unique

$$x=x_n a^n+\dots+x_1 a+x_0, 0\leqslant x_i<a, 1 \leqslant i\leqslant n,$$et$$x_n\neq 0\;.$$

Démonstration : 

• Unicité : Supposons qu'un tel développement existe alors
  $$x=\underbrace{(x_na^{n-1}+\dots+x_1)}_{X_1}a+x_0$$   et$$\quad x_0<a.$$
  Les nombres $x_0$ et $X_1$ sont respectivement le reste et le quotient de la division euclidienne de $x$ par $a$, ils sont donc déterminés de manière unique. Si on pose
  $$X_k=x_na^{n-k}+\dots+x_{k+1}a+x_k$$
  on remarque que $x_k$ est le reste de la division euclidienne de $X_k$ par $a$ et $X_{k+1}$ son quotient. En posant $X_0=x$ une récurrence immédiate prouve que les $x_k$ sont déterminés de manière unique.

• Existence : Pour $x$ fixé dans $\mathbb{N}$, les conditions
  $$y_0=x,\quad y_k=ay_{k+1}+x_k$$   avec$$\quad x_k<a$$
  déterminent par récurrence deux suites $(x_k)_{k\in\mathbb{N}}$ et $(y_k)_{k\in\mathbb{N}}$. Nous allons prouver que la suite $(y_k)_{k\in\mathbb{N}}$ est stationnaire identiquement égale à 0 à partir d'un certain rang. Remarquons que, puisque $1<a$, la suite $(y_k)_{k\in\mathbb{N}}$ vérifie
  $$2y_{k+1}\leqslant ay_{k+1}\leqslant y_k,$$
  ce qui implique que $2^ky_k\leqslant x.$ Nous avons vu dans la preuve de la Proposition 9 que $2k\leqslant 2^k$, on en déduit donc que $2ky_k\leqslant x$ et par conséquent $y_k=0$ dès que $x<2k$ en raison de la compatibilité de la relation d'ordre avec la multiplication.

  On désigne par $n$ le plus grand entier $k$ tel que $y_k\neq 0$. Par définition de $n$ et de la suite $(y_k)_{k\in\mathbb{N}}$, on a

  $$y_n=x_n$$   et$$\quad y_{n-k}=x_na^k+\dots +x_{n-k}, k=1,\dots ,n,$$
  en particulier pour $k=n$, on obtient
  $$x=y_0=x_n a^n+\dots+x_1 a+x_0.$$

$\square$

Notons que dans la base $a$, le nombre entier $a$ s'écrit toujours $\overline{10}$ puisque $a=(1\times a)+0$.

La base communément utilisée est $a=s(9)$, que l'on appelle la base dix, et tout nombre entier s'écrit alors en utilisant les chiffres $0, 1, 2, 3, 4, 5, 6, 7, 8$ et $9$. L'usage courant veut que l'on écrive simplement $545$ pour $\overline{545}$ lorsqu'il n'y a pas d'ambiguïté sur la base choisie.

En informatique les bases $a=2$ et $a=s(F)$ sont souvent utilisées, c'est ce qui est appelé système de numération binaire et système de numération hexadécimale.

Exemple : Si $x$ s'écrit $\overline{125}$ en base dix, il s'écrit $\overline{1111101}$ en binaire et $\overline{7D}$ en hexadécimal.

La démonstration de l'existence du développement dans une base $a$ fixée donne un algorithme pour calculer les chiffres qui apparaissent dans l'écriture d'un nombre entier $x$ dans cette base. Le premier chiffre de droite est donné par le reste de la division euclidienne de $x$ par $a$, le second chiffre par le reste de la division euclidienne du quotient de la division précédente par $a$ et ainsi de suite jusqu'à l'obtention d'un quotient nul.

Relation d'ordre et numération

On considère le problème suivant : étant donnés deux entiers $x$ et $y$, peut-on déterminer facilement si $x\leqslant y$ à partir de leur écriture dans une base donnée.

Fixons une base $a$ arbitraire. L'unicité du développement d'un entier relativement à la base $a$ implique que $x=y$ si et seulement si ils ont même écriture dans la base $a$.

Lemme 1   Si $x\in\mathbb{N}$ s'écrit $\overline{x_n\dots x_0}$ dans la base $a$, alors $a^n\leqslant x< a^{n+1}$.

Démonstration : L'hypothèse du lemme se traduit par

$$x=x_n a^n+\dots+x_1 a+x_0.$$

Par conséquent $a^n\leqslant x_na^n\leqslant x$ puisque $1\leqslant x_n$. Montrons par récurrence sur $n$ que $x< a^{n+1}$. Si $n=0$, $x=x_0<a$. Supposons l'inégalité vraie pour les nombres dont l'écriture dans la base $a$ contient $n+1$ chiffres. Soit $x$ qui s'écrit $\overline{x_{n+1}x_n\dots x_0}$, alors

$$x=x_{n+1}a^{n+1}+y,$$

avec $y$ qui s'écrit $\overline{x_n\dots x_0}$ dans la base $a$ et par conséquent on obtient

$$x< x_{n+1}a^{n+1}+a^{n+1}\leqslant a^{n+1}(x_{n+1}+1)\leqslant a^{n+2}$$

en utilisant l'hypothèse de récurrence et le fait que $x_{n+1}<a$.$\square$

Supposons que $x$ et $y$ s'écrivent respectivement $\overline{x_n\dots x_0}$ et $\overline{y_m\dots y_0}$ dans la base $a$ et que $x\neq y$.

Supposons que $n<m$ alors $n+1\leqslant m$ et puisque $1<a$, le Lemme 1 implique

$$x< a^{n+1}\leqslant a^m\leqslant y,$$

d'où $x< y$.

Nous avons donc prouvé que :

Si deux entiers s'écrivent dans une même base avec un nombre de chiffres différent, le plus petit est celui dont l'écriture possède le moins de chiffres.

Supposons que $m=n$. Puisque $x\neq y$, il existe $1\leqslant r\leqslant n+1$ tel que $x_i=y_i$ pour tout $r\leqslant i$ et $x_{r-1}<y_{r-1}$. On déduit alors du Lemme 1 que

$$x =x_n a^n+\dots+x_{r-1}a^{r-1}+x_{r-2}a^{r-2}+\dots+x_1 a+x_0$$

$$< x_n a^n+\dots+x_{r-1}a^{r-1}+a^{r-1}$$

$$< x_n a^n+\dots+(x_{r-1}+1)a^{r-1}$$

$$< x_n a^n+\dots+y_{r-1}a^{r-1}$$

$$< y$$

Nous avons donc prouvé que :

Si deux entiers s'écrivent dans une même base avec un même nombre de chiffres et si en partant de la gauche les chiffres sont tous égaux jusqu'au rang $r$, alors le plus petit des deux est celui qui a le plus petit chiffre de rang $r-1$.

Lois de composition internes et numération

Soient $x$ et $y$ deux nombres entiers qui s'écrivent respectivement $\overline{x_n\dots x_0}$ et $\overline{y_m\dots y_0}$ dans la base $a$, on cherche un mécanisme pour déterminer l'écriture dans la base $a$ des nombres $x+y$ et $x\times y$.

Comme $+$ et $\times$ sont toutes deux commutatives, on peut supposer sans perte de généralité que $m\leqslant n$.

$\bullet$ Cas de l'addition

Si $m\neq n$ on pose $y_n=\dots=y_{m+1}=0$. Les propriétés de commutativité et d'associativité de $+$ et de distributivité de $\times$ par rapport à $+$ donnent

$$x+y=(x_n+y_n) a^n+\dots+(x_1+y_1) a+(x_0+y_0).$$

Si pour tout $i=0,\dots,n$, $x_i+y_i<a$, le développement ci-dessus correspond au développement de $x+y$ dans la base $a$.

Sinon supposons que l'un des entiers $x_i+y_i$ est supérieur ou égal à $a$, alors

$$x_i+y_i=a+z_i\quad {\rm avec}\quad z_i<a$$

et le nombre $x_i+y_i$ s'écrit alors $\overline{1z_i}$ dans la base $a$. Par suite $(x_i+y_i)a^i=a^{i+1}+z_ia^i$ et $x_{i+1}+y_{i+1}$ doit être remplacé par $x_{i+1}+y_{i+1}+1$, c'est le mécanisme de la retenue.

En conclusion, l'écriture dans la base $a$ du résultat de l'addition de deux entiers nécessite seulement la connaissance de la table d'addition en base $a$ des nombres dont l'écriture en base $a$ ne possède qu'un seul chiffre.

$\bullet$ Cas de la multiplication

Grâce à la distributivité de $\times$ par rapport à $+$ et à l'associativité de $\times$, on a

$$xy=x_n(a^ny)+\dots+x_1(ay)+x_0y.$$

On est donc ramené

1) à multiplier un entier par une puissance de la base,

2) à multiplier un entier par un nombre strictement inférieur à la base et qui s'écrit donc avec un seul chiffre,

3) à faire des additions.

- Multiplication par $a^k$

Cherchons l'écriture en base $a$ de $a^ky$. On a

$$a^ky=ya^k=y_ma^{m+k}+\dots+y_0a^k$$

et $a^ky$ s'écrit donc

$$\overline{y_m\dots y_0\underbrace{0\dots 0}_{k}}.$$

L'existence des $k$ chiffres 0 dans la partie droite de l'écriture de $a^ky$ en base $a$, explique le décalage dans la disposition pratique de la multiplication.

Exemple : En base $a$ avec $5<a$, effectuons la multiplication de $\overline{45}$ par $\overline{101}$, on aura

$$\overline{45}\times \overline{101}=(4a+5)(a^2+1)=(4a^3+5a^2)+(4a+5)=\overline{4500}+\overline{45}$$

qui en pratique s'écrit

$$\begin{array}{r} 45\\ \times 101 \hline 45\\ 45    \hline 4545 \end{array}$$

- Multiplication par un entier strictement inférieur à $a$

Soit $b<a$, alors $by=by_ma^m+\dots+by_0$. Si $by_i<a$ pour tout $i=0,\dots,m$, c'est fini sous réserve de connaître la table de multiplication en base $a$ des nombres dont l'écriture en base $a$ ne possède qu'un seul chiffre.

Si l'un des $by_i$ est supérieur ou égal à $a$, alors

$$by_i=c_ia+z_i\quad {\rm avec}\quad c_i<a\quad {et}\quad z_i<a$$

car $by_i<a^2$ et le nombre $by_i$ s'écrit alors $\overline{c_iz_i}$ dans la base $a$. Par suite $(by_i)a^i=c_ia^{i+1}+z_ia^i$ et $by_{i+1}$ doit être remplacé par $by_{i+1}+c_i$, c'est le mécanisme de la retenue.