Number Theory Textbook
From divisibility and congruences to p-adic numbers and algebraic integers. A textbook series building definitions, theorems, and proofs in a systematic progression.
Number Theory: A Complete Summary of Definitions, Theorems, and Proofs
A single-article survey of undergraduate number theory. Covers divisibility, congruences, the Euclidean algorithm, primes, quadratic residues, arithmetic functions, continued fractions, p-adic valuations, and algebraic integers, together with all key algorithms and a dependency diagram.
Divisibility and Congruences — Laying the Foundations of Number Theory
Starting from the definition of divisibility, we give a rigorous proof of the division algorithm (existence and uniqueness). We then introduce congruences, establish their basic properties and arithmetic rules, and construct the quotient ring Z/nZ.
The Greatest Common Divisor and the Euclidean Algorithm — Algebraic Foundations of an Algorithm
We give rigorous definitions and properties of gcd and lcm, then prove the correctness and O(log min(a,b)) complexity of the Euclidean algorithm. We establish Bezout's identity, develop the extended Euclidean algorithm, and systematically solve linear congruences ax = b (mod n).
Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers
We define prime numbers and establish their basic properties, including Euclid's proof of the infinitude of primes. We then give a rigorous proof of the fundamental theorem of arithmetic (existence and uniqueness of prime factorization), and discuss the sieve of Eratosthenes and the Miller--Rabin primality test.
Applications of Congruences and the Group of Units — The Structure of $(\mathbb{Z}/n\mathbb{Z})^*$
We investigate the group of units (Z/nZ)*, derive the formula for Euler's totient function phi(n), and prove Fermat's little theorem, Euler's theorem, and Wilson's theorem. We also introduce the order of an element and discuss primitive roots.
Primitive Roots and Discrete Logarithms — $(\mathbb{Z}/p\mathbb{Z})^*$ as a Cyclic Group
We prove that (Z/pZ)* is cyclic for every prime p and that the number of primitive roots is phi(p-1). We introduce the discrete logarithm (index), determine the structure of (Z/p^k Z)*, and discuss the computational hardness of the discrete logarithm problem (DLP).
The Chinese Remainder Theorem and Its Applications — Systems of Congruences and Direct Products of Rings
We prove the Chinese remainder theorem as a ring isomorphism. We extend the result to the case where the moduli are not pairwise coprime, present Garner's algorithm, give a CRT-based proof of the multiplicativity of phi, and discuss applications in competitive programming.
Quadratic Residues and the Law of Reciprocity — The Theory of Quadratic Residues
We define the Legendre symbol, prove Euler's criterion, and establish Gauss's lemma. We then prove the law of quadratic reciprocity and discuss the Jacobi symbol and the Tonelli--Shanks algorithm for computing square roots modulo primes.
Arithmetic Functions and Multiplicative Functions — Functions on the Integers
We systematically define the principal multiplicative functions (phi, sigma, mu, d), develop the ring structure of Dirichlet convolution, and give a rigorous proof of the Moebius inversion formula. We also clarify the connection to the inclusion-exclusion principle.
Continued Fractions and Diophantine Approximation — The Theory of Rational Approximation
We define finite and infinite continued fractions, prove convergence, and rigorously establish the properties of convergents. We develop the theory of best rational approximations, solve the Pell equation x^2 - Dy^2 = 1 via continued fractions, and discuss the Stern--Brocot tree.
Chebyshev's Estimates: 0.92 x/ln x < π(x) < 1.11 x/ln x and the Prime Number Theorem
Chebyshev proved that 0.92 x/ln x < π(x) < 1.11 x/ln x for sufficiently large x. This article gives a complete proof via binomial coefficients and the Chebyshev functions θ(x) and ψ(x), then traces the path to the prime number theorem π(x) ~ x/ln x.
$p$-adic Valuations and an Introduction to Local Methods — Viewing Integers One Prime at a Time
We define the p-adic valuation v_p(n) and the p-adic absolute value, and state Ostrowski's theorem. We construct the ring of p-adic integers Z_p, prove Hensel's lemma, and discuss the local-global principle.
Introduction to Algebraic Integers — Extending the Notion of Integer
Using the Gaussian integers Z[i] and the Eisenstein integers Z[omega] as concrete examples, we introduce rings of algebraic integers. We demonstrate the failure of unique factorization in Z[sqrt(-5)] and show how ideals and prime ideal factorization restore uniqueness. We define the class number and discuss its significance.