1.5 Linear Congruence
- Last updated
- Sep 5, 2024
- Save as PDF
- Page ID
- 163792
( \newcommand{\kernel}{\mathrm{null}\,}\)
Linear Congruences
Definition: Linear Congruences
A linear congruences in one variable has the form ax≡b(modm), where m∈Z+, a,b∈Z and x∈Z is a variable.
A linear congruence is similar to a linear equation, solving linear congruence means finding all integer x that makes, ax≡b(modm) true. In this case, we will have only a finite solution in the form of x≡(modm). Thus there will be at most $m$ solutions, namely 0,1,…,m−1.
Thus, a linear congruence in one variable x is of the form ax≡b(modm), where a,b∈Z and m∈Z+. This form of linear congruence has at most m solutions.) In this section, we shall assume a(≠0)∈Z.
Method I: We can find the solutions to a linear congruence, by checking all possible 0,1,…,m−1.
Example 1:
Find all solutions to x≡6(mod11), between 0 and 10 inclusive.
Solution
Possible solutions are 0,1,2,…,10. The only solution is 6.
Example 2:
Find all solutions to 2x≡3(mod7), between 0 and 6 inclusive.
Solution
Possible solutions are 0,1,2,…,6. The only solution is 5.
Example 3:
Solve 3x≡1(mod8).
Solution
Possible solutions are 0,1,2,…,7. The only solution is 3.
Example 4
Find all solutions to 3x≡1(mod6), between 0 and 5 inclusive.
Solution
Possible solutions are 0,1,2,3,4,5. In this case 3x(mod6) is 0,3,0,3,0,3. Thus, 3x≡1(mod6) has no solutions.
Example 5:
Solve 2x≡2(mod4).
Solution
Possible solutions are 0,1,2,3. The solutions are 1 and 3.
The following theorems give a criterion for the solvability of ax≡b(modm).
Method II:
Theorem 1
Let m∈Z+ and a,b,c∈Z. If gcd(c,m)=1 and ac≡bc(modm) then a≡b(modm)
- Proof
-
Let m∈Z+ and a,b,c∈Z. Assume that gcd(c,m)=1 and ac≡bc(modm). Since ac≡bc(modm), ac−bc=mn, for n∈Z. Thus (a−b)c=mn. Thus m∣(a−b)c. Since gcd(c,m)=1, m∣(a−b). Hence, a≡b(modm).
Example 6
Solve 3x≡1(mod8).
Solution
We will solve using the above theorem. 3x≡1≡9(mod8). Hence, x≡3(mod8).
Theorem 2
Let m∈Z+ and a,b,c∈Z. Then ac≡bc(modm) if and only if a≡b(modmgcd(c,m))
- Proof
-
TBA
Example 7
Solve 9x≡6(mod24).
Solution
Since gcd(3,24)=3,, 3x≡2(mod8). Thus 3x≡2≡10≡18(mod8). Hence x≡6(mod8).
The above two methods are tedious when the numbers are large.
Theorem 3
Let m∈Z+ and a,b∈Z, with a be non-zero. Then
ax≡b(modm) has a solution if and only if gcd(a,m)|b. Moreover, if x=x0 is a particular solution to this congruence, then the set of all solutions is {x∈Z|x≡x0(modm)}={x0,x0+md,x0+2md,…,x0+(d−1)md}, where d=gcd(a,m).
- Proof
-
TBA
We will see below how to find the solution for a particular case: Using Multiplicative inverse modulo m
Let m∈Z+. Let a∈Z such that a and m are relatively prime. Then there exist integers x and y such that ax+my=1. Then ax≡1(modm). Note that 1 is the multiplicative identity on modm. In this case, x(modm) is the inverse of a(modm).
Theorem 3
If gcd(a,m)=1 then ax≡b(modm) has a unique solution x≡a−1b(modm). Thus, the set of all solutions is {x∈Z|x≡a−1b(modm)}.
- Proof
-
Since gcd(a,m)=1, therefore a has an inverse a^{-1} \mod m. Hence x \equiv a^{-1}b(mod \, m).
Example \PageIndex{8}
Solve 16x \equiv 11 ( mod \,35) .
Solution
Since 16x \equiv 11 ( mod \,35) , x \equiv (16)^{-1}11 ( mod \,35) \equiv (11)(11) ( mod \,35) \equiv 16 ( mod \,35).
The following theorem guides on solving linear congruence. However, we will discuss it after learning the linear Diophantine equations.
Theorem \PageIndex{4}
Let m \in \mathbb{Z}_+ and a,b \in \mathbb{Z}, with a be non-zero. Then, the linear congruence
ax \equiv b(mod\, m) has a solution if and only if \gcd(a,m) |b. Moreover, if x=x_0 is a particular solution to this congruence, then the set of all solutions is \{x \in \mathbb{Z} | x \equiv x_0(mod\, m)\}=\left\{x_0, x_0+\dfrac{m}{d}, x_0+\dfrac{2m}{d},\ldots, x_0+\dfrac{(d-1)m}{d} \right\}, where d=\gcd(a,m).
The Chinese Remainder Theorem
In this section, we will explore solving simultaneous linear congruences.
Theorem \PageIndex{5}
Let a, b \in \mathbb{Z} and n,m \in \mathbb{N} such that \gcd(n,m) = 1. Then there exists x \in \mathbb{Z} such that x \equiv a(mod\, n) and x \equiv b(mod\, m). Moreover x is unique modulo mn.
Example \PageIndex{5}:
Solve x \equiv 2 (mod\, 3) and x \equiv 3 (mod\, 5).
Solution
Since x \equiv 2 (mod\, 3), the possible solutions are 2, 5, 8, 11, 15, \ldots .
Since x \equiv 3 (mod\, 5), the possible solutions are 3, 8, 13, \ldots.
Then x=8. Since any y such that y \equiv 8 (mod\, 15) are also solutions, we have 23, 38, \cdots
Theorem \PageIndex{6}: Chinese Remainder Theorem
Let a_1, \cdots, a_k \in \mathbb{Z} and m_1,\cdots, m_k \in \mathbb{N} such that \gcd(m_i,m_j) = 1, for all i \ne j. Then there exists x \in \mathbb{Z} such that
\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases} .
Moreover x is unique modulo m_1 \ldots m_k.
Note
Solving Congruences, using Chinese Remainder Theorem
Let \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases} .
Then
Step 1: Calculate the product M = m_1 \times m_2 \times \ldots \times m_k.
Step 2: Calculate the Modulus Factors. For each m_i, calculate M_i = \frac{M}{m_i}.
Step 3: Compute the Inverses. For each M_i, compute the modular inverse M_i^{-1} modulo m_i.
Step 4: Combine Solutions. Finally, the solution x to the system of congruences is given by: x = \left( \sum_{i=1}^{k} a_i M_i M_i^{-1} \right) \mod M
We can use the following table to compute all the listed variables.
a_i | m_i | M_i | M_i^{-1} | M |
Example \PageIndex{6}
Solve \begin{cases} x \equiv 3 \pmod{5} \\ x \equiv 1 \pmod{7} \\ x \equiv 6 \pmod{8} \end{cases} .
Answer
a_i | m_i | M_i | M_i^{-1} | M |
3 | 5 | \dfrac{280}{5}=56 | 1 | 280 |
1 | 7 | \dfrac{280}{7}=40 | 3 | 280 |
6 | 8 | \dfrac{280}{8}=35 | 3 | 280 |
First we calculate M=(5)(7)(8) 280. Now we can calculate M_1,M_2 and M_3.
Next we calculate M_1^{-1},M_2^{-1} and M_3^{-1}.
To calculate M_1^{-1}: we need to solve 56x_1 \equiv 1\pmod{5}. Place these values into the table.
Now, x \equiv ((3)(56)(1)+(7)(40(3)+(8)(35)(3)) \pmod{280} \equiv 918 \pmod{280} \equiv 78 \pmod{280}.