Écriture d'un entier en base a, démonstration
dans Arithmétique
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 :
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 :
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.
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.
Mathematics knows no races or geographic boundaries; for mathematics, the cultural world is one country.
— David Hilbert
Réponses
-
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 ! -
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$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.
(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")
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.Mathematics knows no races or geographic boundaries; for mathematics, the cultural world is one country.— David Hilbert -
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. -
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.Mathematics knows no races or geographic boundaries; for mathematics, the cultural world is one country.— David Hilbert
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres