Number Theory
What this domain tests
Number Theory on PEI Math 521B rewards exact reasoning about divisibility, congruences, and primes rather than computation speed. Expect questions that ask you to prove or disprove a divisibility claim, solve a linear congruence, apply the Euclidean algorithm, or reason about prime factorizations. The exam treats definitions as working tools: you are expected to state them precisely and use them in short proofs.
Core rules and concepts
- Division algorithm: for integers a and b with b > 0, there exist unique q, r with a = bq + r and 0 ≤ r < b. Uniqueness is often the point of a proof.
- gcd and Bézout: gcd(a, b) is the least positive integer of the form ax + by. The Euclidean algorithm produces those coefficients by back-substitution.
- Primes and Euclid's lemma: if p is prime and p | ab, then p | a or p | b. This is the key step in proving unique factorization.
- Congruences: a ≡ b (mod n) means n | (a − b). Linear congruences ax ≡ c (mod n) are solvable exactly when gcd(a, n) | c, and then there are gcd(a, n) solutions modulo n.
- Fermat's little theorem: if p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p). Use it to reduce large exponents.
Worked example
Solve 6x ≡ 9 (mod 15). Here gcd(6, 15) = 3, and 3 | 9, so solutions exist. Divide the congruence and modulus by 3: 2x ≡ 3 (mod 5). Since 2 · 3 = 6 ≡ 1 (mod 5), multiply by 3: x ≡ 9 ≡ 4 (mod 5). The three solutions modulo 15 are x ≡ 4, 9, 14. Checking x = 4: 6 · 4 = 24 ≡ 9 (mod 15). Dividing the modulus without dividing the right side is the standard error; here dividing 9 by 3 is legitimate only because 3 divides it.
Traps that cost marks
- Forgetting that a linear congruence can have multiple solution classes; giving only x ≡ 4 loses marks.
- Confusing "p | ab implies p | a or p | b" (true for primes) with the false general claim for composites, e.g. 6 | 4 · 3 but 6 ∤ 4 and 6 ∤ 3.
- Applying Fermat's little theorem when the modulus is composite or when p | a.
- Treating 1 as prime, or omitting the case analysis for small n in induction proofs about divisibility.