# Modular Arithmetic

Arithmetic on remainders after division by a fixed modulus, giving a finite cyclic structure that underpins hashing and cryptography.

**Rests on:** Proof by Induction

**Leads to:** Bloom Filters, Hash Functions, Post-Quantum Cryptography

*Mathematical Foundations · Discrete Mathematics*


## Why learn this

Modular arithmetic allows us to calculate what happens when numbers cycle around a fixed limit rather than growing infinitely. This is vital for systems that must stay within fixed boundaries, such as a digital clock (where hours reset after 12) or computer memory slots (where data is mapped to specific positions). It explains how we can take any large number and reliably find its position in a small, finite set, which is the core mechanism behind secure online communication and efficient data storage.


## The intuition

When you divide a whole number by another, you get a quotient and a remainder. Modular arithmetic ignores the quotient and keeps only the remainder. The divisor is called the modulus.

For example, take 17 divided by 5. Five fits into 17 three times (3 * 5 = 15), leaving a remainder of 2. So, 17 mod 5 = 2.

This creates a cycle of remainders. If the modulus is 5, the possible results are always integers from 0 to 4. Counting up in this system looks like: 0, 1, 2, 3, 4, 0, 1, 2, 3, 4... When you reach the modulus (5), the remainder resets to 0.

Think of a clock with only five positions: 0, 1, 2, 3, 4. If it is at position 3 and you add 2 hours, you move to position 5. But position 5 is equivalent to position 0 in this cycle because 5 divided by 5 leaves a remainder of 0. The clock wraps around. The result is always within the range [0, modulus - 1].


## An analogy

Imagine a circular track with five stations labeled 0, 1, 2, 3, and 4. You start at station 0.

If you move forward 3 steps from station 3, you are doing the calculation 3 + 3 = 6. On a normal number line, you would be at station 6. But this track has only five stations. After station 4, the track loops back to station 0. So, the 5th step lands on station 0, and the 6th step lands on station 1.

Mathematically, we check where 6 lands by dividing it by the cycle length: 6 divided by 5 equals 1 with a remainder of 1. Therefore, 6 mod 5 = 1. The hand ends up at station 1.

Similarly, if you multiply, say 4 times 2, you get 8. On this clock, 8 is too large to be a valid position. We divide 8 by the modulus (5). 8 divided by 5 equals 1 with a remainder of 3. So, 8 mod 5 = 3. The hand lands on station 3.

This analogy breaks down in one way: real clocks usually count 1 through 12, but modular arithmetic counts 0 through (modulus - 1), starting the cycle at zero.


## Definition

Modular arithmetic is a system where numbers wrap around to zero after reaching a fixed value called the modulus, meaning the result of any operation is the remainder when divided by that modulus.

Formally, for integers a and n (where n > 0), a mod n is the unique integer r such that 0 ≤ r < n and there exists an integer q where a = q*n + r.


## How it connects

Modular arithmetic extends basic arithmetic to work within fixed cycles. It is a central topic in Discrete Mathematics, which studies distinct, countable structures rather than continuous ones. It connects directly to Number Theory, the study of integer properties, and Cryptography, which uses these wrapping mechanisms to secure data.


## The mathematics

Modular arithmetic is a system of arithmetic for integers, where numbers 'wrap around' after reaching a certain value, called the modulus. Think of it like a clock. A standard clock has a modulus of 12. If it is 10 o'clock and you add 4 hours, it becomes 2 o'clock, not 14 o'clock. The number wraps around because we only care about the position on the clock face, which ranges from 1 to 12 (or in mathematics, usually 0 to 11).

In this system, we do not look at the total sum or product. We look only at the remainder after division by the modulus.

Definition of Congruence
We say that two integers a and b are congruent modulo m if they leave the same remainder when divided by m. Here, m is a positive integer greater than 1, called the modulus.

To check if a is congruent to b modulo m, we look at their difference, (a - b). If this difference is exactly divisible by m (meaning there is no remainder), then a and b are congruent.

