Methods of Solving Congruence Equations (Chinese Remainder Theorem)

Introduction

Congruence equations are mathematical expressions of the form $ ax \equiv b \mod m $, where $ a $, $ b $, and $ m $ are integers. These equations seek solutions $ x $ such that when $ a $ is multiplied by $ x $, the result leaves the same remainder as $ b $ when divided by $ m $. The solution to such equations often relies on number-theoretic principles, with the Chinese Remainder Theorem (CRT) serving as a cornerstone in their resolution. The CRT provides a systematic method for solving systems of congruences where the moduli are pairwise coprime, ensuring the existence of a unique solution modulo the product of the moduli. This article explores the core methods for solving congruence equations, emphasizing the CRT's role and alternative approaches for non-coprime moduli.

Core Content

The Chinese Remainder Theorem

The Chinese Remainder Theorem guarantees that if $ m_1, m_2, \ldots, m_k $ are pairwise coprime positive integers, then for any integers $ a_1, a_2, \ldots, a_k $, there exists a unique solution $ x $ modulo $ m_1m_2\ldots m_k $ to the system of congruences:
$$ \begin{cases} x \equiv a_1 \mod m_1 \ x \equiv a_2 \mod m_2 \ \vdots \ x \equiv a_k \mod m_k \end{cases} $$
This theorem is pivotal in number theory, offering a robust framework for solving systems of modular equations. The proof of the CRT typically involves constructing a solution using the extended Euclidean algorithm, ensuring that the solution is both unique and exists under the given conditions.

Extended Euclidean Algorithm

When the moduli $ m_1, m_2, \ldots, m_k $ are not pairwise coprime, the extended Euclidean algorithm can still be employed to solve congruence equations. This algorithm computes the greatest common divisor (GCD) of two integers and expresses it as a linear combination of the integers. For equations of the form $ ax \equiv b \mod m $, where $ \gcd(a, m) $ divides $ b $, the algorithm provides a method to find solutions. However, it requires careful adjustment of the solution to ensure compatibility across all congruences.

For example, consider solving $ 2x \equiv 3 \mod 7 $. The extended Euclidean algorithm finds that $ 2 \times 5 = 10 \equiv 3 \mod 7 $, so $ x \equiv 5 \mod 7 $. This demonstrates how the algorithm can resolve equations with non-coprime moduli by leveraging the GCD's divisibility condition.

Successive Substitutions

A practical approach for solving congruence equations involves successive substitutions, particularly when the moduli are not coprime. This method involves iteratively reducing the problem by substituting solutions into subsequent congruences. For instance, if solving $ x \equiv a \mod m $ and $ x \equiv b \mod n $, where $ \gcd(m, n) \neq 1 $, one can compute a solution by finding a common residue that satisfies both conditions.

This approach is often used in scenarios where the moduli are not coprime but the system is solvable. By iteratively applying the modulo operation and adjusting the solution, successive substitutions ensure that the final result satisfies all congruences. This method is particularly effective in computational contexts where efficiency is paramount.

Modular Inverses

Modular inverses play a critical role in solving congruence equations of the form $ ax \equiv b \mod m $. The inverse of $ a $ modulo $ m $, denoted $ a^{-1} $, is a number $ x $ such that $ ax \equiv 1 \mod m $. If such an inverse exists, the equation $ ax \equiv b \mod m $ can be solved by multiplying both sides by $ a^{-1} $, yielding $ x \equiv b a^{-1} \mod m $.

The existence of a modular inverse depends on $ \gcd(a, m) = 1 $. When this condition holds, the inverse can be computed using the extended Euclidean algorithm. For example, solving $ 3x \equiv 2 \mod 7 $ involves finding $ 3^{-1} \mod 7 $, which is 5, since $ 3 \times 5 = 15 \equiv 1 \mod 7 $. Multiplying both sides by 5 gives $ x \equiv 10 \equiv 3 \mod 7 $, confirming the solution.

Applications and Significance

The methods discussed—CRT, extended Euclidean algorithm,