3.5 Modular arithmetic

Modular arithmetic is a system where integers "wrap around" after reaching a fixed value called the modulus. It's foundational to number theory and abstract algebra, and it shows up constantly in cryptography, computer science, and even everyday tasks like reading a clock.

The core notation is $a \equiv b \pmod{m}$, read as "a is congruent to b modulo m." This means $a$ and $b$ leave the same remainder when divided by $m$. The system works with both positive and negative integers, and it divides all integers into neat groups called equivalence classes based on those remainders.

Fundamentals of modular arithmetic

Definition and notation

Modular arithmetic operates on a finite set of integers that "wrap around" after reaching a specified value called the modulus. Think of a clock: after 12, you don't go to 13, you go back to 1. That's mod 12 in action.

The notation $a \equiv b \pmod{m}$ means that $m$ divides the difference $a - b$. For example, $17 \equiv 2 \pmod{5}$ because $17 - 2 = 15$, and $5$ divides $15$ evenly.

• Integers are grouped into equivalence classes based on their remainders when divided by the modulus
• Negative integers work too: $-3 \equiv 4 \pmod{7}$ because $-3 - 4 = -7$, which is divisible by $7$

Congruence relation

Two integers are congruent modulo $m$ when they share the same remainder upon division by $m$. This congruence relation is actually an equivalence relation because it satisfies three properties:

• Reflexive: $a \equiv a \pmod{m}$ for any integer $a$
• Symmetric: if $a \equiv b \pmod{m}$, then $b \equiv a \pmod{m}$
• Transitive: if $a \equiv b \pmod{m}$ and $b \equiv c \pmod{m}$, then $a \equiv c \pmod{m}$

Because congruence is an equivalence relation, it preserves additive and multiplicative structure. You can add, subtract, or multiply both sides of a congruence and the relationship holds.

Modular equivalence classes

An equivalence class collects all integers that are congruent to each other modulo $m$. Formally:

$[a]_m = \{x \in \mathbb{Z} : x \equiv a \pmod{m}\}$

For mod 3, the equivalence classes are $[0]_3 = \{\ldots, -6, -3, 0, 3, 6, \ldots\}$, $[1]_3 = \{\ldots, -5, -2, 1, 4, 7, \ldots\}$, and $[2]_3 = \{\ldots, -4, -1, 2, 5, 8, \ldots\}$.

• Each class contains infinitely many integers
• The classes partition the integers: every integer belongs to exactly one class, and no two classes overlap
• You can pick any element from a class as its representative, which is what makes modular arithmetic so useful for simplifying calculations

Properties of modular arithmetic

Modular arithmetic shares many algebraic properties with standard arithmetic. These properties give the system a predictable structure that's essential for proofs and applications.

Closure property

Performing addition or multiplication on elements within a modular system always produces a result in the same system.

• Addition: $(a + b) \bmod m$ always falls in the range $[0, m-1]$
• Multiplication: $(a \times b) \bmod m$ also stays within $[0, m-1]$

This guarantees that you never "leave" the system when computing, which is critical for applications like cryptography where you need results to stay within a fixed range.

Associative and commutative properties

Both associativity and commutativity hold for addition and multiplication:

• Associativity:
  • $((a + b) + c) \equiv (a + (b + c)) \pmod{m}$
  • $((a \times b) \times c) \equiv (a \times (b \times c)) \pmod{m}$
• Commutativity:
  • $(a + b) \equiv (b + a) \pmod{m}$
  • $(a \times b) \equiv (b \times a) \pmod{m}$

These let you rearrange terms freely in modular expressions, which is what makes techniques like fast modular exponentiation (square-and-multiply) possible.

Distributive property

Multiplication distributes over addition:

$a \times (b + c) \equiv (a \times b) + (a \times c) \pmod{m}$

This works just like in standard arithmetic and lets you expand or factor modular expressions. It applies to both positive and negative integers within the system.

Identity elements

• Additive identity: $0$, since $a + 0 \equiv a \pmod{m}$ for all $a$
• Multiplicative identity: $1$, since $a \times 1 \equiv a \pmod{m}$ for all $a$

These identities behave the same regardless of the modulus and are essential for defining inverses.

Operations in modular arithmetic

Addition and subtraction

The key rule for modular addition: you can reduce each operand before adding.

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

Subtraction works by adding the additive inverse. The additive inverse of $a$ modulo $m$ is the number $b$ where $a + b \equiv 0 \pmod{m}$. For example, the additive inverse of $3$ mod $7$ is $4$, because $3 + 4 = 7 \equiv 0 \pmod{7}$.

Results always fall within $[0, m-1]$, preserving the cyclic structure. Everyday examples include calculating what day of the week it'll be 10 days from now (mod 7 arithmetic).

