Soit $n$ un entier naturel non nul fixé dans tout cet exposé.
Une partie $A$ de l’ensemble $\Z$ sera qualifiée de système complet de congruences modulo $n$ si et seulement si, pour tout entier relatif $x$, il existe un unique élément $a$ de $A$ tel que $x\equiv a \mod n.$
L’exemple fondamental
Soit $x$ un entier relatif. Vous effectuez la division euclidienne de $x$ par $n.$ Il existe un quotient $q$ et un entier $r\in \llbracket 0, n-1\rrbracket$ tels que :
x = qn+r.
Du coup, vous obtenez :
x\equiv r\mod n.
Supposez qu’il existe $r’\in\llbracket 0, n-1\rrbracket$ tel que :
x\equiv r'\mod n.
Alors vous déduisez :
r\equiv r' \mod n.
Vous avez donc $n\mid r-r’$ donc il existe un entier relatif $k$ tel que $r-r’ = kn.$
Supposez que $k$ soit non nul. Alors $\vert k \vert \geq 1$ et comme $\vert r – r’\vert = \vert k \vert \times n$ vous déduisez $\vert r-r’\vert \geq n.$
Cependant, comme $r$ et $r’$ appartiennent à $\llbracket 0, n-1\rrbracket$ vous déduisez que $1-n\leq r-r’\leq n-1$ et donc $\vert r-r’\vert \leq n-1$ d’où d’une contradiction.
Donc $k=0$ et $r=r’.$ Il a été démontré que :
\forall x\in\Z, \exists! r\in\llbracket 0, n-1\rrbracket, x\equiv r\mod n.
Vous venez de démontrer dans ce paragraphe que l’ensemble $\llbracket 0, n-1\rrbracket$ est un système complet de congruences modulo $n.$
Étudiez le cardinal d’un système de congruences modulo n
Soit $A$ un système complet de congruences modulo $n.$
En raisonnant par l’absurde, supposez que $A$ possède au moins $n+1$ éléments. Vous notez ces entiers relatifs $a_1, \dots, a_{n+1}$ avec $a_1<\cdots<a_{n+1}.$
D’après le paragraphe précédent appliqué pour chaque élément précité, vous déduisez que :
\forall i\in\llbracket 1, n+1\rrbracket, \exists!r_i\in\llbracket 0, n-1\rrbracket, a_i\equiv r_i\mod n.
Les entiers $(r_i)_{1\leq i\leq n+1}$ sont au nombre de $n+1$ et ils appartiennent tous à l’ensemble $\llbracket 0, n-1\rrbracket$ qui comporte $n$ éléments. Utilisant le principe des tiroirs, vous déduisez qu’il existe un couple $(u,v)\in\llbracket 1, n+1\rrbracket^2$ tel que $u<v$ et $r_u = r_v.$ Comme $a_u \equiv r_u \mod n$ et $a_v\equiv r_v \mod n$ vous déduisez que $a_v\equiv a_u \mod n.$
D’une part, $a_v\equiv a_v \mod n$ et d’autre part $a_v\equiv a_u \mod n$ avec $a_u\neq a_v.$ Il a été montré qu’il existe un entier relatif $a_v$ et deux éléments de $A$ tels que $a_v$ leur soit congru modulo $n.$ Cela contredit le fait que $A$ soit un système complet de congruences modulo $n$ donc $A possède au maximum $n$ éléments.
Supposez en raisonnant encore par l’absurde que $A$ possède au maximum $n-1$ éléments.
Si $A$ est vide, alors $1$ doit être congru à un unique élément de $A$ modulo $1$, ce qui est impossible si $A$ ne possède aucun élément, donc $A$ n’est pas vide.
Vous notez $m$ le nombre d’éléments de $A$ vous avez $1\leq m\leq n-1.$ Vous notez les éléments de $A$ ainsi $a_1, \dots, a_{m}$ avec $a_1<\cdots<a_{m}.$
Toujours d’après le paragraphe précédent appliqué pour chaque élément précité, vous déduisez que:
\forall i\in\llbracket 1, m\rrbracket, \exists!r_i\in\llbracket 0, n-1\rrbracket, a_i\equiv r_i\mod n.
L’ensemble $R = \{r_i, 1\leq i \leq m\}$ contient au maximum $m$ éléments et c’est une partie de $\llbracket 0, n-1\rrbracket$ qui en comporte $n$ avec $n>m.$ Donc il existe un entier $r\in\llbracket 0, n-1\rrbracket$ tel que $r\notin R.$
S’il existait $i\in\llbracket 1, m\rrbracket$ tel que $r\equiv a_i \mod n$ alors $r\equiv r_i \mod n.$ Comme $r$ et $r_i$ appartiennent tous les deux à l’ensemble $\llbracket 0, n-1\rrbracket$ $\vert r-r_i\vert \leq n-1.$ Or $n$ divise $ r-r_i$ il existe un entier relatif $k$ tel que $r-r_i = kn$ ce qui implique $\vert r-r_i\vert = \vert k\vert \times n.$ Si $k$ n’est pas nul, il vient $\vert r-r_i\vert \geq n$ ce qui est absurde. Donc $k=0$ et $r=r_i$ et $r\in R$ contradiction. Donc $A$ ne peut pas posséder $n-1$ éléments au maximum.
Il en résulte que tout système complet de congruences modulo $n$ possède exactement $n$ éléments.
Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !