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.04em} \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} \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] $$
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.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] $$
As well, we can also see this property in the form of a linear combination,
$$ \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^*}, $$
$$ si \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]$$
$$ \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]$$
Proofs
Let \((a, b) \in \hspace{0.04em}\mathbb{Z}^2 \) be two integers, and \( n \in \mathbb{N^*} \) a non-zero naturel number.
-
From left to right implication
Let us assume that \(a\) and \(b\) have the same remainder in the Euclidian division by \(n\).
So,
$$ \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*}$$
And,
$$ a - b = n\underbrace{(q - q')} _{ \in \hspace{0.1em} \mathbb{Z} }$$
Therefore \( n \mid (a - b) \).
-
Reciprocal
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\).
-
Equivalence
And as a result of both implications,
$$ \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) $$
Likewise, we will also have:
$$ a \equiv b \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid (b-a) $$
Let \(a \in \hspace{0.04em}\mathbb{Z}\) be an integer, and \( n \in \mathbb{N^*} \) a non-zero natural number.
If \( a \equiv 0 \hspace{0.2em} \bigl[ n \bigr] \), 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 \mid a \).
As a result we get,
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv 0\hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid a $$
Let \(a \in \hspace{0.04em}\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} \bigl[ n \bigr] \Longleftrightarrow n \mid (a - b) $$
Then replacing \(b\) by \(a\),
$$ a \equiv a \hspace{0.2em} \bigl[ n \bigr] \Longleftrightarrow n \mid 0 $$
And finally,
$$ \forall a \in \mathbb{Z}, \enspace \forall n \in \mathbb{N^*}, $$
$$ a \equiv a \hspace{0.2em} \bigl[ n \bigr] $$
Let \((a, b) \in \hspace{0.04em}\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} \bigl[ n \bigr] \Longleftrightarrow n \mid (a - b) $$
Moreover:
$$ n \mid (a - b) \Longleftrightarrow n \mid (b - a) $$
And finally,
$$ \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] $$
Let \((a, b, c) \in \hspace{0.04em} \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} \bigl[ n \bigr] \\ b \equiv c \hspace{0.2em} \bigl[ n \bigr] \end{gather*}\)
With
the congruence equivalence
, we do have this:
$$ \Biggl \{ \begin{gather*} n \mid (a - b) \\ n \mid (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.04em}\mathbb{Z}^2, $$
$$ (a \mid b) \text{ and } (a \mid c) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid (b + c) \qquad (4) $$
With the assertions \( (3) \) et \( (4) \), we can say that as \( n \mid (a - b) \) and \( n \mid (b - c) \), so \( n \mid \bigl( (a - b) + (b- c) \bigr)\).
And in other words: \( n \mid (a - c)\).
Finally, by
the congruence equivalence reciprocal
, we do have this:
$$ n \mid (a - c) \Longleftrightarrow a \equiv c \hspace{0.2em} \bigl[ n \bigr] $$
As a result we get,
$$ \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] $$
Let \((a, b, d) \in \hspace{0.04em} \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} \bigl[ n \bigr] \\ d \mid n \end{gather*}\)
Then, by
the congruence equivalence
, we do have this:
$$ \Biggl \{ \begin{gather*} n \mid (a - b) \\ d \mid 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 \mid b) \text{ and } (b \mid c) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c \qquad (6) $$
With the assertions \( (5) \) and \( (6) \), we can say that as \( d \mid n\) and \( n \mid (a - b)\), so \( d \mid (a - b)\).
Finally, by
the congruence equivalence reciprocal
, we do have this:
$$ d \mid (a - b) \Longleftrightarrow a \equiv b \hspace{0.2em} \bigl[ d \bigr] $$
As a result we get,
$$ \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] $$
Let \((a, b, a', b') \in \hspace{0.04em}\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} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*}\)
With
the congruence equivalence
, we do have this:
$$ \Biggl \{ \begin{gather*} n \mid (a - b) \\ n \mid (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.04em}\mathbb{Z}^2, $$
$$(a \mid b) \text{ and } (a \mid c) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid (b + c) \qquad (8) $$
With the assertions \( (7) \) and \( (8) \), wan can say that as \( n \mid (a - b) \) and \( n \mid (a - b') \), so \( n \mid \bigl( (a - b) + (a' - b') \bigr)\).
Or even that: \( n \mid \bigl( (a + a') - (b + b') \bigr)\).
That leads us to say that:
$$a + a' \equiv b + b' \hspace{0.2em} \bigl[ n \bigr]$$
And finally,
$$ \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] $$
We can also find the minus equation using the equation \( (7') \) instead of \( (7) \) in the reasoning, such as:
$$ \Biggl \{ \begin{gather*} n \mid (b-a) \\ n \mid (b' - a') \end{gather*} \qquad (7') $$
Hence,
$$ \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] $$
As well, we can also see this property in the form of a linear combination,
$$ \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] $$
Let \((a, b, a', b') \in \hspace{0.04em}\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} \bigl[ n \bigr] \\ a' \equiv b' \hspace{0.2em} \bigl[ n \bigr] \end{gather*} \qquad (9)\)
Then from the pair of equations \((9)\), we can dig two others out:
$$ 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*} $$
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} \bigl[ n \bigr] $$
As a result,
$$ \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] $$
Thanks to
the addition property
, we know that:
$$ \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] $$
Now, if apply this property only for two numbers \(a\) and \(b\), we do have:
$$ \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] $$
Thus,
$$ \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] $$
By direct recurrence, we can clearly see that:
$$ \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] $$
Let \((a, b) \in \hspace{0.04em}\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.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] $$
So,
$$ a^2 \equiv b^2 \hspace{0.2em} \bigl[ n \bigr] $$
But also:
$$ a^3 \equiv b^3 \hspace{0.2em} \bigl[ n \bigr] $$
And so on...
$$ a^k \equiv b^k \hspace{0.2em} \bigl[ n \bigr] $$
As a result we found that,
$$ \forall (a, b) \in \hspace{0.04em}\mathbb{Z}^2, \enspace \forall k \in \mathbb{N}, \enspace \forall n \in \mathbb{N^*}, $$
$$ si \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]$$
Let \((a, b, \lambda) \in \hspace{0.04em}\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} \bigl[ n \bigr] \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} \bigl[ n \bigr] $$
$$ \lambda(b-a) \equiv 0 \hspace{0.2em} \bigl[ n \bigr] $$
So that:
$$ n \mid \lambda(b-a) $$
According to
Gauss' theorem
, we know that:
$$ \forall (a, b, c) \in \hspace{0.04em} \mathbb{Z}^3, $$
$$ (a \mid bc) \text{ and } (a \wedge b = 1) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c \qquad \bigl(\text{Gauss' theorem} \bigr) $$
Or in our case:
$$ n \mid \lambda(b-a) \text{ and } \lambda \wedge n = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} n \mid (b - a) $$
Thus,
$$ n \mid (b - a) \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} a \equiv b \hspace{0.2em} \bigl[ n \bigr] $$
Finally we get,
$$ \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]$$
We can simplify a congruence by a number on both sides, only if this number and the divisor are coprime.
Example
-
Solving a congruence equation
Let solve the equation \( (E) \):
$$ 12x \equiv 3 \hspace{0.2em} \bigl[ 5 \bigr] \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.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]$$
Here, \( 3 \wedge 5 = 1\), so we can simplify both sides by \(3\).
$$ 4x \equiv 1 \hspace{0.2em} \bigl[ 5 \bigr] \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.04em}\mathbb{Z}^2 , \forall n \in \hspace{0.04em}\mathbb{N}^*, $$
$$aa' \equiv 1 \hspace{0.2em} \bigl[ n \bigr] $$
The number \(4\) matches because:
$$ 4 \times 4 \equiv 1 \hspace{0.2em} \bigl[ 5 \bigr] \qquad (E') $$
Combining both \((E)\) and \((E')\):
$$ 4x \equiv 4 \times 4 \hspace{0.2em} \bigl[ 5 \bigr] \qquad (E'') $$
\( 4 \wedge 5 = 1\), so we can simplify both sides by \(4\).
$$ x \equiv 4 \hspace{0.2em} \bigl[ 5 \bigr] \qquad (E'') $$
Thus, the set of solutions for \( (E) \) are:
$$ \forall k \in \mathbb{Z}, \enspace \mathcal{S} = \Bigl \{x = 5k + 4 \Bigr \} $$
Index
Back to top