Notation: We write this as:
a ≡ b (mod m)

Read this as: 'a is congruent to b modulo m'.

Example of Congruence:
Let m = 5. Let a = 12 and b = 7.
Calculate the difference: 12 - 7 = 5.
Does 5 divide evenly by 5? Yes, 5 divided by 5 is 1 with remainder 0.
Therefore, 12 ≡ 7 (mod 5).

Another way to see this is to look at the remainders:
12 divided by 5 is 2 with a remainder of 2. So, 12 mod 5 = 2.
7 divided by 5 is 1 with a remainder of 2. So, 7 mod 5 = 2.
Since both have the same remainder (2), they are congruent modulo 5.

The Set of Remainders
When we work modulo m, there are only m possible remainders. These are the numbers:
0, 1, 2, ..., up to m - 1.

For example, if the modulus is 5, the possible remainders are 0, 1, 2, 3, and 4. Any integer you choose will fall into one of these five categories based on its remainder when divided by 5.

Operations in Modular Arithmetic
You can add, subtract, and multiply numbers in modular arithmetic. The rule is simple: perform the operation as usual, then take the remainder of the result divided by m.

Addition:
To add a and b modulo m:
1. Add a and b normally.
2. Divide the sum by m.
3. Take the remainder.

Formula: (a + b) mod m = ((a mod m) + (b mod m)) mod m
This formula tells us we can take the remainders of a and b first, add those small numbers, and then take the remainder of that new sum. The result is the same.

Subtraction:
To subtract b from a modulo m:
1. Subtract b from a normally.
2. Divide the difference by m.
3. Take the remainder.

Note: If the result of the subtraction is negative, we still find the positive remainder. For example, -1 mod 5 is 4, because -1 = (-1 * 5) + 4.

Formula: (a - b) mod m = ((a mod m) - (b mod m)) mod m

Multiplication:
To multiply a and b modulo m:
1. Multiply a and b normally.
2. Divide the product by m.
3. Take the remainder.

Formula: (a × b) mod m = ((a mod m) × (b mod m)) mod m

Division is more complex in modular arithmetic and requires special conditions (specifically, that the number being divided by shares no common factors with the modulus). We will not cover division here.


## A worked example

Let us walk through a complete example using a modulus of 6. This means our possible remainders are 0, 1, 2, 3, 4, and 5.

We will use the numbers 14, 8, and 3.

Step 1: Find the remainder of each number individually.
To work with modular arithmetic easily, we first reduce our large numbers to their remainders modulo 6.

For 14:
Divide 14 by 6. 
6 goes into 14 two times (6 × 2 = 12).
The remainder is 14 - 12 = 2.
So, 14 mod 6 = 2.

For 8:
Divide 8 by 6.
6 goes into 8 one time (6 × 1 = 6).
The remainder is 8 - 6 = 2.
So, 8 mod 6 = 2.

For 3:
Divide 3 by 6.
6 goes into 3 zero times.
The remainder is 3.
So, 3 mod 6 = 3.

Step 2: Check Congruence.
Are 14 and 8 congruent modulo 6?
We check their remainders. 
14 mod 6 = 2.
8 mod 6 = 2.
Since the remainders are identical, 14 ≡ 8 (mod 6).

Alternatively, check the difference:
14 - 8 = 6.
Does 6 divide evenly by 6? Yes. So they are congruent.

Step 3: Perform Addition.
Calculate (14 + 3) mod 6.
Method A: Add first, then reduce.
14 + 3 = 17.
Divide 17 by 6.
6 goes into 17 two times (6 × 2 = 12).
The remainder is 17 - 12 = 5.
Result: 5.

Method B: Reduce first, then add.
14 mod 6 = 2.
3 mod 6 = 3.
Add the remainders: 2 + 3 = 5.
Take the remainder of 5 divided by 6. Since 5 is less than 6, the remainder is 5.
Result: 5.

Both methods give the same result. The sum is congruent to 5 modulo 6.

