Modular Arithmetic
Modular arithmetic is sometimes called "clock arithmetic" because it works just like the hours on a clock. When you go past the maximum value, you wrap around to the beginning.
Interactive Clock
This clock demonstrates how modular arithmetic works. Start at an hour, add more hours, and watch the hand wrap around:
The Mod Operation
The modulo operation gives you the remainder after division. Here's how it works:
Examples
- 17 mod 5 = 2 (because 17 = 3×5 + 2)
- 25 mod 7 = 4 (because 25 = 3×7 + 4)
- 100 mod 10 = 0 (divides evenly)
- 7 mod 12 = 7 (less than modulus)
Negative Numbers
In cryptography, we always want positive remainders:
- -1 mod 5 = 4 (not -1)
- -3 mod 7 = 4 (wrap around)
Modular Calculator
Try different modular operations:
Congruence Notation
Mathematicians use a special notation to say two numbers have the same remainder:
This means "a and b have the same remainder when divided by n".
Examples of Congruence
- 17 ≡ 2 (mod 5) because both give remainder 2
- 25 ≡ 4 (mod 7) because both give remainder 4
- 100 ≡ 0 (mod 10) because both give remainder 0
Powers in Modular Arithmetic
Something fascinating happens when you compute powers mod n: the values eventually repeat! This cyclic behavior is crucial for cryptography.
Power Table Generator
See how powers of a number cycle through values:
Why This Matters for Cryptography
Cryptographic algorithms like RSA use modular arithmetic with numbers that have hundreds of digits. Without the "wrapping around" property, these calculations would be impossible.