congruences et critère de divisibilité

Congruences et critère de divisibilité

Congruences et critère de divisibilité: pourquoi fait-on la somme des chiffres d’un nombre pour voir s’il est divisible par 3 ? Comment voir si un nombre est divisible par 11 ? Et par 7 ? La réponse est dans cet article…

Notions de congruences

Pour la suite, vous aurez besoin de comprendre ce qu’est une congruence. Voici les indispensables.

Si a et b sont deux nombres entiers, avec a > b, la division euclidienne de a par b s’écrit:$$a = bq + r\quad,\quad 0 \leqslant r < b.$$

On dira alors que a est congru à r modulo b, et on écrira:$$a\equiv r \mod b.$$C’est ça une congruence.

Un résultat important est le suivant: si k est un entier naturel, $$a\equiv r\mod b \Rightarrow a^k \equiv r^k \mod b.$$Nous nous en servirons pour le critère de divisibilité par 3 et 9.

Un autre résultat important est que : si a < b et si b = a + r, alors:$$a\equiv -r\mod b.$$Par exemple, $$10=11-1$$donc:$$10\equiv-1\mod11.$$Nous nous en servirons pour établir le critère de divisibilité par 11.

Congruences et critère de divisibilité par 3

Commençons par un critère connu depuis le collège:

Un nombre est divisible par 3 quand la somme de ses chiffres l’est aussi.

Critère de divisibilité par 3

Notons:$$N = \sum_{k=0}^n x_k\times10^k$$c’est-à-dire:$$N = x_n\times10^n + x_{n-1}\times10^{n-1}+cdots+10x_1 +x_0.$$Par exemple,$$148=100 + 40 + 8 = 1\times10^2 + 4\times10^1 + 8\times10^0.$$

Nous savons que:$$10=3\times3+1$$et donc que:$$10\equiv1\mod3$$et donc que pour tout entier naturel k:$$10^k\equiv1\mod3.$$

Ainsi, $$N\equiv\sum_{k=0}^n x_k\mod3,$$autrement dit:$$N\equiv x_n+x_{n-1}+\cdots+x_1+x_0\mod3.$$

On a alors:$$\begin{align}N\text{ divisible par 3} & \iff N \equiv 0 \mod 3\\&\iff x_n+x_{n-1}+\cdots+x_1+x_0\equiv0\mod3 \end{align}$$ce qui signifie que N est divisible par 3 si et seulement si la somme de ses chiffres l’est aussi.

Au passage, on remarquera que remplacer “3” par “9” ne change rien à la démonstration, ce qui signifie le résultat suivant:

Un nombre est divisible par 9 si la somme de ses chiffres l’est aussi.

Critère de divisibilité par 9

Congruences et critère de divisibilité par 11

Les notations sont les mêmes que précédemment.

Nous savons que:$$10\equiv-1\mod11$$donc nous pouvons écrire:$$\begin{align}N & \equiv\sum_{k=0}^n x_k\times(-1)^k\mod11\\&\equiv\sum_{k\text{ pair}}x_k + \sum_{k\text{ impair}}(-1)x_k\mod11\\&\equiv \sum_{k\text{ pair}}x_k – \sum_{k\text{ impair}}x_k\mod11\end{align}$$

Ainsi,$$\begin{align}N\text{ divisible par 11} & \iff N \equiv 0 \mod 11\\&\iff \sum_{k\text{ pair}}x_k – \sum_{k\text{ impair}}x_k\equiv0\mod11\end{align}$$

Cela peut paraître compliqué au prime abord, mais c’est très simple au final. Regardons sur un exemple. Soit:$$N=5025449.$$

Le critère de divisibilité que nous venons de trouver suggère d’ajouter tous les chiffres de rangs pairs (notons P cette somme) et tout ceux de rangs impairs (notons I cette somme).$$\begin{align}P=9+4+2+5=20\\I=4+5+0=9\end{align}$$

\(P-I=20-9=11\equiv0\mod11\) donc \(N\equiv0\mod11\), et donc N est divisible par 11.

Par 7

Les notions sont les mêmes que précédemment. Nous allons justement nous inspirer de la technique précédente en écrivant, dans un premier temps:$$10\equiv-4\mod7$$car \(10\equiv3\mod7\) donc \(10\equiv3-7\mod7\). Ainsi,$$\begin{align}N & \equiv \sum_{k=0}^n (-4)^kx_k\mod7 \\ & \equiv\sum_{k=0}^n(-1)^k 4^kx_k\mod7.\end{align}$$Notons maintenant que:$$\begin{align}4^0 & \equiv 1 \mod 7\\4^1 & \equiv 4 \mod 7\\4^2 & \equiv2\mod7\\4^3 & \equiv 1\mod7\end{align}$$

