Catégorie : Niveau Prépa

Soit $k$ un entier naturel non nul. Dans cette section, vous vous intéressez à la résolution de l’équation :

x^2\equiv 1\mod 2^k.

Traitez le cas où $k=1$

Comme $2^k = 2$ vous calculez tous les carrés modulo $2.$

\begin{array}{|c|c|c|}
\hline
x \mod 2 & 0 & 1\\
\hline
x^2 \mod 2 & 0 & 1\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2) \Longleftrightarrow (x\equiv 1 \mod 2).}

Traitez le cas où $k=2$

Comme $2^2 = 4$ vous calculez tous les carrés modulo $4.$

\begin{array}{|c|c|c|c|c|}
\hline
x \mod 4 & 0 & 1 & 2 & -1\\
\hline
x^2 \mod 4 & 0 & 1 & 0 & 1\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 4) \Longleftrightarrow (\exists a\in\{-1,1\}, x\equiv a \mod 4).}

Traitez le cas où $k=3$

Comme $2^3 = 8$ vous calculez tous les carrés modulo $8.$

\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
x \mod 8  &-1 & 0 & 1 & 2 & 3 & 4  & 5 & 6\\
\hline
x^2 \mod 8 & 1 & 0 & 1 & 4 & 1& 0  & 1  & 4\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 8) \Longleftrightarrow (\exists a\in\{-1,1, 3, 5\}, x\equiv a \mod 8).}

Et après, que se passe-t-il modulo $16$ dans le cas où $k=4$ ?

Vous pourriez penser que le nombre de solutions modulo $2^4=16$ serait égal à $8$ comme le suggère cette analyse.

Analyse. Soit $x$ un nombre entier relatif tel que :

x^2\equiv 1 \mod 16.

Comme $8\mid 16$ et que $16 \mid x^2-1$ il vient $8\mid x^2-1$ et du coup :

x^2\equiv 1 \mod 8.

En appliquant le résultat précédent, vous déduisez qu’il existe $a\in\{-1, 1, 3,5\}$ tel que $x^2\equiv a \mod 8.$

Cas n°1. $x\equiv -1\mod 8.$ Il existe un entier relatif $t$ tel que $x=-1+8t.$ Si $t$ est pair, il existe un entier relatif $k$ tel que $t=2k$ et par suite $x=-1+16k$ et $x\equiv -1\mod 16.$ Si $t$ est impair, il existe un entier relatif $\ell$ tel que $t = 2\ell+1$ et par suite $x = -1+8(2\ell+1) = 7+16\ell$ et $x\equiv 7\mod 16.$

Cas n°2. $x\equiv 1\mod 8.$ En reprenant la démarche du cas précédent, vous déduisez que soit $x\equiv 1\mod 16$ soit $x\equiv 9\mod 16.$

Cas n°3. $x\equiv 3\mod 8.$ De même, vous déduisez que soit $x\equiv 3\mod 16$ soit $x\equiv 11\mod 16.$

Cas n°4. $x\equiv 5\mod 8$ en vous avez : soit $x\equiv 5\mod 16$ soit $x\equiv 13\mod 16.$

Le résultat suivant est ainsi établi :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 16) \implies (\exists a\in\{-1,1, 3, 5, 7, 9, 11, 13\}, x\equiv a \mod 16).}

Il y a huit candidats potentiels.

Synthèse. Soit $x$ un entier relatif.

Si $x\equiv -1\mod 16$, alors $x^2\equiv 1\mod 16.$

Si $x\equiv 1\mod 16$, alors $x^2\equiv 1\mod 16.$

Si $x\equiv 3\mod 16$, alors $x^2\equiv 9\mod 16.$

Si $x\equiv 5\mod 16$, alors $x^2\equiv 25\mod 16$ et $x^2\equiv 9\mod 16.$

Si $x\equiv 7\mod 16$, alors $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$

Si $x\equiv 9\mod 16$, alors $x\equiv -7\mod 16$ donc $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$

Si $x\equiv 11\mod 16$, alors $x\equiv -5\mod 16$ alors $x^2\equiv 25 \mod 16$ et $x^2\equiv 9 \mod 16.$

Si $x\equiv 13\mod 16$, alors $x\equiv -3\mod 16$ alors $x^2 \equiv 9 \mod 16.$

Parmi les 8 candidats, il n’y en a que quatre qui conviennent.

