Congruences et critère de divisibilité

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…

Stéphane Pasquet
Stéphane Pasquet

One thought on “Congruences et critère de divisibilité

René ROUX

René ROUXPublié le  11:29 - Oct 21, 2020

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

    Stéphane Pasquet

    Stéphane PasquetPublié le  11:34 - Oct 21, 2020

    Merci. L’article n’est pas disponible en PDF car j’écris directement les articles sur mon site maintenant. Cela dit, il y a un icône “print” en bas de l’article, et en choisissant d’imprimer au format PDF, on a un résultat… certes, la présentation n’est pas top, mais tout dépend de ce que vous voulez en faire 🙂 Au pire des cas, si vous n’avez pas cette option “print PDF”, je vous l’envoie par mail.

Laissez votre message