Numération positionnelle $b$-adique

 Dans cet article, nous allons voir comment l'écriture décimale permet de représenter les nombres entiers. Cela signifie que les dix symboles '0','1','2',....,'9' permettent de représenter tous les nombres entiers.

Plus généralement, on verra que les nombres entiers peuvent se représenter avec un nombre finis de symboles appelés les chiffres. Le nombre $b$ de symboles  utilisés sera appelée la base.

Numérotation positionnelle $b$-adique

On notera $\mathcal C$ l'ensemble 

$$\left\{0,1,2,3,4,5,6,7,8,9\right\}=\left\{k\in\mathbb N, k<10\right\}$$

Commençons par une propriété.

Propriété 1.

Pour tout entier $p$, il existe un entier naturel $r$ et un unique $r$-uplet $(c_0,c_1,\ldots,c_r)$  d'éléments de $\mathcal C$ avec $c_r\neq 0$ tel que

  $$p=\sum_{i=0}^r c_i\times 10^i=c_r\times 10^r+\ldots+c_0$$

 $r,c_0,\ldots,c_r$ sont uniques.

 Les $c_i$ sont appelés les chiffres de $p$ en base décimale ou base dix.

Soit maintenant $b$ un entier supérieur ou égal à 2.

On note $\mathcal C_b$ l'ensemble  $$\left\{0,...,b-1\right\}=\left\{k\in\mathbb N, k<b\right\}$$

$b$ s'appelera la base.

Propriété 2. 

Pour tout entier $p$, il existe un entier naturel $r$ et un unique $r$-uplet $(c_0,c_1,\ldots,c_r)$  d'éléments de $\mathcal C_b$ avec $c_r\neq 0$ tel que

  $$p=\sum_{i=0}^r c_i\times b^i=c_r\times b^r+\ldots+c_0$$

 $r,c_0,\ldots,c_r$ sont uniques.

 Les $c_i$ sont appelés les chiffres de $p$ en base $b$.

La propriété 1 est donc un cas particulier de la propriété 2 que nous démontrons ci-dessous.

Démonstration.

Soit $p$ un nombre entier naturel. On note $u_0=p$.

Voici le plan de la démonstration  sous forme d'exercice : 

1. Justifier qu'il existe un nombre entier naturel $u_1$ et un entier $0\leq c_0<b$ tel que $u_0=u_1\times b + c_0$.
2. Montrer qu'il existe une suite d'entiers naturels $(u_n)$ et une suite  $(c_n)$ de nombres de $\mathcal C$ vérifiant $u_0=p$, et pour tout $n\in\mathbb N$, la relation
   $$u_n=u_{n+1}\times b + c_n$$
3. Démontrer que si $(u_n)$ est une suite décroissante et que si $n$ est un entier vérifiant $u_n>0$, alors $u_{n+1}<u_n$.
4. a) En déduire qu'il existe un plus petit entier naturel $r$ tel que : $\forall n>r , u_n=0$.
   b) Justifier que $c_r\neq 0$.
   c) Démontrer qu'il existe  un $r$-uplet $(c_0,c_1,\ldots,c_r)$ avec pour tout $0\leq i \leq r$, $c_i\in\mathcal C$ tels que 
   $$p=\sum_{i=0}^r c_i\times b^i=c_0+\ldots+c_r\times b^r$$
5. Montrer que pour tout $p\in\mathbb N$, l'entier $r$ et et les $c_0,\ldots,c_r$ sont uniques.

Réponses : 

1.  $u_1$, et $c_0$ existent car ce sont respectivement le quotient et le reste de $u_0$ dans la division euclidienne par b : $u_0=u_1 b+c_0$, avec $0\leq c_0<b$.
2. L'idée est de construire $u_1,u_2,\ldots$ et $c_0,c_1,\ldots$ de proche en proche en effectuant des divisions euclidiennes par 10. On construit de proche en proche :
•  $u_1$ et $c_0$ tel que $u_0=u_1\times b + c_0$, où le quotient et le reste de $u_0$ dans la division euclidienne par b (déjà fait à la question 1.)
•  $u_2$ et $c_1$ tel que $u_1=u_2\times b + c_1$, où le quotient et le reste de $u_0$ dans la division euclidienne par b.
•  $\vdots$
•  $u_n$ et $c_n$ tel que $u_n=u_{n+1}\times b + c_n$, où le quotient et le reste de $u_n$ dans la division euclidienne par b.
•  $u_{n+1}$ et $c_{n+1}$ tel que $u_{n+1}=u_{n+2}\times b + c_{n+1}$, où le quotient et le reste de $u_{n+1}$ dans la division euclidienne par b.
•  etc.
  Formellement, une construction de proche en proche repose sur une récurrence...   
