Les propriétés des congruences

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{gather*} a = nq + R \\ b= nq' + R \end{gather*} $$

Équivalence de congruence

Nombre congru à zéro

Réflexivité

Symétrie

Transitivité

Réduction du diviseur

Addition

Multiplication

Simplification par un nombre premier avec le diviseur

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.

Puissances

Récapitulatif des proriétés des congruences

---

Démonstrations

Équivalence de congruence

Soit \((a, b) \in \hspace{0.05em}\mathbb{Z}^2 \) deux entiers relatifs, \( n \in \mathbb{N^*} \) un entier naturel non nul.

1. 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.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) \).




2. 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\).




3. Équivalence

À 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) $$

Nombre congru à zéro

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 :

Ce qui montre que \( n/a \).

Soit finalement,

Réflexivité

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 :

Soit en remplaçant \(b\) par \(a\),

Et finalement,

Symétrie

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 :

De plus :

Soit finalement,

Transitivité

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)$$

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 :

Soit finalement,

Réduction du diviseur

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) $$

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 :

Soit finalement,

Addition

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)$$

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 :

Et finalement,

$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \Longleftrightarrow a + a' \equiv b + b' \hspace{0.2em} [n] $$

Et aussi, par conséquent,

$$ \enspace \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \Longleftrightarrow a - a' \equiv b - b' \hspace{0.2em} [n] $$

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')$$

Multiplication

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,

Idem,

On remarque que dans \((10)\) et \((11)\), \(aa'\) et \(bb'\) ont le même reste dans la division euclidienne par \(n\).

Par conséquent,

Soit finalement,

Simplification par un nombre premier avec le diviseur

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 :

Soit que :

Soit dans notre cas :

Et,

Soit finalement,

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.

Puissances

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.

Alors,

Mais aussi :

Et ainsi de suite.

Et finalement,

Récapitulatif des proriétés des congruences

---

Exemple

1. Résolution d'une équation de congruence

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 \} $$