Multiplication

Same reduce-first principle applies:

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

This is extremely useful when working with large numbers. For instance, to compute $47 \times 63 \pmod{5}$, you can first reduce: $47 \equiv 2$ and $63 \equiv 3 \pmod{5}$, so the answer is $2 \times 3 = 6 \equiv 1 \pmod{5}$. Much easier than multiplying 2961 and then dividing.

Modular multiplication forms the backbone of many cryptographic algorithms, including RSA encryption.

Exponentiation

Modular exponentiation computes $a^b \bmod m$. For large exponents, you don't compute $a^b$ first and then reduce. Instead, the square-and-multiply algorithm breaks the exponent into binary and repeatedly squares and reduces:

1. Write the exponent $b$ in binary
2. Start with result = 1
3. For each bit (left to right): square the result and reduce mod $m$; if the bit is 1, also multiply by $a$ and reduce mod $m$

This keeps intermediate values small and runs in $O(\log b)$ multiplications, making it feasible to compute things like $7^{256} \bmod 13$ without ever handling astronomically large numbers.

Fermat's Little Theorem (covered below) provides another shortcut for modular exponentiation when the modulus is prime.

Division and multiplicative inverses

Division in modular arithmetic is trickier than the other operations. You can only "divide" by $a$ modulo $m$ when $\gcd(a, m) = 1$ (i.e., $a$ and $m$ are coprime).

The multiplicative inverse of $a$ modulo $m$ is a number $b$ such that $ab \equiv 1 \pmod{m}$. For example, the inverse of $3$ mod $7$ is $5$, because $3 \times 5 = 15 \equiv 1 \pmod{7}$.

• Not every number has a multiplicative inverse. For instance, $2$ has no inverse mod $6$ because $\gcd(2, 6) = 2 \neq 1$
• When the inverse exists, it can be found using the extended Euclidean algorithm
• Multiplicative inverses are essential for solving linear congruences and implementing cryptographic protocols

Applications of modular arithmetic

Cryptography basics

Modular arithmetic is the mathematical engine behind public-key cryptography. In RSA, for example, encryption and decryption both rely on modular exponentiation with very large numbers (hundreds of digits). The security comes from the fact that certain modular operations are easy to perform but extremely hard to reverse, like factoring the product of two large primes.

The Diffie-Hellman key exchange also depends on modular exponentiation, allowing two parties to establish a shared secret over an insecure channel.

Error detection in coding

• ISBN validation: The check digit of a 13-digit ISBN is computed using mod 10 arithmetic, catching common transcription errors
• Credit card numbers: The Luhn algorithm uses mod 10 to verify that a card number hasn't been mistyped
• Cyclic redundancy checks (CRC): These treat data as polynomials and use modular division to detect transmission errors

Calendar systems

Modular arithmetic is natural for anything cyclical. Days of the week repeat every 7 days, so day-of-week calculations are mod 7.

Zeller's congruence is a formula that uses modular arithmetic to determine the day of the week for any date in history. Leap year rules also involve modular checks: a year is a leap year if it's divisible by 4, except for years divisible by 100, unless they're also divisible by 400.

Computer science applications

• Hash functions often use mod to map data to a fixed range of indices (e.g., index = key mod table_size)
• Memory addressing uses modular arithmetic for circular buffers and wrap-around allocation
• Pseudorandom number generators frequently use linear congruential methods: $x_{n+1} = (ax_n + c) \bmod m$

Solving modular equations

Linear congruences

A linear congruence has the form $ax \equiv b \pmod{m}$. Here's how to determine if it's solvable and find the solutions:

1. Compute $d = \gcd(a, m)$
2. If $d$ does not divide $b$, there is no solution
3. If $d$ divides $b$, there are exactly $d$ solutions modulo $m$
4. Divide through by $d$: solve $\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{m}{d}}$
5. Find the multiplicative inverse of $\frac{a}{d}$ modulo $\frac{m}{d}$ (using the extended Euclidean algorithm) and multiply both sides by it

Example: Solve $6x \equiv 4 \pmod{10}$. Here $\gcd(6, 10) = 2$, and $2$ divides $4$, so solutions exist. Dividing through: $3x \equiv 2 \pmod{5}$. The inverse of $3$ mod $5$ is $2$ (since $3 \times 2 = 6 \equiv 1$), so $x \equiv 4 \pmod{5}$. The two solutions mod 10 are $x = 4$ and $x = 9$.

Chinese remainder theorem

The Chinese Remainder Theorem (CRT) solves systems of simultaneous congruences when the moduli are pairwise coprime:

$x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}$