Step 4: Perform Multiplication.
Calculate (14 × 3) mod 6.
Method A: Multiply first, then reduce.
14 × 3 = 42.
Divide 42 by 6.
6 goes into 42 seven times (6 × 7 = 42).
The remainder is 0.
Result: 0.

Method B: Reduce first, then multiply.
14 mod 6 = 2.
3 mod 6 = 3.
Multiply the remainders: 2 × 3 = 6.
Take the remainder of 6 divided by 6. Since 6 divides evenly into 6, the remainder is 0.
Result: 0.

Both methods give the same result. The product is congruent to 0 modulo 6.

Conclusion:
Modular arithmetic allows us to perform standard operations on integers and then map the results back to a small set of remainders {0, 1, ..., m-1}. The key property is that (a + b) mod m depends only on (a mod m) and (b mod m), not on the original large values of a and b.


## From scratch, in Python

```python
def mod_add(a, b, modulus):
    """Add a and b, then take the remainder when divided by modulus."""
    result = a + b
    while result >= modulus:
        result -= modulus
    return result

def mod_multiply(a, b, modulus):
    """Multiply a and b, then take the remainder."""
    result = 0
    for _ in range(b):  # add a to result, b times
        result = mod_add(result, a, modulus)
    return result

# Example: modulus 6
mod = 6
print(mod_add(14, 3, mod))       # should print 5
print(mod_multiply(14, 3, mod))  # should print 0

# Even simpler: use the built-in modulo operator %
print((14 + 3) % mod)  # 5
print((14 * 3) % mod)  # 0
```


## What the code does

The code defines two functions to perform modular arithmetic without using the % operator.

First, `mod_add` takes two numbers and a modulus. It adds them, then uses a while loop to subtract the modulus repeatedly until the result is smaller than the modulus. This loop is a simple way to compute the remainder, but it's inefficient for large numbers. The built-in `%` operator does the same thing in one step.

Second, `mod_multiply` uses a for loop to add `a` to `result` exactly `b` times, each time reducing modulo the modulus. This shows multiplication as repeated addition, and it also uses `mod_add` to take the remainder after each addition. This prevents the result from ever getting too large.

Finally, the last two print statements show the direct use of the `%` operator, which is the standard, efficient way in Python to get the remainder. The functions illustrate the concept, but in practice you would use `%`.

**Python building blocks introduced:**
- **Function**: a named block of reusable code, defined with `def`. Example: `def mod_add(a, b, modulus):`
- **While loop**: repeats a block as long as a condition is true. Here, it repeats until `result` is less than `modulus`.
- **For loop**: iterates a fixed number of times. Here, it runs `b` times.
- **Return statement**: sends a value back from a function to where it was called.


## Common misconceptions

**Modular arithmetic is only about clocks** — I know it's like a clock, but that's a bit of a toy. Real math doesn't use this.

The clock analogy is a good starting point, but modular arithmetic is a rigorous mathematical structure with deep applications in number theory, cryptography, and computer science. It is not a toy, but a fundamental concept. In fact: Modular arithmetic is a core branch of discrete mathematics. The clock is a simple example, but the concept of congruence classes and modular inverses underpins modern cryptography and hashing algorithms used worldwide.

**The result can be negative** — If I compute -3 mod 5, I should get -3, because -3 divided by 5 is 0 remainder -3.

By definition, the remainder r must be between 0 and m-1 (inclusive). A negative number does not fit this definition. In fact: The remainder is always non-negative. For -3 mod 5, we find the integer k such that -3 = k*5 + r, with 0 <= r < 5. In this case, k = -1, so -3 = -5 + 2, thus r = 2. So -3 mod 5 = 2.

**Modular arithmetic is just for hacking, not for AI** — I'm learning AI, so I don't need to know about number theory. It's only for cryptography.

Modular arithmetic is pervasive in AI, from hashing for fast data access to random number generation and certain positional encoding schemes. In fact: Modular arithmetic is used in hashing (for embeddings and feature engineering), in the initialization of model weights via RNGs, and in specific transformer architectures for positional encodings. It is a fundamental tool for building efficient and scalable AI systems.

