The properties of congruences

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

Congruence equivalence

$$ a \equiv b \hspace{0.2em} [n] \Longleftrightarrow n/(a -b) $$

Congruence between a number and zero

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

Reflexivity

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

Symmetry

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

Transitivity

Simplification of the divisor

We can simplify a congruence by a number on both sides, only if this number and the divisor are coprime.

Addition

Multiplication

Simplification by a coprime number with the divisor

Powers

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

---

Démonstrations

Congruence equivalence

Let \((a, b) \in \hspace{0.05em}\mathbb{Z}^2 \) be two integers, and \( n \in \mathbb{N^*} \) a non-zero naturel number.

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




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




3. Equivalence

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

Congruence between a number and zero

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:

Which shows that \( n/a \).

As a result we get,

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

Reflexivity

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:

Then replacing \(b\) by \(a\),

And finally,

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

Symmetry

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:

Moreover:

And finally,

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

Transitivity

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

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:

As a result we get,

Simplification of the divisor

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

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:

As a result we get,

Addition

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

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:

And finally,

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

Multiplication

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,

Idem,

We notice that in \((10)\) and \((11)\), \(aa'\) and \(bb'\) have the same remainder in the Euclidian division by \(n\).

Thus,

As a result,

Simplification by a coprime number with the divisor

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:

So that:

Or in our case:

Thus,

Finally we get,

We can simplify a congruence by a number on both sides, only if this number and the divisor are coprime.

Powers

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.

So,

But also:

And so on...

As a result we found that,

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

---

Example

1. Solving a congruence equation

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