A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

150 personne(s) sur le site en ce moment

A lire

Articles

Math/Infos

Récréation
A télécharger

Télécharger

Théorème de Cantor-Bernstein

Loi forte grd nbre

Nains magiques

Critères de divisibilité

suivant: Généralisation à d'autres systèmes monter: bad précédent: Congruences Table des matières

Critères de divisibilité

Soit

$\displaystyle N=1001001001001001001001001.$

Le nombre

est-il premier

? Non. Il est divisible par

car la somme de ses chiffres est divisible par

. De façon générale, on sait qu'un nombre est divisible par

ssi la somme de ses chiffres l'est. De même pour

au lieu de

. On sait aussi qu'un nombre est divisible par

ssi la somme alternée $c_0-c_1+c_2- \ldots$ de ses chiffres l'est (

est le chiffre des unités,

celui des dizaines, ...). La divisibilité par

, par contre, ne semble être reliée ni à la divisibilité par

de la somme ni à celle de la somme alternée de ses chiffres comme le montrent les exemples $7, 14, 21, \ldots$ .

En fait, nous allons voir qu'un nombre est divisible par si et seulement si c'est le cas pour le nombre

$\displaystyle c_0+3c_1+2c_2-c_3-3c_4-2c_5+c_6+3c_7+2c_8-c_9-3c_{10}- \ldots$

Par exemple, le nombre

est divisible par

. Plus généralement, tout nombre dont l'écriture décimale est

-périodique et comporte un nombre de chiffres divisible par

est divisible par

.

Ces faits trouvent leur explication à l'aide de deux outils : 1) le calcul des congruences et 2) le calcul des restes de puissances. Le lemme suivant élucide le rôle que joue le calcul des congruences :

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

$\displaystyle a_i\equiv 10^i\;(n)$ $\displaystyle \mbox{ pour tout $i\in{\mbox{\bf N}}$.}$

Soit $N\in{\mbox{\bf N}}$ et soient $c_0, c_1, \ldots, c_s\in \{0,\ldots, 9\}$ les chiffres de son écriture décimale (

=unités, ...). Alors nous avons

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

En particulier,

est divisible par

si et seulement si $a_0 c_0 + a_1 c_1 + \ldots + a_s c_s$ est divisible par

.

Démonstration. Par définition de l'écriture décimale, on a

$\displaystyle N = c_0 + c_1 \times 10 + c_2 \times 10^2 + c_3 \times 10^3 + \cdots + c_s \times 10^s.$

Puisque $10^i\equiv a_i\;(n)$ , les règles du calcul des congruences nous permettent de conclure que

$\displaystyle N \equiv\; c_0 a_0 + c_1 a_1 + c_2 a_2 + c_3 a_3 + \ldots + c_r a_r (n).$

$\surd$

Exemple 20 Déduisons le critère de divisibilité par

que nous avons évoqué plus haut. Pour pouvoir appliquer le lemme, il nous faut calculer une suite d'entiers

tels que $a_i \equiv 10^i\; (7)$ . La suite des

vérifie donc les congruences

$\displaystyle a_0$	$\displaystyle \equiv$	$\displaystyle 1\; (7)$
$\displaystyle a_{i+1}$	$\displaystyle \equiv$	$\displaystyle 3 a_i \; (7)$

(car $10 \equiv 3\;(7)$ ). Pour $a_0, \ldots a_6$ , nous trouvons

$\displaystyle 1,3,2,-1, -3, -2,1 .$

Donc $a_6\equiv a_0\;(7)$ et par récurrence, on trouve que $a_i \equiv a_{i+6}\; (7)$ pour tout $i\in{\mbox{\bf N}}$ . Pour la suite des

, on peut donc choisir la suite

-périodique suivante

$\displaystyle 1,3,2,-1,-3,-2,1,3,2,-1,-3,-2,1,3,2,-1,-3,-2, \ldots$

D'après le lemme, il s'ensuit que

est divisible par

ssi c'est le cas pour le nombre

$\displaystyle c_0+3c_1+2c_2-c_3-3c_4-2c_5+c_6+3c_7+2c_8-c_9-3c_{10}- \ldots$

où les

sont les chiffres de l'écriture décimale de

(

=unités,

=dizaines, ...).

suivant: Généralisation à d'autres systèmes monter: bad précédent: Congruences Table des matières

Bernhard_Keller

©Emmanuel Vieillard Baron 01-01-2001

Adresse Mail:

Actuellement 16057 abonnés

Qu'est-ce que c'est ?

Taper le mot à rechercher

Mode d'emploi

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page