With congruences, even if we have to deal with negative numbers in an equation, we will try to get back to positive numbers.
Let \((a, b) \in \hspace{0.05em} \mathbb{Z}^2\) be two natural numbers, with \( a > b\).
We say that \(a\) and \(b\) are congruent modulo \(n\), if they have the same remainder \(R\) in the Euclidian division by \(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) $$
Congruence between a number and zero
$$ \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] $$
We can simplify a congruence by a number on both sides, only if this number and the divisor are coprime.
$$ \forall (a, b, a', b') \in \hspace{0.05em}\mathbb{Z}^4, \enspace \forall n \in \mathbb{N^*}, $$
$$ \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 a + a' \equiv b + b' \hspace{0.2em} [n] $$
$$ \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 a - a' \equiv b - b' \hspace{0.2em} [n] $$
$$ \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 by a coprime number with the divisor
$$ \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]$$
$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall k \in \mathbb{N}, \enspace \forall n \in \mathbb{N^*}, $$
$$ si \enspace a \equiv b \hspace{0.2em} [n] \hspace{0.2em} \Longrightarrow \hspace{0.2em} a^k \equiv b^k \hspace{0.2em} [n]$$
Recap table of the properties of congruences
Let \((a, b) \in \hspace{0.05em}\mathbb{Z}^2 \) be two integers, and \( n \in \mathbb{N^*} \) a non-zero naturel number.
Let us assume that \(a\) and \(b\) have the same remainder in the Euclidian division by \(n\).
So,
$$ \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*}$$
And,
$$ a - b = n\underbrace{(q - q')} _\text{ \( \in \mathbb{Z} \)}$$
Therefore \( n/(b-a) \).
Let's now assume that \(n\) divides \((a- b)\).
So,
$$ a - b = nk \enspace ( k \in \mathbb{Z}) \qquad (1) $$
On the other hand, the number \(b\) can be written as:
$$ \forall q \in \mathbb{Z}, \enspace \exists R \in \mathbb{N}, \enspace 0 \leqslant R < n, \enspace b = nq + R \qquad (2) $$
We can inject \((1)\) into \((2)\) :
$$ a = n(q + k) + R $$
And finally,
$$ \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*}$$
Thus \(a\) and \(b\) have the same remainder in the Euclidian division by \(n\).
And as a result of both implications,
$$ \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) $$
Likewise, we will also have:
$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow n/(b-a) $$
Let \(a \in \hspace{0.05em}\mathbb{Z}\) be an integer, and \( n \in \mathbb{N^*} \) a non-zero natural number.
If \( a \equiv 0 \hspace{0.2em} [n] \), then \( a \) has no remainder in the Euclidian division by \( n \) and can be written as:
$$ \exists q \in \mathbb{Z}, \enspace a = n q $$
Which shows that \( n/a \).
As a result we get,
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv 0\hspace{0.2em} [n] \Longleftrightarrow n/a $$
Let \(a \in \hspace{0.05em}\mathbb{Z}\) be an integer, and \( n \in \mathbb{N^*} \) a non-zero natural number.
With the congruence equivalence, we know that:
$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow n/(a -b) $$
Then replacing \(b\) by \(a\),
$$ a \equiv a \hspace{0.2em} [n] \Longleftrightarrow n/0 $$
And finally,
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv a \hspace{0.2em} [n] $$
Let \((a, b) \in \hspace{0.05em}\mathbb{Z}^2\) be two integers, and \( n \in \mathbb{N^*} \) a non-zero natural number.
With the congruence equivalence, we know that:
$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow n/(a -b) $$
Moreover:
$$ n/(a - b) \Longleftrightarrow n/(b - a) $$
And finally,
$$ \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] $$
Let \((a, b, c) \in \hspace{0.05em} \mathbb{Z}^3 \) be three integers, and \( n \in \mathbb{N^*} \) a non-zero natural number.
If: \( \Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ b \equiv c \hspace{0.2em} [n] \end{gather*}\)
With the congruence equivalence, we do have this:
$$ \Biggl \{ \begin{gather*} n/(a-b) \\ n/(b-c) \end{gather*} \qquad (3)$$
Now, by the addition of the dividends property in divisibility, we know that :
$$ \forall a \in (\mathbb{Z}^*), \enspace \forall (b , c) \in \hspace{0.05em}\mathbb{Z}^2, $$
$$ a/b \enspace and \enspace a/c \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/(b + c) \qquad (4) $$
With the assertions \( (3) \) et \( (4) \), we can say that as \( n/(a-b) \) and \( n/(b-c) \), so \( n/ \bigl( (a - b) + (b- c) \bigr)\).
And in other words: \( n/( a - c)\).
Finally, by the congruence equivalence reciprocal, we do have this:
$$ n/(a - c) \Longleftrightarrow a \equiv c \hspace{0.2em} [n] $$
As a result we get,
$$ \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] $$
Let \((a, b, d) \in \hspace{0.05em} \mathbb{Z}^3 \) three integers, and \( n \in \mathbb{N^*} \) a non-zero natural number.
If: \(\Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ d/n \end{gather*}\)
Then, by the congruence equivalence, we do have this:
$$ \Biggl \{ \begin{gather*} n/(a-b) \\ d/n \end{gather*} \qquad (5) $$
Now, by the transitivity property in divisibility, we know that:
$$ \forall (a, b) \in (\mathbb{Z}^*)^2, \enspace \forall c \in \mathbb{Z}, $$
$$ a/b \enspace and \enspace b/c \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/c \qquad (6) $$
With the assertions \( (5) \) and \( (6) \), we can say that as \( d/n\) and \( n/(a - b)\), so \( d/(a - b)\).
Finally, by the congruence equivalence reciprocal, we do have this:
$$ d/(a - b) \Longleftrightarrow a \equiv b \hspace{0.2em} [d] $$
As a result we get,
$$ \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] $$
Let \((a, b, a', b') \in \hspace{0.05em}\mathbb{Z}^4 \) be four integers, and \( n \in \mathbb{N^*} \) a non-zero natural number.
If: \(\Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*}\)
With the congruence equivalence, we do have this:
$$ \Biggl \{ \begin{gather*} n/(a-b) \\ n/(a'-b') \end{gather*} \qquad (7)$$
Now, by the addition of the dividends property in divisibility, we know that :
$$ \forall a \in (\mathbb{Z}^*), \enspace \forall (b , c) \in \hspace{0.05em}\mathbb{Z}^2, $$
$$a/b \enspace and \enspace a/c \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/(b + c) \qquad (8) $$
With the assertions \( (7) \) and \( (8) \), wan can say that as \( n/(a-b) \) and \( n/(a - b') \), so \( n/ \bigl( (a - b) + (a' - b') \bigr)\).
Or even that: \( n/ \bigl( (a + a') - (b + b') \bigr)\).
That leads us to say that:
$$a + a' \equiv b + b' \hspace{0.2em} [n]$$
And finally,
$$ \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*}$$
And also as a consequence of it,
$$ \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] $$
We can also find the minus equation using the equation \( (7') \) instead of \( (7) \) in the reasoning, such as:
$$ \Biggl \{ \begin{gather*} n/(b-a) \\ n/(b' - a') \end{gather*} \qquad (7')$$
Let \((a, b, a', b') \in \hspace{0.05em}\mathbb{Z}^4 \) be four integers, et \( n \in \mathbb{N^*} \) a non-zero natural number.
If: \(\Biggl \{ \begin{gather*} a \equiv b \hspace{0.2em} [n] \\ a' \equiv b' \hspace{0.2em} [n] \end{gather*} \qquad (9)\)
Then from the pair of equations \((9)\), we can dig two others out:
$$ 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*} $$
Consequently,
$$ 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)$$
We notice that in \((10)\) and \((11)\), \(aa'\) and \(bb'\) have the same remainder in the Euclidian division by \(n\).
Thus,
$$ a a' \equiv b b' \hspace{0.2em} [n] $$
As a result,
$$ \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] $$
Let \((a, b, \lambda) \in \hspace{0.05em}\mathbb{Z}^2 \) three integers, and \( n \in \mathbb{N^*} \) a non-zero natural number.
If: \( \Biggl \{ \begin{gather*} a\lambda \equiv b\lambda \hspace{0.4em} [n] \qquad (12) \\ \lambda\wedge n = 1 \end{gather*} \)
From the expression \( (12) \) we do have this:
$$ a\lambda -b\lambda \equiv 0 \hspace{0.2em} [n] $$
$$ \lambda(b-a) \equiv 0 \hspace{0.2em} [n] $$
So that:
$$ n / \lambda(b-a) $$
According to Gauss' theorem, we know that:
$$ \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 $$
Or in our case:
$$ n / \lambda(b-a) \enspace et \enspace \lambda \wedge n = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} n /(b-a) $$
Thus,
$$ n /(b-a) \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} [n] $$
Finally we get,
$$ \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]$$
We can simplify a congruence by a number on both sides, only if this number and the divisor are coprime.
Let \((a, b) \in \hspace{0.05em}\mathbb{Z}^2 \) two integers, \( k \in \mathbb{N} \) a natural number, and \( n \in \mathbb{N^*} \) a non-zero natural number.
From the multiplication property of the congruences above, we know that:
$$ \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] $$
So,
$$ a^2 \equiv b^2 \hspace{0.2em} [n] $$
But also:
$$ a^3 \equiv b^3 \hspace{0.2em} [n] $$
And so on...
$$ a^k \equiv b^k \hspace{0.2em} [n] $$
As a result we found that,
$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, \enspace \forall k \in \mathbb{N}, \enspace \forall n \in \mathbb{N^*}, $$
$$ si \enspace a \equiv b \hspace{0.2em} [n] \hspace{0.2em} \Longrightarrow \hspace{0.2em} a^k \equiv b^k \hspace{0.2em} [n]$$
Let solve the equation \( (E) \):
$$ 12x \equiv 3 \hspace{0.2em} [5] \qquad (E) $$
First of all, we can try to simplify it.
From the simpliciation property of the congruences seen above:
$$ \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]$$
Here, \( 3 \wedge 5 = 1\), so we can simplify both sides by \(3\).
$$ 4x \equiv 1 \hspace{0.2em} [5] \qquad (E) $$
Then, the method is to find an inverse of \(4\) modulo \(5\).
We say that \(a\) is inversible modulo \(n\) if and only if \(a \wedge n = 1\).
Then, we call \(a'\) the inverse of \(a\) modulo \(n\), and:
$$ \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] $$
The number \(4\) matches because:
$$ 4 \times 4 \equiv 1 \hspace{0.2em} [5] \qquad (E') $$
Combining both \((E)\) and \((E')\):
$$ 4x \equiv 4 \times 4 \hspace{0.2em} [5] \qquad (E'') $$
\( 4 \wedge 5 = 1\), so we can simplify both sides by \(4\).
$$ x \equiv 4 \hspace{0.2em} [5] \qquad (E'') $$
Thus, the set of solutions for \( (E) \) are:
$$ \forall k \in \mathbb{Z}, \enspace \mathcal{S} = \Bigl \{x = 5k + 4 \Bigr \} $$
Go to the top of the page
