Finding Solutions to a System of Modular Equations

Purpose
The purpose of this activity is give you extra practice solving systems of modular equations using the Chinese Remainder Theorem.

Chinese Remainder Theorem: Let m_1, \dots, m_r \in \mathbb{N} be pairwise coprime and set m:=m_1m_2\cdots m_r. For any choice a_1,\dots, a_r \in \mathbb{Z}, there exists a solution x \in \mathbb{Z} to the system of congruences:

    \begin{align*}x& \equiv a_1 \mod m_1 \\x &\equiv a_2 \mod m_2 \\&\vdots \\x &\equiv a_r \mod m_r\end{align*}


Moreover, if x_0 is a solution then the set of all solutions is equal to x_0 + m\mathbb{Z}.

How Do We Actually Solve?
Step 1: Set n_i=m/m_i, where m=m_1m_2\cdots m_r.

Step 2: Find b_i\in \mathbb{Z}, with b_in_i\equiv 1 \mod m_i, i.e. find the inverse of n_i+m_i\mathbb{Z} in \mathbb{Z}/m_i\mathbb{Z}.

Step 3: Compute x:=a_1b_1n_1 + a_2b_2n_2 + \cdots + a_rb_rn_r, this is the solution.

Example 1
Solve the following system of modular equations:

    \begin{align*}x& \equiv 4 \mod 5 \\x &\equiv 3 \mod 7 \end{align*}


Step 1: Let a_1=4 and m_1=5 and a_2=3 and m_2=7.

    \begin{align*}m&=m_1\cdot m_2= 5\cdot 7 = 35 \\n_1 &= m/m_1=35/5=7 \\n_2 &= m/m_2=35/7=5 \end{align*}


Step 2: Find b_1,b_2 \in \mathbb{Z} such that 7b_1 \equiv 1 \mod 5 and 5b_2 \equiv 1\mod 7. By Fermat’s Little Theorem:

    \begin{align*}b_1=7^{5-2}=7^3=343\equiv 3 \mod 5 \\b_2=5^{7-2}=5^5=3125 \equiv 3 \mod 7\end{align*}


Step 3: The solution is x=4\cdot 3\cdot 7 + 3\cdot 3 \cdot 5 = 129.

Verification:

    \begin{align*}129 = 5(25)+4 &\text{ if and only if } 129 \equiv 4 \mod 5 \\129 = 7(18)+3 & \text{ if and only if } 129 \equiv 3 \mod 5\end{align*}


Therefore, the set of solutions is 129+35\mathbb{Z}=24 + 35\mathbb{Z}.

Example 2
Solve the following system of modular equations:

    \begin{align*}x& \equiv 7 \mod 8 \\x &\equiv 6 \mod 21\end{align*}


Step 1: Let a_1=7 and m_1=8 and a_2=6 and m_2=21.

    \begin{align*}m&=m_1\cdot m_2= 8\cdot 21 = 168 \\n_1 &= m/m_1=168/8=21 \\n_2 &= m/m_2=168/21=8\end{align*}


Step 2: Find b_1,b_2 \in \mathbb{Z} such that 21b_1 \equiv 1 \mod 8 and 8b_2 \equiv 1\mod 21. By applying Bezout’s Theorem,

Step 3: The solution is x=7\cdot 21\cdot (-3) + 6\cdot 8 \cdot 8 = -57.

    \[\begin{array}{rcccc}&&q_i&u_i&v_i \\i=0: &&& 0 & 1 \\i=1: & 21=8(2)+5 & 2 & 1 &-2 \\i=2: & 8=5(1)+3 & 1 & -1 & 3 \\i=3: & 5=3(1)+2 & 1 & 2 &-5 \\i=4: & 3=2(1)+1 & 1 & -3 & 8 \\i=5: & 2=1(2)\end{array}\]


Therefore 1=21(-3)+8(8). Warning: In this case, we obtain both b_1 and b_2, but this is not the case when dealing with more equations.

Verification:

    \begin{align*}-57 = 8(-8)+7 &\text{ if and only if } -57 \equiv 7 \mod 8 \\-57 = 21(-3)+6 & \text{ if and only if } -57 \equiv 6 \mod 21\end{align*}


Therefore, the set of solutions is -57+168\mathbb{Z}=111 + 168\mathbb{Z}.