Modular Arithmetic

Introduction

Modular arithmetic is a fundamental concept in number theory that deals with remainders when dividing integers. It's often described as "clock arithmetic" because it wraps around after reaching a certain value, just like how a 12-hour clock works. After 12, we start back at 1 instead of continuing to 13, 14, etc.

In programming, modular arithmetic is incredibly useful for:

• Hashing functions
• Cryptography algorithms
• Random number generation
• Solving problems with cyclic patterns
• Preventing integer overflow

This guide will explain modular arithmetic from the ground up and show how to implement it in code.

The Basics of Modular Arithmetic

What is the Modulo Operation?

The modulo operation finds the remainder after division of one number by another. We write:

$a \bmod m$

Which means "a modulo m" - the remainder when a is divided by m.

For example:

• 7 mod 3 = 1 (7 ÷ 3 = 2 with remainder 1)
• 15 mod 4 = 3 (15 ÷ 4 = 3 with remainder 3)
• 20 mod 5 = 0 (20 ÷ 5 = 4 with remainder 0)

In most programming languages, this operation is represented by the % operator:

python

print(7 % 3)  # Output: 1
print(15 % 4)  # Output: 3
print(20 % 5)  # Output: 0

Congruence Relation

We say that two numbers a and b are congruent modulo m if they have the same remainder when divided by m.

We write this as:

$a \equiv b \pmod{m}$

For example:

• 7 ≡ 1 (mod 3) because both 7 and 1 leave remainder 1 when divided by 3
• 15 ≡ 3 (mod 4) because both 15 and 3 leave remainder 3 when divided by 4
• 20 ≡ 0 (mod 5) because both 20 and 0 leave remainder 0 when divided by 5

In code, we can check if two numbers are congruent modulo m:

python

def are_congruent(a, b, m):
    return a % m == b % m

print(are_congruent(7, 1, 3))  # Output: True
print(are_congruent(15, 3, 4))  # Output: True
print(are_congruent(20, 0, 5))  # Output: True
print(are_congruent(8, 3, 5))  # Output: False

Properties of Modular Arithmetic

Modular arithmetic follows several important properties that make it useful in algorithms:

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$

python

def modular_add(a, b, m):
    return (a % m + b % m) % m

def modular_subtract(a, b, m):
    return (a % m - b % m) % m

print(modular_add(14, 23, 10))  # Output: 7
print(modular_subtract(14, 23, 10))  # Output: 1

2. Multiplication

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

python

def modular_multiply(a, b, m):
    return (a % m * b % m) % m

print(modular_multiply(15, 18, 7))  # Output: 4

3. Exponentiation

Computing large powers efficiently using modular arithmetic:

python

def modular_power(base, exponent, modulus):
    if modulus == 1:
        return 0
    
    result = 1
    base = base % modulus
    
    while exponent > 0:
        # If exponent is odd, multiply result with base
        if exponent % 2 == 1:
            result = (result * base) % modulus
        
        # Exponent is even, square the base
        exponent = exponent >> 1  # Divide exponent by 2
        base = (base * base) % modulus
    
    return result

print(modular_power(2, 10, 1000))  # Output: 24
print(modular_power(3, 100, 1000))  # Output: 343

This algorithm is much more efficient than computing the full power and then taking modulo, especially for large exponents.

Modular Inverse

The modular inverse of a number a with respect to modulo m is another number x such that:

$a \times x \equiv 1 \pmod{m}$

The modular inverse exists if and only if a and m are coprime (their greatest common divisor is 1).

We can compute the modular inverse using the Extended Euclidean Algorithm:

python

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return gcd, y - (b // a) * x, x

def modular_inverse(a, m):
    gcd, x, y = extended_gcd(a, m)
    
    if gcd != 1:
        raise Exception("Modular inverse does not exist")
    else:
        return (x % m + m) % m  # Ensure result is positive

# Example
print(modular_inverse(3, 11))  # Output: 4
# Verification: (3 * 4) % 11 = 1

Solving Congruence Equations

A linear congruence equation has the form:

$ax \equiv b \pmod{m}$

The solution is:

$x \equiv a^{-1}b \pmod{m}$

where $a^{-1}$ is the modular inverse of a.

python

def solve_congruence(a, b, m):
    try:
        a_inv = modular_inverse(a, m)
        return (a_inv * b) % m
    except Exception as e:
        return f"No solution: {e}"

# Solve: 3x ≡ 5 (mod 11)
print(solve_congruence(3, 5, 11))  # Output: 9
# Verification: (3 * 9) % 11 = 5

The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) lets us solve systems of congruence equations:

$x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$ $\vdots$ $x \equiv a_n \pmod{m_n}$

Where all $m_i$ are pairwise coprime.

Here's how to implement it:

python

