Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
230 personne(s) sur le site en ce moment
E. Cartan
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
 
 
 
 
 
Critères de divisibilité next up previous contents
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 $ N$ est-il premier ? Non. Il est divisible par $ 3$ car la somme de ses chiffres est divisible par $ 3$. De façon générale, on sait qu'un nombre est divisible par $ 3$ ssi la somme de ses chiffres l'est. De même pour $ 9$ au lieu de $ 3$. On sait aussi qu'un nombre est divisible par $ 11$ ssi la somme alternée $ c_0-c_1+c_2- \ldots$ de ses chiffres l'est ($ c_0$ est le chiffre des unités, $ c_1$ celui des dizaines, ...). La divisibilité par $ 7$, par contre, ne semble être reliée ni à la divisibilité par $ 7$ 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 $ 7$ 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 $ 100100100100$ est divisible par $ 7$. Plus généralement, tout nombre dont l'écriture décimale est $ 3$-périodique et comporte un nombre de chiffres divisible par $ 6$ est divisible par $ 7$.

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 ($ c_0$=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, $ N$ est divisible par $ n$ si et seulement si $ a_0 c_0 + a_1 c_1 + \ldots + a_s c_s$ est divisible par $ n$.


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 $ 7$ que nous avons évoqué plus haut. Pour pouvoir appliquer le lemme, il nous faut calculer une suite d'entiers $ a_i$ tels que $ a_i \equiv 10^i\; (7)$. La suite des $ a_i$ 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 $ a_i$, on peut donc choisir la suite $ 6$-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 $ N$ est divisible par $ 7$ 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 $ c_i$ sont les chiffres de l'écriture décimale de $ N$ ($ c_0$=unités, $ c_1$=dizaines, ...).


next up previous contents
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:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

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

Nous contacter

Le vote Linux

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