**Modular arithmetic is just a trick, not real math** — It's just a shorthand for a computer. It's not a deep concept.

This trivializes the subject. The properties of congruence (reflexive, symmetric, transitive) turn the set of integers into equivalence classes, forming a group, a ring, a field. These structures are the foundation of abstract algebra. In fact: Modular arithmetic is a precise and rigorous branch of mathematics with deep structures. The set of integers modulo m forms a group under addition, and if m is prime, all non-zero elements have multiplicative inverses, forming a finite field.


## In short

Modular arithmetic is the arithmetic of remainders. After dividing any integer by a fixed modulus m, the remainder is always between 0 and m-1. This creates a finite cycle. Two numbers are congruent if they have the same remainder. This simple idea is the backbone of hashing, checksums, and public-key cryptography, and it shows up in AI through efficient data structures and some model components. If you remember one thing, remember: the result of any modular operation is always bounded, and this bounding is what makes it so useful.


## Where this is used

Modular arithmetic is a workhorse across computing and AI systems.

- **Hashing**: A hash function takes an input (like a string 'hello') and returns a number within a fixed range. A common technique is to interpret the input as a large integer and then take its remainder when divided by a prime modulus (e.g., 1000003). Python's built-in `hash()` function does something similar, and dictionary/set implementations use these hashes to quickly find stored values. In AI, hashing is used in feature engineering for categorical variables (feature hashing) and to create efficient lookup tables for embeddings.
- **Checksums and data integrity**: When downloading a file, a checksum (like MD5 or SHA-1) is computed. This is essentially a modular operation: the file's bytes are treated as a huge number, and the remainder after division by a fixed prime is the checksum. If even one bit changes, the checksum changes, alerting the user to corruption.
- **Public-key cryptography**: RSA encryption relies heavily on modular arithmetic. It uses modular exponentiation (computing y = x^e mod n) for encryption and decryption. The security comes from the difficulty of reversing this operation without knowing the private key. This is foundational for secure HTTPS connections and digital signatures.
- **Large language models (LLMs)**: Some transformer models use 'rotary positional encodings' (RoPE) which involve rotations in a plane, and these rotations are naturally periodic, which is closely related to modular arithmetic on angles. Additionally, tokenization often involves hashing subwords to a fixed vocabulary size.
- **Small models on devices (TinyML)**: On constrained devices, memory is limited. Hash tables built on modular arithmetic allow efficient lookups of model weights or speech recognition phrase tables without storing a full matrix. Also, random number generators used for initializing weights are often based on modular multiplication (linear congruential generators).
- **Retrieval-augmented generation (RAG)**: RAG systems store documents as embeddings (lists of numbers). To quickly find similar documents, they often use 'locality-sensitive hashing' (LSH), which involves hashing vectors into buckets, and modular arithmetic plays a role in the hashing functions.
- **Agentic systems**: Agents that plan and call tools need to schedule actions and manage resources. Round-robin scheduling and rate limiting are often implemented using modular counters (e.g., `current_index % num_tools`).
- **Everyday applied ML**: In recommender systems, collaborative filtering often uses matrix factorization, where user and item IDs can be hashed to a fixed size. In fraud detection, transactions are clustered based on time, and time can be bucketed into hours of the day using modular arithmetic (e.g., `timestamp % 24`).

**What a developer actually writes**: In Python, developers use the `%` operator directly for hashing: `bucket_index = hash_value % num_buckets`. For cryptographic purposes, they use libraries like `cryptography` or `pycryptodome` which internally perform modular exponentiation. For LSH, they might use the `datasketch` library, which implements MinHash, a technique that relies on random hash functions.

**What breaks when done badly**: If a poor modulus is chosen (e.g., a non-prime) for hashing, it can lead to more collisions, slowing down dictionary lookups to O(n). In cryptography, using a weak modulus can make the security vulnerable to attacks, compromising data privacy.


---

Read this on the web: https://basavapurushottam.com/learn-ai/modular-arithmetic
