📊 Section 1 -- Interactive Simulation
Controls
Parameters
Display
💡 Section 2 -- The Idea, Step by Step
Modular arithmetic is the math of things that wrap around. Here it is built up from a clock face to the theorem behind RSA.
If it is $9$ o'clock and you wait $5$ hours, it becomes $2$ o'clock -- not $14$. A clock only has twelve numbers, so once you pass $12$ you start over. That "starting over" is the whole idea: $9+5=14$, but on a 12-hour clock, $14$ and $2$ are the same place.
The number you wrap around is the modulus $n$. We write $a\equiv b\pmod{n}$ to mean $a$ and $b$ land on the same spot -- equivalently, $n$ divides $a-b$. To find where a number lands, divide and keep the remainder: $17\bmod5=2$, because $17=3\cdot5+2$. In the sim, the Modulus $n$ slider sets the clock size and Base $a$ picks the number you drop onto it.
Multiply a number by itself on the clock and the landing spots form a repeating cycle. Fermat's Little Theorem says something surprising: if $p$ is prime and $a$ shares no factor with it, then $a^{p-1}\equiv1\pmod{p}$ -- climb the ladder of powers $a^1,a^2,\ldots$ and you always return to $1$ within $p-1$ steps. For $a=3$, $p=7$: $3^6=729=104\cdot7+1\equiv1\pmod7$. This is what makes giant exponents cheap: to get $2^{100}\bmod13$ you never compute $2^{100}$ -- since $2^{12}\equiv1$, only $100\bmod12=4$ matters, giving $2^4=16\equiv3$. The Power $k$ slider walks up this ladder one rung at a time.
$$a^{p-1}\equiv1\pmod{p}\quad(p\text{ prime},\ \gcd(a,p)=1)$$
Set $n=7$, $a=3$ and step $k$ upward: every nonzero residue $1\ldots6$ lights up exactly once before the cycle returns to $1$ -- that base is a primitive root. Now keep $n=7$ but switch to $a=2$ and watch a shorter cycle that skips spots. Finally set $n=12$ (not prime) and notice the Primitive root? readout turn to No -- Fermat's clean return to $1$ is a privilege of prime moduli.
📐 Section 3 -- Modular Arithmetic & Fermat
If $p$ is prime and $\gcd(a,p)=1$, then $a^{p-1}\equiv1\pmod{p}$, equivalently $a^p\equiv a\pmod{p}$.
Euler's generalization: $a^{\phi(n)}\equiv1\pmod{n}$ for $\gcd(a,n)=1$ where $\phi(n)$ is Euler's totient.
| Symbol | Definition | Example ($n=12$) |
|---|---|---|
| $a\equiv b\pmod{n}$ | $n\mid(a-b)$ | $26\equiv2\pmod{12}$ |
| $\gcd(a,n)$ | Greatest common divisor | $\gcd(9,12)=3$ |
| $\phi(n)$ | Euler totient: count coprime to $n$ | $\phi(12)=4$ |
| order of $a$ | Smallest $k$: $a^k\equiv1$ | ord$_7(3)=6$ |
| primitive root | $a$ with order $\phi(p)$ | 3 is prim. root mod 7 |
$\mathbb{Z}/n\mathbb{Z}=\{0,1,\ldots,n-1\}$ with addition and multiplication mod $n$. Forms a ring. If $n$ is prime, it is a field $\mathbb{F}_p$ (every nonzero element has a multiplicative inverse). $5^{-1}\pmod7$: since $5\cdot3=15\equiv1$, so $5^{-1}\equiv3$.
The set $\{a,2a,3a,\ldots,(p-1)a\}\pmod p$ is a permutation of $\{1,2,\ldots,p-1\}$ (since $\gcd(a,p)=1$). Multiplying: $(a)(2a)\cdots((p-1)a)\equiv(p-1)!\pmod p$. So $a^{p-1}(p-1)!\equiv(p-1)!$. Cancel $(p-1)!$ (invertible mod prime): $a^{p-1}\equiv1\pmod p$.
$3^1=3,3^2=9\equiv2,3^3=6,3^4=18\equiv4,3^5=12\equiv5,3^6=15\equiv1\pmod7$ ✓. Fermat: $3^{7-1}=3^6\equiv1\pmod7$ ✓. Order of 3 mod 7 is 6 = $\phi(7)$, so 3 is a primitive root.
Compute $a^k\pmod n$ in $O(\log k)$ multiplications by repeated squaring: $a^{12}=a^8\cdot a^4=(a^2)^4\cdot(a^2)^2$. Compute $a^2,a^4,a^8$ and multiply selected factors. Used in RSA encryption: $m^e\pmod n$ with $e$ having hundreds of bits.
Given $x\equiv a_1\pmod{n_1}$, $x\equiv a_2\pmod{n_2}$ with $\gcd(n_1,n_2)=1$: unique solution $x\pmod{n_1n_2}$. Construction: $M=n_1n_2$, $M_1=n_2$, $M_2=n_1$, find inverses $y_i=M_i^{-1}\pmod{n_i}$, then $x=a_1M_1y_1+a_2M_2y_2\pmod M$.
Choose primes $p,q$; $n=pq$; $\phi(n)=(p-1)(q-1)$. Choose $e$ with $\gcd(e,\phi(n))=1$; $d=e^{-1}\pmod{\phi(n)}$. Public key $(n,e)$, private key $d$. Encrypt: $c=m^e\pmod n$. Decrypt: $c^d=m^{ed}\equiv m\pmod n$ by Euler's theorem. Security relies on hardness of factoring $n$.
❓ Section 4 -- FAQ
Think of a clock with $n$ positions (0 to $n-1$). $a\bmod n$ is where you land after $a$ steps clockwise. Addition mod $n$ wraps around. The simulation shows this on an actual clock. $26\bmod12=2$ -- after 2 full revolutions and 2 extra steps, land at 2.
Key takeaway: a mod n = position on n-clock after a steps. Addition wraps around the clock.The graph plots $a^k\bmod p$ for $k=0,1,2,\ldots$. For a primitive root mod $p$, all values $1,2,\ldots,p-1$ appear exactly once in each period of length $p-1$. For non-primitive bases, the cycle is shorter. The cycle length = order of $a$ mod $p$.
Key takeaway: Power cycle: a^k mod p repeats with period = order of a. Primitive root: all p-1 nonzero residues appear.RSA encryption (fundamental building block). Primality testing (Miller-Rabin, Fermat test). Hashing algorithms. Pseudorandom number generators (linear congruential). Diffie-Hellman key exchange uses discrete logarithm in $\mathbb{Z}_p^*$. Error-correcting codes (Reed-Solomon uses arithmetic in $\mathbb{F}_{2^k}$).
Key takeaway: RSA, primality testing, Diffie-Hellman, Reed-Solomon codes -- all built on modular arithmetic.If $a^{n-1}\equiv1\pmod n$ for all $\gcd(a,n)=1$, $n$ might still be composite -- these are Carmichael numbers (561, 1105, ...). The Fermat primality test is probabilistic, not deterministic. Miller-Rabin test strengthens it: no Carmichael numbers pass. AKS algorithm gives deterministic polynomial-time primality test.
Key takeaway: Carmichael numbers pass Fermat test but are composite. Miller-Rabin fixes this; AKS is deterministic.Fermat: $2^{12}\equiv1\pmod{13}$ (since 13 is prime, $\gcd(2,13)=1$). Write $100=12\cdot8+4$. So $2^{100}=(2^{12})^8\cdot2^4\equiv1^8\cdot16\equiv3\pmod{13}$. Check: $2^4=16=13+3\equiv3$ ✓. Fermat reduces large exponent to small one.
Key takeaway: 2^100 mod 13: 100 = 12*8 + 4, so 2^100 = (2^12)^8 * 2^4 = 1 * 16 = 3 mod 13.The multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ has order $p-1$ and is cyclic. A primitive root $g$ is a generator: $g^0,g^1,\ldots,g^{p-2}$ are all $p-1$ nonzero residues. The discrete logarithm $\log_g a$ is the exponent. Primitive roots exist for primes and for $2,4,p^k,2p^k$. For composite moduli, the group may not be cyclic.
Key takeaway: (Z/pZ)* is cyclic of order p-1. Primitive root = generator. Discrete log is the inverse operation.