Modular Operations
♾️ Any size, exactly
All arithmetic here uses exact big-integer math — paste a 50-digit number and the answers stay correct. (The previous version silently broke past ~9 quadrillion.)
The modular clock
Numbers mod n live on a circle of n positions — arithmetic wraps around like clock hands.
Step-by-step
Fast Modular Exponentiation
🧠 Why square-and-multiply?
Computing a^e by repeated multiplication takes e−1 steps. Squaring along the binary digits of e takes about 2·log₂(e) — the difference between impossible and instant, and the engine inside RSA.
Binary breakdown of e
Intermediate values along the ladder
Each column is the running result after one operation — ■ squaring or ■ multiply. Heights are values mod n.
Square-and-multiply, step by step
| # | Operation | Running value |
|---|
Extended Euclidean Algorithm
🔑 Why this algorithm matters
Euclid's algorithm (c. 300 BC) is among the oldest still in daily use. Its extended form finds x and y with ax + by = gcd(a,b) — which is exactly how modular inverses, and therefore RSA private keys, are computed.
Bézout's identity
Modular inverse a⁻¹ (mod b)
Euclid's staircase
Each bar is a remainder; the quotient labels show how many times one number fits into the previous. The last nonzero remainder is the gcd.
Algorithm table
| Step | Quotient | Remainder | x | y |
|---|
Each row satisfies a·x + b·y = remainder — Bézout at every step.
Congruence Solver
🏮 A 1,700-year-old puzzle
The Chinese Remainder Theorem traces to Sun Tzu's 3rd-century puzzle: "a number leaves remainder 2 by threes, 3 by fives, 2 by sevens." (Answer: 23.) Today the same theorem speeds up RSA decryption in your browser.
Solution process
Solutions on the residue wheel 0 … n−1
Green cells are the residues that solve the congruence.
Complete solution set
Cryptography Lab
⚠️ Classroom-sized keys
These demos use tiny numbers so every step is visible. Real RSA uses primes of 1,024+ bits; real Diffie–Hellman uses 2,048-bit groups or elliptic curves. The Crack panel shows exactly why.
Generated keys
Encrypt → decrypt
🔓 Now break it
RSA's entire security is that factoring n is slow. For demo-sized n, it isn't:
Clock Arithmetic, Explained
🕐 The big idea
Modular arithmetic is arithmetic that wraps around. On a 12-hour clock, 5 hours after 9 o'clock isn't 14 — it's 2, because 14 = 12 + 2. We write that as 14 ≡ 2 (mod 12): "14 is congruent to 2, modulo 12."
Two numbers are congruent mod n exactly when they leave the same remainder on division by n — or equivalently, when n divides their difference. That tiny definition powers everything on this page.
📜 Gauss and the ≡ sign
Carl Friedrich Gauss formalized congruences in Disquisitiones Arithmeticae (1801), written when he was 21 — choosing the ≡ symbol deliberately, because congruence behaves so much like equality. You can add, subtract, and multiply congruences freely:
- If a ≡ b and c ≡ d (mod n), then a+c ≡ b+d, a−c ≡ b−d, and ac ≡ bd (mod n).
- Division is the exception: a÷b means multiplying by b⁻¹, which exists only when gcd(b, n) = 1.
🔍 Where it hides in daily life
- Check digits: the last digit of an ISBN, UPC barcode, or credit-card number is a modular checksum that catches typos. Try the validators below.
- Calendars: "what day of the week is 1,000 days from now?" is a mod-7 question.
- Hashing: hash tables and checksums reduce huge values mod a table size.
- Music: the twelve-tone octave is arithmetic mod 12 — transposition is modular addition.
- Cryptography: RSA, Diffie–Hellman, and ElGamal (see the Crypto Lab) all run on modular exponentiation.
🧪 Try it: real-world check digits
Both validators run the genuine industry formulas, live.
ISBN-10 (books, pre-2007)
UPC-A (12-digit barcodes)
⚡ Two theorems that run the internet
Fermat's little theorem (1640): if p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p). It gives instant inverses (a⁻¹ ≡ a^(p−2)) and fast primality tests.
Euler's generalization (1763): a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1, where φ counts the integers below n coprime to it. RSA decryption works precisely because m^(ed) = m^(1+kφ(n)) ≡ m (mod n).
🧮 Handy facts
- A number is divisible by 9 exactly when its digit sum is — because 10 ≡ 1 (mod 9). The old bookkeepers' trick "casting out nines" is mod-9 arithmetic.
- Divisibility by 11: alternately add and subtract digits — because 10 ≡ −1 (mod 11).
- −1 mod n is n−1: "one step backwards on the clock."
- There are exactly φ(n) invertible residues mod n; they form a group under multiplication.