9.2 Modular Inverses, Fast Exponentiation, and the Chinese Remainder Theorem

Modular arithmetic preserves addition and multiplication, but not arbitrary division. Whether "division by a" is possible depends on whether a has a multiplicative inverse modulo the chosen modulus.

All variables are integers and moduli are positive. The inverse discussion assumes m≥2; the exponentiation and congruence-merging code also handles modulus 1 explicitly.

Congruence Allows Addition, Subtraction, and Multiplication

If:

a ≡ b (mod m)
c ≡ d (mod m)

then:

a + c ≡ b + d (mod m)
a - c ≡ b - d (mod m)
a × c ≡ b × d (mod m)

This means we can perform arithmetic operations on remainders throughout calculations, avoiding the growth of intermediate values. However, in fixed-width integers, multiplying first may still cause overflow. For very large modular multiplications, arbitrary-precision integers or specialized algorithms are required.

Canceling Factors Conditionally

From:

ac ≡ bc (mod m)

one cannot always conclude a≡b.

Example:

2·1 ≡ 2·3 (mod 4)

Both sides leave a remainder of 2, but 1≢3 (mod 4).

If gcd(c,m)=1, then c has a multiplicative inverse modulo m and can be canceled.

Modular Inverse

The inverse of a modulo m, written a⁻¹, satisfies:

a · a⁻¹ ≡ 1 (mod m)

The inverse exists if and only if:

gcd(a, m) = 1

By Bézout's identity: if ax+my=1, then:

a · x ≡ 1 (mod m)

Thus, x mod m is the modular inverse.

Example: Find the inverse of 3 modulo 11:

4 · 3 - 1 · 11 = 1

Therefore, 3⁻¹≡4 (mod 11).

Linear congruence:

a · x ≡ b (mod m)

Let d=gcd(a,m). A solution exists exactly when d|b, in which case there are exactly d distinct solutions modulo m. Divide the equation and modulus by d; the reduced coefficient is coprime to the reduced modulus. For example, 14x≡8 (mod 30) becomes 7x≡4 (mod 15), giving x≡7 (mod 15): the two classes modulo 30 are 7 and 22.

Fast Modular Exponentiation

Computing a^e mod m should not involve generating a huge a^e. This Python 3 square-and-multiply implementation processes the binary exponent:

def pow_mod(a, e, m):
    if e < 0 or m <= 0:
        raise ValueError("require an integer exponent e >= 0 and modulus m > 0")
    result, base = 1 % m, a % m
    while e:
        if e & 1:
            result = result * base % m
        base = base * base % m
        e //= 2
    return result

print(pow_mod(7, 181, 13))  # 7
print(pow_mod(9, 0, 1))    # 0

The invariant is result × base^e ≡ a^original_exponent (mod m). There are O(log(e+1)) modular multiplications, whose individual big-integer cost must be counted separately. Initializing with 1 % m also gives the canonical remainder for exponent zero and modulus 1. An implementation must consider:

• Whether the exponent allows negative values;
• Whether the modulus is positive;
• Whether multiplication operations may overflow;
• Whether cryptographic use cases require constant-time execution to avoid branching and memory access leaks based on the exponent bits.

Teaching code should not be used directly for key operations.

Since Python 3.8, pow(a, -1, m) supports modular inverses of coprime integers: pow(17, -1, 43) returns 38. Negative exponents are not always defined, and this API does not make the teaching loop constant time.

Fermat and Euler Theorems

If p is prime and p∤a:

a^(p-1) ≡ 1 (mod p)

Euler's theorem generalizes this to the case where n≥1 and gcd(a,n)=1:

a^φ(n) ≡ 1 (mod n)

φ(n) is the count of integers between 1 and n that are coprime to n.

If p is prime:

φ(p) = p - 1

If p,q are distinct primes:

φ(pq) = (p - 1)(q - 1)

The condition gcd(a,n)=1 cannot be omitted. Fermat's little theorem describes a necessary property of primes, but it is not a sufficient criterion: composite numbers can also exhibit the same behavior for certain or all coprime bases.

Chinese Remainder Theorem

For k≥1 moduli m₁,...,m_k, each greater than 1 and pairwise coprime, then the system of congruences:

x≡a₁ (mod m₁)
...
x≡a_k (mod m_k)

has a unique solution modulo:

M=m₁...m_k

We construct the solution as:

M_i = M / m_i
y_i = M_i⁻¹ mod m_i
x = Σ a_i * M_i * y_i mod M

Since M_i y_i is 1 modulo m_i and 0 modulo all other moduli, it acts like a basis vector selecting its corresponding component.

Example:

x≡2 (mod 3)
x≡3 (mod 5)
x≡2 (mod 7)

Solves to:

x≡23 (mod 105)

Non-Coprime Moduli

Two congruences:

x ≡ a (mod m)
x ≡ b (mod n)

have a common solution if and only if:

a ≡ b (mod gcd(m, n))

If a solution exists, it is unique modulo lcm(m,n). The standard "pairwise coprime" version is merely a simpler special case.

Substitute x=a+mk into the second congruence to get mk≡b-a (mod n). Divide by g=gcd(m,n), then invert m/g modulo n/g. This Python 3.8+ implementation returns the canonical remainder and merged modulus, or None for incompatible congruences:

from math import gcd

def merge_crt(a, m, b, n):
    if m <= 0 or n <= 0:
        raise ValueError("moduli must be positive integers")
    g = gcd(m, n)
    if (b - a) % g:
        return None
    reduced = n // g
    k = 0 if reduced == 1 else ((b - a) // g * pow(m // g, -1, reduced)) % reduced
    modulus = m * reduced
    return (a + m * k) % modulus, modulus

x, modulus = merge_crt(2, 3, 3, 5)
print(merge_crt(x, modulus, 2, 7))  # (23, 105)
print(merge_crt(2, 4, 6, 8))       # (6, 8)
print(merge_crt(1, 4, 2, 6))       # None

When n/g=1, the first condition already implies the second, so no inverse is needed for that degenerate modulus. This example merges integer constraints; it does not run a scheduler or cryptographic device.

Engineering Applications and Boundaries

• Phase alignment in multi-cycle scheduling;
• Breaking large integer operations into modular components using coprime moduli and reconstructing the result;
• CRT acceleration in RSA private-key computations;
• Residue number systems and error-correcting codes.

CRT decomposition does not automatically ensure security. Cryptographic implementations must also defend against fault injection and side-channel attacks, and verify computed results, using audited libraries.

Completion Checklist

1. Evaluate 17⁻¹ mod 43;
2. Resolve 14x≡8 (mod 30);
3. Manually compute 7^181 mod 13;
4. Solve a system of three pairwise coprime congruences using the Chinese Remainder Theorem (CRT);
5. Construct a system of congruences that are not coprime and have no solution;
6. Explain why modular exponentiation may still overflow at fixed-width integer multiplication even when using modular arithmetic.

References

• MIT Mathematics for Computer Science

• Python: pow