Engineering Fluency OS

Why This Matters

Every clock in the world runs on modular arithmetic. After 12 comes 1, not 13. In computing, modular arithmetic is everywhere: hash table indexing uses mod to map keys to buckets, cryptographic algorithms like RSA compute modular exponentials with huge numbers, and circular buffers wrap around using mod. The concept of congruence — that 15 and 3 are "the same" modulo 12 — lets us work with remainders instead of impossibly large numbers.

The modular inverse of a number a modulo m is the number b such that (a * b) mod m = 1. This is the key operation in RSA decryption: you encrypt with one key and decrypt by multiplying with its modular inverse. Without modular arithmetic, modern internet security would not exist.

Define Terms

Visual Model

Mod Operationa mod m = remainder

Congruencea = b (mod m) if m | (a - b)

Clock ArithmeticHours wrap at 12

PropertiesAdd, multiply, power mod m

Modular Inversea * a_inv = 1 (mod m)

Modular Exponentiationa^b mod m efficiently

RSA Encryptionc = m^e mod n

The full process at a glance. Click Start tour to walk through each step.

Modular arithmetic: from basic remainders to the heart of RSA encryption.

Code Example

Code

// Basic modular arithmetic
console.log("17 mod 5:", 17 % 5);     // 2
console.log("23 mod 7:", 23 % 7);     // 2
console.log("-3 mod 5:", ((-3 % 5) + 5) % 5); // 2 (handle negative)

// Congruence check
function isCongruent(a, b, m) {
  return ((a - b) % m + m) % m === 0;
}
console.log("17 = 2 (mod 5):", isCongruent(17, 2, 5)); // true
console.log("17 = 3 (mod 5):", isCongruent(17, 3, 5)); // false

// Modular properties: (a * b) mod m = ((a mod m) * (b mod m)) mod m
const a = 123456789, b = 987654321, m = 1000000007;
const direct = Number(BigInt(a) * BigInt(b) % BigInt(m));
const modular = ((a % m) * (b % m)) % m;
console.log("Direct:", direct);
console.log("Modular:", modular); // Same result, avoids overflow

// Extended GCD for modular inverse
function extGcd(a, b) {
  if (b === 0) return [a, 1, 0];
  const [g, x1, y1] = extGcd(b, a % b);
  return [g, y1, x1 - Math.floor(a / b) * y1];
}

function modInverse(a, m) {
  const [g, x] = extGcd(a, m);
  if (g !== 1) return null; // No inverse exists
  return ((x % m) + m) % m;
}
console.log("Inverse of 3 mod 7:", modInverse(3, 7)); // 5
console.log("Verify: 3 * 5 mod 7 =", (3 * 5) % 7);   // 1

// Modular exponentiation: a^b mod m via repeated squaring
function modPow(base, exp, mod) {
  let result = 1;
  base = base % mod;
  while (exp > 0) {
    if (exp % 2 === 1) {
      result = (result * base) % mod;
    }
    exp = Math.floor(exp / 2);
    base = (base * base) % mod;
  }
  return result;
}
console.log("2^10 mod 1000:", modPow(2, 10, 1000));   // 24
console.log("3^100 mod 97:", modPow(3, 100, 97));     // 35

Interactive Experiment

Try these exercises:

Compute 7^4 mod 11 by hand. Then verify with the modPow function.
Find the modular inverse of 5 mod 11. Verify that 5 times its inverse gives 1 mod 11.
What happens when you try to find the modular inverse of 6 mod 9? Why does it fail?
Use modular exponentiation to compute 2^1000 mod 1000000007. How fast is it compared to computing 2^1000 directly?
Create a simple Caesar cipher: shift each letter by 3 positions using mod 26. Encrypt "HELLO" and decrypt the result.

Quick Quiz

Coding Challenge

Modular Exponentiation

Write a function called `modPow` that takes three arguments: `base`, `exp`, and `mod`, and returns `(base ^ exp) % mod` computed efficiently using repeated squaring. Do NOT compute base^exp directly — the numbers would be astronomically large. Instead, repeatedly square the base and reduce mod m at each step. If exp is odd, multiply the result by base (mod m). Halve exp each iteration.

Loading editor...

Real-World Usage

Modular arithmetic is one of the most applied mathematical concepts in computing:

RSA encryption: Encryption computes c = m^e mod n, and decryption computes m = c^d mod n. Both use modular exponentiation with numbers that are hundreds of digits long.
Hash tables: The hash function h(key) = key mod tableSize maps keys to buckets. Choosing a prime table size ensures better distribution.
Checksums and error detection: ISBN numbers, credit card validation (Luhn algorithm), and CRC codes all use modular arithmetic to detect errors.
Circular buffers: Ring buffers in operating systems and network stacks use mod to wrap indices: nextIndex = (currentIndex + 1) % bufferSize.
Random number generators: Linear congruential generators compute x(n+1) = (a * x(n) + c) mod m. The quality of randomness depends on the choice of a, c, and m.

Modular Arithmetic