Système de numération bijectif

En nous inspirant de la construction d'un nombre en base ${\displaystyle k}$ usuelle[6], démontrons que quel que soit l'entier naturel non nul ${\displaystyle k}$, tout entier naturel ${\displaystyle n}$ non nul a une, et une seule, décomposition de la forme : ${\displaystyle n=a_{0}+a_{1}\times k+a_{2}\times k^{2}+...+a_{p}\times k^{p}}$ où les ${\displaystyle a_{j}}$ sont des entiers naturels non nuls inférieurs ou égaux à ${\displaystyle k}$.

Démontrons d'abord que si ${\displaystyle n}$ a une telle décomposition, elle est unique. Raisonnons par récurrence: si ${\displaystyle n}$ a deux décompositions notons les ${\displaystyle (a_{p},...a_{1},a_{0})}$ et ${\displaystyle (b_{q},...b_{1},b_{0})}$, et démontrons que ${\displaystyle b_{0}=a_{0}}$.

Si ${\displaystyle n}$ n'est pas divisible par ${\displaystyle k}$, le reste de sa division par ${\displaystyle k}$ est ${\displaystyle a_{0}}$ mais aussi ${\displaystyle b_{0}}$. Donc : ${\displaystyle b_{0}=a_{0}}$. Si ${\displaystyle n}$ est divisible par ${\displaystyle k}$, alors ${\displaystyle a_{0}=b_{0}=k}$ (car aucun ${\displaystyle a_{j}}$ ou ${\displaystyle b_{j}}$ ne peut être nul). Donc, dans tous les cas : ${\displaystyle a_{0}=b_{0}}$. Si ${\displaystyle n=a_{0}=b_{0}}$, alors ${\displaystyle n}$ ne peut avoir que la représentation (${\displaystyle a_{0}}$), car ${\displaystyle n}$ est strictement inférieur à tout nombre représenté par un chaine de longueur supérieure se terminant par ${\displaystyle a_{0}}$[7].

Si ${\displaystyle n>a_{0}}$, intéressons nous au nombre entier ${\displaystyle (n-a_{0})/k}$ : il vaut ${\displaystyle a_{1}+a_{2}\times k+...+a_{p}\times k^{p-1}}$, mais aussi ${\displaystyle b_{1}+b_{2}\times k+...+b_{p}\times k^{p-1}}$. Il a donc deux décompositions. Donc, comme démontré ci-dessus, ${\displaystyle b_{1}=a_{1}}$. Et par récurrence, on démontre que, pour tout ${\displaystyle i}$, ${\displaystyle b_{i}=a_{i}}$, donc ${\displaystyle n}$ n'a qu'une seule décomposition.

Démontrons maintenant que tout entier naturel ${\displaystyle n}$ a une décomposition de type ${\displaystyle (a_{0},a_{1},...,a_{p})}$. Pour cela, il suffit d'en construire une, et on peut le faire par récurrence comme suit : si ${\displaystyle n}$ n'est pas divisible par ${\displaystyle k}$, on choisit le reste de sa division par ${\displaystyle k}$ comme valeur de ${\displaystyle a_{0}}$, et si est divisible par ${\displaystyle k}$, on pose ${\displaystyle a_{0}=k}$. Si ${\displaystyle n=a_{0}}$, on a trouvé une décomposition valable.

Si ${\displaystyle n>a_{0}}$, alors ${\displaystyle n_{1}=n-a_{0}}$ est, par construction, un entier non nul qui est divisible par ${\displaystyle k}$. Appliquons à ${\displaystyle n_{1}/k}$ la méthode appliquée précédemment pour définir ${\displaystyle a_{1}}$. Si ${\displaystyle n=a_{1}\times k+a_{0}}$, on a trouvé une décomposition valable. Sinon, posons : ${\displaystyle n_{2}=n-a_{1}\times k-a_{0}}$. ${\displaystyle n_{2}}$ est, par construction, divisible par ${\displaystyle k^{2}}$. En appliquant la même méthode à ${\displaystyle n_{2}/k^{2}}$ on définit ${\displaystyle a_{2}}$ puis, par récurrence, tous les ${\displaystyle a_{i}}$, et on a ainsi construit une décomposition valable de ${\displaystyle n}$.

On a donc bien démontré que tout entier naturel non nul ${\displaystyle n}$ a une décomposition du type recherché, et qu'elle est unique.