Théorie > Théorie des nombres > Arithmétique modulaire


Général

Introduction Chapitre entier

Points théoriques

Définition Propriétés Exemple d'utilisation Critères de divisibilité Théorème de Wilson

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6 Exercice 7

Critères de divisibilité

L'utilisation des modulos permet également de simplifier certaines démonstrations. Nous allons, afin de vous familiariser encore plus avec cette notion, présenter en détails les critères de divisibilité par $9$ et par $11$ qui se prouvent sans peine à l'aide de l'arithmétique modulaire.

Critère de divisibilité par $9$

Il est bien connu qu'un nombre est divisible par $9$ si et seulement si la somme de ses chiffres l'est. Ce critère se démontre très facilement en travaillant modulo $9$ :

On considère le nombre $x$ dont l'écriture décimale est $a_k a_{k-1}\dots a_1 a_0$. Cela signifie que
$$x = 10^k \cdot a_k + 10^{k-1} \cdot a_{k-1} + \ldots + 10 \cdot a_1 + a_0.$$ Or, étant donné que $10 \equiv 1 \pmod 9$, il en est de même pour toutes ses puissances : $10^i \equiv 1^i \equiv 1 \pmod 9$. Dès lors, on voit que
$$ x \equiv a_k + a_{k-1} + \ldots + a_1 + a_0 \pmod 9.$$ Cela signifie que $x$ et la somme des chiffres de $x$ donnent le même reste après division par $9$. En particulier, l'un est divisible par $9$ si et seulement si l'autre l'est aussi. Il s'agit bien sûr du même raisonnement pour le critère bien connu de divisibilité par $3$.

Critère de divisibilité par $11$

Le critère de divisibilité par $11$, un peu moins connu que celui par $9$, est pourtant très similaire. Nous allons le découvrir directement par sa démonstration. On travaille évidemment modulo $11$ dans ce cas-ci :

On considère à nouveau le nombre $x$ dont l'écriture décimale est $a_k a_{k-1}\dots a_1 a_0$, d'où
$$x = 10^k \cdot a_k + 10^{k-1} \cdot a_{k-1} + \ldots + 10 \cdot a_1 + a_0.$$ Cette fois-ci, on a $10 \equiv -1 \pmod {11}$, et donc $10^i \equiv (-1)^i \pmod{11}$, ce qui signifie que
$$ x \equiv (-1)^k a_k + (-1)^{k-1} a_{k-1} + \ldots - a_1 + a_0 \pmod{11}.$$ Ainsi, $x$ et la somme alternée des chiffres de $x$ donnent le même reste après division par $11$. Pour savoir si un nombre est divisible par $11$, il suffit donc de regarder ce qu'il en est de la somme alternée de ses chiffres (en commencant par la gauche ou par la droite, ce qui ne change éventuellement que le signe du résultat).

Par exemple, le nombre $91839$ est divisible par $11$ car $9-1+8-3+9 = 22$, alors que $3576$ ne l'est pas car $3-5+7-6 = -1$.