congruences

 

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,0⩽r<b.$$a=bq+r,0⩽r<b.$$

On dira alors que a est congru à r modulo b, et on écrira:

a≡rmodb.$$a\equiv r\mathrm{mod}b.$$

C’est ça une congruence.

Un résultat important est le suivant: si k est un entier naturel,

a≡rmodb⇒ak≡rkmodb.$$a\equiv r\mathrm{mod}b\Rightarrow a^k\equiv r^k\mathrm{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≡−rmodb.$$a\equiv -r\mathrm{mod}b.$$

Par exemple,

10=11−1$$10=11-1$$

donc:

10≡−1mod11.$$10\equiv -1\mathrm{mod}11.$$

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=∑k=0nxk×10k$$N=\sum _{k=0}^n{x}_k\times {10}^k$$

c’est-à-dire:

N=xn×10n+xn−1×10n−1+cdots+10x1+x0.$$N=x_n\times {10}^n+x_{n-1}\times {10}^{n-1}+cdots+10x_1+x_0.$$

Par exemple,

148=100+40+8=1×102+4×101+8×100.$$148=100+40+8=1\times {10}^2+4\times {10}^1+8\times {10}^0.$$

Nous savons que:

10=3×3+1$$10=3\times 3+1$$

et donc que:

10≡1mod3$$10\equiv 1\mathrm{mod}3$$

et donc que pour tout entier naturel k:

10k≡1mod3.$${10}^k\equiv 1\mathrm{mod}3.$$

Ainsi,

N≡∑k=0nxkmod3,$$N\equiv \sum _{k=0}^n{x}_k\mathrm{mod}3,$$

autrement dit:

N≡xn+xn−1+⋯+x1+x0mod3.$$N\equiv x_n+x_{n-1}+\cdots +x_1+x_0\mathrm{mod}3.$$

On a alors:

N divisible par 3⟺N≡0mod3⟺xn+xn−1+⋯+x1+x0≡0mod3$$\begin{array}{rl}N\text{ divisible par 3}& ⟺N\equiv 0\mathrm{mod}3\\ & ⟺x_n+x_{n-1}+\cdots +x_1+x_0\equiv 0\mathrm{mod}3\end{array}$$

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.

Congruences et critère de divisibilité par 11

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

Nous savons que:

10≡−1mod11$$10\equiv -1\mathrm{mod}11$$

donc nous pouvons écrire:

N≡∑k=0nxk×(−1)kmod11≡∑k pairxk+∑k impair(−1)xkmod11≡∑k pairxk–∑k impairxkmod11$$\begin{array}{rl}N& \equiv \sum _{k=0}^n{x}_k\times (-1{)}^k\mathrm{mod}11\\ & \equiv \sum _{k\text{ pair}}{x}_k+\sum _{k\text{ impair}}(-1)x_k\mathrm{mod}11\\ & \equiv \sum _{k\text{ pair}}{x}_k–\sum _{k\text{ impair}}{x}_k\mathrm{mod}11\end{array}$$

Ainsi,

N divisible par 11⟺N≡0mod11⟺∑k pairxk–∑k impairxk≡0mod11$$\begin{array}{rl}N\text{ divisible par 11}& ⟺N\equiv 0\mathrm{mod}11\\ & ⟺\sum _{k\text{ pair}}{x}_k–\sum _{k\text{ impair}}{x}_k\equiv 0\mathrm{mod}11\end{array}$$

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

N=5025449.$$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).

P=9+4+2+5=20I=4+5+0=9$$\begin{array}{r}P=9+4+2+5=20\\ I=4+5+0=9\end{array}$$

P−I=20−9=11≡0mod11$P-I=20-9=11\equiv 0\mathrm{mod}11$ donc N≡0mod11$N\equiv 0\mathrm{mod}11$, et donc N est divisible par 11.

Congruences et critère de divisibilité - Mathweb.fr - Par 3, 11, 13, 7 et... 17?