def chinese_remainder_theorem(remainders, moduli):
    # Ensure inputs are lists
    if not isinstance(remainders, list) or not isinstance(moduli, list):
        raise TypeError("Inputs must be lists")
    
    # Ensure equal length
    if len(remainders) != len(moduli):
        raise ValueError("Number of remainders must equal number of moduli")
    
    # Calculate product of all moduli
    product = 1
    for modulus in moduli:
        product *= modulus
    
    result = 0
    for i in range(len(moduli)):
        partial_product = product // moduli[i]
        inverse = modular_inverse(partial_product, moduli[i])
        result += remainders[i] * partial_product * inverse
    
    return result % product

# Solve the system:
# x ≡ 2 (mod 3)
# x ≡ 3 (mod 5)
# x ≡ 2 (mod 7)
print(chinese_remainder_theorem([2, 3, 2], [3, 5, 7]))  # Output: 23

Practical Applications

1. Hashing Functions

Modular arithmetic is used in hash functions to map data to a fixed-size array:

python

def simple_hash(string, table_size):
    hash_value = 0
    for char in string:
        hash_value = (hash_value * 31 + ord(char)) % table_size
    return hash_value

# Example hash values
print(simple_hash("apple", 100))  # Output: 54
print(simple_hash("banana", 100))  # Output: 32
print(simple_hash("cherry", 100))  # Output: 11

2. Cryptography

Many cryptographic algorithms like RSA use modular arithmetic:

python

def simple_rsa_example():
    # Very simplified RSA example (not secure!)
    p, q = 11, 13
    n = p * q  # Public modulus
    phi = (p-1) * (q-1)
    
    # Public exponent
    e = 7
    
    # Private exponent (modular inverse of e modulo phi)
    d = modular_inverse(e, phi)
    
    # Original message
    message = 9
    
    # Encryption: c = m^e mod n
    ciphertext = modular_power(message, e, n)
    
    # Decryption: m = c^d mod n
    decrypted = modular_power(ciphertext, d, n)
    
    return {
        "public_key": (n, e),
        "private_key": d,
        "message": message,
        "ciphertext": ciphertext,
        "decrypted": decrypted
    }

result = simple_rsa_example()
print(f"Message: {result['message']}")
print(f"Encrypted: {result['ciphertext']}")
print(f"Decrypted: {result['decrypted']}")

3. Clock Problems

Modular arithmetic can help solve time-related problems:

python

def what_time_is_it(current_hour, hours_ahead):
    return (current_hour + hours_ahead) % 12 or 12

# If it's 10 o'clock now, what time will it be in 5 hours?
print(what_time_is_it(10, 5))  # Output: 3

4. Cyclic Phenomena

Many natural and programming problems involve cycles:

python

def day_of_week(start_day, days_ahead):
    days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
    start_index = days.index(start_day)
    return days[(start_index + days_ahead) % 7]

# If today is Wednesday, what day will it be 10 days from now?
print(day_of_week("Wednesday", 10))  # Output: Saturday

Common Pitfalls and Tips

Negative Numbers in Modular Arithmetic

In mathematics, the result of a modulo operation is always between 0 and m-1. However, some programming languages (like C and C++) might return negative results for negative inputs.

python

# Python handles negative modulo correctly
print(-7 % 3)  # Output: 2 (not -1)

# To ensure consistent behavior across languages:
def positive_modulo(n, m):
    return ((n % m) + m) % m

print(positive_modulo(-7, 3))  # Output: 2

Modular Arithmetic with Large Numbers

When dealing with very large numbers, direct computation might cause overflow. Use the properties of modular arithmetic to keep intermediate results small:

python

def large_modular_power(base, exponent, modulus):
    """
    Compute (base^exponent) % modulus efficiently 
    even for very large exponents
    """
    return modular_power(base, exponent, modulus)

# Computing 3^1000000 % 1000000007
print(large_modular_power(3, 1000000, 1000000007))

Summary

Modular arithmetic is a powerful mathematical tool with numerous applications in computer science and programming:

• It provides a way to handle cyclic structures and operations
• It's fundamental for hashing, cryptography, and number theory algorithms
• It helps prevent integer overflow when dealing with large numbers
• Its properties allow for efficient computation of otherwise intractable problems

By understanding modular arithmetic, you can solve a wide range of programming problems more efficiently and implement important algorithms in fields like cryptography and data structures.

Exercises

1. Write a function to find the last digit of 2^n for any n.
2. Implement a function to determine if a year is a leap year using modular arithmetic.
3. Write a program that uses the Chinese Remainder Theorem to solve a system of three congruence equations.
4. Implement a function to compute the modular multiplicative inverse using Fermat's Little Theorem.
5. Create a simple hash table implementation using modular hashing.

Additional Resources

• Number Theory for Competitive Programming
• Khan Academy's Modular Arithmetic Course
• Book: "A Computational Introduction to Number Theory and Algebra" by Victor Shoup
• Book: "Concrete Mathematics" by Graham, Knuth, and Patashnik

By mastering modular arithmetic, you'll have a powerful tool in your programming toolkit that will help you solve many complex problems elegantly and efficiently.