3. Soit $n\in\mathbb N$, on a $u_n=u_{n+1}\times b + c_n$, avec $0\leq c_n<b$.  
   Puisque $c_n\geq 0$, $u_n=u_{n+1}\times b + c_n\geq u_{n+1}\times b$, d'où l'on déduit que $u_{n+1}\leq \frac{u_n}{b}\leq u_n$.
   En particulier si $u_n>0$, $u_{n+1}\leq \frac{u_n}{b} <u_n$ (En effet si $x\geq 0$, $x\leq b x$ car $(b-1)x\geq 0$.
   Même chose en remplaçant les inégalités larges par des inégalités strictes.). 
   Ainsi $\forall n\in\mathbb N, u_{n+1}\leq u_n$. La suite $(u_n)$ est donc décroissante.
   De plus si $u_n>0$, alors $u_{n+1}<u_n$.
4.  Montrons dans un premier temps qu'il existe un entier $t$ tel que $u_t=0$.
   
    a) Première idée.
   Supposons que $u_n>0$ pour tout $n\in\mathbb N$. Alors pour tout $k\in\mathbb N$, $u_{k+1}>u_k$ donc $u_{k+1}-u_k\geq 1$.
   
    Par conséquent, on comprend facilement (faire une récurrence au besoin) que puisque $u_{n}<u_{n-1}<\ldots<u_1<u_0$, on a $u_n\leq u_0-n$. Ainsi on est assuré  d'avoir pour le nombre entier $N=u_0$, $u_{N}\leq 0$, d'où $u_{u_0}=0$.
   
   Il est donc impossible que pour tout $n\in\mathbb N$, $u_n>0$.
   
    b) Autre idée. 
   On peut aussi utiliser l'inégalité $u_{n+1}\leq \frac{u_n}{b}$ de la question précédente et montrer (faire une récurrence) que pour tout entier naturel $n$, on a $$u_n\leq \frac{u_0}{b^n}$$
   Comme $$\lim_{n\rightarrow + \infty}\frac{u_0}{b^n}=0$$ il existe un $N>0$ tel que si $n>N$, $u_n\leq \frac{u_0}{b^n}<\frac 1 2$.
   Ainsi comme $u_n$ est entier, $n>N$, $u_n=0$.
   
   Notons $$I=\left\{i\in\mathbb N | u_i=0\right\}$$
   D'après ce qui précède,  $I$ est non-vide. Comme c'est un sous-ensemble de $\mathbb N$, il possède un plus petit élément. Notons le $m$, et notons $r=m-1$.
   Par construction, $r$ est donc le plus petit entier naturel tel que $\forall n>r , u_n=0$.
   
   Par définition de $r<m$, $u_{r}>0$. En effet sinon, cela contredirait la minimalité de $m$.

Exemples. 

Le nombre deux-mille-cinq s'écrit :

•  $2005$ en base dix
•  $31010$ en base 5 ($2005=3\times 5^4+5^3+5$)
• $3725$ en base 8 ($2005=3\times 8^3+7\times 8^2 + 2\times 8 +5$)
•  $7D5$ en base seize, ici $D$ est le ``chiffre treize'' ($2005=7\times 16^2+13\times 16+5$)

Pour éviter les confusions, on les notera respectivement $2005_{10}$, $31010_{5}$, $3725_{8}$, $7D5_{16}$. On remarquera que l'indice représente la base (écrite en base dix). En général, lorsque la base n'est pas précisé et qu'il n'y a pas d'ambiguité, c'est que la base est dix.

Exemple 1. Ecrire 2023 en base 10.

$2023=  1011\times 2+1$ donc $c_0=1$

  $1011=  505\times 2+1$ donc $c_1=1$

  $505=  252\times 2+1$ donc $c_2=1$

  $252= 126\times 2$ donc $c_3=0$

  $126=63\times 2$ donc $c_4=0$

  $63=31\times 2 +1$ donc $c_5=1$

  $31=15\times 2 +1$ donc $c_6=1$

  $15=7\times 2+1$ donc $c_7=1$

  $7=3\times 2+1$ donc $c_8=1$

  $3=1\times2 + 1$ donc $c_9=1$

  $1=0\times 2 +1$ donc $c_{10}=1$ et $r=9$.

  Ainsi en base 2, deux-mille-vingt-deux s'écrit $1111100111$

Exemple 2.  Ecrire 2023 en base 5.

$2023=  404\times 5+3$ donc $c_0=3$

  $404= 80 \times 5 + 4$ donc $c_1=4$

  $80=16 \times 5 +0$ donc $c_2=0$

  $16=3\times 5+1$ donc $c_3=1$

  $3=0\times 5+3$ donc $c_4=3$ et $r=4$

Ainsi en base 5, deux-mille-vingt-trois s'écrit $31043$

Exemple 3.  Ecrire 2023 en base $2^4$ (écriture hexadécimale) - (On utilisera $\mathcal{C}_{2^4}=\left\{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F\right\}$)

 Remarque : En base seize, $A$ est 10, $B$ est onze, ..., $F$ est quinze.

  $2023=126\times 16+7$ donc $c_0=7$

  $126=7\times 16 + 14$ donc $c_1=14$ sera représenté par $E$

  $7=0\times 7+ 7$ donc $c_2=7$

  Donc l'écrituire hexadécimale de deux-mille-vingt-deux est $7E7$.