The theorem guarantees a unique solution modulo $m_1 \times m_2 \times \cdots \times m_k$.

Example: Find $x$ such that $x \equiv 2 \pmod{3}$ and $x \equiv 3 \pmod{5}$. Testing values: $x = 8$ works ($8 = 2 \times 3 + 2$ and $8 = 1 \times 5 + 3$). The unique solution mod 15 is $x \equiv 8 \pmod{15}$.

CRT is used in secret sharing schemes, fast Fourier transforms, and for breaking large computations into smaller parallel ones.

Fermat's little theorem

If $p$ is prime and $a$ is not divisible by $p$, then:

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

For example, $2^6 = 64 \equiv 1 \pmod{7}$ (since $7$ is prime and $7 \nmid 2$).

This is powerful for simplifying large exponents. To compute $2^{100} \pmod{7}$: since $2^6 \equiv 1 \pmod{7}$, write $2^{100} = (2^6)^{16} \cdot 2^4 \equiv 1^{16} \cdot 16 \equiv 2 \pmod{7}$.

Fermat's Little Theorem generalizes to Euler's theorem for composite moduli: $a^{\phi(m)} \equiv 1 \pmod{m}$ when $\gcd(a, m) = 1$, where $\phi(m)$ is Euler's totient function. Both results are fundamental to primality testing and RSA cryptography.

Modular arithmetic vs standard arithmetic

Similarities and differences

Both systems share the core algebraic properties: associativity, commutativity, and distributivity all hold. The key differences:

• Standard arithmetic works with the infinite set of integers; modular arithmetic works with a finite set $\{0, 1, 2, \ldots, m-1\}$
• Division is always defined (except by zero) in standard arithmetic, but in modular arithmetic it's only defined when the divisor is coprime to the modulus
• Standard integers have a natural ordering ($3 < 5 < 7$); in modular arithmetic, "less than" and "greater than" don't carry meaningful information
• Modular arithmetic often produces more compact representations, which is why it's so useful computationally

Cyclic nature of modular systems

The defining feature of modular arithmetic is its wrap-around behavior. After $m - 1$, the next value is $0$ again. This creates a cyclic structure, like the hours on a clock.

This cyclic property introduces concepts that don't exist in standard arithmetic, like the order of an element: the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{m}$. It also makes modular arithmetic the natural tool for modeling anything periodic.

Limitations of modular arithmetic

• Not all elements have multiplicative inverses, so division is restricted
• There's no meaningful way to say one residue is "bigger" than another
• Only integers are represented; irrational and real numbers don't fit into the system
• Reducing a number mod $m$ loses information: both $5$ and $12$ become $5$ mod $7$, and you can't recover which original value you started with
• Choosing the wrong modulus can cause collisions (distinct values mapping to the same residue), which matters in applications like hashing

Advanced concepts

Primitive roots

A primitive root modulo $n$ is an integer $g$ whose powers generate every element coprime to $n$. Formally, $g$ is a primitive root mod $n$ if the set $\{g^1, g^2, \ldots, g^{\phi(n)}\}$ modulo $n$ gives all integers from $1$ to $n-1$ that are coprime to $n$.

• Primitive roots exist for all prime moduli, but not for all composite moduli. Specifically, they exist for moduli of the form $1, 2, 4, p^k,$ and $2p^k$ where $p$ is an odd prime.
• The number of primitive roots mod $p$ (for prime $p$) is $\phi(p-1)$
• Primitive roots are central to the Diffie-Hellman key exchange and discrete logarithm problems

Quadratic residues

An integer $a$ is a quadratic residue modulo $n$ if the equation $x^2 \equiv a \pmod{n}$ has a solution. If no solution exists, $a$ is a quadratic non-residue.

For a prime $p$, exactly half of the nonzero residues are quadratic residues and half are non-residues. The Legendre symbol $\left(\frac{a}{p}\right)$ encodes this: it equals $1$ if $a$ is a QR mod $p$, $-1$ if not, and $0$ if $p \mid a$.

Quadratic residues connect to deep results like the law of quadratic reciprocity and have applications in primality testing, factorization, and probabilistic encryption.

Modular exponentiation algorithms

Efficient modular exponentiation is critical for practical cryptography, where exponents can be hundreds of digits long.

• Binary exponentiation (square-and-multiply): Processes the exponent bit by bit, requiring at most $2\log_2(b)$ modular multiplications to compute $a^b \bmod m$
• Montgomery multiplication: Replaces expensive division operations with cheaper bit-shift operations by working in a special "Montgomery form," making repeated modular multiplications faster
• These algorithms are what make RSA and similar systems computationally feasible, and ongoing research continues to optimize them for specific hardware