Conclusion. Par analyse-synthèse, il vient d’être démontré que :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 16) \Longleftrightarrow (\exists a\in\{-1,1, 7, 9\}, x\equiv a \mod 16).}

Le nombre de solutions modulo $16$ reste finalement égal à $4.$ Vous allez montrer que cela se généralise.

Passez au cas général en étudiant la situation pour $k\geq 3$

Dans cette section, vous supposez que $k$ est un entier supérieur ou égal à $3.$

Pour tout entier $n\geq 3$ vous notez $\mathscr{P}(n)$ la propriété suivante :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2^n) \Longleftrightarrow (\exists a\in\left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}, x\equiv a \mod 2^n).}

Initialisation. Il a été démontré ci-dessus que :

\forall x\in\Z, (x^2\equiv 1\mod 8) \Longleftrightarrow (\exists a\in\{-1,1, 3, 5\}, x\equiv a \mod 8).

Comme $3 = -1+2^{3-1}$ et $5 = 1+2^{3-1}$ vous en déduisez que $\mathscr{P}(3)$ est vérifiée.

Hérédité. Soit $n$ un entier supérieur ou égal à $3.$ Supposez $\mathscr{P}(n).$

Soit $x$ un entier relatif tel que $x^2\equiv 1 \mod 2^{n+1}.$

Comme $2^n \mid 2^{n+1}$ vous déduisez $x^2\equiv 1 \mod 2^n.$ D’après l’hypothèse de récurrence, il existe un entier $a\in \left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}$ tel que $x\equiv a\mod 2^n.$

Cas n°1. $a\in\{-1,1\}.$ De $x\equiv a \mod 2^n$ vous déduisez l’existence d’un entier relatif $t_1$ tel que $x = a+2^n t_1.$ Si $t_1$ est pair, il existe un entier relatif $k_1$ tel que $t_1 = 2k_1$ et par suite $x=a+2^{n+1}k_1$ et $x\equiv a\mod 2^{n+1}.$

Si $t_1$ est impair il existe un entier relatif $\ell_1$ tel que $t_1 = 1+2\ell_1$ et par suite $x = a+2^n(1+2\ell_1)$ d’où $x=a+2^n+2^{n+1}\ell_1$ et $x\equiv a+2^n \mod 2^{n+1}.$

Cas n°2. $a\in\{-1+2^{n-1}, 1+2^{n-1}\}.$ Il existe $b\in\{-1,1\}$ tel que $a = b+2^{n-1}.$ Comme $x\equiv a \mod 2^n$ vous déduisez qu’il existe un entier relatif $t$ tel que $x = a+2^n t$ ce qui donne $x = b+2^{n-1}+2^n t.$ En élevant au carré, il vient :

\begin{align*}
x^2 &= b^2+2^{2n-2}+t^2\times 2^{2n}+b2^{n}+bt\times2^{n+1}+t\times 2^{2n}\\
&= b^2+2^{n+1}2^{n-3}+t^2\times 2^{n+1}2^{n-1}+b\times 2^n+bt\times 2^{n+1}+t\times 2^{n+1}2^{n-1}.
\end{align*}

Comme $n\geq 3$ tous les exposants qui apparaissent dans les puissances de $2$ sont positifs ou nuls. Modulo $2^{n+1}$ vous obtenez :

x^2\equiv b^2+b\times 2^n\mod 2^{n+1}.

Or, $b^2=1$ donc :

x^2\equiv 1+b\times 2^n\mod 2^{n+1}.

Comme $x^2\equiv 1 \mod 2^{n+1}$ vous déduisez :

\begin{align*}
1 \equiv 1+b\times 2^n \mod 2^{n+1}\\
b\times 2^n \equiv 0 \mod 2^{n+1}.
\end{align*}

Il existe un entier relatif $k$ tel que $b\times 2^n = k\times 2^{n+1}.$ En divisant par $2^n$ vous obtenez $b = 2k$ donc $b$ est pair. Or, $b\in\{-1,1\}$ d’où une contradiction. Ainsi le cas n°2 ne peut se produire.

Vous déduisez l’implication suivante :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n+1}) \implies (\exists u\in\left\{-1,1, -1+2^{n}, 1+2^{n}\right\}, x\equiv u \mod 2^{n+1}).

Il reste à montrer la réciproque.

Soit $x$ un entier relatif.

