Difficulty: Intermediate. Prerequisites: Chapters 1–2 (logic, sets, functions).
Chapter 3 introduces asymptotic notation (Big O, Big Ω, Big Θ) for classifying how fast functions grow, which is the language you will use to talk about algorithm efficiency. Chapter 4 covers number theory tools (divisibility, modular arithmetic, the Euclidean algorithm, the Chinese Remainder Theorem) and applies them to cryptography, culminating in RSA. Both chapters carry 4 questions each on the final.
Big O (O(g(x)))
An upper bound on a function's growth rate. f(x) is O(g(x)) if there exist constants C > 0 and k such that |f(x)| ≤ C|g(x)| for all x > k. Think of it as "f grows no faster than g."
Big Omega (Ω(g(x)))
A lower bound on a function's growth rate. f(x) is Ω(g(x)) if there exist constants C > 0 and k such that |f(x)| ≥ C|g(x)| for all x > k. Think of it as "f grows at least as fast as g."
Big Theta (Θ(g(x)))
A tight bound: f(x) is Θ(g(x)) when f(x) is both O(g(x)) and Ω(g(x)). In simple terms, f and g grow at the same rate.
Divisibility (a | b)
a divides b if there is an integer c such that b = ac. Equivalently, b/a is an integer.
Modulus (a mod m)
The remainder when a is divided by m.
Congruence (a ≡ b (mod m))
a and b leave the same remainder when divided by m. Equivalently, m divides (a - b).
GCD (greatest common divisor)
The largest integer that divides both a and b. Found efficiently using the Euclidean algorithm.
Euclidean algorithm
A recursive procedure: gcd(a, b) = gcd(b, a mod b), stopping when the remainder is 0.
Chinese Remainder Theorem (CRT)
If m_1, m_2, …, m_n are pairwise coprime, the system of congruences x ≡ a_i (mod m_i) has a unique solution modulo m_1 · m_2 · … · m_n.
Fermat's Little Theorem
If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p).
RSA
A public-key cryptosystem built on modular exponentiation and the difficulty of factoring large numbers.
Note: all logs in this course are base 2 unless stated otherwise.
To find the tight Big O, replace every term with the dominant (fastest-growing) term, then sum the coefficients.
Example 1: 3x³ + 12x² + 7. Each of x³, x² and x⁰ is bounded above by x³. Replacing gives (3 + 12 + 7)x³ = 22x³. So 3x³ + 12x² + 7 is O(x³), with C = 22 and k = 1.
Example 2: 5n²log(n) + 6n(log(n))². Break into factors: n·n·log(n) vs n·log(n)·log(n). Cancel common factors to get n vs log(n). Since n grows faster, n²log(n) dominates. The result is O(n²log(n)), with C = 11 and k = 1.
The same idea, but from the bottom. Replace every term with the smallest term. For the tightest bound, use the largest term.
Example: 3x³ + 12x² + 7. The loosest lower bound replaces everything with x⁰, giving 22x⁰. But the tightest Ω uses the largest term: 3x³ + 12x² + 7 ≥ 3x³ for all x ≥ 1, so it is Ω(x³).
f(x) is Θ(g(x)) when its Big O and Big Ω match. For 3x³ + 12x² + 7, the tight Big O is O(x³) and the tight Big Ω is Ω(x³), so it is Θ(x³).
a, b are integers with a ≠ 0. a divides b (written a | b) if there exists an integer c such that b = ac.
If a | b and a | c, then a | (b + c).
If a | b, then a | bc for any integer c.
If a | b and b | c, then a | c (transitivity).
a mod m = the remainder when a is divided by m.
a ≡ b (mod m) means m | (a - b), or equivalently a mod m = b mod m.
(a + b) mod m = ((a mod m) + (b mod m)) mod m.
ab mod m = ((a mod m)(b mod m)) mod m.
These properties let you reduce large numbers before adding or multiplying.
Base X to Base 10: if the digits are A_n, A_(n-1), …, A_0, the value is ∑ A_i · X^i.
Base 10 to Base X: repeatedly divide by X and collect remainders. The remainders, read in reverse order, form the digits in Base X.
Binary, Octal, Hexadecimal shortcuts: 4 binary digits = 1 hex digit. 3 binary digits = 1 octal digit.
The long multiplication algorithm works the same way as in base 10; you just carry according to the new base. The source guide works through A06 × DE1 in hexadecimal, yielding 8B1D46.
To compute b^n mod m for very large values:
Express n in binary.
Compute b mod m.
Repeatedly square: b^(2^i) mod m = (b^(2^(i-1)) mod m)² mod m.
Multiply together the terms whose positions correspond to 1-bits in the binary representation of n.
The Euclidean algorithm computes gcd(a, b) by repeatedly applying: gcd(a, b) = gcd(b, a mod b), until the remainder is 0. The last non-zero remainder is the GCD.
If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p). A useful corollary: a^p ≡ a (mod p). This is helpful for simplifying large modular exponentiations.
Given a system of congruences x ≡ a_1 (mod m_1), x ≡ a_2 (mod m_2), … where the moduli are pairwise coprime, there is a unique solution modulo M = m_1 · m_2 · … · m_n.
RSA is built on modular exponentiation and the difficulty of factoring large numbers. The key steps are:
Choose two large primes p and q. Compute n = pq.
Compute φ(n) = (p - 1)(q - 1).
Choose e such that gcd(e, φ(n)) = 1. The public key is (n, e).
Find d such that de ≡ 1 (mod φ(n)). The private key is (n, d).
Encrypt: c = m^e mod n. Decrypt: m = c^d mod n.
The security of RSA rests on the fact that factoring n into p and q is computationally hard for large n.
Students often confuse Big O with Big Θ. Big O is an upper bound only. Saying f is O(n²) does not mean f grows as fast as n²; it means f grows no faster than n².
The tightest Big Ω uses the largest term, not the smallest. Replacing all terms with x⁰ gives a valid but loose lower bound.
A congruence a ≡ b (mod m) does not mean a = b. It means a and b differ by a multiple of m.
Fermat's Little Theorem requires that a and p be coprime. If p divides a, the theorem does not apply in its a^(p-1) ≡ 1 form.
⚠️ 4 questions on the final cover Number Theory and Crypto. Expect at least one modular exponentiation problem.
⚠️ Be able to find Big O, Big Ω and Big Θ and state the witnesses C and k.
⚠️ Know the Euclidean algorithm well enough to run it by hand.
⚠️ Base conversion (especially binary to hex and back) comes up frequently.
True or false: if f(x) is O(x²), then f(x) is also O(x³).
Fill in the blank: gcd(252, 105) = ___.
True or false: 17 ≡ 5 (mod 6).
What is 2⁴ mod 5?
Fill in the blank: in RSA, the public key consists of ___ and ___.
Answers: 1. True (x³ is a valid, though loose, upper bound). 2. 21. 3. True (17 - 5 = 12, and 6 | 12). 4. 16 mod 5 = 1. 5. n and e.
Q: Find the tight Big O of 7n³ + 3n² + 5n. State C and k.
A: Each term is bounded by n³, so the sum ≤ (7 + 3 + 5)n³ = 15n³ for all n > 1. It is O(n³) with C = 15, k = 1.
Q: Use the Euclidean algorithm to find gcd(270, 192).
A: 270 = 1 · 192 + 78. 192 = 2 · 78 + 36. 78 = 2 · 36 + 6. 36 = 6 · 6 + 0. gcd = 6.
Q: Convert 1011 0110 in binary to hexadecimal.
A: Split into groups of 4: 1011 = B, 0110 = 6. Answer: B6.
Q: Compute 3¹⁰ mod 7 using Fermat's Little Theorem.
A: 7 is prime and gcd(3, 7) = 1, so 3⁶ ≡ 1 (mod 7). 3¹⁰ = 3⁶ · 3³ · 3¹ = 1 · 27 · 3 (mod 7). 27 mod 7 = 6, so 6 · 3 = 18, and 18 mod 7 = 4. Wait, let me recalculate: 3¹⁰ = (3⁶)¹ · 3⁴. 3⁶ ≡ 1. 3⁴ = 81, 81 mod 7 = 4. So 3¹⁰ mod 7 = 4.
Big O notation reappears when analysing recursive algorithms in Chapter 5. Modular arithmetic underpins the counting and probability work in Chapters 6 and 7, particularly when dealing with remainders and divisibility conditions.
CS 18200, CS 182, Purdue, discrete math, asymptotic notation, Big O, Big Omega, Big Theta, upper bound, lower bound, tight bound, growth rate, algorithm complexity, divisibility, modular arithmetic, modulus, congruence, base conversion, binary, octal, hexadecimal, modular exponentiation, Euclidean algorithm, GCD, Chinese Remainder Theorem, CRT, Fermat's Little Theorem, RSA, public key cryptography, encryption, decryption