Avec les congruences, même si l'on a des nombres négatifs dans une équation, on essaie toujours de se ramener à des nombres positifs.
Soient \((a, b) \in \hspace{0.04em} \mathbb{Z}^2\) deux entiers naturels, avec \( a > b\).
On dit que \(a\) est congru \(b\) modulo \(n\), s'ils ont le même reste \(R\) dans la division euclidienne par \(n\).
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow \exists (q, q') \in \hspace{0.04em} \mathbb{N}^2, \enspace \exists R \in \hspace{0.04em} \mathbb{N}, \enspace 0 \leqslant R < n, \ \Biggl \{ \begin{gather*} a = nq + R \\ b= nq' + R \end{gather*} $$
$$ \forall (a, b) \in \hspace{0.04em} \mathbb{Z}^2, \enspace n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid (a - b) $$
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv 0\hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid a $$
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv a \hspace{0.2em} \bigl[ n \bigr] $$
$$ \forall (a, b) \in \hspace{0.04em} \mathbb{Z}^2, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow b \equiv a \hspace{0.2em} \bigl[ n \bigr] $$
$$ \forall (a, b, c) \in \hspace{0.04em} \mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ b \equiv c \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv c \hspace{0.2em} \bigl[ n \bigr] $$
$$ \forall (a, b, d) \in \hspace{0.04em} \mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ d \mid n \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} \bigl[ d \bigr] $$
$$ \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow a + a' \equiv b + b' \hspace{0.2em} \bigl[ n \bigr] $$
$$ \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow a - a' \equiv b - b' \hspace{0.2em} \bigl[ n \bigr] $$
Par conséquent on peut aussi voir cette propriété sous forme de combinaison linéaire,
$$ \forall (\lambda, \mu) \in \hspace{0.04em}\mathbb{Z}^2, \enspace \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow \lambda a + \mu a' \equiv \lambda b + \mu b' \hspace{0.2em} \bigl[ n \bigr] $$
$$ \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a a' \equiv b b' \hspace{0.2em} \bigl[ n \bigr] $$
$$ \forall (a, b, c) \in \hspace{0.04em}\mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \hspace{0.2em} \Longrightarrow \hspace{0.2em} a c \equiv b c \hspace{0.2em} \bigl[ n \bigr] $$
$$ \forall (a, b) \in \hspace{0.04em}\mathbb{Z}^2, \enspace \forall k \in \mathbb{N}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \hspace{0.2em} \Longrightarrow \hspace{0.2em} a^k \equiv b^k \hspace{0.2em} \bigl[ n \bigr]$$
$$ \forall (a, b, \lambda) \in \hspace{0.04em}\mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a\lambda \equiv b\lambda \hspace{0.2em} \bigl[ n \bigr] \\ \lambda \wedge n = 1 \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} \bigl[ n \bigr]$$
On ne peut simplifier une congruence de chaque côté par un nombre, uniquement si ce nombre est premier avec le diviseur de l'équation.
Démonstrations
Soit \((a, b) \in \hspace{0.04em}\mathbb{Z}^2 \) deux entiers relatifs, \( n \in \mathbb{N^*} \) un entier naturel non nul.
-
Implication de gauche à droite
Prenons pour hypothèse que \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
Alors,
$$ \forall (q, q') \in \hspace{0.04em}\mathbb{Z}^2, \enspace \exists R \in \mathbb{N}, \enspace 0 \leqslant R < n, \enspace \Biggl \{ \begin{gather*} a = nq + R \\ b = nq' + R \end{gather*}$$
Soit,
$$ a - b = n\underbrace{(q - q')} _{ \in \hspace{0.1em} \mathbb{Z} }$$
Et donc \( n \mid (a - b) \).
-
Réciproque
Supposons maintenant que \(n\) divise \((a- b)\).
Soit,
$$ a - b = nk \enspace ( k \in \mathbb{Z}) \qquad (1) $$
D'autre part, le nombre \(b\) peut s'écrire sous la forme :
$$ \forall q \in \mathbb{Z}, \enspace \exists R \in \mathbb{N}, \enspace 0 \leqslant R < n, \enspace b = nq + R \qquad (2) $$
On peut injecter \((1)\) dans \((2)\) :
$$ a = n(q + k) + R $$
Soit finalement,
$$ \forall q \in \mathbb{Z}, \enspace \exists R \in \mathbb{N}, \enspace 0 \leqslant R < n, \enspace \Biggl \{ \begin{gather*} a = n(q + k) + R \\ b = nq + R \end{gather*}$$
Donc \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
-
Équivalence
À partir des deux implications précédentes, il en résulte une équivalence,
$$ \forall (a, b) \in \hspace{0.04em} \mathbb{Z}^2, \enspace n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid (a - b) $$
De même, on aura :
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid (b-a) $$
Soit \(a \in \hspace{0.04em}\mathbb{Z}\) un entier relatif, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Si \( a \equiv 0 \hspace{0.2em} \bigl[ n \bigr] \), alors \( a \) n'a pas de reste dans la division euclidienne par \( n \) et s'écrit :
$$ \exists q \in \mathbb{Z}, \enspace a = n q $$
Ce qui montre que \( n \mid a \).
Soit finalement,
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv 0\hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid a $$
Soit \(a \in \hspace{0.04em}\mathbb{Z}\) un entier relatif, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Avec
l'équivalence de congruence
, on sait que :
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid (a - b) $$
Soit en remplaçant \(b\) par \(a\),
$$ a \equiv a \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid 0 $$
Et finalement,
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv a \hspace{0.2em} \bigl[ n \bigr] $$
Soit \((a, b) \in \hspace{0.04em}\mathbb{Z}^2\) deux entiers relatifs, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Avec
l'équivalence de congruence
, on sait que :
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid (a - b) $$
De plus :
$$ n \mid (a - b) \Longleftrightarrow n \mid (b - a) $$
Soit finalement,
$$ \forall (a, b) \in \hspace{0.04em}\mathbb{Z}^2, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow b \equiv a \hspace{0.2em} \bigl[ n \bigr] $$
Soit \((a, b, c) \in \hspace{0.04em} \mathbb{Z}^3 \) trois entiers relatifs, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Si : \(\Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ b \equiv c \hspace{0.2em} \bigl[ n \bigr] \end{gather*}\)
Avec
l'équivalence de congruence
, on a :
$$ \Biggl \{ \begin{gather*} n \mid (a - b) \\ n \mid (b - c) \end{gather*} \qquad (3)$$
Avec les assertions \( (3) \) et \( (4) \), on peut alors dire que comme \( n \mid (a - b) \) et \( n \mid (b - c) \), alors \( n \mid \bigl( (a - b) + (b- c) \bigr)\).
Soit que \( n \mid (a - c)\).
Enfin, par
la réciproque de l'équivalence de congruence
, on a :
$$ n \mid (a - c) \Longleftrightarrow a \equiv c \hspace{0.2em} \bigl[ n \bigr] $$
Soit finalement,
$$ \forall (a, b, c) \in \hspace{0.04em} \mathbb{Z}^3 , \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ b \equiv c \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv c \hspace{0.2em} \bigl[ n \bigr] $$
Soit \((a, b, d) \in \hspace{0.04em} \mathbb{Z}^3 \) trois entiers relatifs, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Si : \( \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ d \mid n \end{gather*}\)
Alors, par
l'équivalence de congruence
, on a :
$$ \Biggl \{ \begin{gather*} n \mid (a - b) \\ d \mid n \end{gather*} \qquad (5) $$
Or, par
la propriété de transitivité de la divisibilité
, on sait que :
$$ \forall (a, b) \in (\mathbb{Z}^*)^2, \enspace \forall c \in \mathbb{Z}, $$
$$ (a \mid b) \text{ et } (b \mid c) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c \qquad (6) $$
Avec les assertions \( (5) \) et \( (6) \), on peut alors dire que comme \( d \mid n\) et \( n \mid (a - b)\), alors \( d \mid (a - b)\).
Enfin, par
la réciproque de l'équivalence de congruence
, on a :
$$ d \mid (a - b) \Longleftrightarrow a \equiv b \hspace{0.2em} \bigl[ d \bigr] $$
Soit finalement,
$$ \forall (a, b, d) \in \hspace{0.04em} \mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ d \mid n \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} \bigl[ d \bigr] $$
Soit \((a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4 \) quatre entiers relatifs, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Si : \(\Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*}\)
Avec
l'équivalence de congruence
, on a :
$$ \Biggl \{ \begin{gather*} n \mid (a - b) \\ n \mid (a'-b') \end{gather*} \qquad (7)$$
Avec les assertions \( (7) \) et \( (8) \), on peut alors dire que comme \( n \mid (a - b) \) et \( n \mid (a - b') \), alors \( n \mid \bigl( (a - b) + (a' - b') \bigr)\).
Ou encore que \( n \mid \bigl( (a + a') - (b + b') \bigr)\).
Ce qui nous amène à dire que :
$$ a + a' \equiv b + b' \hspace{0.2em} \bigl[ n \bigr] $$
Et finalement,
$$ \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow a + a' \equiv b + b' \hspace{0.2em} \bigl[ n \bigr] $$
On peut aussi retrouver la même formule de soustractions en prenant l'équation \( (7') \) à la place \( (7) \) dans le raisonnement, tel que :
$$ \Biggl \{ \begin{gather*} n \mid (b-a) \\ n \mid (b' - a') \end{gather*} \qquad (7') $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow a - a' \equiv b - b' \hspace{0.2em} \bigl[ n \bigr] $$
Par conséquent on peut aussi voir cette propriété sous forme de combinaison linéaire,
$$ \forall (\lambda, \mu) \in \hspace{0.04em}\mathbb{Z}^2, \enspace \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow \lambda a + \mu a' \equiv \lambda b + \mu b' \hspace{0.2em} \bigl[ n \bigr] $$
Soit \((a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4 \) quatre entiers relatifs, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Si : \(\Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \qquad (9)\)
Alors, du couple d'équations \((9)\), on en tire deux autres :
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow \exists (q_a, q_b) \in \mathbb{Z}, \enspace \exists R \in \mathbb{N}, \enspace 0 \leqslant R < n, \enspace \Biggl \{ \begin{gather*} a = nq_a + R \\ b = nq_b + R \end{gather*} $$
$$ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow \exists (k_a, k_b) \in \mathbb{Z}, \enspace \exists R' \in \mathbb{N}, \enspace 0 \leqslant R' < n, \enspace \Biggl \{ \begin{gather*} a' = nk_a + R' \\ b' = nk_b + R' \end{gather*} $$
Par suite,
$$ aa' = (nq_a + R)(nk_a + R') $$
$$ aa' = n^2q_ak_a + nq_aR' + Rnk_a + RR' $$
$$ aa' = n( \underbrace{ nq_ak_a + q_aR' + Rk_a} _\text{ \( \in \mathbb{Z} \) } ) + RR' $$
$$ aa' = nQ + RR' \qquad (10) $$
Idem,
$$ bb' = (nq_b + R)(nk_b + R') $$
$$ bb' = n^2q_bk_b + nq_bR' + Rnk_b + RR' $$
$$ bb' = n( \underbrace{ nq_bk_b + q_bR' + Rk_b} _\text{ \( \in \mathbb{Z} \) } ) + RR' $$
$$ bb' = nQ' + RR' \qquad (11)$$
On remarque que dans \((10)\) et \((11)\), \(aa'\) et \(bb'\) ont le même reste dans la division euclidienne par \(n\).
Par conséquent,
$$ a a' \equiv b b' \hspace{0.2em} \bigl[ n \bigr] $$
Soit finalement,
$$ \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a a' \equiv b b' \hspace{0.2em} \bigl[ n \bigr] $$
Grace à
la propriété de d'addition
, nous savons que :
$$ \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow a + a' \equiv b + b' \hspace{0.2em} \bigl[ n \bigr] $$
Or, si on applique cette propriété avec uniquement deux nombres \(a\) et \(b\), on a :
$$ \forall (a, b) \in \hspace{0.04em}\mathbb{Z}^2, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow a + a \equiv b + b \hspace{0.2em} \bigl[ n \bigr] $$
Soit,
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \Longleftrightarrow 2a \equiv 2b \hspace{0.2em} \bigl[ n \bigr] $$
Par une récurrence directe, on voit bien que :
$$ \forall (a, b, c) \in \hspace{0.04em}\mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \hspace{0.2em} \Longrightarrow \hspace{0.2em} a c \equiv b c \hspace{0.2em} \bigl[ n \bigr] $$
Soit \((a, b) \in \hspace{0.04em}\mathbb{Z}^2 \) deux entiers relatifs, \( k \in \mathbb{N} \) un entier naturel, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
De
la propriété de multiplication des congruences
ci-dessus, on sait que :
$$ \forall (a, b, a', b') \in \hspace{0.04em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a a' \equiv b b' \hspace{0.2em} \bigl[ n \bigr] $$
Alors,
$$ a^2 \equiv b^2 \hspace{0.2em} \bigl[ n \bigr] $$
Mais aussi :
$$ a^3 \equiv b^3 \hspace{0.2em} \bigl[ n \bigr] $$
Et ainsi de suite.
$$ a^k \equiv b^k \hspace{0.2em} \bigl[ n \bigr] $$
Et finalement,
$$ \forall (a, b) \in \hspace{0.04em}\mathbb{Z}^2, \enspace \forall k \in \mathbb{N}, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace a \equiv b \hspace{0.2em} \bigl[ n \bigr] \hspace{0.2em} \Longrightarrow \hspace{0.2em} a^k \equiv b^k \hspace{0.2em} \bigl[ n \bigr]$$
Soit \((a, b, \lambda) \in \hspace{0.04em}\mathbb{Z}^2 \) trois entiers relatifs, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Si : \( \Biggl \{ \begin{gather*} a\lambda \equiv b\lambda \hspace{0.4em} \bigl[ n \bigr] \qquad (12) \\ \lambda\wedge n = 1 \end{gather*} \)
De l'expression \( (12) \) on tire que :
$$ a\lambda -b\lambda \equiv 0 \hspace{0.2em} \bigl[ n \bigr] $$
$$ \lambda(b-a) \equiv 0 \hspace{0.2em} \bigl[ n \bigr] $$
Soit que :
$$ n \mid \lambda(b-a) $$
D'après
le théorème de Gauss
, on sait que :
$$ \forall (a, b, c) \in \hspace{0.04em} \mathbb{Z}^3, $$
$$ (a \mid bc) \text{ et } (a \wedge b = 1) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c \qquad \bigl(\text{Théorème de Gauss} \bigr) $$
Soit dans notre cas :
$$ n \mid \lambda(b-a) \text{ et } \lambda \wedge n = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} n \mid (b - a) $$
Et,
$$ n \mid (b - a) \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} \bigl[ n \bigr] $$
Soit finalement,
$$ \forall (a, b, \lambda) \in \hspace{0.04em}\mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a\lambda\equiv b\lambda \hspace{0.2em} \bigl[ n \bigr] \\ \lambda \wedge n = 1 \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} \bigl[ n \bigr]$$
On ne peut simplifier une congruence de chaque côté par un nombre, uniquement si ce nombre est premier avec le diviseur de l'équation.
Exemple
-
Résolution d'une équation de congruence
Résolvons l'équation \( (E) \) :
$$ 12x \equiv 3 \hspace{0.2em} \bigl[ 5 \bigr] \qquad (E) $$
Dans un premier temps, on peut essayer de simplifier l'équation.
D'après
la propriété de simplification des congruences
vue plus haut :
$$ \forall (a, b, \lambda) \in \hspace{0.04em}\mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a\lambda\equiv b\lambda \hspace{0.2em} \bigl[ n \bigr] \\ \lambda \wedge n = 1 \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} \bigl[ n \bigr]$$
Ici, \( 3 \wedge 5 = 1\), alors on peut diviser chaque membre par \(3\).
$$ 4x \equiv 1 \hspace{0.2em} \bigl[ 5 \bigr] \qquad (E) $$
Ensuite, la méthode consiste à chercher un inverse de \(4\) modulo \(5\).
On dit que \(a\) est inversible modulo \(n\) si et seulement si \(a \wedge n = 1\).
Alors, on appelle \(a'\) l'inverse de \(a\) modulo \(n\), et :
$$ \forall (a, a') \in \hspace{0.04em}\mathbb{Z}^2 , \forall n \in \hspace{0.04em}\mathbb{N}^*, $$
$$aa' \equiv 1 \hspace{0.2em} \bigl[ n \bigr] $$
Le nombre \(4\) convient car :
$$ 4 \times 4 \equiv 1 \hspace{0.2em} \bigl[ 5 \bigr] \qquad (E') $$
En combinant \((E)\) et \((E')\) :
$$ 4x \equiv 4 \times 4 \hspace{0.2em} \bigl[ 5 \bigr] \qquad (E'') $$
\( 4 \wedge 5 = 1\), alors on peut diviser chaque membre par \(4\).
$$ x \equiv 4 \hspace{0.2em} \bigl[ 5 \bigr] \qquad (E'') $$
L'ensemble des solutions de \( (E) \) sont :
$$ \forall k \in \mathbb{Z}, \enspace \mathcal{S} = \Bigl \{x = 5k + 4 \Bigr \} $$
Index
Retour en haut de page