Écriture d'un entier en base a, démonstration

jcc · October 2021

Bonjour à tous,
Je commence à travailler l'arithmétique avec l'ouvrage de Mohammed El Amrani "Arithmétique dans $\mathbb{Z}$ et $\mathbb{K}[X]$". J'ai un problème de compréhension avec l'application de l'hypothèse de récurrence dans la partie Existence de la démonstration de la proposition 3.3, Chapitre 1 §3.

Proposition. Soit $a \in \mathbb{N}, a \geq 2$. Pour $m \in \mathbb{N}^*$, il existe un unique entier naturel $p$ et une une unique $(p+1)$-liste $(x_0,x_1,\ldots,x_p)$ d'éléments de $[0,a-1]$ tels que :

$m=x_pa^p+\cdots+x_1a+x_0$, avec $x_p \neq 0$.

Démonstration. Existence. Raisonnons par récurrence forte sur $m \geq 1$. Le résultat est vrai si $1 \leq m < a$, car il suffit de prendre $p = 0$ et $x_0 = m$.
Pour $m \geq a$, supposons le résultat vrai jusqu'au rang $m-1$ et montrons le au rang $m$.
Soient $q$ et $r$ le quotient et le reste de la division euclidienne de $m$ par $a$. Alors $0 \leq r < a$ et $q \geq 1$ car $m \geq a$, et on a $q < m$ puisque $a > 1$.
Par hypothèse de récurrence, il existe $p \in \mathbb{N}^*$ et $(x_1,x_2,\ldots,x_p)$ une $p$-liste d'éléments de $[0,a-1]$ telle que :

$q = \sum\limits_{k=1}^p x_ka^{k-1}$ et $x_p \neq 0\quad$ ($\leftarrow$ C'est là que je perds pied, mais je recopie jusqu'au bout)

En posant $x_0 = r$, la $(p+1)$-liste $(x_0,x_1,\cdots,x_p)$ est à éléments dans $[0,a-1]$ et on a bien

$m = r + qa = \sum\limits_{k=0}^p x_ka^{k}$ avec $x_p \neq 0$

Mon interrogation. Ma question (bien naïve certainement), est la suivante : pourquoi lors de l'application de l'hypothèse de récurrence à $q$, applique-t-on un changement d'indice, et a-t-on une $p$-liste en lieu et place de la $(p+1)$-liste de l'hypothèse ?.
J'ai essayé de développer $qa + r$ en reprenant l'hypothèse "brute", i.e. avec $q = \sum\limits_{k=0}^p x_ka^{k}$ et $x_p \neq 0$, mais sans grand succès.
Cordialement.
JC.

gerard0 · October 2021

Bonjour.

J'ai d'abord pensé que c'était simplement l'hypothèse de récurrence réécrite : Changement d'indice k'=k+1, mais ça ne marche pas ! C'est un peu plus futé, car le p de l'application est le p+1 du théorème. Il y a bien p+1 termes (au sens du théorème), mais les puissances ont été écrites k-1. Ce qui donnera la bonne formulation à la fin (*). Le terme constant de $q$ est destiné à devenir le coefficient de a à la fin, donc il est déjà nommé $x_1$.
Si tu butes toujours, regarde avec une somme pour p=3

Cordialement.

(*) L'auteur se simplifie la rédaction au détriment de la compréhension !

jcc · October 2021

Bonjour Gérard0,

Un grand merci pour le point de démarrage. Le fait de coucher sur papier un exemple avec $p=3$ a été salutaire. J'avais bien compris dès le départ qu'il s'agissait de mettre les indices en cohérence avec l'étape suivante, pour que le produit $qa$ revienne directement dans les notations de la proposition. Cependant, cette pirouette m'a bien perturbé !

Tentative de clarification : Peut-on imaginer compléter le passage coupable comme suit ?

En appliquant telle quelle l'hypothèse de récurrence à $q$, nous avons :

$q = \sum\limits_{k=0}^p x_ka^{k}$ avec $x_p \neq 0$

Afin de faciliter l'étape suivante, opérons un décalage des indices comme suit :

$q = \sum\limits_{k=1}^{p'=p+1} x_ka^{k-1}$ avec $x_{p'} \neq 0$
(Je préfère préciser avec $p'$, l'emploi de $p$ prête beaucoup à confusion je trouve. Cela laisse penser que l'on s'arrête à $a^{p-1}$, avec le $p$ "d'origine")

Remarquons que seule la notation des indices est changée, la $(p+1)$-liste $(x_0,x_1,\cdots,x_p)$ est notée $(x_1,x_2,\cdots,x_{p'=p+1})$, i.e. une $p'$-liste, et les puissances de $a$ présentes dans la somme sont inchangées.

Le produit $qa$ est alors :

$a.\sum\limits_{k=1}^{p'} x_ka^{k-1} = \sum\limits_{k=1}^{p'} x_ka^{k} $ avec $x_{p'} \neq 0$

Ainsi, en posant maintenant $x_0 =r$, et nous obtenons bien :

$m = r + qa = x_0 + \sum\limits_{k=1}^{p'} x_ka^{k} = \sum\limits_{k=0}^{p'} x_ka^{k} avec x_{p'} \neq 0$ où la $(p'+1)$-liste $(x_0,x_1,\cdots,x_{p'})$ est à éléments dans $[0,a-1]$.

Interrogation N°2 : Mon complément est-il correct, en particulier avec le passage à $p'$ dans la somme ?

Cordialement.

JC.

gerard0 · October 2021

Oui, sauf faute de frappe que je n'aurais pas vue.

Cordialement.

NB : Le fait d'utiliser un exemple simple dans les formules avec des sommes ou des produits est un truc efficace et facile.

jcc · October 2021

Re-bonjour.

Bien reçu, je peux donc reprendre mes notes avec ce complément fort éclairant, même quant à la "mécanique" de la construction en numération.

Encore merci.

Écriture d'un entier en base a, démonstration

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 25