S’il existe $a\in\{-1,1\}$ tel que $x\equiv a \mod 2^{n+1}$ alors $x^2\equiv a^2\mod 2^{n+1}.$ Or $a^2=1$ donc $x^2\equiv 1 \mod 2^{n+1}.$

S’il existe $a\in\{-1,1\}$ tel que $x\equiv a+2^n \mod 2^{n+1}$ alors :

\begin{align*}
x^2\equiv a^2+2^{2n}+a\times 2^{n+1} \mod 2^{n+1}\\
x^2\equiv a^2+2^{n+1}2^{n-1}+a\times 2^{n+1} \mod 2^{n+1}\\
x^2 \equiv a^2 \mod 2^{n+1}.
\end{align*} 

Comme $a^2=1$ vous obtenez encore $x^2\equiv 1 \mod 2^{n+1}.$

Vous avez démontré ce qui suit :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n+1}) \impliedby (\exists u\in\left\{-1,1, -1+2^{n}, 1+2^{n}\right\}, x\equiv u \mod 2^{n+1}).

De ces deux implications, il en résulte que $\mathscr{P}(n+1)$ est vraie.

Conclusion. Par récurrence vous avez montré que pour tout entier $n$ supérieur ou égal à $3$, vous avez :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n}) \Longleftrightarrow (\exists u\in\left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}, x\equiv u \mod 2^{n}).

Comme l’entier $k$ est supérieur ou égal à $3$, le résultat final est ainsi établi :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2^{k}) \Longleftrightarrow (\exists a\in\left\{-1,1, -1+2^{k-1}, 1+2^{k-1}\right\}, x\equiv a \mod 2^{k}).}

Dans le contenu rédigé dans l'article 352 une méthode permettant de résoudre une équation linéaire avec congruences a été développée.

Sera présentée ici une méthode alternative qui ne fait pas appel au $PGCD$ directement.

Soit $a$ un entier naturel non nul, $b$ un entier relatif et $n$ un entier naturel non nul.

Vous souhaitez résoudre l’équation suivante d’inconnue $x$ entière :

ax\equiv b\mod n.

Remarquez que vous pouvez remplacer $a$ et $b$ respectivement par leurs résidus modulo $n.$

Autrement dit, dans la suite, vous supposez que $a$ est un entier naturel non nul strictement inférieur à $n$, que $b$ est un entier naturel strictement inférieur à $n.$

Le théorème fondamental

Vous effectuez la division euclidienne de $n$ par $a$, il existe un quotient $q\in\N$ et un reste $r\in\N$ avec $0\leq r \leq a-1$ tels que $n = aq+r.$

Vous allez établir que l’équation $ax\equiv b\mod n$ d’inconnue $x\in\Z$ admet au moins une solution, si et seulement si, l’équation $ry \equiv -b \mod a$ d’inconnue $y\in \Z$ admet au moins une solution.

Premier sens

Soit $x\in\Z$ tel que $ax\equiv b \mod n.$

Il existe un entier relatif $k$ tel que $ax = b+ nk.$ Vous remplacez $n$ par $aq+r$ du coup :

\begin{align*}
ax &= b +(aq+r)k\\
ax &= b +aqk+rk\\
a(x-qk) - b &= rk.
\end{align*}

Cela prouve que $rk \equiv -b \mod a.$

Donc l’équation $ry \equiv -b \mod a$ d’inconnue $y\in \Z$ admet au moins une solution qui est $k.$

Second sens

Soit $y\in\Z$ tel que $ry \equiv -b \mod a.$

Il existe un entier relatif $t$ tel que $ry = -b+at.$ Vous utilisez le fait que $r = n-aq$ ce qui fournit :

\begin{align*}
(n-aq)y = -b+at\\
ny-aqy = -b+at\\
ny+b = a(t+qy).
\end{align*}

Cela prouve que $a(t+qy) \equiv b \mod n.$ Or, $t+qy\in\Z.$

Donc l’équation $ax\equiv b\mod n$ d’inconnue $x\in\Z$ admet au moins une solution qui est $t+qy.$

Déduisez une solution de l’équation $ax\equiv b\mod n$ à partir d’une solution de l’équation $ry\equiv -b\mod a$

Soit $y$ un entier relatif tel que $ry\equiv -b \mod a.$

Alors $a$ divise $ry+b.$ Donc $t = \frac{ry+b}{a}$ est un nombre entier et $ry = -b+at.$

D’après le calcul effectué à la section précédente, si vous posez $x = t+qy$, alors $x$ est un entier relatif et $ax\equiv b\mod n.$

