Aller au contenu
Topos Uranos
Français

Systèmes de numération de position

Résumé

Cette leçon étudie la numération de position, dans laquelle la valeur de chaque chiffre dépend de la place qu’il occupe. Elle démontre que tout entier naturel s’écrit d’une seule manière dans n’importe quelle base b≥2b \geq 2, par un procédé qui consiste à diviser de façon répétée par la base, et enseigne à convertir des nombres entre la base 1010 et les bases 22, 88 et 1616, et entre ces dernières en regroupant des chiffres binaires. Elle montre que l’addition et la multiplication se calculent dans n’importe quelle base avec les mêmes règles qu’en base 1010, explique pourquoi les critères de divisibilité fonctionnent et les étend à d’autres bases, et se termine par une note sur l’histoire de la numération et sur l’usage de la base 22 dans les ordinateurs.

Objectifs d’apprentissage

  1. Interpréter la numération de position et calculer la valeur d’un nombre écrit dans n’importe quelle base.
  2. Démontrer l’existence et l’unicité de l’écriture en base bb, et l’obtenir par des divisions successives.
  3. Convertir des nombres entre les bases 22, 88, 1010 et 1616, et additionner et multiplier en base 22.
  4. Justifier les critères de divisibilité par b−1b - 1 et par b+1b + 1 en base bb, et les appliquer en base 1010 et dans d’autres bases.

La numération de position

Quand on écrit 20252025, on n’additionne pas quatre chiffres : chacun est multiplié par une puissance de 1010 qui dépend de son rang. Le premier 22 vaut deux milliers ; le second, deux dizaines. Le chiffre 00 indique qu’il n’y a pas de centaines et, en occupant sa place, maintient les autres au rang qui leur revient.

2025=2⋅103+0⋅102+2⋅10+52025 = 2 \cdot 10^3 + 0 \cdot 10^2 + 2 \cdot 10 + 5

Ce principe, appelé numération de position, ne dépend pas du nombre 1010. Si b≥2b \geq 2 est un entier naturel, appelé base, les chiffres en base bb sont les nombres 0,1,…,b−10, 1, \ldots, b - 1, et une suite de chiffres ak,ak−1,…,a1,a0a_k, a_{k-1}, \ldots, a_1, a_0, avec ak≠0a_k \neq 0, représente le nombre

n=akbk+ak−1bk−1+⋯+a1b+a0n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0

Les chiffres s’écrivent les uns à côté des autres, de gauche à droite, et la base s’indique en indice : par exemple, 341253412_5 est le nombre qui en base 55 s’écrit avec les chiffres 33, 44, 11 et 22, et se lit « 34123412 en base 55 ». On dit que aia_i occupe le rang ii, compté à partir de la droite en commençant par 00. Sans indice, un nombre est écrit en base 1010. En base 22 il n’y a que deux chiffres, 00 et 11, que l’on appelle bits ; en base 1616 il en faut seize, et aux dix chiffres habituels on ajoute les lettres A, B, C, D, E et F, qui valent 1010, 1111, 1212, 1313, 1414 et 1515.

Or la valeur d’un nombre écrit en base bb peut se calculer en mettant bb en facteur encore et encore, ce qui évite de calculer des puissances : c’est le schéma de Horner.

LemmeSchéma de Horner

Pour tout kk et tous nombres a0,a1,…,aka_0, a_1, \ldots, a_k, la somme des produits aibia_i b^i s’obtient en partant de aka_k et en répétant kk fois l’opération qui consiste à multiplier par bb et à ajouter le coefficient suivant.

akbk+ak−1bk−1+⋯+a1b+a0=(⋯((akb+ak−1)b+ak−2)⋯ )b+a0a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0 = (\cdots((a_k b + a_{k-1}) b + a_{k-2}) \cdots) b + a_0

La démonstration est une récurrence sur kk qui n’utilise que la distributivité. L’expression est la valeur en x=bx = b du polynôme akxk+⋯+a1x+a0a_k x^k + \cdots + a_1 x + a_0, et la leçon sur l’algèbre des polynômes y reviendra.

Démonstration

  1. a0=a0a_0 = a_0

    Initialisation : pour k=0k = 0, les deux membres se réduisent à a0a_0, car le schéma n’effectue aucune opération.

  2. ckbk+⋯+c1b+c0=(⋯(ckb+ck−1)⋯ )b+c0\dato{h}{c_k b^k + \cdots + c_1 b + c_0 = (\cdots(c_k b + c_{k-1}) \cdots) b + c_0}

    Hypothèse de récurrence : le schéma est valable pour toute somme de k+1k + 1 termes, à coefficients quelconques, qui va jusqu’à la puissance bkb^k.

  3. ak+1bk+1+⋯+a1b+a0=(ak+1bk+⋯+a2b+a1) b+a0a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{(a_{k+1} b^k + \cdots + a_2 b + a_1)} \, b + a_0

    Soit une somme qui va jusqu’à bk+1b^{k+1}. Par distributivité, on met bb en facteur dans tous les termes sauf le dernier.

  4. ak+1bk+1+⋯+a1b+a0=((⋯(ak+1b+ak)⋯ )b+a1) b+a0a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{((\cdots(a_{k+1} b + a_k) \cdots) b + a_1)} \, b + a_0

    La parenthèse a la forme de l’hypothèse de récurrence, avec les coefficients ci=ai+1c_i = a_{i+1} ; on l’écrit avec le schéma, et en la multipliant par bb et en ajoutant a0a_0 on obtient le schéma pour k+1k + 1. D’après le principe de récurrence, il est valable pour tout kk.

ExempleLa valeur d’un nombre écrit en base 5

Calculer le nombre qui, en base 55, s’écrit 341253412_5, de deux manières : en additionnant les valeurs des rangs et avec le schéma de Horner.

Démonstration

  1. 34125=3⋅53+4⋅52+1⋅5+23412_5 = \resaltar{3} \cdot 5^3 + \resaltar{4} \cdot 5^2 + \resaltar{1} \cdot 5 + \resaltar{2}

    Chaque chiffre est multiplié par la puissance de 55 qui correspond à son rang : 535^3, 525^2, 55 et 11.

  2. 3⋅125+4⋅25+1⋅5+2=375+100+5+2=4823 \cdot \resaltar{125} + 4 \cdot \resaltar{25} + 1 \cdot 5 + 2 = \resaltar{375} + \resaltar{100} + 5 + 2 = \dato{v}{482}

    Nous calculons les puissances et les produits, et nous additionnons.

  3. 34125=((3⋅5+4)⋅5+1)⋅5+23412_5 = \resaltar{((3 \cdot 5 + 4) \cdot 5 + 1)} \cdot 5 + 2

    Avec le schéma de Horner, nous mettons 55 en facteur dans les trois premiers termes, puis dans les deux premiers de la parenthèse.

  4. 3⋅5+4=19,19⋅5+1=96,96⋅5+2=482\resaltar{3 \cdot 5 + 4} = 19, \quad \resaltar{19 \cdot 5 + 1} = 96, \quad \resaltar{96 \cdot 5 + 2} = \resaltar{482}

    On calcule de l’intérieur vers l’extérieur : chaque résultat est multiplié par la base et on lui ajoute le chiffre suivant. On obtient la même valeur, sans aucune puissance.