Extended Euclidean Algorithm

The Extended Euclidean Algorithm serves as a enhancement to the classic Euclidean method. While the standard algorithm computes only the greatest common divisor (\gcd(a, b)), this variant simultaneously determines the coefficients that express the GCD as a linear combination of the input integers.

For any two integers (a) and (b), the algorithm finds integers (x) and (y) satisfying:

[ax + by = \gcd(a, b)]

These coefficients are known as Bézout coefficients, and the equation is referred to as Bézout's identity. This algorithm plays a crucial role in number theory, particularly in solving linear congruence equations and computing modular multiplicative inverses.

Linear Congruence Equations

A linear congruence has the form:

[ax \equiv b \pmod m]

Here, (a) and (b) are known integers, (x) is the unknown to solve for, and the congruence symbol indicates that both sides yield the same remainder when divided by (m).

The equation asks: find an integer (x) such that (ax) and (b) leave identical remainders when divided by (m). Solutions either exist uniquely (modulo (m)) or not at all, depending on the relationship between (a), (b), and (m).

Algorithm Derivation

The Extended Euclidean Algorithm employs recursion, mirroring the structure of its basic counterpart.

Given non-negative integers (a) and (b) with (a \le b), let (r = a \bmod b). The Euclidean algorithm establishes (\gcd(a, b) = \gcd(b, r)).

From the recursive step:

[bx_1 + ry_1 = \gcd(b, r)]

Since (r = a - \left\lfloor\frac{a}{b}\right\rfloor b), substitution yields:

[\gcd(a, b) = bx_1 + (a - \left\lfloor\frac{a}{b}\right\rfloor b)y_1]

Simplifying:

[\gcd(a, b) = ay_1 + b(x_1 - \left\lfloor\frac{a}{b}\right\rfloor y_1)]

Thus, the Bézout coefficients are (x = y_1) and (y = x_1 - \left\lfloor\frac{a}{b}\right\rfloor y_1).

Implementation

long long modInverse(long long a, long long mod) {
    long long x, y;
    long long g = extendedGcd(a, mod, x, y);
    if (g != 1) return -1;
    return (x % mod + mod) % mod;
}

long long extendedGcd(long long p, long long q, long long &u, long long &v) {
    if (q == 0) {
        u = 1;
        v = 0;
        return p;
    }
    
    long long u1, v1;
    long long gcd = extendedGcd(q, p % q, u1, v1);
    
    u = v1;
    v = u1 - (p / q) * v1;
    
    return gcd;
}

The extendedGcd function returns the GCD while populating u and v with the Bézout coefficients through recursive computation.

Chinese Remainder Theorem

When dealing with systems of congruence equations, the Chinese Remainder Theorem (CRT) provides a powerful solution framework. Historically, this theorem originates from the ancient Chinese mathematical text "Sunzi Suanjing" (The Mathematical Classic of Master Sun), which contains the famous "remainder problem":

Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7.

This classical problem establishes the foundation for solving simultaneous congruences.

Problem Formulation

Given a system of congruences:

[\begin{cases} x \equiv a_1 \pmod m_1\ x \equiv a_2 \pmod m_2\ \vdots\ x \equiv a_n \pmod m_n \end{cases}]

When the moduli (m_1, m_2, \ldots, m_n) are pairwise coprime, CRT guarantees a unique solution modulo (M = m_1 \cdot m_2 \cdot \cdots \cdot m_n).

Solution Approach

For pairwise coprime moduli, the solution follows these steps:

1. Compute the product (M = m_1 \cdot m_2 \cdots m_n)
2. For each equation (i), calculate (M_i = M / m_i)
3. Find the modular inverse (t_i) of (M_i) modulo (m_i) using the Extended Euclidean Algorithm
4. Combine the results: (x = \sum_{i=1}^{n} a_i \cdot M_i \cdot t_i \pmod M)

When moduli are not pairwise coprime, the Extended Euclidean Algorithm helps determine whether a solution exists and computes it accordingly.

Practical Implementation

struct CongruenceSystem {
    std::vector<long long> remainders;
    std::vector<long long> moduli;
    
    long long solve() {
        long long prodMod = 1;
        for (long long m : moduli) {
            prodMod *= m;
        }
        
        long long solution = 0;
        
        for (size_t i = 0; i < remainders.size(); ++i) {
            long long ai = remainders[i];
            long long mi = moduli[i];
            long long Mi = prodMod / mi;
            
            long long inv, tmp;
            extendedGcd(Mi, mi, inv, tmp);
            
            inv = (inv % mi + mi) % mi;
            solution = (solution + ai * Mi * inv) % prodMod;
        }
        
        return (solution + prodMod) % prodMod;
    }
};

This implementation accepts vectors of remainders and moduli, then computes the unified solution using the CRT formula. The result is normalized to ensure a non-negative value within the range ([0, M)).

Usage Example

CongruenceSystem system;
system.remainders = {2, 3, 2};
system.moduli = {3, 5, 7};
long long answer = system.solve();

This solves the classical problem: finding a number that gives remainders 2, 3, and 2 when divided by 3, 5, and 7 respectively.