French flag English flag
Index des cours

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


Équivalence de congruence

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


Nombre congru à zéro

$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$

$$ a \equiv 0\hspace{0.2em} [n] \Longleftrightarrow n/a $$


Réflexivité

$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$

$$ a \equiv a \hspace{0.2em} [n] $$


Symétrie

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


Transitivité

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


Réduction du diviseur

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


Addition

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


Multiplication

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


Puissances

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


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

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


  3. Réciproque

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


  5. Équivalence

  6. À 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 :

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


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 :

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


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 :

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


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

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


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

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


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

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


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,

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


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 :

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


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.

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


Exemple


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

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

Index des cours
Retour en haut de page