Ce contenu complète un autre article.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 361.

Soit $n$ un entier naturel non nul.

Pour toute partie $A$ de $\Z$ vous direz que $A$ constitue un ensemble d’entiers non congruents modulo $n$ si et seulement si :

Un système complet de congruences modulo $n$ est nécessairement un ensemble d’entiers non congruents modulo $n$

Soit $A$ un système complet de congruences modulo $n.$

Il est rappelé que l’ensemble $A$ vérifie la propriété $\mathscr{P}$ qui est : « pour tout entier relatif $x\comma$ il existe un unique $a\in A$ tel que $x\equiv a \mod n.$ »

Soit maintenant $(x,y)\in A^2$ un couple d’éléments de $A$ tel que $x\equiv y \mod n.$

L’entier $y$ est un élément de $A$ vérifiant $x\equiv y \mod n.$

Or, $x$ est aussi un élément de $A$ tel que $x\equiv x \mod n.$

D’après la propriété $\mathscr{P}$ appliquée à $x\comma$ vous déduisez par unicité que $x=y.$

Tout ensemble d’entiers non congruents modulo $n$ qui possède exactement $n$ éléments est un système complet de congruences modulo $n$

Soit $A$ une partie de $\Z$ comportant exactement $n$ éléments, vous les notez $a_1, \dots, a_n$ avec $a_1\lt\cdots\lt a_n.$ Supposez de plus que $A$ soit un ensemble d’entiers non congruents modulo $n.$

Soit $x$ un entier relatif fixé.

Vous raisonnez par l’absurde et supposez qu’il n’existe aucun élément $a\in A$ tel que $x\equiv a \mod n.$

Vous utilisez le fait que l’ensemble $\llbracket 0, n-1\rrbracket$ est un système complet de congruences modulo $n.$ Pour tout $i\in\llbracket 1, n\rrbracket$ il existe un unique $r_i\in\llbracket 0, n-1\rrbracket$ tel que $a_i\equiv r_i \mod n.$ De même, il existe un unique $r\in\llbracket 0,n-1\rrbracket$ tel que $x\equiv r\mod n.$

Notez que s’il existe $i\in\llbracket 1, n\rrbracket$ tel que $r = r_i$ alors $x \equiv r \equiv r_i \equiv a_i \mod n$ ce qui fournit, par transitivité de la congruence, $x\equiv a_i\mod n.$ Cela contredit l’hypothèse faite sur $x.$

Par conséquent, pour tout $i\in\llbracket 1, n\rrbracket, r_i \neq r.$

L’ensemble $\{ r_i, 1\leq i\leq n\}$ est inclus dans l’ensemble $\llbracket 0,n-1\rrbracket \setminus \{r\}$ qui comporte $n-1$ éléments.

Si $n=1\comma$ l’ensemble $\llbracket 0,n-1\rrbracket \setminus \{r\}$ est vide alors qu’il contient $r_1\comma$ ce qui est absurde.

Si $n\geq 2\comma$ les $n$ entiers $r_1,\dots,r_n$ appartiennent à un ensemble qui comporte $n-1$ éléments. En utilisant le principe des tiroirs, vous déduisez qu’il existe $(i,j)\in\llbracket 1, n\rrbracket ^2$ tel que $i\lt j$ et $r_i=r_j.$ Vous déduisez $a_i\equiv r_i \equiv r_j \equiv a_j \mod n$ et par transitivité $a_i\equiv a_j \mod n.$ Comme $A$ est un ensemble d’entiers non congruents modulo $n\comma$ cela implique $a_i=a_j.$ Or $i\lt j$ donc $a_i \lt a_j$ d’où une contradiction.

Dans tous les cas, l’hypothèse faite sur $x$ est absurde. Il a été démontré que :

Soit $x$ un entier relatif. Supposez qu’il existe $(a,a’)\in A^2$ tel que :

Alors $a\equiv a’\mod n$ et comme $A$ est un ensemble d’entiers non congruents modulo $n\comma$ vous avez $a=a’.$

Ainsi :

L’ensemble $A$ est bien un système complet de congruences modulo $n.$