Il y a donc un “cycle” dans les puissances de 4 modulo 7, ce qui nous permet d’écrire:$$N\equiv x_0-4x_1+2x_2-x_3+4x_4-2x_5+x_6-4x_7+\cdots\mod7$$

Ainsi, N est divisible par 7 si \(x_0-4x_1+2x_2-x_3+4x_4-2x_5+x_6-4x_7+\cdots\equiv0\mod7\).

Je vous l’accorde, celui-là, il est cool… 🙂 Regardons sur un exemple en prenant:$$N=379995.$$On calcule:$$x_0-4x_1+2x_2-x_3+4x_4-2x_5+x_6.$$Pour ma part, je présente les calculs en tableau:

signescoef.×chiffres=résultats
+1×5=5
4×9=-36
+2×9=18
1×9=-9
+4×7=28
2×3=-6

Quand on ajoute les résultats (dernière colonne), on trouve 0 (qui est bien congru à 0 modulo 7), donc N est bien divisible par 7.

Par 13

Nous allons nous inspirer de ce qui a été fait pour 7. En effet,$$10\equiv-3\mod13$$et:$$\begin{align}3^0\equiv1\mod13\\3^1\equiv3\mod13\\3^2\equiv9\mod13\\3^3\equiv1\mod13\end{align}$$donc:$$N\equiv x_0-3x_1+9x_2-x_3+3x_4-9x_5+x_6-3x_7+\cdots\mod13$$

Ainsi, $$N\equiv0\mod13\iff x_0-3x_1+9x_2-x_3+3x_4-9x_5+x_6-3x_7+\cdots\equiv0\mod13.$$

Prenons N = 5888766 et présentons les calculs dans un tableau comme précédemment:

signescoef.×chiffres=résultats
+1×6=6
3×6=-18
+9×7=63
1×8=-8
+3×8=24
9×8=-72
+1×5=5

On trouve 98 – 98 (en ajoutant les positifs d’une part, les négatifs d’autre part), donc la somme est bien congrue à 0 modulo 13, et donc N est bien divisible par 13.

Par 17… euh, non merci !

Si l’on raisonne de même avec 17, on a:$$N=\sum_{k=0}^n(-1)^k7^k \mod17$$ et$$\begin{align}7^0&\equiv1 \mod 17\\7^1&\equiv7 \mod 17\\7^2&\equiv15 \mod 17\\7^3&\equiv3 \mod 17\\7^4&\equiv4 \mod 17\\7^5&\equiv11 \mod 17\\7^6&\equiv9 \mod 17\\7^7&\equiv12 \mod 17\\7^8&\equiv16 \mod 17\\7^9&\equiv10 \mod 17\\7^{10}&\equiv2 \mod 17\\7^{11}&\equiv14 \mod 17\\7^{12}&\equiv13 \mod 17\\7^{13}&\equiv6 \mod 17\\7^{14}&\equiv8 \mod 17\\7^{15}&\equiv5 \mod 17\\7^{16}&\equiv1 \mod 17\end{align}$$

Le fait que le cycle soit supérieur à 3 est problématique car il faudrait retenir en l’occurrence 16 coefficients (contre 3 pour la divisibilité par 7 ou 13).

Comprenez donc que je n’insiste pas…

0 0 votes
Évaluation de l'article
S’abonner
Notification pour
guest
3 Commentaires
Le plus ancien
Le plus récent Le plus populaire
Commentaires en ligne
Afficher tous les commentaires

Super article…
disponible en pdf ?
Merci pour cette très belle leçon de congruence.

Nicolas Patrois

André Deledicq propose un autre critère dans son livre La jubilation mathématique.
On ne cherche pas la valeur des puissances de 10 modulo 3 ou 7 ou 17, on va prendre le problème par l’autre bout.
Par exemple on va regarder si 457986304 est divisible par 17, ça se fait de tête.
457986304 est divisible par 17
ssi 45798630−5×4=45798610 est divisible par 17
ssi 4579861−5×0=4579861 est divisible par 17
ssi 457986−5×1=457981 est divisible par 17
ssi 45798−5×1=45793 est divisible par 17
ssi 4579−5×3=4564 est divisible par 17
ssi 456−5×4=436 est divisible par 17
ssi 43−5×6=13 est divisible par 17
Ce qui est faux.
Mais pourquoi 5 ? Parce que 17×3=51=5×10+1.
Pour 13, on a 13×3=39=4×10−1 donc on multiplie par 4 le dernier chiffre, qu’on ajoute cette fois, au nombre de dizaines du nombre. On retrouve ainsi les critères pour 3, 9 et 11.