Loading [MathJax]/extensions/TeX/mathchoice.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.5 Linear Congruence

( \newcommand{\kernel}{\mathrm{null}\,}\)

Linear Congruences

Definition: Linear Congruences

A linear congruences in one variable  has the form axb(modm), where mZ+a,bZ and xZ is a variable.

A linear congruence is similar to a linear equation, solving linear congruence means finding all integer x that makes, axb(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,,m1.

Thus, a linear congruence in one variable x is of the form axb(modm), where a,bZ and mZ+. 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,,m1.

Example 1:

Find all solutions to  x6(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 2x3(mod7), between 0 and 6 inclusive.

Solution

Possible solutions are 0,1,2,,6. The only solution is 5.

Example 3:

Solve 3x1(mod8).

Solution

Possible solutions are 0,1,2,,7. The only solution is 3.

Example 4

Find all solutions to 3x1(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, 3x1(mod6) has no solutions.

Example 5:

Solve 2x2(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 axb(modm).

Method II:

Theorem 1

Let mZ+ and  a,b,cZ. If gcd(c,m)=1 and acbc(modm) then ab(modm)

Proof

Let mZ+ and  a,b,cZ. Assume that gcd(c,m)=1 and acbc(modm). Since acbc(modm), acbc=mn, for nZ. Thus (ab)c=mn. Thus m(ab)c. Since gcd(c,m)=1m(ab). Hence, ab(modm).

Example 6

Solve 3x1(mod8).

Solution

We will solve using the above theorem.  3x19(mod8). Hence,  x3(mod8).

Theorem 2

Let mZ+ and  a,b,cZ. Then acbc(modm) if and only if  ab(modmgcd(c,m))

Proof

TBA

Example 7

Solve 9x6(mod24).

Solution

Since gcd(3,24)=3,3x2(mod8). Thus 3x21018(mod8). Hence x6(mod8).

The above two methods are tedious when the numbers are large.  

Theorem 3

Let  mZ+ and  a,bZ, with a be non-zero. Then

axb(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 {xZ|xx0(modm)}={x0,x0+md,x0+2md,,x0+(d1)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 mZ+.  Let aZ such that a and m are relatively prime. Then there exist integers x and y such that ax+my=1. Then  ax1(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 axb(modm) has a unique solution xa1b(modm). Thus, the set of all solutions is {xZ|xa1b(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}.

 


1.5 Linear Congruence is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.

Support Center

How can we help?