Accéder à mon compte > Accéder à ma feuille d'exercices >

\'Ecriture en base $b$ - Bibm@th.net

Exercice 1

- Écriture en base $b$ [Signaler une erreur] [Ajouter à ma feuille d'exos]

Soit $b\geq 2$ un entier. On souhaite démontrer que tout entier $n\geq 1$ s'écrit uniquement $$n=\sum_{k=0}^p a_k b^k$$ avec $p\geq 0$, $a_k\in\{0,\dots,b-1\}$ et $a_p\geq 1$.

Existence : démontrer l'existence en procédant par récurrence forte. Pour l'hérédité, on pourra utiliser la division euclidienne de $n$ par $b$.
Unicité : on suppose que $n$ admet deux décompositions distinctes \[ n=\sum_{k=0}^p a_k b^k\textrm{ et }n=\sum_{k=0}^{p'}a'_k b^k. \] On peut supposer $p\geq p'$. Quitte à compléter la suite $a'_k$ par $a'_{p'+1}=\dots=a'_p=0$, on peut supposer que $p=p'$. Soit $\ell\in\{0,\dots,p\}$ le plus grand possible tel que $a_\ell\neq a'_\ell$.
1. Vérifier que $(a_\ell-a'_\ell)b^\ell=\sum_{k=0}^{\ell-1}(a'_k-a_k)b^k$.
2. Démontrer que, pour toute suite finie $c_0,\dots,c_{\ell-1}$ avec $0\leq c_k\leq b-1$, on a \[\sum_{k=0}^{\ell-1}c_k b^k < b^\ell. \]
3. Conclure.
Donner l'écriture de 37 (écrit en base 10) en base 2, puis en base 3.

Indication

Corrigé

Pour $n\geq 1$, on note $H_n$ la propriété suivante : $$H_n="\exists p\geq 0,\exists (a_0,\dots,a_p)\in\{0,\dots,b-1\}\textrm{ avec }a_p\geq 1\textrm{ tels que }n=\sum_{k=0}^p a_k b^k. "$$ Initialisation : $H_1$ est vraie, car $1=1\times b^0$ (on a $p=0$ et $a_0=1$).
Hérédite : Soit $n\geq 1$ et supposons $H_1,\dots,H_{n}$ vraies. Prouvons $H_{n+1}$. On distingue deux cas :
- soit $n+1<b$. Dans ce cas, on peut écrire $n+1=(n+1)b^0$, et on a le résultat avec $p=0$ et $a_0=n+1$.
- soit $n+1\geq b$. Dans ce cas, on réalise la division euclidienne de $n+1$ par $b$. On écrit donc $$n+1=bq+r,\ 0\leq r\leq b-1.$$ On a alors $q\leq n$ et on peut appliquer l'hypothèse de récurrence à $q$ : $q$ s'écrit $$q=\sum_{k=0}^p a_k b^k,\ 0\leq a_k\leq b-1,\ a_p\geq 1.$$ On obtient alors $$n+1=\sum_{k=0}^p a_k b^{k+1}+r=r+\sum_{k=1}^{p+1} a_{k-1} b^k.$$ On obtient alors bien que $n+1$ s'écrit $$n+1=\sum_{k=0}^{p'} a'_k b^k, 0\leq a'_k\leq b-1,\ a'_{p'}\geq 1$$ en posant $p'=p+1$, $a'_k=a_{k-1}$ pour $k= 1,\dots,p'$ et $a'_0=r$.
Dans tous les cas $H_{n+1}$ est vraie.
Donc, par le principe de récurrence forte, $H_n$ est vraie pour tout entier $n\geq 1$.
1. Il suffit d'écrire que $$n=\sum_{k=0}^p a_k b^k=\sum_{k=0}^p a'_k b^k$$ ce qui s'écrit encore, par définition de $\ell$, $$n=\sum_{k=0}^\ell a_k b^k=\sum_{k=0}^\ell a'_k b^k.$$ Ceci s'écrit à son tour $$a_\ell b^\ell+\sum_{k=0}^{\ell-1} a_k b^k=a'_\ell b^\ell+\sum_{k=0}^{\ell-1} a'_k b^k$$ ce qui donne immédiatement le résultat voulu.
2. On écrit simplement que $$\sum_{k=0}^{\ell-1} c_k b^k\leq (b-1)\sum_{k=0}^{\ell-1}b^k=b^\ell-1<b^\ell$$ où on a reconnu une somme géométrique.
3. Supposons par exemple que $a_\ell>a'_\ell$. On a alors, puisque $|a'_k-a_k|\leq b-1$, $$\left|\sum_{k=0}^{\ell-1} (a'_k-a_k)b^k\right|\leq\sum_{k=0}^{\ell-1} |a'_k-a_k| b^k<b^{\ell}\leq (a_\ell-a'_\ell)b^\ell$$ ce qui contredit l'hypothèse faite. On a donc bien démontré l'unicité de la décomposition en base b.
On va faire des divisions euclidiennes successives : \begin{align*} 37&=2\times 18+1\\ &=2\times (2\times 9+0)+1\\ &=2\times (2\times (2\times 4+1))+1\\ &=2\times (2\times (2\times 2^2+1))+1\\ &=2^5+2^2+2^0 \end{align*} $37$ s'écrit donc en base $2$ : $100101$. En base 3, on a \begin{align*} 37&=3\times 12+1\\ &=3\times ( 3\times 4)+1\\ &=3\times ( 3\times(3+1))+1\\ &=3^3+3^2+3^0. \end{align*} $37$ s'écrit donc en base $3$ : $1101$.