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.05em} \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} [n] \Longleftrightarrow \exists (q, q') \in \hspace{0.05em} \mathbb{N}^2, \enspace \exists R \in \hspace{0.05em} \mathbb{N}, \enspace 0 \leqslant R < n, \ \Biggl \{ \begin{align*} a = nq + R \\ b= nq' + R \end{align*} $$
$$ \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, \enspace n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow n/(a -b) $$
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv 0\hspace{0.2em} [n] \Longleftrightarrow n/a $$
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv a \hspace{0.2em} [n] $$
$$ \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow b \equiv a \hspace{0.2em} [n] $$
$$ \forall (a, b, c) \in \hspace{0.05em} \mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ b \equiv c \hspace{0.2em} [n] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv c \hspace{0.2em} [n] $$
$$ \forall (a, b, d) \in \hspace{0.05em} \mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ d/n \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} [d] $$
$$ \forall (a, b, a', b') \in \hspace{0.05em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \Longleftrightarrow $$
$$ \enspace \Biggl \{ \begin{gather*} a + a' \equiv b + b' \hspace{0.2em} [n] \\ a - a' \equiv b - b' \hspace{0.2em} [n] \end{gather*}$$
$$ \forall (a, b, a', b') \in \hspace{0.05em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a a' \equiv b b' \hspace{0.2em} [n] $$
Simplification par un nombre premier avec le diviseur
$$ \forall (a, b, \lambda) \in \hspace{0.05em}\mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a\lambda \equiv b\lambda \hspace{0.2em} [n] \\ \lambda \wedge n = 1 \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} [n]$$
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.
$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall k \in \mathbb{N}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} [n] \hspace{0.2em} \Longrightarrow \hspace{0.2em} a^k \equiv b^k \hspace{0.2em} [n]$$
Soit \((a, b) \in \hspace{0.05em}\mathbb{Z}^2 \) deux entiers relatifs, \( n \in \mathbb{N^*} \) un entier naturel non nul.
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.05em}\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')} _\text{ \( \in \mathbb{Z} \)}$$
Et donc \( n/(b-a) \).
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\).
À partir des deux implications précédentes, il en résulte une équivalence,
$$ \forall (a, b) \in \hspace{0.05em} \mathbb{Z}^2, \enspace n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow n/(a -b) $$
De même, on aura :
$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow n/(b-a) $$
Soit \(a \in \hspace{0.05em}\mathbb{Z}\) un entier relatif, et \( n \in \mathbb{N^*} \) un entier naturel non nul.
Si \( a \equiv 0 \hspace{0.2em} [n] \), 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/a \).
Soit finalement,
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv 0\hspace{0.2em} [n] \Longleftrightarrow n/a $$
Soit \(a \in \hspace{0.05em}\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} [n] \Longleftrightarrow n/(a -b) $$
Soit en remplaçant \(b\) par \(a\),
$$ a \equiv a \hspace{0.2em} [n] \Longleftrightarrow n/0 $$
Et finalement,
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv a \hspace{0.2em} [n] $$
Soit \((a, b) \in \hspace{0.05em}\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} [n] \Longleftrightarrow n/(a -b) $$
De plus :
$$ n/(a - b) \Longleftrightarrow n/(b - a) $$
Soit finalement,
$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow b \equiv a \hspace{0.2em} [n] $$
Soit \((a, b, c) \in \hspace{0.05em} \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} [n] \\ b \equiv c \hspace{0.2em} [n] \end{gather*}\)
Avec l'équivalence de congruence, on a :
$$ \Biggl \{ \begin{gather*} n/(a-b) \\ n/(b-c) \end{gather*} \qquad (3)$$
Or, par la propriété de d'additions des dividendes dans la divisibilité, on sait que :
$$ \forall a \in (\mathbb{Z}^*), \enspace \forall (b , c) \in \hspace{0.05em}\mathbb{Z}^2, $$
$$ a/b \enspace et \enspace a/c \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/(b + c) \qquad (4) $$
Avec les assertions \( (3) \) et \( (4) \), on peut alors dire que comme \( n/(a-b) \) et \( n/(b-c) \), alors \( n/ \bigl( (a - b) + (b- c) \bigr)\).
Soit que \( n/( a - c)\).
Enfin, par la réciproque de l'équivalence de congruence, on a :
$$ n/(a - c) \Longleftrightarrow a \equiv c \hspace{0.2em} [n] $$
Soit finalement,
$$ \forall (a, b, c) \in \hspace{0.05em} \mathbb{Z}^3 , \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ b \equiv c \hspace{0.2em} [n] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv c \hspace{0.2em} [n] $$
Soit \((a, b, d) \in \hspace{0.05em} \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} [n] \\ d/n \end{gather*}\)
Alors, par l'équivalence de congruence, on a :
$$ \Biggl \{ \begin{gather*} n/(a-b) \\ d/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/b \enspace et \enspace b/c \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c \qquad (6) $$
Avec les assertions \( (5) \) et \( (6) \), on peut alors dire que comme \( d/n\) et \( n/(a - b)\), alors \( d/(a - b)\).
Enfin, par la réciproque de l'équivalence de congruence, on a :
$$ d/(a - b) \Longleftrightarrow a \equiv b \hspace{0.2em} [d] $$
Soit finalement,
$$ \forall (a, b, d) \in \hspace{0.05em} \mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ d/n \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} [d] $$
Soit \((a, b, a', b') \in \hspace{0.05em}\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} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*}\)
Avec l'équivalence de congruence, on a :
$$ \Biggl \{ \begin{gather*} n/(a-b) \\ n/(a'-b') \end{gather*} \qquad (7)$$
Or, par la propriété de d'additions des dividendes dans la divisibilité, on sait que :
$$ \forall a \in (\mathbb{Z}^*), \enspace \forall (b , c) \in \hspace{0.05em}\mathbb{Z}^2, $$
$$ a/b \enspace et \enspace a/c \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/(b + c) \qquad (8) $$
Avec les assertions \( (7) \) et \( (8) \), on peut alors dire que comme \( n/(a-b) \) et \( n/(a - b') \), alors \( n/ \bigl( (a - b) + (a' - b') \bigr)\).
Ou encore que \( n/ \bigl( (a + a') - (b + b') \bigr)\).
Ce qui nous amène à dire que :
$$ a + a' \equiv b + b' \hspace{0.2em} [n] $$
Et finalement,
$$ \forall (a, b, a', b') \in \hspace{0.05em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \Longleftrightarrow $$
$$ \enspace \Biggl \{ \begin{gather*} a + a' \equiv b + b' \hspace{0.2em} [n] \\ a - a' \equiv b - b' \hspace{0.2em} [n] \end{gather*}$$
On peut conclure sur la seconde propriété en utilisant l'équation \( (7') \) à la place de \( (7) \) dans le raisonnement, tel que :
$$ \Biggl \{ \begin{gather*} n/(b-a) \\ n/(b' - a') \end{gather*} \qquad (7')$$
Soit \((a, b, a', b') \in \hspace{0.05em}\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} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \qquad (9)\)
Alors, du couple d'équations \((9)\), on en tire deux autres :
$$ a \equiv b \hspace{0.2em} [n] \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} [n] \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} [n] $$
Soit finalement,
$$ \forall (a, b, a', b') \in \hspace{0.05em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a a' \equiv b b' \hspace{0.2em} [n] $$
Soit \((a, b, \lambda) \in \hspace{0.05em}\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} [n] \qquad (12) \\ \lambda\wedge n = 1 \end{gather*} \)
De l'expression \( (12) \) on tire que :
$$ a\lambda -b\lambda \equiv 0 \hspace{0.2em} [n] $$
$$ \lambda(b-a) \equiv 0 \hspace{0.2em} [n] $$
Soit que :
$$ n / \lambda(b-a) $$
D'après le théorème de Gauss, on sait que :
$$ \forall (a, b, c) \in \hspace{0.05em} \mathbb{Z}^3, $$
$$ a / bc \enspace et \enspace x \wedge n = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c $$
Soit dans notre cas :
$$ n / \lambda(b-a) \enspace et \enspace \lambda \wedge n = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} n /(b-a) $$
Et,
$$ n /(b-a) \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} [n] $$
Soit finalement,
$$ \forall (a, b, \lambda) \in \hspace{0.05em}\mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a\lambda\equiv b\lambda \hspace{0.2em} [n] \\ \lambda \wedge n = 1 \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} [n]$$
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.
Soit \((a, b) \in \hspace{0.05em}\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.05em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a a' \equiv b b' \hspace{0.2em} [n] $$
Alors,
$$ a^2 \equiv b^2 \hspace{0.2em} [n] $$
Mais aussi :
$$ a^3 \equiv b^3 \hspace{0.2em} [n] $$
Et ainsi de suite.
$$ a^k \equiv b^k \hspace{0.2em} [n] $$
Et finalement,
$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall k \in \mathbb{N}, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace a \equiv b \hspace{0.2em} [n] \hspace{0.2em} \Longrightarrow \hspace{0.2em} a^k \equiv b^k \hspace{0.2em} [n]$$
Résolvons l'équation \( (E) \) :
$$ 12x \equiv 3 \hspace{0.2em} [5] \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.05em}\mathbb{Z}^3, \enspace \forall n \in \mathbb{N^*}, $$
$$ \enspace \Biggl \{ \begin{gather*} a\lambda\equiv b\lambda \hspace{0.2em} [n] \\ \lambda \wedge n = 1 \end{gather*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} [n]$$
Ici, \( 3 \wedge 5 = 1\), alors on peut diviser chaque membre par \(3\).
$$ 4x \equiv 1 \hspace{0.2em} [5] \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.05em}\mathbb{Z}^2 , \forall n \in \hspace{0.05em}\mathbb{N}^*, $$
$$aa' \equiv 1 \hspace{0.2em} [n] $$
Le nombre \(4\) convient car .
$$ 4 \times 4 \equiv 1 \hspace{0.2em} [5] \qquad (E') $$
En combinant \((E)\) et \((E')\) :
$$ 4x \equiv 4 \times 4 \hspace{0.2em} [5] \qquad (E'') $$
\( 4 \wedge 5 = 1\), alors on peut diviser chaque membre par \(4\).
$$ x \equiv 4 \hspace{0.2em} [5] \qquad (E'') $$
L'ensemble des solutions de \( (E) \) sont :
$$ \forall k \in \mathbb{Z}, \enspace \mathcal{S} = \Bigl \{x = 5k + 4 \Bigr \} $$
Retour en haut de page
