From the Euclidean algorithm and modular arithmetic to RSA cryptography, quadratic reciprocity, Pell's equation, and the prime number theorem — a complete treatment for competition math, cryptography, and graduate preparation.
We write d | n (read: d divides n) if there exists an integer k such that n = dk. Key properties: if d | a and d | b then d | (ax + by) for all integers x, y. The greatest common divisor GCD(a, b) is the largest integer dividing both a and b. Two integers are coprime (or relatively prime) when GCD(a, b) = 1.
Bezout's Identity
For any integers a and b, there exist integers x and y such that ax + by = GCD(a, b). The set of all integer linear combinations of a and b is exactly the set of multiples of GCD(a, b).
The most efficient classical method for computing GCD relies on the identity GCD(a, b) = GCD(b, a mod b). Apply repeatedly until the remainder is 0; the last nonzero remainder is the GCD.
Worked Example: GCD(252, 105)
252 = 2 (105) + 42
105 = 2 (42) + 21
42 = 2 (21) + 0
The last nonzero remainder is 21, so GCD(252, 105) = 21.
Back-substitute through the steps above to express GCD(a, b) as a linear combination ax + by. This yields the integers guaranteed by Bezout's identity and is the key tool for computing modular inverses.
Worked Example: Express GCD(35, 13) = 1 as 35x + 13y
35 = 2(13) + 9 → 9 = 35 - 2(13)
13 = 1(9) + 4 → 4 = 13 - 1(9)
9 = 2(4) + 1 → 1 = 9 - 2(4)
Back-substitute: 1 = 9 - 2(13 - 9) = 3(9) - 2(13) = 3(35 - 2(13)) - 2(13) = 3(35) - 8(13)
Therefore 35(3) + 13(-8) = 1. Modular inverse of 35 mod 13 is 3.
We write a ≡ b (mod n) when n | (a - b). The residue classes modulo n partition the integers into n equivalence classes. Congruence is compatible with addition, subtraction, and multiplication: if a ≡ b and c ≡ d (mod n) then a + c ≡ b + d and ac ≡ bd (mod n). Division requires care — you can cancel a factor d from ac ≡ bc (mod n) only if GCD(d, n) = 1.
ax ≡ b (mod n) has a solution iff GCD(a, n) | b. When it does, there are GCD(a, n) distinct solutions mod n. Find a particular solution via the extended Euclidean algorithm, then add multiples of n / GCD(a, n).
The inverse of a mod n is an integer x with ax ≡ 1 (mod n). It exists iff GCD(a, n) = 1. Once found, modular division by a is multiplication by its inverse. Example: inverse of 3 mod 7 is 5 because 3(5) = 15 ≡ 1 (mod 7).
A system x ≡ a1 (mod n1), x ≡ a2 (mod n2) can be solved by substitution or CRT. When moduli are coprime, the solution is unique mod n1*n2.
p is prime iff (p - 1)! ≡ -1 (mod p). Example: 4! = 24 ≡ -1 ≡ 4 (mod 5), confirming 5 is prime. Computationally impractical but theoretically elegant.
When n1, n2, ..., nk are pairwise coprime, the CRT establishes a ring isomorphism between Z/NZ and Z/n1Z x Z/n2Z x ... x Z/nkZ (where N = n1 n2 ... nk). Concretely, any system of congruences with pairwise coprime moduli has a unique solution mod N.
Worked Example: Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
N = 3 · 5 · 7 = 105. Compute N1 = 35, N2 = 21, N3 = 15.
Find y1: 35 y1 ≡ 1 (mod 3) → 2 y1 ≡ 1 (mod 3) → y1 = 2.
Find y2: 21 y2 ≡ 1 (mod 5) → y2 = 1.
Find y3: 15 y3 ≡ 1 (mod 7) → y3 = 1.
x ≡ 2(35)(2) + 3(21)(1) + 2(15)(1) = 140 + 63 + 30 = 233 ≡ 233 - 2(105) = 23 (mod 105).
Answer: x ≡ 23 (mod 105).
The totient function phi(n) counts the integers from 1 to n that are coprime to n. It is multiplicative: phi(mn) = phi(m) phi(n) when GCD(m, n) = 1. The general formula for any n with prime factorization p1^a1 ... pk^ak is:
phi(n) = n · (1 - 1/p1) · (1 - 1/p2) · ... · (1 - 1/pk)
Example: phi(72) = phi(8) · phi(9) = 4 · 6 = 24. Alternatively, phi(72) = 72 · (1 - 1/2) · (1 - 1/3) = 72 · 1/2 · 2/3 = 24.
If p is prime and GCD(a, p) = 1, then a^(p-1) ≡ 1 (mod p). More generally, a^p ≡ a (mod p) for all integers a. This gives a fast method for reducing large exponents: replace the exponent by its remainder mod (p - 1).
Worked Example: Compute 7^222 mod 11
11 is prime, GCD(7, 11) = 1, so 7^10 ≡ 1 (mod 11).
222 = 22 · 10 + 2, so 7^222 = (7^10)^22 · 7^2 ≡ 1^22 · 49 ≡ 49 (mod 11).
49 = 4 · 11 + 5, so 7^222 ≡ 5 (mod 11).
Euler's theorem generalizes Fermat's: if GCD(a, n) = 1 then a^phi(n) ≡ 1 (mod n). This holds for any modulus n, not just primes. It is the theoretical cornerstone of RSA encryption.
Worked Example: Compute 5^100 mod 12
phi(12) = phi(4) · phi(3) = 2 · 2 = 4. GCD(5, 12) = 1.
So 5^4 ≡ 1 (mod 12). 100 = 25 · 4, so 5^100 = (5^4)^25 ≡ 1 (mod 12).
An integer a is a quadratic residue mod p (p an odd prime not dividing a) if the congruence x^2 ≡ a (mod p) has a solution. There are exactly (p - 1)/2 quadratic residues and (p - 1)/2 quadratic non-residues among 1, 2, ..., p - 1. Their product is ≡ -1 (mod p) (Wilson's theorem connection).
Legendre Symbol
The Legendre symbol (a / p) equals 1 if a is a QR mod p, -1 if a is a QNR mod p, and 0 if p | a. By Euler's criterion: (a / p) ≡ a^((p-1)/2) (mod p). The symbol is completely multiplicative: (ab / p) = (a / p)(b / p).
Gauss's Law of Quadratic Reciprocity is one of the most celebrated results in number theory. For distinct odd primes p and q:
(p / q)(q / p) = (-1)^((p-1)/2 · (q-1)/2)
Equivalently: (p / q) = (q / p) unless both p and q are ≡ 3 (mod 4), in which case (p / q) = -(q / p). Supplementary laws: (-1 / p) = (-1)^((p-1)/2) — so -1 is a QR mod p iff p ≡ 1 (mod 4). And (2 / p) = (-1)^((p^2 - 1)/8) — so 2 is a QR mod p iff p ≡ 1 or 7 (mod 8).
Worked Example: Is 3 a quadratic residue mod 11?
By Euler's criterion: 3^((11-1)/2) = 3^5 = 243 ≡ 243 - 22(11) = 1 (mod 11).
So (3 / 11) = 1: yes, 3 is a QR mod 11.
Check: 5^2 = 25 ≡ 3 (mod 11). Confirmed.
The multiplicative group (Z/pZ)* is cyclic of order p - 1 for any prime p. A primitive root mod p is a generator g of this group — every nonzero residue mod p is a power of g. Primitive roots exist modulo p, p^k, 2p^k, 2, 4, and no other moduli. There are phi(p - 1) primitive roots mod p.
Worked Example: Find a primitive root mod 7
We need g with order 6 = phi(7). Candidates: 2, 3, 4, 5, 6.
Test g = 3: 3^1=3, 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1 (all mod 7).
3 generates all of 1,2,3,4,5,6 — so 3 is a primitive root mod 7.
Given primitive root g mod p, every nonzero a mod p can be written as a = g^k (mod p) for a unique k in (0, p - 2). This k is the discrete logarithm of a base g mod p (written log_g a). Computing discrete logarithms is believed to be computationally hard for large p — this hardness underpins Diffie-Hellman key exchange and ElGamal encryption. Algorithms like baby-step giant-step run in O(sqrt(p)) time; index calculus is sub-exponential for smooth primes.
RSA is the world's most widely deployed public-key cryptosystem. Its security rests on the presumed difficulty of factoring large integers.
Choose large primes p, q. Set n = pq. Compute phi(n) = (p-1)(q-1). Choose e with GCD(e, phi(n)) = 1 (typically e = 65537). Find d with ed ≡ 1 (mod phi(n)). Public key: (e, n). Private key: (d, n).
Encryption: C = M^e mod n. Decryption: M = C^d mod n. Correctness: C^d = M^(ed) = M^(1 + k·phi(n)) ≡ M (mod n) by Euler's theorem, when GCD(M, n) = 1.
An attacker who can factor n = pq recovers phi(n) and then d. Best known factoring algorithms (GNFS) run in sub-exponential time L(n)^(1/3), requiring key sizes of 2048+ bits for modern security.
Toy RSA Example (small numbers for illustration only)
p = 11, q = 13 → n = 143, phi(n) = 10 · 12 = 120.
Choose e = 7, GCD(7, 120) = 1. Find d: 7d ≡ 1 (mod 120) → d = 103.
Encrypt M = 2: C = 2^7 mod 143 = 128.
Decrypt C = 128: M = 128^103 mod 143 = 2. (Verified via fast modular exponentiation.)
The equation ax + by = c has an integer solution iff GCD(a, b) | c. If (x0, y0) is a particular solution, the general solution is x = x0 + (b/d)t, y = y0 - (a/d)t for all integers t, where d = GCD(a, b).
Worked Example: Find all integer solutions to 14x + 22y = 8
GCD(14, 22) = 2 and 2 | 8, so solutions exist. Divide by 2: 7x + 11y = 4.
Extended EA gives 7(8) + 11(-5) = 1, so 7(32) + 11(-20) = 4.
Particular solution: x0 = 32, y0 = -20.
General solution: x = 32 + 11t, y = -20 - 7t for t in Z.
A continued fraction for a real number x is an expression x = a0 + 1/(a1 + 1/(a2 + ...)), written [a0; a1, a2, ...]. For rationals, the expansion terminates. For quadratic irrationals like sqrt(D), it is eventually periodic. The convergents p_k/q_k (formed by truncating the expansion) are the best rational approximations to x in the sense that |x - p/q| is minimized for denominators up to q_k.
Continued Fraction of sqrt(3)
sqrt(3) = 1.732..., so a0 = 1.
sqrt(3) = [1; 1, 2, 1, 2, ...] — period 2.
Convergents: 1/1, 2/1, 5/3, 7/4, 19/11, 26/15, ...
Each convergent p/q satisfies |sqrt(3) - p/q| less than 1/(q^2 sqrt(3)).
The equation x^2 - Dy^2 = 1 (D a positive non-square integer) always has infinitely many positive integer solutions. The fundamental solution (x1, y1) — the smallest with x1, y1 > 0 — is found from the continued fraction expansion of sqrt(D). If the period of the CF expansion of sqrt(D) is r, the fundamental solution appears at convergent p_(r-1) / q_(r-1) (or p_(2r-1) / q_(2r-1) when r is even). All solutions are (xn, yn) where xn + yn sqrt(D) = (x1 + y1 sqrt(D))^n.
Worked Example: Solve x^2 - 5y^2 = 1
sqrt(5) = [2; 4, 4, 4, ...] — period 1.
First convergent beyond a0: (2·4 + 1)/4 = 9/4.
Check: 9^2 - 5·4^2 = 81 - 80 = 1. Fundamental solution: (9, 4).
Next solution: (9 + 4 sqrt(5))^2 = 161 + 72 sqrt(5), giving (161, 72).
Let pi(x) denote the number of primes up to x. Computing pi(x) for small x is easy, but understanding how pi(x) behaves as x grows large is one of the deepest problems in mathematics. Legendre, Gauss, and Chebyshev made early progress before the full Prime Number Theorem was proved in 1896.
| x | pi(x) | x / ln(x) | Ratio pi(x) / (x/ln x) |
|---|---|---|---|
| 100 | 25 | 21.7 | 1.151 |
| 1,000 | 168 | 144.8 | 1.160 |
| 10,000 | 1,229 | 1,085.7 | 1.132 |
| 100,000 | 9,592 | 8,685.9 | 1.104 |
| 1,000,000 | 78,498 | 72,382.4 | 1.084 |
Prime Number Theorem (PNT)
pi(x) ~ x / ln(x) as x approaches infinity. Equivalently, pi(x) ~ Li(x) where Li(x) = integral from 2 to x of dt / ln(t) (the logarithmic integral, a sharper approximation). The n-th prime p_n ~ n · ln(n).
The PNT was proved independently by Hadamard and de la Vallee-Poussin in 1896 using complex analysis — specifically by showing that the Riemann zeta function has no zeros on the line Re(s) = 1.
For Re(s) > 1, the Riemann zeta function is:
zeta(s) = sum_(n=1)^(inf) 1/n^s = product_(p prime) 1/(1 - p^(-s))
The product formula (Euler product) encodes the Fundamental Theorem of Arithmetic. The function extends analytically to all of C except a simple pole at s = 1, where zeta(s) ~ 1/(s-1). Special values: zeta(2) = pi^2/6, zeta(4) = pi^4/90.
The Riemann Hypothesis
All non-trivial zeros of zeta(s) — the zeros with 0 < Re(s) < 1 — lie on the critical line Re(s) = 1/2. This is the most famous open problem in mathematics (one of the Clay Millennium Prize Problems). If true, it implies the sharpest possible error bound in the PNT:
pi(x) = Li(x) + O(sqrt(x) · ln(x))
Computationally, the first 10^13 non-trivial zeros have been verified to lie on the critical line. The hypothesis remains unproven in general.
Bezout's Identity
ax + by = GCD(a, b) has integer solutions x, y for all a, b.
Fermat's Little Theorem
If p is prime and p does not divide a, then a^(p-1) ≡ 1 (mod p).
Euler's Theorem
If GCD(a, n) = 1, then a^phi(n) ≡ 1 (mod n).
Chinese Remainder Theorem
Pairwise coprime moduli guarantee a unique solution mod their product.
Wilson's Theorem
p is prime iff (p-1)! ≡ -1 (mod p).
Quadratic Reciprocity
(p/q)(q/p) = (-1)^((p-1)/2 · (q-1)/2) for distinct odd primes p, q.
Prime Number Theorem
pi(x) ~ x / ln(x); primes become less dense at a logarithmic rate.
Dirichlet's Theorem
Every arithmetic progression a, a+d, a+2d, ... with GCD(a,d)=1 contains infinitely many primes.
Practice GCD computations, modular arithmetic, quadratic residues, and more with AI-powered step-by-step feedback. Build the fluency you need for competition math, cryptography, and graduate coursework.
Start Practicing FreeNo account required to begin.