Modular Arithmetic

Last updated: December 2024

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

1. Definition of Congruence

Two integers $a$ and $b$ are congruent modulo $m$ if $m$ divides $(a - b)$:

$$a \equiv b \pmod{m} \iff m \mid (a - b)$$

Equivalently: $a = b + km$ for some integer $k$.

2. Properties of Congruences

For integers $a, b, c, d$ and positive integer $m$:

3. Modular Arithmetic Operations

3.1 Addition and Subtraction

$$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$$ $$(a - b) \bmod m = ((a \bmod m) - (b \bmod m)) \bmod m$$

3.2 Multiplication

$$(ab) \bmod m = ((a \bmod m)(b \bmod m)) \bmod m$$

3.3 Exponentiation

For computing $a^n \bmod m$ efficiently, use repeated squaring.

4. Modular Inverses

The modular inverse of $a$ modulo $m$ is an integer $x$ such that:

$$ax \equiv 1 \pmod{m}$$

The inverse exists if and only if $\gcd(a, m) = 1$.

5. Extended Euclidean Algorithm

For integers $a$ and $b$, finds integers $x$ and $y$ such that:

$$ax + by = \gcd(a, b)$$

When $\gcd(a, m) = 1$, this gives us $ax \equiv 1 \pmod{m}$.

6. Euler's Totient Function

$\phi(n)$ counts the positive integers up to $n$ that are coprime to $n$:

$$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

where the product is over all prime divisors of $n$.

7. Euler's Theorem

If $\gcd(a, n) = 1$, then:

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

Fermat's Little Theorem (special case when $n = p$ is prime):

$$a^{p-1} \equiv 1 \pmod{p}$$

8. Chinese Remainder Theorem

For pairwise coprime moduli $m_1, m_2, \ldots, m_k$, the system:

$$x \equiv a_1 \pmod{m_1}$$ $$x \equiv a_2 \pmod{m_2}$$ $$\vdots$$ $$x \equiv a_k \pmod{m_k}$$

has a unique solution modulo $M = m_1 m_2 \cdots m_k$.

9. Quadratic Residues

An integer $a$ is a quadratic residue modulo $p$ if there exists $x$ such that:

$$x^2 \equiv a \pmod{p}$$

Legendre Symbol: For odd prime $p$ and $a$ not divisible by $p$:

$$\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p \\ -1 & \text{if } a \text{ is not a quadratic residue modulo } p \end{cases}$$

10. Wilson's Theorem

A positive integer $p > 1$ is prime if and only if:

$$(p-1)! \equiv -1 \pmod{p}$$

11. Applications

11.1 Cryptography

RSA encryption uses modular exponentiation and the difficulty of computing discrete logarithms.

11.2 Computer Science

Hash functions, pseudorandom number generators, and error-correcting codes.

11.3 Calendar Calculations

Day of the week calculations use modular arithmetic.

12. Code Example

# Python code for modular arithmetic
def gcd(a, b):
    """Euclidean algorithm for GCD"""
    while b:
        a, b = b, a % b
    return a

def extended_gcd(a, b):
    """Extended Euclidean algorithm"""
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def mod_inverse(a, m):
    """Modular inverse of a modulo m"""
    gcd, x, y = extended_gcd(a, m)
    if gcd != 1:
        return None  # Inverse doesn't exist
    return (x % m + m) % m

def mod_exp(base, exp, mod):
    """Fast modular exponentiation"""
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp = exp >> 1
        base = (base * base) % mod
    return result

def chinese_remainder_theorem(remainders, moduli):
    """Solve system of congruences"""
    if len(remainders) != len(moduli):
        return None
    
    # Check if moduli are pairwise coprime
    for i in range(len(moduli)):
        for j in range(i + 1, len(moduli)):
            if gcd(moduli[i], moduli[j]) != 1:
                return None
    
    total = 0
    prod = 1
    for m in moduli:
        prod *= m
    
    for r, m in zip(remainders, moduli):
        p = prod // m
        total += r * mod_inverse(p, m) * p
    
    return total % prod

def euler_totient(n):
    """Euler's totient function"""
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

# Examples
print(f"gcd(48, 18) = {gcd(48, 18)}")
print(f"Inverse of 3 mod 7: {mod_inverse(3, 7)}")
print(f"3^10 mod 7 = {mod_exp(3, 10, 7)}")
print(f"φ(12) = {euler_totient(12)}")

# Chinese Remainder Theorem example
remainders = [2, 3, 2]
moduli = [3, 5, 7]
solution = chinese_remainder_theorem(remainders, moduli)
print(f"CRT solution: {solution}")

13. References