Vous trouvez maintenant une expression de $x$ qui ne fait pas intervenir le quotient $q.$ En effet :

\begin{align*}
x &= t+qy\\
&=\frac{ry+b}{a}+\frac{aqy}{a}\\
&=\frac{(aq+r)y+b}{a}\\
&=\frac{ny+b}{a}.
\end{align*}

Vous utiliserez dans la suite :

\boxed{x=\frac{ny+b}{a}.}

En définitive, si $k$ est une solution de l’équation $ry \equiv -b \mod a$, alors $\frac{nk+b}{a}$ est une solution de l’équation $ax\equiv b\mod n.$

Note. Au passage, comme $x$ est un entier relatif, vous constatez que le nombre $a$ divise $ny+b.$ Cela peut se voir depuis le début. Comme $ry\equiv -b \mod a$ vous avez $(n-aq)y \equiv -b \mod a$ si bien que $ny\equiv -b \mod a$ et $ny+b\equiv 0 \mod a.$

Application

L’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z$ admet-elle au moins une solution ? Si oui, en déterminer une.

Vous appliquez le théorème fondamental précité pour le savoir.

Vous effectuez la division euclidienne de $231$ par $143.$ Comme $231 = 1\times 143+88$ Vous trouvez un reste égal à $88.$

Il s’agit maintenant de savoir si l’équation $88 y_1\equiv -44 \mod 143$ d’inconnue $y_1\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $143$ par $88.$ Comme $143 = 1\times 88+55$ Vous trouvez un reste égal à $55.$

Il s’agit maintenant de savoir si l’équation $55 y_2 \equiv 44 \mod 88$ d’inconnue $y_2\in\Z$ admet au moins une solution.

En divisant par $11$ cette équation est équivalente à $5y_2\equiv 4 \mod 8.$

Vous effectuez la division euclidienne de $8$ par $5.$ Comme $8 = 1\times 5+3$ Vous trouvez un reste de $3.$

Il s’agit maintenant de savoir si l’équation $3 y_3 \equiv -4 \mod 5$ d’inconnue $y_3\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $5$ par $3.$ Comme $5= 1\times 3+2$ Vous trouvez un reste de $2.$

Il s’agit maintenant de savoir si l’équation $2 y_4 \equiv 4 \mod 3$ d’inconnue $y_4\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $3$ par $2.$ Comme $3= 1\times 2+1$ Vous trouvez un reste de $1.$

Vous tombez alors sur l’équation $y_5 \equiv -4 \mod 2$ d’inconnue $y_5\in\Z$ qui admet au moins une solution, il suffit de prendre $y_5 = 0.$ Il s’ensuit que toutes les équations précitées admettent au moins une solution. Pour chacune d’entre elles, vous en calculez une.

Il vient successivement :

\begin{align*}
y_4 &= \frac{3y_5+4}{2} = \frac{4}{2} = 2
\\
y_3 &= \frac{5y_4-4}{3} = \frac{10-4}{3} = 2
\\
y_2 &= \frac{8y_3+4}{5} = \frac{16+4}{5} = 4
\\
y_1 &= \frac{143y_2-44}{88} = \frac{572-44}{88} = \frac{528}{88} = 6
\\
x&=\frac{231y_1+44}{143} = \frac{1386+44}{143}=10.
\end{align*} 

En définitive, $10$ est une solution de l’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z.$

Prolongement

Déterminez toutes les solutions de l’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z$ en les décrivant modulo $231.$

Cet exposé complète 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 :

\forall (x,y)\in A^2,  (x \equiv y \mod n) \implies x=y.

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$, il existe un unique $a\in A$ tel que $x\equiv a \mod n.$ »

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

$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$, 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<\cdots<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.$ Or, cela est une contradiction.

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. Utilisant le principe des tiroirs, vous déduisez qu’il existe $(i,j)\in\llbracket 1, n\rrbracket ^2$ tel que $i<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$, cela implique $a_i=a_j.$ Or $i<j$ donc $a_i < a_j$ d’où une contradiction.

Il a été démontré que :

\forall x\in \Z, \exists a\in A, x\equiv a\mod n.

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

\begin{align*}
x\equiv a\mod n\\
x\equiv a' \mod n.
\end{align*}

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

Ainsi :

\forall x\in \Z, \exists !a\in A, x\equiv a\mod n.

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

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.