A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

personnes(s) sur le site en ce moment.

B. Malgrange

A lire

Articles

Math/Infos

Récréation
A télécharger

Télécharger

Théorème de Cantor-Bernstein

Théo. Sylow

Théo. Ascoli

Théo. Baire

Loi forte grd nbre

Nains magiques

suivant: L'algorithme d'Euclide-Bézout monter: bad précédent: Critères de divisibilité Table des matières

Généralisation à d'autres systèmes de numération

Le fondement mathématique des systèmes de numération est le lemme suivant :

Lemme Soit $b\geq 2$ un entier. Pour tout entier $N\in{\mbox{\bf N}}$ , il existe des entiers uniques $c_i\in\{0,\ldots, b-1\}$ , $i\in{\mbox{\bf N}}$ , nuls sauf pour un nombre fini d'entre eux, tels que

$\displaystyle N = c_0 + c_1 b + c_2 b^2 + \cdots + c_i b^i + \cdots$

Notation. Dans la situation du lemme, si $N\neq 0$ et que est le dernier coefficient non nul, nous écrivons

$\displaystyle N=[c_s, c_{s-1}, \ldots, c_1, c_0]_b.$

et nous appelons l'expression à droite l'écriture de en base . Il nous arrivera d'omettre les crochets et les virgules comme dans l'exemple suivant

$\displaystyle 1995_{10}= 11111001011_2 = 133023_8.$

Dans les cas de

, on parle de l'écriture binaire, octale et hexadécimale, respectivement. Si

excède 10, les `chiffres' de

sont représentés par les premières lettres de l'alphabet. Par exemple, les chiffres du système hexadécimal sont

. Ainsi on a

$\displaystyle 1995_{10}= 7CB_{16}.$

Démonstration. On prouve d'abord l'existence par récurrence sur . Pour on pose pour tout $i\in{\mbox{\bf N}}$ . Supposons . Effectuons la division euclidienne par

$\displaystyle n=qb+r.$

D'après l'hypothèse de récurrence, le nombre

s'écrit

$\displaystyle q=c_0'+c_1' b+ \cdots + c_t' b^t$

et donc

$\displaystyle n= r+c_0' b+ c_1' b^2 + \cdots + c_t' b^{t+1}$

On pose donc

et $c_i=c'_{i-1}$ pour

. Montrons l'unicité. Si nous avons

$\displaystyle n=c_0 + c_1 b + c_2 b^2 +\cdots = d_0 + d_1 b + d_2 b^2 +\cdots$

alors

car les deux apparaissent comme le reste de la division euclidienne de

par

. Nous enlevons

des deux côtés et nous divions par

pour obtenir

$\displaystyle (n-c_0)/b= c_1 + c_2 b + \cdots = d_1 + d_2 b + \cdots.$

L'unicité s'ensuit par récurrence sur

. $\surd$

Lemme Soit $n\geq 2$ un entier et , $i\in{\mbox{\bf N}}$ , une suite d'entiers tels que

$\displaystyle b^i\equiv a_i\;(n).$

Soit $N\in{\mbox{\bf N}}$ et

, $i\in{\mbox{\bf N}}$ , les chiffres de son écriture en base

(

=unités, ...). Alors on a

$\displaystyle N\equiv a_0 c_0 + a_1 c_1 + a_2 c_2 \cdots \;(n).$

En particulier,

est divisible par

, si c'est le cas pour $a_0 c_0 + a_1 c_1 + a_2 c_2 \cdots$ .

Démonstration. La démonstration est analogue à celle du cas . $\surd$

Exemples 21 Nous avons $8^i\equiv 1 \;(7)$ . Donc un nombre est divisible par

ssi la somme des chiffres de son écriture octale est divisible par

Nous avons $16^i \equiv (-1)^i\;(16)$ . Donc un nombre est divisible par ssi la somme alternée des chiffres de son écriture hexadécimale est divisible par .