Démonstration : systèmes de numération
dans Arithmétique
Bonjour
Je souhaite démontrer la partie unicité du théorème suivant par récurrence, mais j'ai un problème pour la conclusion.
Théorème.
Soit $b$ un entier supérieur ou égal à 2 et $a$ un entier naturel non nul.
$a$ s'écrit de manière unique sous la forme :
$a = a_nb^n+\cdots+a_1b+a_0$,
avec $n\in\mathbb{N},\ a_i\in\{0,1,\ldots,b-1\}$ pour tout $i$, et $a_n\neq 0$
Preuve de l'unicité de l'écriture.
Soit $b$ un entier supérieur ou égal à 2.
Soit $a\in\mathbb{N}^*$.
Si $a<b$, il suffit de prendre $a_0 = a$.
Si $a\geq b$ :
On initialise la récurrence pour $a=b$ en se servant de la division euclidienne dans $\mathbb{N}$ pour justifier l’existence d’un unique couple $(a_1,a_0)$ de $\mathbb{N}^2$ tel que $a = a_1b+a_0$ avec $0\leq a_0< b$. Ce couple est $(1,0)$ et par conséquent l'unicité est démontrée pour $a=b$.
Hérédité. Soit $a>b$.
On suppose que $a$ s'écrit de manière unique comme détaillé dans le théorème :
$a = a_nb^n+...+a_1b+a_0$,
avec $n\in\mathbb{N},\ a_i\in\{0,1,\ldots,b-1\}$ pour tout $i$, et $a_n\neq 0$.
C'est ici que je bloque pour conclure : à ce stade il semble évident que $a+1$ possède lui aussi une écriture unique...
Mais peut-on le justifier simplement ?
J'ai une façon de faire, mais c'est laborieux...
Merci.
N.B. J'ai à disposition une démonstration sans récurrence.
Je la comprends, mais je ne pense pas mémoriser "l'astuce" très longtemps à moins de relire la démo tous les deux jours...
Je souhaite démontrer la partie unicité du théorème suivant par récurrence, mais j'ai un problème pour la conclusion.
Théorème.
Soit $b$ un entier supérieur ou égal à 2 et $a$ un entier naturel non nul.
$a$ s'écrit de manière unique sous la forme :
$a = a_nb^n+\cdots+a_1b+a_0$,
avec $n\in\mathbb{N},\ a_i\in\{0,1,\ldots,b-1\}$ pour tout $i$, et $a_n\neq 0$
Preuve de l'unicité de l'écriture.
Soit $b$ un entier supérieur ou égal à 2.
Soit $a\in\mathbb{N}^*$.
Si $a<b$, il suffit de prendre $a_0 = a$.
Si $a\geq b$ :
On initialise la récurrence pour $a=b$ en se servant de la division euclidienne dans $\mathbb{N}$ pour justifier l’existence d’un unique couple $(a_1,a_0)$ de $\mathbb{N}^2$ tel que $a = a_1b+a_0$ avec $0\leq a_0< b$. Ce couple est $(1,0)$ et par conséquent l'unicité est démontrée pour $a=b$.
Hérédité. Soit $a>b$.
On suppose que $a$ s'écrit de manière unique comme détaillé dans le théorème :
$a = a_nb^n+...+a_1b+a_0$,
avec $n\in\mathbb{N},\ a_i\in\{0,1,\ldots,b-1\}$ pour tout $i$, et $a_n\neq 0$.
C'est ici que je bloque pour conclure : à ce stade il semble évident que $a+1$ possède lui aussi une écriture unique...
Mais peut-on le justifier simplement ?
J'ai une façon de faire, mais c'est laborieux...
Merci.
N.B. J'ai à disposition une démonstration sans récurrence.
Je la comprends, mais je ne pense pas mémoriser "l'astuce" très longtemps à moins de relire la démo tous les deux jours...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Ceci étant dit, ton message m’a fait penser à une possible autre récurrence, toujours sur a, qui je pense est meilleure que celle de mon premier message. Je la rédige tout à l’heure.
Initialisation évidente.
On suppose que $P(k)$ est vraie pour $0 \leq k \leq n-1$. Soit $a$ un entier entre $b^n$ et $b^{n+1}$. On fait la division euclidienne de $a$ par $b^n$ : $a = qb^n + r$ avec $0 \leq r < b^n$ et $1 \leq q < b$ à cause des inégalités sur $a$. On applique l'hypothèse de récurrence à $r$, ce qui donne l'existence. L'unicité provient de l'unicité de $q$ et $r$ et de l'unicité de la décomposition pour $r$.
Soit $a>0$ et $b\geq 2$.
L'hypothèse de récurrence est $\mathcal{P}(a)$ : "$a$ possède une écriture unique comme détaillé dans l'énoncé du théorème" (cf post initial).
Initialisation évidente pour $a=1$.
Hérédité.
Soit $a>1$.
Si $\mathcal{P}(a)$ est vraie, alors $a$ peut être associé à un unique élément de $[\![0,b-1 ]\!]^{n+1}$.
Il s'agit de $A=(a_0,a_1,...,a_n)$
De plus, si $\mathcal{P}(a)$ est vraie alors $a\in[\![0,b^{n+1}-1 ]\!]$
Or, on sait qu'à partir de la relation d'ordre usuelle sur $\mathbb{N}$, on peut créer un ordre lexicographique sur $[\![0,b-1 ]\!]^{n+1}$. On sait aussi que $[\![0,b-1 ]\!]^{n+1}$ muni de l'ordre lexicographique est isomorphe à $[\![0,b^{n+1}-1 ]\!]$ muni de la relation d'ordre usuelle sur $\mathbb{N}$.
Ainsi, l'unique successeur de $a$ dans $[\![0,b^{n+1}-1 ]\!]$ est associé à un unique élément de $[\![0,b-1 ]\!]^{n+1}$ : le successeur de $A$. Ceci démontre à la fois l’existence et l’unicité d’une écriture en base $b$ pour $a+1$ : $\mathcal{P}(a+1)$ est vraie. Remarque : le cas limite $a=b^{n+1}-1$ donne directement $a+1 = b^{n+1}$.
Question : la partie en gras est, me semble-t-il, vraie. Cependant, en invoquant cette propriété, ne serais-je pas en train de mener un raisonnement du type « si le théorème est vrai, alors il est vrai » ?
Si $a$ possède l'écriture donnée alors pour chaque $i\in\N$, $\sum_{k\geq i}a_kb^{k-i}$ et $\sum_{k=0}^{i-1}a_kb^k$ sont respectivement le quotient $q_i$ et le reste $r_i$ dans la division euclidienne de $a$ par $b^{i}$.
On en déduit que pour tout $i\in\N$, $a_i=\frac{r_{i+1}-r_i}{b^{i}}=q_i-bq_{i+1}$ est entièrement déterminé par la donnée de $a$ et de ces divisions euclidiennes.
Cela prouve donc l'unicité voulue.
Si vous retirez les restrictions : a et an non nuls, je pense que la preuve est immédiate à moins que l'exercice est un support d'introduction d'autres notions.
Je pense que c'est une faute de frappe. C'était $n \neq 0$ et non $a_n\neq 0$. Car si tous les an sont non-nuls, on a un nombre avec une infinité de chiffres non escamotables.