Number Theory

Syllabus

• Divisibility, gcd, Euclidean algorithm; primes vs irreducibles; Fundamental Theorem of Arithmetic and consequences.
• Arithmetic functions: ω(n), Ω(n), d(n), σ(n), φ(n); additive vs multiplicative functions; summatory functions.
• Möbius function and summatory Möbius function; perfect numbers (selected results).
• Congruences: complete and reduced residue systems; multiplicativity of φ(n); Euler–Fermat theorem.
• Linear congruences and linear Diophantine equations; systems of congruences; computational applications.
• Quadratic and higher-power congruences; reduction to prime and prime-power moduli; counting solutions and degree reduction mod p.
• Wilson’s theorem; solutions to x^k ≡ 1 (mod p); k-th power residues; order of an element; primitive roots and index.
• Quadratic residues: Legendre symbol, Euler’s criterion/lemma; quadratic reciprocity (statements), Gauss lemma (statement), evaluation of (2/p).
• Infinitely many primes; basic bounds/estimates for π(x).