Foundations of Number Theory

An Introduction to Number Theory What is Number Theory? Number theory is the branch of pure mathematics that studies the integers and the properties of objects constructed from them. At its core, number theory asks fundamental questions about numbers: What makes a number prime? How can we solve equations with integer solutions? What patterns exist among the integers? Number theorists investigate prime numbers—integers greater than one divisible only by one and themselves—along with related mathematical objects like rational numbers (fractions of integers) and algebraic integers (generalizations of ordinary integers used in more abstract settings). The field encompasses both the concrete and computational (How do we find prime numbers?) and the deeply theoretical (What can we prove about the distribution of primes?). Number theory has two main branches distinguished by their methods. Analytic number theory uses tools from calculus and complex analysis to study integers indirectly. Algebraic number theory employs abstract algebraic structures like fields and rings to understand number systems that generalize the ordinary integers. Elementary Number Theory: Foundations and Core Concepts Elementary number theory forms the foundation of the subject. It deals with the most basic properties of integers and is largely self-contained, requiring only the properties of ordinary integers to understand. The Euclidean Algorithm and Greatest Common Divisor The greatest common divisor (GCD) of two integers is the largest positive integer that divides both of them. Computing the GCD is one of the oldest algorithms in mathematics: the Euclidean algorithm. The Euclidean algorithm repeatedly applies Euclid's division lemma, which states that for any integers $a$ and $b$ with $b \neq 0$, we can write $a = bq + r$ where $0 \leq r < |b|$. To find the GCD of $a$ and $b$, we replace the pair $(a,b)$ with $(b, r)$ and repeat until the remainder becomes zero. The last nonzero remainder is the GCD. Example: To find $\gcd(48, 18)$: $48 = 18 \cdot 2 + 12$ $18 = 12 \cdot 1 + 6$ $12 = 6 \cdot 2 + 0$ Therefore $\gcd(48, 18) = 6$. Prime Numbers and Their Infinite Abundance A prime number is an integer greater than one whose only positive divisors are one and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... One of the most beautiful results in all of mathematics is Euclid's theorem: there are infinitely many prime numbers. The proof is remarkably elegant. Suppose there were only finitely many primes: $p1, p2, \ldots, pn$. Consider the number $P = p1 \cdot p2 \cdots pn + 1$. This number is not divisible by any of the listed primes (dividing $P$ by any $pi$ leaves remainder 1). Since $P > 1$, it must have a prime divisor. But this prime divisor cannot be on our list, contradicting the assumption that we had listed all primes. To find all primes up to a given number $N$, we can use the sieve of Eratosthenes. This algorithm works by iteratively marking the multiples of each prime as composite (non-prime): start with all numbers from 2 to $N$; mark 2 as prime and strike out all its multiples; move to the next unmarked number (3), mark it prime, and strike its multiples; continue until every number is either marked prime or struck out. The Fundamental Theorem of Arithmetic The fundamental theorem of arithmetic states that every integer greater than one can be expressed uniquely as a product of prime numbers, up to the order of the factors. For example, $60 = 2^2 \cdot 3 \cdot 5$. This unique factorization is so important that it underpins much of what makes the integers special. Modular Arithmetic and Congruences Modular arithmetic is a system of arithmetic performed with a fixed modulus $m$. Two integers $a$ and $b$ are congruent modulo $m$, written $a \equiv b \pmod{m}$, if $m$ divides $a - b$. For example, $17 \equiv 5 \pmod{12}$ because $12 \mid (17-5) = 12$. Congruences behave like equations: if $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a+c \equiv b+d \pmod{m}$ and $ac \equiv bd \pmod{m}$. Modular arithmetic is useful for solving problems that involve remainders. For instance, what is the remainder when $2^{100}$ is divided by 7? Rather than computing $2^{100}$ directly, we can work modulo 7: $2^3 = 8 \equiv 1 \pmod{7}$, so $2^{100} = 2^{99} \cdot 2 = (2^3)^{33} \cdot 2 \equiv 1^{33} \cdot 2 = 2 \pmod{7}$. Fermat's Little Theorem and Euler's Theorem Fermat's Little Theorem is a cornerstone result about modular arithmetic. It states: if $p$ is prime and $a$ is an integer not divisible by $p$, then $$a^{p-1} \equiv 1 \pmod{p}.$$ This powerful result has numerous applications, from primality testing to cryptography. Euler's theorem generalizes Fermat's result. Before stating it, we need to define Euler's totient function $\varphi(n)$, which counts how many integers from 1 to $n$ are coprime to $n$ (share no common factor other than 1). Euler's theorem states: for any integer $a$ coprime to $n$, $$a^{\varphi(n)} \equiv 1 \pmod{n}.$$ When $n$ is prime, $\varphi(n) = n-1$, which gives us Fermat's Little Theorem. Diophantine Equations A Diophantine equation is a polynomial equation for which we seek integer or rational solutions. The name honors Diophantus of Alexandria, who studied such problems extensively in the 3rd century AD. A classic example is the Pythagorean equation: $x^2 + y^2 = z^2$. Integer solutions to this equation, called Pythagorean triples, represent the sides of right triangles with integer lengths. The triple $(3, 4, 5)$ is the most famous: $3^2 + 4^2 = 9 + 16 = 25 = 5^2$. Some Diophantine equations have infinitely many solutions, others have finitely many, and some have none at all. Determining which case applies and finding all solutions is often extremely difficult—this is where number theory becomes a research frontier. Analytic Number Theory: Understanding Prime Distribution While elementary number theory studies integers using only basic properties, analytic number theory employs powerful tools from real and complex analysis to answer questions about how integers behave statistically. The Prime Number Theorem One of the most important results in mathematics is the prime number theorem. It describes how the number of primes less than or equal to $x$—denoted $\pi(x)$ and called the prime-counting function—grows as $x$ increases. The theorem states that $$\pi(x) \sim \frac{x}{\log x} \text{ as } x \to \infty,$$ where $\log$ denotes the natural logarithm. The notation $\sim$ means the ratio of the two sides approaches 1. In other words, for very large $x$, approximately $\frac{x}{\log x}$ of the integers less than $x$ are prime. This result was conjectured by Legendre in the early 19th century and finally proved (independently) by Hadamard and de la Vallée Poussin in 1896, demonstrating the power of analytic methods in number theory. The Riemann Zeta Function Central to analytic number theory is the Riemann zeta function, defined by the infinite series $$\zeta(s) = \sum{n=1}^{\infty} \frac{1}{n^s},$$ where $s$ is a complex number with $\operatorname{Re}(s) > 1$ (so the series converges). The zeta function connects to primes through Euler's product formula: $$\zeta(s) = \prod{p \text{ prime}} \frac{1}{1-p^{-s}}.$$ This remarkable formula shows that the zeta function "knows" about all the primes. The proof is surprisingly elegant: using unique factorization, the product expands to give exactly the sum $\sum{n=1}^{\infty} \frac{1}{n^s}$. <extrainfo> The Riemann zeta function can be analytically continued to other values of $s$, and the famous Riemann Hypothesis concerns the location of its zeros. This hypothesis remains one of the most important unsolved problems in mathematics and has profound implications for the distribution of prime numbers. </extrainfo> Algebraic Number Theory: Extending the Integers Algebraic number theory studies number systems that generalize the ordinary integers. It uses abstract algebra—the theory of fields, rings, and ideals—to understand these extended systems. Algebraic Numbers and Number Fields An algebraic number is any complex number that is a root of a polynomial equation with rational coefficients. For example, $\sqrt{2}$ is algebraic because it satisfies $x^2 - 2 = 0$. Even the seemingly exotic number $\frac{1 + \sqrt{5}}{2}$ (the golden ratio) is algebraic because it satisfies $x^2 - x - 1 = 0$. A number field is a finite-dimensional extension of the rational numbers $\mathbb{Q}$. The simplest number fields are quadratic fields, consisting of all numbers of the form $$a + b\sqrt{d}$$ where $a, b \in \mathbb{Q}$ and $d$ is a fixed non-square rational number. For instance, the Gaussian integers are $\{a + bi : a, b \in \mathbb{Z}\}$, which form a quadratic field. The Role of Ideals A remarkable and troubling discovery in algebraic number theory is that unique factorization fails in many number fields. That is, there are number fields where an integer can be factored into "primes" in more than one way. For example, in the ring $\mathbb{Z}[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b \in \mathbb{Z}\}$, the number 6 factors in two different ways: $$6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}).$$ To restore unique factorization, mathematicians introduced ideals—generalizations of numbers that behave much like numbers but satisfy unique factorization properties. Prime ideals are the generalization of prime numbers. This theory, developed primarily by Kummer, Dedekind, and others in the 19th century, is one of the greatest achievements in mathematics. Quadratic Reciprocity The law of quadratic reciprocity, proved by Gauss, is a cornerstone theorem of algebraic number theory. It describes when a number is a quadratic residue modulo a prime—that is, when the congruence $x^2 \equiv a \pmod{p}$ has a solution. <extrainfo> The law of quadratic reciprocity is remarkably elegant but notoriously difficult to state precisely without significant notation. In its simplest form, for distinct odd primes $p$ and $q$, there is a precise relationship between whether $p$ is a quadratic residue modulo $q$ and whether $q$ is a quadratic residue modulo $p$. </extrainfo> Other Important Subfields Beyond the major branches, number theory encompasses several other active areas: <extrainfo> Diophantine Approximation investigates how closely real numbers can be approximated by rational numbers. A rational number $\frac{p}{q}$ is a good approximation to a real number $\alpha$ if $|\alpha - \frac{p}{q}| < \frac{1}{q^2}$ for large $q$. This field studies which numbers have good rational approximations and which do not. Probabilistic Number Theory asks statistical questions about integers. For example: what fraction of integers are prime? What does a "typical" integer look like? These questions are answered not deterministically but in a probabilistic or average-case sense. Combinatorial Number Theory studies additive structures in sets of integers. A central question is: if you take a large subset of the integers, must it contain patterns like long arithmetic progressions? Results like the Green-Tao theorem (proving that the primes contain arbitrarily long arithmetic progressions) represent major achievements in this area. Computational Number Theory focuses on algorithmic questions: How do we test whether a number is prime? How do we factor large integers? These questions have practical importance for cryptography. Remarkably, we can test primality of large numbers efficiently, but no known algorithm factors large integers in polynomial time—a gap that underlies much of modern cryptography. </extrainfo>