Clock math, fast modular exponentiation, Fermat's little theorem, modular inverses, the Chinese Remainder Theorem, and RSA cryptography — all explained through stunning animations.
// WHAT YOU'LL LEARN
Prerequisites: Basic arithmetic · Divisibility · Prime numbers (recommended)
// DEFINITION
Modular arithmetic is arithmetic where numbers wrap around after reaching a certain value called the modulus. The result of a mod n is the remainder when a is divided by n.
Think of a clock: if it's 10 o'clock and you wait 5 hours, it's not 15 o'clock — it's 3 o'clock. That's (10 + 5) mod 12 = 3.
// TRY IT
17 ÷ 5 = 3 remainder 2
17 = 5 × 3 + 2
// CLOCK MATH
The clock is the most familiar example of modular arithmetic. Drag the sliders to see how addition wraps around at 12.
RESULT
10 + 5 = 15 → 3 o'clock
(10 + 5) mod 12 = 3 → 3
// PROPERTIES
(a + b) mod n = ((a mod n) + (b mod n)) mod n
You can take mod at each step.
(a - b) mod n = ((a mod n) - (b mod n) + n) mod n
Add n to handle negatives.
(a × b) mod n = ((a mod n) × (b mod n)) mod n
The most useful property.
a^b mod n = ((a mod n)^b) mod n
Take mod of the base first.
a ≡ b (mod n) ⟺ n | (a - b)
a and b have the same remainder.
a ≡ b, b ≡ c ⟹ a ≡ c (mod n)
Congruence is transitive.
// FAST MODULAR EXPONENTIATION
Naive multiplication takes O(b) — too slow for crypto where b can be 2048 bits. Binary exponentiation uses the binary representation of b to compute the result in O(log b) steps.
13 in binary = 1101
RESULT
3^13 mod 7 = 3
Press PLAY to trace the algorithm through the flowchart.
Press PLAY to step through the algorithm line by line.
// MODULAR INVERSE
The modular multiplicative inverse of a mod n is a number x such that a × x ≡ 1 (mod n). It exists if and only if gcd(a, n) = 1.
The inverse lets us "divide" — dividing by a is the same as multiplying by a⁻¹. The Extended Euclidean Algorithm finds it.
We need x where 3x ≡ 1 (mod 7)
Try x=1: 3×1=3 ≠ 1
Try x=2: 3×2=6 ≠ 1
Try x=3: 3×3=9≡2 ≠ 1
Try x=4: 3×4=12≡5 ≠ 1
Try x=5: 3×5=15≡1 ✓
So 3⁻¹ mod 7 = 5
If p is prime, the inverse of a mod p is:
a⁻¹ ≡ a^(p-2) (mod p)
This follows from Fermat's little theorem: a^(p-1) ≡ 1, so a × a^(p-2) ≡ 1.
// THEOREMS
a^(p-1) ≡ 1 (mod p)
If p is prime and gcd(a, p) = 1, then a raised to (p-1) is congruent to 1 mod p. This is the basis for primality testing and computing modular inverses.
a^φ(n) ≡ 1 (mod n)
Generalization of Fermat: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), where φ(n) counts numbers from 1 to n coprime to n. Fermat is the special case where n is prime (φ(p) = p-1).
// RSA CRYPTOGRAPHY
RSA combines everything we've learned: primes, modular exponentiation, Euler's theorem, and modular inverses. Change the message and watch encryption/decryption happen in real time.
// KEY GENERATION
p (prime)
61
chosen secretly
q (prime)
53
chosen secretly
n = p × q
3233
public modulus
φ(n) = (p-1)(q-1)
3120
secret
e (public exponent)
17
public, gcd(e,φ)=1
d = e⁻¹ mod φ(n)
2753
private exponent
Public key: (n=3233, e=17) — share with everyone
Private key: (n=3233, d=2753) — keep secret!
// ENCRYPT & DECRYPT
Must be 0 ≤ m < n=3233
🔒 ENCRYPT
c = m^e mod n
42^17 mod 3233 = 2557
🔓 DECRYPT
m = c^d mod n
2557^2753 mod 3233 = 42
Decryption recovered the original message! RSA works ✓
Since e × d ≡ 1 (mod φ(n)), we have e × d = 1 + k×φ(n)for some integer k. By Euler's theorem, m^φ(n) ≡ 1 (mod n), so m^(e×d) = m^(1+k×φ(n)) = m × (m^φ(n))^k ≡ m × 1^k ≡ m (mod n). Decryption recovers the original message! The security relies on the fact that finding φ(n) requires factoring n = p × q, which is computationally infeasible for large primes.
// PRACTICE & ASSESS
Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.
// TUTORIAL QUIZZES · LEVELS 1–9
Nine progressive quizzes from Level 1 to Level 9. Each has 10 questions with a 10-minute timer. XP scales with level — L1 gives 10 XP, L9 gives 90 XP. Click a quiz to expand and begin.
// REFERENCES
// READY?
Practice 10,000+ coding problems, follow career roadmaps, and get hired.