Fact-checked by Grok 2 weeks ago

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions, exploring questions like divisibility or arithmetic progressions, as well as touching on other concepts related to integers, such as rational numbers, or algebraic constructions like p-adic numbers.^[1] Historically, the preferred term for this field was 'arithmetic' (from the Greek word meaning the art of counting numbers), and the modern term 'number theory' became established in the 19th century, notably through Adrien-Marie Legendre's book 'Essai sur la théorie des nombres' (1798).^[2] Regarded by Gauss as the "queen of mathematics" for its elegance and depth, this field has roots tracing back to ancient civilizations.^[3] Its historical development began with practical applications in ancient Mesopotamia, such as the Babylonian tablet Plimpton 322 (circa 1800 BCE) documenting Pythagorean triples—sets of integers a, b, c satisfying a^2 + b^2 = c^2.^[1] In classical Greece, Euclid's Elements (circa 300 BCE) established foundational results, including the proof of the infinitude of prime numbers using the argument that assuming finitely many primes leads to a contradiction via the construction of a new prime from their product plus one.^[4] The field matured in the early modern period through contributions from Pierre de Fermat (1607–1665), who posed challenges like Fermat's Last Theorem—stating no positive integers a, b, c satisfy a^n + b^n = c^n for integer n > 2—and Leonhard Euler (1707–1783), who proved many of these conjectures.^[1] Carl Friedrich Gauss's Disquisitiones Arithmeticae (1801) systematized the subject, introducing concepts like quadratic reciprocity and laying groundwork for modular arithmetic.^[1] In the 19th and 20th centuries, number theory diversified into major branches: elementary number theory, which uses basic tools to study divisibility and primes, as in the Fundamental Theorem of Arithmetic asserting unique prime factorization for every integer greater than 1; analytic number theory, employing complex analysis to investigate prime distribution, exemplified by the Prime Number Theorem (proven independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896), which approximates the number of primes up to x as about x / \ln x; algebraic number theory, examining integers in algebraic number fields and ideals; and computational number theory, developing algorithms for tasks like integer factorization.^[4]^[5]^[1] Notable unsolved problems include the Riemann Hypothesis (1859), conjecturing that all non-trivial zeros of the Riemann zeta function have real part 1/2, which would refine prime distribution estimates, and the Goldbach Conjecture (1742), positing every even integer greater than 2 as a sum of two primes.^[5] Beyond pure mathematics, number theory underpins modern applications in cryptography, such as the RSA algorithm relying on the difficulty of factoring large semiprimes, and in coding theory for error detection.^[5]

Historical Development

Ancient and Classical Origins

The study of numbers in ancient civilizations arose from practical imperatives, including the regulation of calendars, astronomical observations for agriculture and navigation, and commercial transactions requiring accurate reckoning. Babylonian mathematics, preserved on cuneiform clay tablets from the Old Babylonian period (c. 2000–1600 BCE), emphasized sexagesimal arithmetic and tables of reciprocals to solve problems in trade, land measurement, and celestial predictions, reflecting a utilitarian approach to numerical relations.^[6] Egyptian mathematics, documented in papyri such as the Rhind Papyrus (c. 1650 BCE), focused on fractions, areas, and volumes to support Nile flood-based surveying, taxation, and calendar adjustments tied to the heliacal rising of Sirius for agricultural timing.^[7] In ancient India, mathematical inquiries were motivated by astronomical computations for ritual calendars and epic astronomical treatises like the Vedanga Jyotisha (c. 1400–1200 BCE), which calculated lunar-solar cycles and planetary positions to align religious observances with cosmic events.^[8] A striking example of early numerical sophistication is the Plimpton 322 tablet, a cuneiform artifact from Larsa dated around 1800 BCE, which records 15 rows of Pythagorean triples—integers a, b, c satisfying a^2 + b^2 = c^2—arranged in descending order of the angle opposite c, possibly serving as a trigonometric table for surveying or astronomical alignments.^[9] This tablet demonstrates Babylonian familiarity with generating such triples via parameter equations, predating Greek geometry by over a millennium and underscoring the empirical roots of number-theoretic ideas in practical contexts.^[10] Greek scholars shifted toward axiomatic and theoretical explorations of numbers. In his Elements (c. 300 BCE), Euclid compiled and proved fundamental results, including Book IX, Proposition 20, which establishes the infinitude of primes by assuming a finite list and constructing a new prime as one more than their product, leading to a contradiction.^[11] Euclid also formalized the algorithm for the greatest common divisor in Book VII, Proposition 2: for integers a > b > 0, \gcd(a, b) = \gcd(b, a \mod b), repeated until the remainder is zero, with the process rooted in repeated subtraction or division to reveal shared divisors efficiently. Eratosthenes (c. 276–194 BCE), librarian at Alexandria, invented the sieve method to identify primes up to n by iteratively eliminating multiples of each integer starting from 2, marking composites while preserving primes—a simple yet effective tool for listing primes without testing divisibility for each number.^[12] Diophantus of Alexandria (3rd century CE) pioneered the systematic investigation of integer solutions to equations in his 13-volume Arithmetica, emphasizing indeterminate problems where multiple solutions exist, such as finding rationals or integers satisfying linear or quadratic forms.^[13] He introduced innovative notation, using \varsigma for the unknown, coefficients as subscripts, and abbreviations like \Delta\Upsilon for squares, enabling concise algebraic manipulations that prefigured symbolic algebra and focused on positive integer ("numbered") solutions.^[14] Parallel developments in India enriched these ideas. Aryabhata (476–550 CE), in his Aryabhatiya, articulated rules for testing divisibility by small primes and addressed integer solutions to linear congruences within astronomical contexts, such as computing planetary periods modulo cycles.^[15] Brahmagupta (598–668 CE), in Brahmasphutasiddhanta, advanced solutions to the Pell equation x^2 - d y^2 = 1 for nonsquare d using the chakravala method—a cyclic algorithm generating fundamental solutions and composites—and explored quadratic indeterminate forms, classifying them by discriminant for applications in calendar corrections and geometry.^[16]^[17] Greeks also infused number theory with philosophical inquiry, particularly regarding "perfect" numbers—positive integers equaling the sum of their proper divisors (excluding themselves). Euclid proved in Elements Book IX, Proposition 36, that if $2^p - 1 is prime (a Mersenne prime), then $2^{p-1}(2^p - 1) is even perfect, and in Proposition 37, that every such even perfect number is triangular, expressible as the k(k+1)/2 for some k = 2^p - 1.^[18] These results linked arithmetic perfection to geometric forms, reflecting Pythagorean ideals of harmony in numbers and influencing later searches for odd perfect numbers, which remain elusive.^[19]

Early Modern Advances

The revival of number theory in Europe during the 17th and 18th centuries marked a shift toward rigorous algebraic techniques and proofs, building briefly on Diophantus' ancient methods of solving indeterminate equations. Pierre de Fermat (1607–1665), a French lawyer and amateur mathematician, initiated this resurgence through his private correspondence, where he posed challenges and claimed results without full proofs, often prompting responses from contemporaries.^[20] In a 1640 letter to Marin Mersenne, Fermat stated what is now known as Fermat's Little Theorem: if p is a prime number and a is an integer not divisible by p, then a^{p-1} \equiv 1 \pmod{p}.^[20] This result, proved later by Leonhard Euler in 1736, provided a foundational tool for modular arithmetic. Fermat also advanced the study of sums of squares; in 1638, he asserted that every natural number can be expressed as the sum of at most four integer squares, a claim he supported with partial arguments but left unproven.^[20] Additionally, in letters such as one to Mersenne in 1640, he outlined a theorem on sums of two squares, stating that an odd prime can be written as p = x^2 + y^2 with integers x and y if and only if p \equiv 1 \pmod{4}, using descent methods to argue uniqueness up to order and signs.^[21] Fermat's most famous conjecture, Fermat's Last Theorem, appeared in a 1637 marginal note in his copy of Diophantus' Arithmetica, claiming that there are no positive integers x, y, z satisfying x^n + y^n = z^n for integer n > 2, with a purported proof too large for the margin.^[20] Fermat's ideas circulated through extensive letter exchanges, facilitated by networks like that of Marin Mersenne (1588–1648), a Minim friar who connected over 140 scholars across Europe, including Fermat, René Descartes, and Pierre de Carcavi, fostering debates on Diophantine problems and prime properties. Mersenne's Harmonie universelle (1636–1637) and personal correspondence served as hubs for sharing unpublished results, accelerating the dissemination of number-theoretic insights amid the era's scientific revolution.^[22] René Descartes (1596–1650) contributed indirectly through his 1637 La Géométrie, which introduced analytic geometry by coordinating algebraic equations with geometric loci, enabling the translation of number problems into coordinate-based solutions and influencing later algebraic approaches to Diophantine equations.^[23] In the 18th century, Leonhard Euler (1707–1783) systematized and expanded these foundations. In his 1737 paper "Variae observationes circa series infinitas," Euler proved the infinitude of primes by showing that the harmonic series \sum_{n=1}^\infty \frac{1}{n} diverges, while the Euler product \sum_{n=1}^\infty \frac{1}{n^s} = \prod_p (1 - p^{-s})^{-1} for s=1 implies \sum_p \frac{1}{p} diverges similarly, as a finite number of primes would yield convergence.^[24] This established that the sum of the reciprocals of the primes diverges, providing quantitative evidence for unbounded prime growth. Euler also introduced the totient function \phi(n) = n \prod_{p \mid n} (1 - 1/p), where the product is over distinct primes p dividing n, counting integers up to n coprime to n; he introduced it in his 1763 paper "Demonstration of a new method in the theory of arithmetic" (E271).^[25] Joseph-Louis Lagrange (1736–1813) culminated these advances with his four-square theorem, proved in 1770 and published in the Mémoires de l'Académie royale des Sciences de Paris. The theorem states that every natural number is the sum of four integer squares: n = a^2 + b^2 + c^2 + d^2 for integers a, b, c, d.^[26] Lagrange's proof reduces the problem to primes using the multiplicativity of the sum-of-squares representation and relies on Euler's four-square identity, which shows that the product of two sums of four squares is itself a sum of four squares:

(a^2 + b^2 + c^2 + d^2)(e^2 + f^2 + g^2 + h^2) = (ae - bf - cg - dh)^2 + (af + be + ch - dg)^2 + (ag - bh + ce + df)^2 + (ah + bg - cf + de)^2.

This identity, discovered by Euler around 1746, allows descent from composite to prime cases, confirming Fermat's 1638 assertion.^[26] Another key result from this period is Wilson's theorem, conjectured by John Wilson around 1770: for a prime p, (p-1)! \equiv -1 \pmod{p}. Lagrange provided the first proof in 1771, linking factorial properties to prime detection.^[27] These developments, disseminated through academies and letters, laid algebraic groundwork for later systematic theories.

19th-Century Foundations

The foundations of modern number theory in the 19th century were established through the systematic rigorization of concepts initiated by Carl Friedrich Gauss in his Disquisitiones Arithmeticae (1801), which provided a comprehensive framework for arithmetic investigations.^[28] Gauss introduced the notation for congruences, defining a \equiv b \pmod{m} as the condition that m divides a - b, thereby formalizing modular arithmetic as a core tool for studying integer properties. A cornerstone of this work was the law of quadratic reciprocity, which states that for distinct odd primes p and q, \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{(p-1)(q-1)}{4}}, where \left( \frac{\cdot}{\cdot} \right) denotes the Legendre symbol; this law connected the solvability of quadratic congruences across different moduli and built upon earlier ideas like Euler's totient function as a foundational building block for counting coprime integers. Central to quadratic reciprocity and the study of quadratic residuosity was the Legendre symbol \left( \frac{a}{p} \right), introduced by Adrien-Marie Legendre, which equals 1 if a is a nonzero quadratic residue modulo an odd prime p, -1 if it is a quadratic nonresidue, and 0 if p divides a.^[29] This symbol facilitated efficient computation of whether x^2 \equiv a \pmod{p} has solutions, with Euler's criterion providing a key evaluation method: for an odd prime p and integer a not divisible by p, a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod{p}.^[30] These tools enabled deeper exploration of prime-related patterns, culminating in Peter Gustav Lejeune Dirichlet's 1837 theorem asserting that if \gcd(a, m) = 1, then there are infinitely many primes in the arithmetic progression n \equiv a \pmod{m}.^[31] Further advancements addressed limitations in unique factorization beyond the integers. Ernst Kummer, in the 1840s, developed the theory of ideal numbers to resolve failures of unique factorization in rings of cyclotomic integers, such as \mathbb{Z}[\zeta_p] for prime p \equiv 3 \pmod{4}; his ideal numbers grouped elements to restore unique factorization at an abstract level, serving as a precursor to the modern ideal theory.^[32] Concurrently, Joseph Liouville's 1844 work demonstrated the existence of transcendental numbers, such as \sum_{k=1}^\infty 10^{-k!}, by showing they cannot satisfy any polynomial equation with integer coefficients, thereby distinguishing them from algebraic numbers and laying groundwork for separating algebraic integers in broader rings. Developments in continued fractions, advanced by Joseph-Louis Lagrange, provided tools for approximating irrationals and solving Diophantine equations; Lagrange's 1770 theorem established that the continued fraction expansion of any positive quadratic irrational is eventually periodic, influencing 19th-century applications to Pell equations and quadratic forms.^[33] Évariste Galois's early 19th-century group theory, though primarily algebraic, exerted influence on number theory by inspiring analyses of field extensions and symmetries in cyclotomic fields, which Kummer later utilized in his ideal theory.^[34]

20th-Century Expansion and Subfields

The 20th century marked a period of profound expansion in number theory, transforming it from a collection of disparate results into a field with distinct subfields supported by powerful analytic and algebraic frameworks. This growth was fueled by the application of complex analysis, abstract algebra, and computational insights to longstanding problems, leading to the formalization of analytic, algebraic, and Diophantine branches. Key developments addressed the distribution of primes, the structure of number fields, and the solvability of polynomial equations over the integers, while unresolved conjectures like the Riemann Hypothesis continued to guide research directions.^[35] In the 1910s and 1920s, G. H. Hardy and J. E. Littlewood pioneered analytic methods, culminating in the circle method, which approximated integrals over the unit circle to estimate the number of representations of integers as sums of primes or powers. This technique, first applied to the ternary Goldbach conjecture in 1923, provided asymptotic results for additive problems and laid the groundwork for analytic number theory by bridging Fourier analysis with Diophantine approximations.^[36] Concurrently, algebraic innovations advanced class field theory, with Emil Artin introducing his reciprocity law in 1927, which established a canonical isomorphism between the idele class group and the Galois group of maximal abelian extensions. Helmut Hasse extended these ideas in the 1930s through local-global principles and explicit constructions of class fields, unifying global reciprocity laws across number fields. This built briefly on Gauss's quadratic reciprocity law from 1801 as a foundational special case for abelian extensions of the rationals.^[35]^[37]^[38] The Riemann Hypothesis, proposed in 1859, remained a central unsolved problem, motivating extensive 20th-century efforts to delineate zero-free regions for the zeta function, which refine estimates in the prime number theorem. Progress included Vinogradov's work in the 1930s on zero-free strips and the independent Vinogradov-Korobov method in the 1950s, yielding explicit regions of the form \sigma > 1 - c (\log t)^{-2/3} (\log \log t)^{-1/3} for |\Im s| = t \geq 3, enhancing bounds on prime gaps and the error term in prime distribution.^[39] These advances underscored the hypothesis's role in analytic number theory. Meanwhile, the field diversified: analytic number theory, exemplified by Hardy's emphasis on prime distribution; algebraic number theory, centered on Hilbert's 12th problem from 1900, which sought explicit generators for abelian extensions via transcendental functions; and Diophantine number theory, highlighted by Andrew Wiles's 1994 proof of Fermat's Last Theorem, reducing it to the modularity theorem for elliptic curves over the rationals.^[35] Foundational shifts also occurred through Kurt Gödel's incompleteness theorems of 1931, which demonstrated that any consistent formal system encompassing Peano arithmetic cannot prove its own consistency or capture all truths about natural numbers, thereby limiting axiomatic approaches to number theory's foundations and prompting reliance on informal reasoning for key results.^[40] Additionally, Kurt Hensel's introduction of p-adic numbers in 1897 provided a non-Archimedean completion of the rationals at each prime p, enabling local analysis; this framework expanded significantly in the 20th century for studying Diophantine equations and Galois representations via tools like the p-adic zeta function.^[41] A notable modern milestone emerged in the 1960s with the Birch and Swinnerton-Dyer conjecture, formulated by B. J. Birch and H. P. F. Swinnerton-Dyer, which posits that for an elliptic curve E over the rationals, the rank of E(Q) equals the order of vanishing of its L-function L(E, s) at s=1, with the leading coefficient relating to the Tate-Shafarevich group and regulators. This conjecture bridges elliptic curves and L-functions, influencing progress in the Langlands program and modular forms.^[42]

Elementary Concepts

Divisibility and Primes

Number theory primarily concerns the properties and relationships of integers, denoted by the set \mathbb{Z}, which comprises all positive integers, negative integers, and zero. Divisibility is a foundational concept in this domain: for integers a and b with a \neq 0, a divides b, written a \mid b, if there exists an integer k such that b = a k.^[43] This relation captures the idea of one integer being a multiple of another and forms the basis for many structural results in the theory.^[44] The greatest common divisor of two integers a and b, denoted \gcd(a, b), is the largest positive integer that divides both a and b.^[45] Bézout's identity states that \gcd(a, b) can be expressed as a linear combination: there exist integers x and y such that \gcd(a, b) = a x + b y.^[46] This identity is crucial for understanding the structure of ideals in \mathbb{Z} and is proven using the Euclidean algorithm, which iteratively replaces (a, b) with (b, a \mod b) until reaching zero, yielding the gcd.^[47] Complementing the gcd, the least common multiple \operatorname{lcm}(a, b) is the smallest positive integer divisible by both a and b, satisfying the relation \operatorname{lcm}(a, b) = \frac{|a b|}{\gcd(a, b)} for nonzero a, b.^[48] This formula follows directly from prime factorization properties and highlights the interplay between common divisors and multiples.^[49] A prime number p is a positive integer greater than 1 that has no positive divisors other than 1 and itself.^[50] Euclid's theorem establishes the infinitude of primes: suppose there are finitely many primes p_1, \dots, p_n; then the number N = p_1 \cdots p_n + 1 is not divisible by any p_i, so N must have a prime factor not among them, yielding a contradiction.^[51] This proof, dating to ancient times, demonstrates that no finite list exhausts the primes.^[52] The fundamental theorem of arithmetic asserts that every integer n > 1 can be uniquely factored into primes: n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, where the p_i are distinct primes and e_i \geq 1, up to the order of factors.^[53] The existence follows from the well-ordering principle: consider the set of integers greater than 1 without prime factorization; it has a minimal element m, which must then be prime or factor into smaller non-prime-factorable parts, contradicting minimality unless m is prime.^[54] Uniqueness relies on the fact that if two factorizations differ, a prime from one must divide a product in the other, implying further factorization and contradiction via Euclid's lemma (primes divide products only if they divide a factor).^[55] In the ring \mathbb{Z}, irreducible elements—non-units that cannot be factored into non-units—are precisely the primes (up to units \pm 1).^[56] An element is irreducible if whenever it factors as a = b c, one of b or c is a unit; in \mathbb{Z}, this coincides with primality because \mathbb{Z} is a principal ideal domain, ensuring irreducibles generate prime ideals.^[57] The Euclid-Mullin sequence provides a constructive way to generate distinct primes: begin with p_1 = 2, and define p_{k+1} as the smallest prime dividing P_k + 1, where P_k = \prod_{i=1}^k p_i; the sequence is $2, 3, 7, 43, 13, \dots, conjectured to include all primes but unproven.^[58] The sieve of Eratosthenes is an efficient algorithm for finding all primes up to a given n: initialize a list of numbers from 2 to n, mark multiples of each prime starting from 2 (skipping even numbers after 2 for optimization), and the unmarked numbers are primes.^[59] Its time complexity is O(n \log \log n), arising from the harmonic sum of sieving steps, making it practical for moderate n despite not being optimal asymptotically.^[60]

Congruences and Arithmetic Functions

In number theory, congruences provide a fundamental framework for studying integers modulo a fixed integer, building on the concept of divisibility. Two integers a and b are congruent modulo m, denoted a \equiv b \pmod{m}, if m divides a - b.^[61] This relation is an equivalence relation, satisfying reflexivity (a \equiv a \pmod{m}), symmetry (if a \equiv b \pmod{m}, then b \equiv a \pmod{m}), and transitivity (if a \equiv b \pmod{m} and b \equiv c \pmod{m}, then a \equiv c \pmod{m}).^[61] Congruences preserve arithmetic operations: if a \equiv b \pmod{m} and c \equiv d \pmod{m}, then a + c \equiv b + d \pmod{m} and a \cdot c \equiv b \cdot d \pmod{m}.^[62] The Chinese Remainder Theorem is a key result enabling the decomposition of systems of congruences. It states that if m and n are coprime integers (i.e., \gcd(m, n) = 1), then the system x \equiv a \pmod{m} and x \equiv b \pmod{n} has a unique solution modulo mn.^[63] The proof relies on the existence of integers u and v such that u m + v n = 1 by Bézout's identity, allowing construction of x = a v n + b u m, which satisfies both congruences.^[63] This theorem generalizes to any finite set of pairwise coprime moduli and is crucial for solving simultaneous congruences in modular arithmetic.^[64] Fermat's Little Theorem and Euler's theorem offer powerful tools for exponentiation in modular settings, particularly when dealing with coprime bases. Fermat's Little Theorem asserts that if p is prime and \gcd(a, p) = 1, then a^{p-1} \equiv 1 \pmod{p}.^[65] This result, first stated by Pierre de Fermat in 1640, follows from the fact that the nonzero residues modulo p form a multiplicative group of order p-1.^[66] Euler's theorem generalizes this: if \gcd(a, n) = 1, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi(n) is Euler's totient function counting integers up to n coprime to n.^[67] Euler proved this in 1736 by considering the multiplicative group of units modulo n, whose order is \phi(n).^[67] Arithmetic functions map positive integers to complex numbers and capture intrinsic properties like the number or sum of divisors. A function f is multiplicative if f(mn) = f(m) f(n) whenever \gcd(m, n) = 1; such functions are completely determined by their values at prime powers due to unique prime factorization.^[68] The Möbius function \mu(n) is a classic example: \mu(n) = 0 if n has a squared prime factor, \mu(1) = 1, and \mu(n) = (-1)^k if n is a product of k distinct primes.^[69] Introduced by August Ferdinand Möbius in 1832, it inverts the divisor function via Möbius inversion: if g(n) = \sum_{d|n} f(d), then f(n) = \sum_{d|n} \mu(d) g(n/d).^[70] Another important multiplicative function is the divisor function \sigma(n) = \sum_{d|n} d, which sums the positive divisors of n; for n = p_1^{a_1} \cdots p_k^{a_k}, \sigma(n) = \prod (1 + p_i + \cdots + p_i^{a_i}).^[71] The Möbius function connects deeply to analytic number theory through its Dirichlet series \sum_{n=1}^\infty \mu(n) / n^s = 1 / \zeta(s) for \Re(s) > 1, where \zeta(s) is the Riemann zeta function.^[72] This reciprocal relation implies that the prime number theorem is equivalent to \sum_{n \leq x} \mu(n) = o(x) as x \to \infty.^[73] The Riemann Hypothesis posits that all nontrivial zeros of \zeta(s) lie on the line \Re(s) = 1/2, which would strengthen bounds on the error term in the prime number theorem via properties of this series.^[73] Wilson's Theorem provides a converse-like characterization of primes using factorials. It states that p is prime if and only if (p-1)! \equiv -1 \pmod{p}.^[74] Discovered by John Wilson in 1770 and proved by Joseph-Louis Lagrange in 1773, the theorem arises from pairing inverses in the multiplicative group modulo p, leaving only 1 and p-1 \equiv -1.^[74] This criterion enables primality tests: for a candidate n > 1, compute (n-1)! \mod n; if it equals n-1, then n is prime, though direct computation is inefficient for large n.^[74]

Analytic Number Theory

Distribution of Primes

The distribution of prime numbers among the positive integers is a central concern in analytic number theory, where tools from complex analysis are employed to quantify their frequency and patterns. Building upon elementary observations that primes are infinite and irregularly spaced, the prime counting function \pi(x), which enumerates the number of primes less than or equal to x, provides a measure of their density. In 1850, Pafnuty Chebyshev established the first asymptotic estimate, showing that \pi(x) \sim \frac{x}{\log x} in the sense that there exist positive constants A and B such that A \frac{x}{\log x} < \pi(x) < B \frac{x}{\log x} for sufficiently large x. This bound, derived using properties of the binomial coefficient and Stirling's approximation, marked a significant advance by confirming that primes are asymptotically as dense as suggested by Gauss's earlier heuristic based on the harmonic series.^[75] The Prime Number Theorem, proved independently in 1896 by Jacques Hadamard and Charles Jean de la Vallée Poussin, refines Chebyshev's estimate to the precise asymptotic \pi(x) \sim \mathrm{Li}(x), where \mathrm{Li}(x) = \int_2^x \frac{dt}{\log t} is the logarithmic integral function. Their proofs rely on the non-vanishing of the Riemann zeta function \zeta(s) on the line \mathrm{Re}(s) = 1, ensuring that the zeta function has no zeros in this critical region, which controls the growth of \pi(x). The zeta function is initially defined for complex s with \mathrm{Re}(s) > 1 by the Dirichlet series \zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s}, which converges absolutely in this half-plane and admits an Euler product representation \zeta(s) = \prod_p (1 - p^{-s})^{-1} over primes p, linking it directly to the primes. Riemann extended this to the entire complex plane via analytic continuation in 1859, yielding a meromorphic function with a simple pole at s=1 and no other poles.^[76]^[77] A key property enabling this continuation is the functional equation \zeta(s) = 2^s \pi^{s-1} \sin(\pi s / 2) \Gamma(1-s) \zeta(1-s), which relates values at s and $1-s and was also established by Riemann in 1859. This equation, derived using the gamma function \Gamma(s) and contour integration, symmetrizes the zeta function across the critical line \mathrm{Re}(s) = 1/2. The zeros of \zeta(s), denoted \rho, profoundly influence prime distribution through the explicit formula for the Chebyshev function \psi(x) = \sum_{p^k \leq x} \log p, which weights primes by their powers. In 1895, Hans von Mangoldt proved that

\psi(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \log(2\pi) - \frac{1}{2} \log(1 - x^{-2}),

where the sum is over nontrivial zeros \rho of \zeta(s). This formula explicitly connects oscillations in \psi(x) (and thus \pi(x)) to the imaginary parts of the zeros, implying that \pi(x) = \mathrm{Li}(x) + O(\sqrt{x} \log x) under the Riemann Hypothesis, which posits all nontrivial zeros lie on \mathrm{Re}(s) = 1/2.^[77]^[78] Refinements to the Prime Number Theorem include studies of error terms and biases in prime distribution. The Chebyshev bias refers to the observed tendency for more primes congruent to 3 modulo 4 than to 1 modulo 4 up to large x, despite the theorem predicting equal density in arithmetic progressions with coprime moduli; this bias, first noted by Chebyshev in 1853, arises from the distribution of zeta zeros and logarithmic densities, with Rubinstein and Sarnak quantifying in 1994 that the proportion of x where the bias favors 3 mod 4 is approximately 99.59% under suitable assumptions on the zeros. More generally, error terms in \pi(x) - \mathrm{Li}(x) are bounded by \Omega(\sqrt{x} (\log x \log \log x / \log \log \log x)^{1/2}), reflecting irregular fluctuations tied to the zeros. These analytic insights also support empirical verifications of conjectures involving primes; for instance, the Goldbach conjecture—that every even integer greater than 2 is the sum of two primes—has been checked computationally up to $4 \times 10^{18} in 2014, with all such numbers satisfying the representation, though a proof remains elusive.^[79]^[80]

Zeta Functions and L-Functions

Zeta functions and L-functions generalize the Riemann zeta function to incorporate arithmetic progressions and other structures, enabling refined analyses of prime distributions through analytic continuation and functional equations. The Riemann zeta function corresponds to the case of the trivial Dirichlet character. These functions play a pivotal role in connecting additive and multiplicative properties of integers to complex analysis.^[81] Dirichlet L-functions, introduced by Dirichlet in 1837, are defined for a Dirichlet character \chi modulo q as

L(s, \chi) = \sum_{n=1}^\infty \frac{\chi(n)}{n^s}

for \operatorname{Re}(s) > 1, where \chi is a completely multiplicative homomorphism from (\mathbb{Z}/q\mathbb{Z})^\times to \mathbb{C}^\times extended periodically. They admit an Euler product representation

L(s, \chi) = \prod_p \left(1 - \frac{\chi(p)}{p^s}\right)^{-1},

valid under the same convergence condition, reflecting the multiplicative nature of \chi. For non-principal \chi, L(s, \chi) extends to an entire function on the complex plane, while for the principal character, it relates to the zeta function with a pole at s=1. Dirichlet used these to prove the infinitude of primes in arithmetic progressions. Euler computed explicit values for even positive integers of the zeta function, such as \zeta(2) = \pi^2/6 and \zeta(4) = \pi^4/90, using Fourier series expansions of trigonometric functions.^[81] The Prime Number Theorem for arithmetic progressions states that if \gcd(a, q) = 1, then the number of primes \pi(x; q, a) up to x congruent to a modulo q satisfies \pi(x; q, a) \sim \operatorname{Li}(x)/\varphi(q), where \operatorname{Li}(x) is the logarithmic integral and \varphi is Euler's totient function. This asymptotic was established by de la Vallée Poussin in 1896 using properties of non-vanishing of L(s, \chi) near s=1. The Generalized Riemann Hypothesis posits that all non-trivial zeros of L(s, \chi) lie on the critical line \operatorname{Re}(s) = 1/2, extending the classical Riemann Hypothesis and implying stronger error terms in prime distribution estimates. Connections between L-functions and modular forms are highlighted by the Taniyama-Shimura conjecture, proposed in the 1950s and proved as the modularity theorem in 2001, which asserts that every elliptic curve over \mathbb{Q} corresponds to a weight-2 newform whose associated L-function matches the curve's L-function. This links analytic number theory to algebraic geometry, with profound implications for Diophantine equations. The Selberg zeta function, introduced by Selberg in 1956 for Fuchsian groups acting on the hyperbolic plane, is defined as a product over primitive closed geodesics \gamma:

Z(s) = \prod_{\gamma} \prod_{k=0}^\infty \left(1 - e^{-(s + k) l(\gamma)}\right),

where l(\gamma) is the length of \gamma; its zeros relate to eigenvalues of the hyperbolic Laplacian, analogous to Riemann zeros for primes. Applications to twin primes arise through the Hardy-Littlewood conjecture of 1923, where the constant in the asymptotic for twin prime pairs involves products over primes akin to evaluations of L-functions at s=1, specifically the twin prime constant C_2 = \prod_{p>2} (1 - 1/(p-1)^2) \approx 0.66016.

Algebraic Number Theory

Number Fields and Rings

In algebraic number theory, a number field K is a finite field extension of the rational numbers \mathbb{Q}, typically generated by adjoining an algebraic integer \alpha to \mathbb{Q}, denoted K = \mathbb{Q}(\alpha).^[82] The degree [K : \mathbb{Q}] of this extension equals the dimension of K as a vector space over \mathbb{Q}, which coincides with the degree of the minimal polynomial of \alpha over \mathbb{Q}.^[82] For example, quadratic number fields arise from minimal polynomials of the form x^2 - d where d is a square-free integer, generating K = \mathbb{Q}(\sqrt{d}) with degree 2.^[83] The ring of integers \mathcal{O}_K of a number field K is defined as the integral closure of \mathbb{Z} in K, consisting of all elements in K that are roots of monic polynomials with integer coefficients.^[84] This ring extends the integers \mathbb{Z} and captures the "integral" elements within K. A prominent example is the Gaussian integers \mathbb{Z}, which form \mathcal{O}_K for the number field K = \mathbb{Q}(i), where i satisfies the minimal polynomial x^2 + 1 = 0.^[85] Associated to elements \alpha \in K is the norm N_{K/\mathbb{Q}}(\alpha), defined as the absolute value of the determinant of the \mathbb{Q}-linear map on K given by multiplication by \alpha.^[86] This norm is multiplicative, N(\alpha \beta) = N(\alpha) N(\beta), and for \alpha \in \mathcal{O}_K, it takes integer values, aiding in the study of factorization in \mathcal{O}_K. The units of \mathcal{O}_K, denoted \mathcal{O}_K^\times, are elements with norm \pm 1. By Dirichlet's unit theorem, the unit group \mathcal{O}_K^\times is finitely generated of rank r_1 + r_2 - 1, where r_1 is the number of real embeddings of K into \mathbb{R} and $2r_2 is the number of complex embeddings (counting conjugates separately), with a finite torsion subgroup consisting of roots of unity in K.^[87] The discriminant \Delta_K of a number field K is an integer invariant that quantifies the ramification of prime ideals from \mathbb{Z} to \mathcal{O}_K, arising as the determinant of the trace form on a \mathbb{Z}-basis of \mathcal{O}_K.^[88] For quadratic fields \mathbb{Q}(\sqrt{d}) with minimal polynomial x^2 - d, the discriminant is $4d if d \equiv 2,3 \pmod{4} and d if d \equiv 1 \pmod{4}, reflecting how primes ramify or split in the extension.^[88] Smaller discriminants indicate less ramification and often simpler arithmetic structure. The rings of integers \mathcal{O}_K are Dedekind domains, meaning they are Noetherian, integrally closed in their fraction field K, and every nonzero prime ideal is maximal.^[89] In such domains, every nonzero ideal factors uniquely into a product of prime ideals, generalizing unique prime factorization in \mathbb{Z}.^[89] A key class of number fields is the cyclotomic fields \mathbb{Q}(\zeta_n), generated by a primitive nth root of unity \zeta_n, which satisfy the nth cyclotomic polynomial. These extensions are Galois over \mathbb{Q} with Galois group isomorphic to (\mathbb{Z}/n\mathbb{Z})^\times, the multiplicative group of integers modulo n.^[90]

Ideals and Class Groups

In algebraic number theory, the ring of integers \mathcal{O}_K of a number field K is a Dedekind domain, meaning every nonzero prime ideal is maximal and every nonzero ideal factors uniquely into prime ideals. This unique factorization of ideals compensates for the potential failure of unique factorization in elements, which occurs when \mathcal{O}_K is not a principal ideal domain. The decomposition of a rational prime p into prime ideals in \mathcal{O}_K is given by p \mathcal{O}_K = \prod_{i=1}^g \mathfrak{p}_i^{e_i}, where the \mathfrak{p}_i are distinct prime ideals lying over p, the e_i are the ramification indices, and g is the number of such primes; the residue degrees f_i = [\mathcal{O}_K / \mathfrak{p}_i : \mathbb{Z}/p\mathbb{Z}] satisfy \sum_{i=1}^g e_i f_i = [K : \mathbb{Q}].^[91]^[92] Fractional ideals extend the notion of ideals to allow "denominators," providing a framework for studying invertibility and the class group. A fractional ideal \mathfrak{a} of \mathcal{O}_K is a finitely generated \mathcal{O}_K-submodule of K such that there exists a nonzero \alpha \in K with \alpha \mathfrak{a} \subseteq \mathcal{O}_K; principal fractional ideals take the form (\alpha) = \alpha \mathcal{O}_K for \alpha \in K^\times. In Dedekind domains, every nonzero fractional ideal is invertible, meaning \mathfrak{a} \cdot \mathfrak{a}^{-1} = \mathcal{O}_K where \mathfrak{a}^{-1} = \{\beta \in K \mid \beta \mathfrak{a} \subseteq \mathcal{O}_K\}, and the set of fractional ideals forms a group under multiplication. The norm of an ideal, defined as N(\mathfrak{a}) = |\mathcal{O}_K / \mathfrak{a}| for integral ideals (extended multiplicatively to fractional ones), measures size and aids in decomposition analysis.^[93]^[94] The ideal class group \mathrm{Cl}_K quantifies the obstruction to unique factorization in elements by forming the group of fractional ideals modulo principal fractional ideals, with multiplication induced by ideal product; its order is the class number h_K = |\mathrm{Cl}_K|. Dirichlet proved that \mathrm{Cl}_K is finite, but a geometric proof using Minkowski's theorem on convex bodies in lattices shows that every ideal class contains an integral ideal of norm at most the Minkowski bound M_K = \frac{n!}{n^n} \left( \frac{4}{\pi} \right)^s \sqrt{|\Delta_K|}, where n = [K : \mathbb{Q}], s is the number of complex embeddings, and \Delta_K is the discriminant, implying only finitely many such ideals generate the group.^[95]^[96] The Hilbert class field H_K of K is the maximal unramified abelian extension of K, and by class field theory, [H_K : K] = h_K with \mathrm{Gal}(H_K / K) \cong \mathrm{Cl}_K. This extension realizes the class group algebraically and is used to study unramified covers of the ring class field. For quadratic fields K = \mathbb{Q}(\sqrt{d}) with d < 0 square-free, the class number h_K = 1 (so \mathcal{O}_K is a PID and Euclidean) holds precisely for d = -1, -2, -3, -7, -11, -19, -43, -67, -163, as completely classified by Heegner, Baker, and Stark.^[97]^[98]

Diophantine Problems

Linear and Quadratic Equations

Linear Diophantine equations of the form ax + by = c, where a, b, c \in \mathbb{Z} and a, b are not both zero, seek integer solutions x, y \in \mathbb{Z}. Such equations are solvable if and only if \gcd(a, b) divides c. If a particular solution (x_0, y_0) exists, the general solution is given by x = x_0 + (b/d)t, y = y_0 - (a/d)t for all t \in \mathbb{Z}, where d = \gcd(a, b). This parametrization arises from Bézout's identity, which guarantees integer linear combinations equaling the gcd, extended to multiples of d. Solvability conditions rely on divisibility properties from the Euclidean algorithm. Pell's equation, x^2 - d y^2 = 1 where d > 0 is square-free, is a fundamental quadratic Diophantine equation whose positive integer solutions form an infinite group under composition.^[99] The minimal nontrivial solution, called the fundamental solution (x_1, y_1), generates all others via (x_k + y_k \sqrt{d}) = (x_1 + y_1 \sqrt{d})^k for k \geq 1.^[99] These solutions correspond to the units of norm 1 in the ring \mathbb{Z}[\sqrt{d}], where the norm is N(a + b\sqrt{d}) = a^2 - d b^2.^[99] The continued fraction expansion of \sqrt{d} provides an algorithm to find the fundamental unit efficiently.^[99] Binary quadratic forms f(x, y) = a x^2 + b x y + c y^2 with integer coefficients represent integers n if f(x, y) = n for some x, y \in \mathbb{Z}. The Hasse-Minkowski theorem states that a quadratic form over \mathbb{Q} represents zero nontrivially if and only if it does so over \mathbb{R} and every \mathbb{Q}_p for primes p, establishing a local-global principle for isotropy.^[100] This theorem, proved by Hasse in 1921 for \mathbb{Q} and extended by Minkowski, classifies equivalence of forms via local invariants like discriminant and Hasse invariant.^[100] For representation problems, it implies that solvability over \mathbb{Q} reduces to local solubility checks.^[100] Fermat's theorem on sums of two squares characterizes positive integers representable as n = x^2 + y^2 with x, y \in \mathbb{Z}: such n must have all primes congruent to 3 modulo 4 appearing to even exponents in their prime factorization, including the factor 2 to any power.^[101] For odd primes p, p = x^2 + y^2 if and only if p \equiv 1 \pmod{4}, with uniqueness up to signs and order.^[101] The proof uses descent in the Gaussian integers \mathbb{Z}, where primes \equiv 3 \pmod{4} remain prime and those \equiv 1 \pmod{4} factor as (a + bi)(a - bi).^[101] The identity (x^2 + y^2)(u^2 + v^2) = (xu - yv)^2 + (xv + yu)^2 shows the set of such n is multiplicative.^[101] Legendre's three-square theorem states that a positive integer n is representable as n = x^2 + y^2 + z^2 with x, y, z \in \mathbb{Z} if and only if n is not of the form $4^k (8m + 7) for integers k \geq 0, m \geq 0.^[102] The necessity follows from quadratic residues modulo 8, as squares are 0, 1, or 4 modulo 8, so sums of three are at most 12 but never 7 modulo 8, and the power of 4 preserves this obstruction.^[102] Sufficiency uses Dirichlet's theorem on primes in arithmetic progressions and class number estimates to construct representations via quadratic forms.^[102] This result, proved by Legendre in 1798 and refined by Dirichlet in 1850, contrasts with Lagrange's four-square theorem by highlighting modular obstructions.^[102] A key example of quadratic equations arises in Pythagorean triples satisfying x^2 + y^2 = z^2. Primitive triples, where \gcd(x, y, z) = 1, are generated by integers m > n > 0 with \gcd(m, n) = 1 and m - n odd, via x = m^2 - n^2, y = 2mn, z = m^2 + n^2 (or swapped).^[103] Euclid described this parametrization in the Elements (Book X, Proposition 28, circa 300 BCE), ensuring x^2 + y^2 = z^2 and primitivity from the conditions on m, n.^[103] All triples are scalar multiples of primitive ones, yielding infinitely many solutions.^[103]

Higher-Degree and Elliptic Curves

Higher-degree Diophantine equations, involving polynomials of degree greater than two, often exhibit only finitely many integer solutions, contrasting with the infinite parametrizable solutions possible for quadratic forms in certain cases. A landmark result is Fermat's Last Theorem, which asserts that there are no positive integers x, y, z, n with n > 2 satisfying x^n + y^n = z^n. This was proved by Andrew Wiles in 1995 using the modularity theorem for semistable elliptic curves over the rationals, linking the equation to properties of modular forms.^[104] Elliptic curves provide a central framework for studying such problems, defined over the rationals \mathbb{Q} by Weierstrass equations of the form E: y^2 = x^3 + a x + b, where a, b \in \mathbb{Q} and the discriminant is nonzero to ensure nonsingularity. The set of rational points E(\mathbb{Q}) forms an abelian group under the chord-and-tangent law: to add points P and Q, draw the line through them (or the tangent if P = Q), find the third intersection point with E, and reflect it over the x-axis to obtain P + Q, with the point at infinity serving as the identity. The torsion subgroup of E(\mathbb{Q}) consists of points of finite order, which is finite and can be effectively computed. The Mordell-Weil theorem states that E(\mathbb{Q}) is finitely generated, isomorphic to \mathbb{Z}^r \oplus T where T is the torsion subgroup and r \geq 0 is the rank.^[105] A key application is the Mordell equation y^2 = x^3 + k for fixed integer k \neq 0, which defines an elliptic curve whose integer solutions correspond to integer points on E. By the Mordell-Weil theorem, E(\mathbb{Q}) has finite rank, implying only finitely many rational points up to bounded denominators, and thus finitely many integer solutions overall; this finiteness was first proved directly by Mordell in 1922. Siegel's theorem extends this to all genus 1 curves, guaranteeing finitely many integer points on any such affine curve over \mathbb{Q}, with effective bounds obtainable via heights measuring point complexity. The ABC conjecture, if true, would imply finiteness of integer solutions to superelliptic equations y^m = f(x) for fixed degree m > 2 and polynomials f of fixed degree greater than 2, by bounding the radical of summands in generalized Fermat-type equations.^[106]^[107]^[108] The Birch and Swinnerton-Dyer conjecture connects the arithmetic of elliptic curves to their analytic properties, predicting that the rank r of E(\mathbb{Q}) equals the order of the zero of the L-function L(E, s) at s = 1. This conjecture, formulated in the 1960s based on computational evidence, has been verified for many curves and implies precise information about the distribution of rational points, influencing finiteness results in higher-degree Diophantine problems.^[42]

Other Branches

Computational Number Theory

Computational number theory focuses on the development and analysis of algorithms for performing arithmetic operations and solving problems in number theory, particularly those involving large integers and related structures. It bridges theoretical mathematics with practical computation, enabling the verification of properties like primality and the decomposition of composites into factors. These techniques are essential for applications requiring efficient handling of numbers with hundreds or thousands of digits, where brute-force methods are infeasible. Primality testing determines whether a given integer is prime, a fundamental task in number theory. The AKS algorithm, introduced in 2002 by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, provides a deterministic polynomial-time method for this purpose, running in time O(log^{6} n) for an n-bit number, thus proving that primality is in the complexity class P. Prior to AKS, probabilistic tests like the Miller-Rabin algorithm, proposed by Gary L. Miller in 1976 and refined by Michael O. Rabin in 1980, were widely used; it identifies composites with high probability through repeated witness checks, with error probability less than 4^{-k} after k iterations, making it efficient for practical purposes despite its randomized nature. Integer factorization decomposes a composite number into its prime factors, a computationally intensive problem central to number theory. The quadratic sieve, developed by Carl Pomerance in 1984, factors numbers up to about 100 digits by finding smooth relations over quadratic residues modulo n using a sieving process. For larger integers, the general number field sieve (GNFS), pioneered by Arjen Lenstra, Derek Lenstra, and Mark Manasse in 1990, represents the state-of-the-art asymptotic method, with subexponential time complexity O(exp(c (log n)^{1/3} (log log n)^{2/3})) for some constant c, enabling the factorization of RSA-768—a 768-bit (232-digit) semiprime—in 2009 by a team using distributed computing over two years. The discrete logarithm problem involves finding an exponent x such that g^x ≡ h mod p for a prime p, generator g, and h in the multiplicative group. The baby-step giant-step algorithm, devised by Daniel Shanks in 1971, solves it in O(√p) time and space by partitioning the search into "baby" and "giant" steps, suitable for smaller groups. For finite fields, the index calculus method, with roots in earlier work and formalized by Leonard Adleman in 1977, achieves subexponential time by constructing a factor base and solving linear equations over logarithms, outperforming BSGS for large p. The elliptic curve method (ECM) for factorization leverages the group law on elliptic curves modulo n to detect small factors efficiently. Introduced by Hendrik Lenstra in 1983, it operates by attempting to compute scalar multiples on the curve E(ℤ/nℤ), where a failed computation due to a non-trivial gcd reveals a factor; its runtime depends on the smallest prime factor p as approximately O(exp(√(2 log p log log p))), making it effective for factors up to 50-60 digits. A related approach, Pollard's rho algorithm from 1975 by John Pollard, uses a pseudo-random walk in the ring ℤ/nℤ to find small factors in expected O(√p) time via collision detection with Floyd's cycle-finding method, often serving as a first-line tool before more advanced sieves. Modern computational number theory relies on specialized software for implementing these algorithms. PARI/GP, developed since 1981 at the Université Bordeaux, provides a library and interpreter for high-precision arithmetic and number-theoretic functions, including built-in primality tests and factorization routines. Similarly, SageMath, an open-source system initiated in 2005, integrates tools like PARI and ECM implementations for comprehensive computations in number fields and elliptic curves. Looking ahead, quantum computing poses threats through Peter Shor's 1994 algorithm, which factors integers in polynomial time on a quantum computer using period-finding via quantum Fourier transform, though current hardware limitations keep classical methods dominant.

Probabilistic and Geometric Number Theory

Probabilistic number theory employs probabilistic models to analyze the average behavior of arithmetic functions over large sets of integers. A foundational result in this area is the Erdős–Kac theorem, which describes the distribution of the number of distinct prime factors ω(n) of an integer n. Specifically, for integers n up to x, the standardized value (ω(n) - log log n) / sqrt(log log n) converges in distribution to a standard normal random variable N(0,1) as x → ∞. Another key contribution is Cramér's probabilistic model for the distribution of primes, introduced in the 1930s. In this model, each integer n ≥ 3 is treated as prime independently with probability 1 / log n, mimicking the prime number theorem. This random model predicts that the maximal gap between consecutive primes up to x is asymptotically (log x)^2 with high probability. Geometric number theory, pioneered by Hermann Minkowski in 1896, investigates the distribution of lattice points within convex bodies in Euclidean space to derive bounds and structural properties relevant to Diophantine approximation and quadratic forms. Minkowski's fundamental theorems assert that any convex body symmetric about the origin with volume greater than 2^n contains a non-zero lattice point from the integer lattice ℤ^n, and more generally, provide estimates for the number of lattice points inside such bodies. Central to this framework are the successive minima λ_i(L) of a lattice L in ℝ^n, defined as the infimum of lengths of linearly independent vectors in L that span an i-dimensional subspace. A significant advancement in this area is Siegel's mean value theorem for quadratic forms, established in 1945, which computes the average value of the theta series associated to positive definite quadratic forms over the space of lattices. This theorem states that the integral over the space of unimodular lattices of the product of theta functions equals the volume of the fundamental domain times a constant depending on the dimension. It has important applications to problems in the geometry of numbers, including estimates for class numbers of quadratic fields by relating the average number of representations to regulator and discriminant invariants.^[109] Arithmetic geometry extends these ideas by incorporating heights to measure the complexity of algebraic points. On projective space ℙ^m over the algebraic numbers, the (absolute logarithmic) height H(P) of a point P = [x_0 : ... : x_m] with coordinates in a number field is defined as the exponential of (1/[K:ℚ]) times the sum over places of local height contributions, normalized appropriately. Northcott's theorem, proved in 1950, asserts that for any fixed degree d and bound B, there are only finitely many points in ℙ^m(ℚ̄) of degree at most d and height at most B. A prominent example illustrating geometric and analytic techniques is the circle problem, which quantifies the discrepancy between the number of lattice points inside a circle of radius √n and the area πn. This discrepancy is captured by the error term in the partial sum ∑{k=1}^n r_2(k), where r_2(n) denotes the number of ways to write n as a sum of two integer squares, given explicitly by r_2(n) = 4 ∑{d|n} χ(d) with χ the non-principal Dirichlet character modulo 4 satisfying χ(-1)=-1. The best known unconditional bound for the error is O(n^{1/2 + ε}) for any ε > 0.

Applications

In Cryptography

Number theory forms the foundation of modern public-key cryptography, where the computational difficulty of certain number-theoretic problems serves as the basis for secure key exchange and encryption protocols. These systems rely on the assumption that problems like integer factorization and discrete logarithms are intractable for classical computers, enabling asymmetric encryption where public keys are openly shared while private keys remain secret. Seminal developments in the 1970s and 1980s transformed these mathematical challenges into practical security mechanisms, influencing protocols like TLS for secure web communication.^[110] The RSA cryptosystem, proposed in 1977 by Rivest, Shamir, and Adleman, exemplifies this approach by basing security on the integer factorization problem (IFP). To generate keys, two large primes p and q are chosen, and n = p q is computed as the modulus, with the public exponent e selected coprime to \phi(n) = (p-1)(q-1). The private exponent d satisfies e d \equiv 1 \pmod{\phi(n)}. Encryption of a message m yields c = m^e \mod n, and decryption recovers m = c^d \mod n, leveraging Euler's theorem for correctness. The system's security stems from the presumed hardness of factoring n to recover p and q, with no efficient classical algorithm known for large n. RSA remains widely used for digital signatures and key encapsulation, though key sizes have grown to 2048 bits or more for adequate security.^[110]^[110]^[110] Diffie-Hellman key exchange, introduced in 1976 by Diffie and Hellman, enables secure shared secret generation over insecure channels using the discrete logarithm problem (DLP) in the multiplicative group of a finite field \mathbb{F}_p^*. Parties agree on a prime p and generator g; Alice computes g^a \mod p and sends it to Bob, who replies with g^b \mod p, allowing both to derive the shared key g^{a b} \mod p while an eavesdropper faces the DLP of extracting a or b from g^a \mod p. This protocol underpins ephemeral key exchanges in protocols like IPsec and SSH, with security relying on the intractability of DLP for large p.^[111]^[111]^[111] Elliptic curve cryptography (ECC), independently proposed by Neal Koblitz and Victor S. Miller in 1985, adapts these ideas to the group law on elliptic curves over finite fields E(\mathbb{F}_p), offering equivalent security to RSA or Diffie-Hellman with significantly smaller key sizes due to the higher complexity of the elliptic curve DLP (ECDLP). The curve is defined by y^2 = x^3 + a x + b \mod p, with points forming an additive group under the chord-and-tangent law. Elliptic curve Diffie-Hellman (ECDH) mirrors the original protocol using scalar multiplication Q = d G, where G is a base point, enabling shared secrets like d_A d_B G. ECDSA, standardized by NIST in 2000 but rooted in these foundations, uses ECC for digital signatures via ephemeral keys and hash functions. ECC's efficiency—256-bit keys matching 3072-bit RSA—makes it ideal for resource-constrained devices like mobile phones and IoT sensors.^[112]^[113]^[112] Central to these systems are the IFP, which challenges efficient decomposition of composite integers into primes, and the DLP, requiring computation of logarithms in cyclic groups like \mathbb{F}_p^* or E(\mathbb{F}_p). No subexponential classical algorithms exist for general instances, though specialized cases (e.g., smooth numbers) are vulnerable; index calculus attacks on DLP in \mathbb{F}_p^* are faster than Pollard's rho but still exponential for strong parameters.^[110]^[111]^[113] Early number-theoretic cryptosystems included the 1978 Merkle-Hellman knapsack, based on the subset sum problem disguised via modular multiplications, but it was broken in 1982 by Shamir's polynomial-time lattice-based attack exploiting correlations in the public key. Quantum computing poses existential threats: Shor's 1994 algorithm factors integers and solves DLPs in polynomial time on a quantum computer, potentially breaking RSA, Diffie-Hellman, and ECC with sufficient qubits (e.g., millions for 2048-bit RSA).^[114]^[115]^[115]^[116] Post-quantum cryptography addresses these vulnerabilities with number-theoretic alternatives resistant to Shor. Lattice-based schemes like NTRU, introduced in 1998 by Hoffstein, Pipher, and Silverman, use short polynomials in ring \mathbb{Z}/(x^N - 1) for encryption, relying on the hardness of shortest vector problems in ideal lattices; NTRUEncrypt supports efficient key generation and resists known quantum attacks. Code-based systems, such as McEliece's 1978 proposal using Goppa codes for error-correcting encryption, base security on decoding random linear codes, a problem intractable even quantumly, though public keys are large. These candidates, evaluated by NIST since 2016, prioritize lattice and code hardness over traditional factoring or logs. In August 2024, NIST finalized standards including FIPS 203 for ML-KEM (lattice-based key encapsulation), FIPS 204 for ML-DSA (lattice-based signatures), and FIPS 205 for SLH-DSA (hash-based signatures). In March 2025, the code-based HQC was selected for further standardization.^[117]^[117]^[118]^[118]^[119]^[120]

In Computer Science and Coding

Number theory plays a pivotal role in computer science and coding theory, particularly through the application of finite fields and algebraic structures to enable efficient algorithms for data processing and error resilience. In coding theory, number-theoretic constructs facilitate the design of error-correcting codes that protect information against transmission errors, while in algorithmic design, they underpin transforms and generators that optimize computations like convolution and randomization. These applications leverage properties of primes and polynomials to construct robust computational frameworks, distinct from their use in cryptographic protocols.^[121] Error-correcting codes represent a cornerstone of number theory's impact on coding, with Reed-Solomon codes exemplifying the use of polynomials over finite fields \mathbb{F}_q. These codes encode data as coefficients of a polynomial of degree less than k, then evaluate it at n-k distinct nonzero elements of \mathbb{F}_q to produce parity symbols, enabling correction of up to (n-k)/2 symbol errors through syndrome decoding and error locator polynomials derived via the Berlekamp-Massey algorithm. Introduced by Irving S. Reed and Gustave Solomon in 1960, Reed-Solomon codes achieve the Singleton bound for minimum distance, making them optimal for burst error correction in channels with symbol erasures.^[121] BCH codes extend this framework by incorporating cyclotomic fields to define roots of unity in \mathbb{F}_{2^m}, allowing systematic construction of cyclic codes that correct multiple errors using a generator polynomial with consecutive powers of a primitive element as roots. Developed independently by Alexis Hocquenghem in 1959 and Raj Bose and Dinesh Ray-Chaudhuri in 1960, these codes factor the error locator polynomial via the Berlekamp-Massey method and Chien search for root finding, supporting up to t errors where the designed distance is $2t+1. Their reliance on the structure of cyclotomic cosets in extension fields ensures efficient encoding and decoding for binary and non-binary alphabets.^[122] In signal processing and algorithmic efficiency, number-theoretic transforms (NTTs) provide integer-based alternatives to the fast Fourier transform (FFT) for computing convolutions modulo a prime p \equiv 1 \pmod{2n}, where n is the sequence length. By selecting a primitive nth root of unity modulo p, the NTT performs the discrete Fourier transform analog over \mathbb{Z}/p\mathbb{Z}, enabling exact convolution without floating-point precision issues via the Chinese Remainder Theorem for multi-prime moduli. Seminal work by James H. McClellan and Charles M. Rader in 1979 formalized NTTs for digital signal processing, demonstrating their utility in hardware implementations for fast multiplication of large integers and polynomials. Pseudorandom number generators in computer science draw on quadratic residues for unpredictability, as seen in the Blum-Blum-Shub (BBS) generator, which iterates x_{i+1} = x_i^2 \mod n where n = pq for distinct Blum primes p, q \equiv 3 \pmod{4}, outputting the least significant bit of each x_i. Proposed by Lenore Blum, Manuel Blum, and Michael Shub in 1986, BBS ensures next-bit unpredictability under the quadratic residuosity assumption, with period at least n^{1/4} and resistance to linear feedback analysis, making it suitable for Monte Carlo simulations and derandomization in algorithms.^[123] Hash functions and graph algorithms benefit from modular arithmetic and cycle detection techniques rooted in number theory, such as modular reductions for universal hashing over \mathbb{Z}/p\mathbb{Z} to minimize collisions in data structures like hash tables. The Pollard rho method, introduced by John M. Pollard in 1975, detects cycles in pseudo-random walks over functional graphs using Floyd's cycle-finding algorithm with f(x) = x^2 + c \mod n, enabling efficient factorization and discrete logarithm computation by identifying gcd computations on differences, with expected time complexity O(\sqrt{n}). This approach extends to parallel variants for large-scale graph traversal in network analysis. Central to these applications are finite fields \mathbb{F}_{p^k}, constructed as quotient rings \mathbb{F}_p / (f(x)) where f(x) is an irreducible polynomial of degree k over the prime field \mathbb{F}_p. Irreducibility is verified probabilistically via distinct-degree factorization or deterministically using the Berlekamp algorithm, which solves for the kernel of the Berlekamp subalgebra map Q(y) = y^q - y in the ring of q-th powers, yielding factors through gcd computations with trace polynomials. Elwyn R. Berlekamp's 1967 algorithm factors square-free polynomials over \mathbb{F}_q in polynomial time O(k^3), foundational for implementing field arithmetic in coding and transforms.^[124] Practical implementations highlight these concepts, as in QR codes where Reed-Solomon codes over \mathbb{F}_{2^8} provide error correction levels up to 30% symbol damage by interleaving RS(38,26) blocks for data and ECC, ensuring readability under occlusion. Similarly, the PSLQ algorithm detects integer relations among real numbers \{a_1, \dots, a_n\} by iteratively reducing a basis via partial Gram-Schmidt orthogonalization and monitoring the smallest column norm, terminating when it falls below a threshold \epsilon. Developed by Helaman R. P. Ferguson and David H. Bailey in 1992, PSLQ runs in O(n^3 \log B) time for precision B, enabling discoveries like relations in physical constants for computational verification.^[125]

In Physics and Other Sciences

Number theory's partition function p(n), which enumerates the number of unrestricted partitions of the positive integer n into sums of positive integers without regard to order, plays a significant role in theoretical physics, particularly in the computation of topological string partition functions on local toric Calabi-Yau threefolds. In this context, p(n) serves as a fundamental building block for generating exact results in the enumerative geometry underlying string theory models. Ramanujan's congruences for p(n), such as p(5k+4) \equiv 0 \pmod{5} for nonnegative integers k, arise from the modular properties of the generating function \sum_{n=0}^\infty p(n) q^n = \prod_{m=1}^\infty (1 - q^m)^{-1}, which is a modular form of weight -1/2 on the full modular group. These congruences, proven using the theory of modular forms, extend to broader arithmetic properties that influence physical models relying on modular invariance, such as partition sums in conformal field theories.^[126] In quantum physics, Jacobi theta functions, which are modular forms closely related to number-theoretic theta series, appear in the exact solutions for wave functions in the Aharonov-Bohm effect, where the phase shift for a charged particle encircling a magnetic flux tube is described by a multi-valued wave function involving theta-like periodicities. Similarly, theta functions contribute to the geometric interpretation of the Berry phase in adiabatic quantum evolution, linking the holonomy around parameter space cycles to modular transformations in the quantum state.^[127] Zeta function regularization, rooted in the analytic continuation of the Riemann zeta function from number theory, is essential for computing the Casimir effect, where the vacuum energy between two parallel conducting plates separated by distance a is given by E = -\frac{\pi^2 \hbar c}{720 a^3} A, with the regularization assigning a finite value to the divergent sum via \zeta(-3) = \frac{1}{120}. This technique renormalizes the infinite zero-point energies of quantum field modes, yielding the attractive force F = -\frac{\pi^2 \hbar c}{240 a^4} A.^[128] In string theory, monstrous moonshine reveals a profound connection between the Monster group M, the largest sporadic finite simple group, and the

[j&#36;-invariant](/page/J-invariant) modular function

j(\tau) = q^{-1} + 744 + 196884 q + \cdots, where the Fourier coefficients (starting from q^1) match the graded dimensions of the smallest nontrivial representation of M. This correspondence, conjectured by [Conway](/page/Conway) and [Norton](/page/Norton) and proven by Borcherds, manifests in heterotic string compactifications on K3 \times T^2$, where the Monster symmetry emerges in the twisted sector of the worldsheet conformal field theory, influencing partition functions and vertex operator algebras. Algebraic number theory underpins the symmetry analysis of crystal lattices in chemistry through the classification of space groups, which incorporate translational lattices and point group symmetries describable via rings of algebraic integers; for instance, the rotational symmetries in crystallographic point groups correspond to roots of unity in cyclotomic fields, enabling the enumeration of the 230 three-dimensional space groups. This framework aids in modeling atomic arrangements in solid-state chemistry, where the arithmetic of ideal classes in number fields helps resolve ambiguities in lattice symmetries.^[129] In biology, number theory informs sequence alignments by leveraging arithmetic topology to interpret genetic variations as knots or links in a three-dimensional analogy to number fields, allowing dynamic programming algorithms to incorporate modular constraints on substitution matrices for efficient scoring of alignments under evolutionary models.^[130] A key application in string theory involves black hole entropy, where the microscopic counting of states for extremal black holes yields S = 2\pi \sqrt{\frac{c n}{6}} via the Cardy formula, with n related to partition numbers p(k); alternatively, corrections incorporate zeta regularization, as in the leading term \frac{1}{4} (1 - 24 \zeta(-1)) = \frac{3}{4} for specific two-dimensional models, aligning the Bekenstein-Hawking entropy S = \frac{A}{4 G \hbar} with modular invariant partition functions.

References

[1]
Number Theory - Department of Mathematics at UTSA
Jan 5, 2022 · ... number theory is the queen of mathematics." Number theorists study ... Gauss. In his old age, he was the first to prove Fermat's Last ...
[2]
Number Theory | JHU CTY - Johns Hopkins Center for Talented Youth
Called "The Queen of Mathematics" by the great mathematician Carl Friedrich Gauss, number theory is the study of the natural number system from which all ...
[3]
[PDF] 4 Number Theory I: Prime Numbers - Penn Math
Number theory is the mathematical study of the natural numbers, the positive whole numbers such as 2, 17, and 123. Despite their ubiquity and apparent sim-.<|control11|><|separator|>
[4]
Number Theory and Cryptography I. Introduction
Number theory is a vast and fascinating field of mathematics, sometimes called "higher arithmetic," consisting of the study of the properties of whole numbers.Missing: overview | Show results with:overview
[5]
Methods and traditions of Babylonian mathematics: Plimpton 322 ...
Plimpton 322 is a Babylonian tablet with values related to triangle parameter equations, forming Pythagorean triples, and is associated with other Babylonian ...
[6]
3 The Egyptian Calendar | Calendars in Antiquity - Oxford Academic
The Egyptian civil calendar is a 365-day fixed scheme. The chapter also discusses lunar calendars and their relationship to the civil calendar.
[7]
[PDF] Ancient Mathematics: A Chronological Exploration of Egyptian ...
The article highlights significant contributions during the Pre-Middle and Classical periods, focusing on luminaries such as Aryabhata, Bhaskara I, Varahamihira ...
[8]
Plimpton 322: A Study of Rectangles | Foundations of Science
Aug 3, 2021 · This broken clay tablet dates from the Old Babylonian (OB) period (1900–1600 BCE) and contains a table of “Pythagorean triples” over a millennium before ...
[9]
The Plimpton 322 Tablet and the Babylonian Method of Generating ...
Mar 31, 2010 · Overall, the tablet is more or less viewed as a list of fifteen Pythagorean triplets, but scholars are divided on how and why the list was ...
[10]
[1202.3670] Euclid's theorem on the infinitude of primes - math - arXiv
Feb 16, 2012 · We provide a comprehensive historical survey of 200 different proofs of famous Euclid's theorem on the infinitude of prime numbers (300 {\small BC}--2022)}.Missing: Elements algorithm scholarly
[11]
The Sieve of Eratosthenes on JSTOR
R. A. Fisher, The Sieve of Eratosthenes, The Mathematical Gazette, Vol. 14, No. 204 (Dec., 1929), pp. 564-566.
[12]
[PDF] The Symbolic and Mathematical Influence of Diophantus's Arithmetica
Jan 1, 2015 · Diophantus's symbols for integers were in standard Greek alphabetical notation. The integers from 1 to 10 were expressed by using the first ten.Missing: source | Show results with:source
[13]
Practicing algebra in late antiquity: The problem-solving of ...
Diophantus begins his Arithmetica3 with an introduction in which he exposes the technical terms, the notation, the operations with the terms, the steps used to ...
[14]
[PDF] Mathematics in Ancient India - Indian Academy of Sciences
SERIES I ARTICLE Among the quadratic equations, the most famous are the special equations of the form x2 - Dy2 = 1, known as the Pell equation, for which ...Missing: scholarly source
[15]
[PDF] On the Brahmagupta- Fermat-Pell Equation: The Chakrav¯ala ... - HAL
Jul 29, 2023 · In the following pages we take a fresh look at the ancient Indian Chakrav¯ala or Cyclic algorithm for solving the Brahmagupta-Fermat-Pell ...
[16]
[PDF] PELL'S EQUATIONS - TCU Digital Repository
Dec 12, 2022 · Brahmagupta obtained foundational results concerning what he called “square-nature” problems, and singled out Pell's equations for the ...
[17]
[PDF] Variations on Euclid's Formula for Perfect Numbers
Euclid showed around 300 BCE [2, Proposition IX.36] that all numbers of the form x = 2q−1Mq, where Mq = 2q − 1 is prime (A000668), are perfect.Missing: source | Show results with:source
[18]
[PDF] Perfect Numbers: - UNL Digital Commons
In Euclid's Elements, he outlines a proposition surmising that a “double proportion” process resulted in perfect numbers. (For example, 28 has proper divisors ...
[19]
Pierre Fermat (1601 - 1665) - Biography - MacTutor
Fermat is best remembered for this work in number theory, in particular for Fermat's Last Theorem. This theorem states that. x n + y n = z n x^{n} + y^{n} ...
[20]
Sums of Powers of Positive Integers - Pierre de Fermat (1601-1665 ...
We will assume that Fermat already knew or had derived formulas for the sums of the first n positive integers and of their squares and cubes, and now wished ...
[21]
Small Skills, Big Networks: Marin Mersenne as Mathematical ...
A useful discussion of Mersenne and his correspondence network can be found in Hans Bots, “Marin Mersenne, 'secrétaire général' de la République des Lettres ( ...
[22]
René Descartes (1596 - 1650) - Biography - MacTutor
Biography · He makes the first step towards a theory of invariants, which at later stages derelativises the system of reference and removes arbitrariness.
[23]
[PDF] Infinitely many primes - How Euler Did It
This month, we return to one of Euler's early papers, Variae observationes circa series infinitas, to see what Euler has to say there about prime numbers.Missing: original | Show results with:original
[24]
Math Origins: The Totient Function
Leonhard Euler's totient function, φ(n), is an important object in number theory, counting the number of positive integers less than or equal to n which are ...
[25]
proof of Lagrange's four-square theorem - PlanetMath.org
Mar 22, 2013 · The following proof is essentially Lagrange's original, from around 1770 ... This is the Euler four-square identity, q.v., with different notation ...
[26]
Lagrange's Work on Wilson's Theorem: Three Mini-Primary Source ...
The theorem is known today as Wilson's Theorem in honor of John Wilson (1741–1793), a student of Edward Waring (1736–1798), who made the observation.Missing: original | Show results with:original
[27]
Disquisitiones Arithmeticae - Yale University Press
The first translation into English of the standard work on the theory of numbers by one of the greatest masters of modern mathematical analysis.
[28]
Legendre Symbol -- from Wolfram MathWorld
The Legendre symbol is a number theoretic function (a/p) which is defined to be equal to +/-1 depending on whether a is a quadratic residue modulo p.Missing: residuosity | Show results with:residuosity<|separator|>
[29]
Euler's Criterion -- from Wolfram MathWorld
### Summary of Euler's Criterion
[30]
[0808.1408] There are infinitely many prime numbers in all ... - arXiv
Aug 10, 2008 · Dirichlet's proof of infinitely many primes in arithmetic progressions was published in 1837, introduced L-series for the first time, and it is said to have ...
[31]
[PDF] Kummer's theory on ideal numbers and Fermat's Last Theorem
The failure of unique factorization in the ring of integers of certain cyclotomic fields is what motivated Ernst Kummer to develop his theory of ideal numbers, ...
[32]
Lagrange's Continued Fraction Theorem -- from Wolfram MathWorld
Lagrange's continued fraction theorem, proved by Lagrange in 1770, states that any positive quadratic surd sqrt(a) has a regular continued fraction which is ...
[33]
The development of Galois theory - Projects - MacTutor
For the remainder of the 19th century, most progress in Galois Theory was due to the development of Field Theory in Germany. While Lagrange had induced the ...
[34]
S0273-0979-07-01152-4.pdf - American Mathematical Society
Apr 19, 2007 · The first complete proof of the quadratic reciprocity law was given by Gauss in 1801 in Disquisitiones Arithmeticae [7]. After the two ...
[35]
Introduction and overview
In 1923,. Hardy and Littlewood used the circle method to prove the ternary Gold- bach conjecture for “sufficiently large” odd values of 𝑛 ≥ 𝐶 (under the.
[36]
A Delicate Collaboration: Adrian Albert and Helmut Hasse and the ...
A Delicate Collaboration: Adrian Albert and Helmut Hasse and the Principal Theorem in Division Algebras in the Early 1930's.
[37]
What is a Reciprocity Law? - jstor
A complete proof is far beyond the scope of this paper. In fact, the proof of the theorem involves almost all of "class field theory over the rationals." ...<|separator|>
[38]
an explicit zero-free region for the riemann zeta-function
Jun 26, 1998 · ABSTRACT. This paper gives an explicit zero-free region for the Riemann zeta-function derived from the Vinogradov- Korobov method. We prove ...
[39]
The Incompleteness Theorem
Apr 2, 2006 · Gödel's incompleteness theorem did away with the sec- ond of these goals, and shortly thereafter Gödel was able to show that the first was ...
[40]
Field Theory: From Equations to Axiomatization - jstor
Weber proved (often reproved, after Dedekind) various theorems about fields, which later became useful in Artin's formulation of Galois theory, and which are.
[41]
[PDF] THE BIRCH AND SWINNERTON-DYER CONJECTURE
Since the original conjecture was stated, much more elaborate conjectures concerning special values of L-functions have appeared, due to Tate,. Lichtenbaum, ...
[42]
[PDF] Number Theory I 1 Divisibility - DSpace@MIT
Feb 17, 2005 · If a divides b, then b is a multiple of a. For example, 63 is a multiple of 7. This seems simple enough, but let's play with this definition.
[43]
[PDF] Number Theory Divisibility and Primes
Divisibility and Primes. Definition. If a and b are integers and there is some integer c such that a = b · c, then we say.
[44]
[PDF] Numbers: GCD and Bezout's Identity1 - Dartmouth Computer Science
Aug 28, 2021 · In English, Bezout's identity says that given any two positive numbers a and b, there is a integer linear combination of these numbers to get ...Missing: theory | Show results with:theory
[45]
[PDF] Divisibility and greatest common divisor - Keith Conrad
Equation (3.2) is called Bezout's identity. Before we prove Theorem 3.5 we illustrate the idea of the proof in some examples.Missing: theory | Show results with:theory
[46]
2.4 The Bezout Identity - Mathematics and Computer Science
A representation of the gcd d of a and b as a linear combination of the original numbers is called an instance of the Bezout identity.
[47]
3.6 The GCD and the LCM
The gcd of two numbers depends directly and simply on their factorizations, and this approach gives us significant new information.
[48]
[PDF] lcm(a, b) × gcd(a, b) = ab for any positive integers a, b. - UMD MATH
Theorem: lcm(a, b) × gcd(a, b) = ab for any positive integers a, b. Proof: First a. Lemma: If m > 0, lcm (ma, mb) = m × lcm (a, b). Since lcm(ma, mb) is a ...
[49]
Prime Numbers - Department of Mathematics at UTSA
Dec 11, 2021 · Introduction. A prime number (or prime for short) is a natural number that has exactly two divisors: itself and the number 1.
[50]
[PDF] The infinitude of the primes - Keith Conrad
Euclid's proof of the infinitude of the primes uses the fact that all integers greater than. 1 have a prime factor, so let's discuss that first. Lemma 2.1.Missing: scholarly source
[51]
[PDF] A Collection of Proofs regarding the Infinitude of Primes
Dec 14, 2013 · Around 300BC, Euclid demonstrated, with a proof by contradiction, that infinitely many prime numbers exist. Since his work, the development of ...Missing: source | Show results with:source
[52]
[PDF] The Fundamental Theorem of Arithmetic
Both parts of the proof will use the. Well-ordering Principle for the set of natural numbers. (1) We first prove that every a > 1 can be written as a product of ...
[53]
[PDF] Fundamental Theorem of Arithmetic and Divisibility Review Mini ...
By the well-ordering principle, there is a LEAST natural number, call it n0 > 1, that cannot be written as a product or primes.
[54]
[PDF] Math 406 Section 3.5: The Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic states that every positive integer greater than 1 can be written uniquely as a product of powers of primes.<|control11|><|separator|>
[55]
[PDF] A Non-UFD Integral Domain in Which Irreducibles are Prime
Roughly speaking, irreducibles are used to produce factorizations of elements, while primes are used to show that factorizations are unique. More precisely, we ...Missing: theory | Show results with:theory
[56]
[PDF] Lecture 24 - MATH 415–502, Fall 2022 [3mm] Modern Algebra I
Irreducible elements are primes and negative primes. Factorization into irreducible factors is, up to a sign, the usual prime factorization. It is unique up to.Missing: theory | Show results with:theory
[57]
Sieve of Eratosthenes
The Sieve of Eratosthenes is a method for finding all primes up to (and possibly including) a given natural n. This method works well when n is relatively ...
[58]
[PDF] The Genuine Sieve of Eratosthenes - Computer Science
Runciman, Colin. (1997). Lazy wheel sieves and spirals of primes. Journal of functional programming, 7(2), 219–225.
[59]
Congruence -- from Wolfram MathWorld
Congruences satisfy a number of important properties, and are extremely useful in many areas of number theory.
[60]
Congruences
Congruences. Clearly, any two integers are congruent with respect to the modulus 𝑚 = 1. The definition of congruence can trivially be extended for 𝑚 < 0, but ...
[61]
proof of Chinese remainder theorem - PlanetMath.org
Mar 22, 2013 · First we prove that ai+∏j≠iaj=R 𝔞 i + ∏ j ≠ i 𝔞 j = R for each i i . Without loss of generality, assume that i=1 i = 1 . Then ...
[62]
Appendices to Quadratic Number Theory J. L. Lehman
Order Relation on Natural Numbers. Subset inclusion provides a partial order relation on the elements of N. We first explore some properties of this relation.
[63]
Fermat's Little Theorem -- from Wolfram MathWorld
It is unclear when the term "Fermat's little theorem" was first used to describe the theorem, but it was used in a German textbook by Hensel (1913) and appears ...Missing: statement source
[64]
Number Theory Summary
Euler's Criterion. An integer n coprime with an odd prime p is a quadratic residue modulo p if and only if (n|p)=1. Proof. The integers 1, 22,..., (p − 1)2 ...Missing: source | Show results with:source
[65]
Euler's Totient Theorem -- from Wolfram MathWorld
A generalization of Fermat's little theorem. Euler published a proof of the following more general theorem in 1736. Let phi(n) denote the totient function.
[66]
multiplicative function - PlanetMath.org
Mar 22, 2013 · A multiplicative function is completely determined by its values at the powers of prime numbers, a consequence of the fundamental theorem of arithmetic.
[67]
Möbius Function -- from Wolfram MathWorld
The Möbius function is a number theoretic function defined by mu(n)={0 if n has one or more repeated prime factors; 1 if n=1; (-1)^k if n is a product of k ...Missing: examples | Show results with:examples
[68]
Arithmetic Functions
λ(n)=(−1)Ω(n). The divisor function d(n) is multiplicative, but not totally multiplicative. ... The Möbius mu-function μ is the unique multiplicative arithmetic ...
[69]
Divisor Function -- from Wolfram MathWorld
The divisor function sigma_k(n) for n an integer is defined as the sum of the kth powers of the (positive integer) divisors of n, sigma_k(n)=sum_(d|n)d^k.
[70]
Riemann Zeta Function -- from Wolfram MathWorld
The Riemann zeta function is an extremely important special function of mathematics and physics that arises in definite integration.
[71]
Panorama of Arithmetic Functions
We will often denote a prime number by the letter p. A function f : N → C is called an arithmetic function. Sometimes an arithmetic.
[72]
Wilson's Theorem -- from Wolfram MathWorld
This theorem was proposed by John Wilson and published by Waring (1770), although it was previously known to Leibniz. It was proved by Lagrange in 1773.Missing: source | Show results with:source
[73]
[PDF] chebyshev's theorem and bertrand's postulate - Williams College
Sep 25, 2019 · In 1845, Joseph Bertrand conjectured that there's always a prime between n and 2n for any integer n > 1. This was proved less than a decade ...
[74]
[PDF] Prime Number Theorem - UC Davis Math
In 1896 the prime number theorem was finally proved by Jacques Hadamard [12] and also by Charles–Jean de la Vallée Poussin [6]. The first part of the proof is ...
[75]
[PDF] Riemann's Zeta Function - UCLA Statistics & Data Science
Although Chebyshev's work was published in France well be- fore Riemann's paper, Riemann does not refer to Chebyshev in his paper. He does refer to ...
[76]
[PDF] Explicit formulæ
The above formula was first proved rigorously by von. Mangoldt (1895), and ... von Mangoldt (1895) also proved the explicit formula (12.1). Landau (1909 ...
[77]
Chebyshev's Bias - Project Euclid
The title refers to the fact, noted by Chebyshev in 1853, that primes congruent to 3 modulo 4 seem to predominate over those congruent to 1.
[78]
Empirical verification of the even Goldbach conjecture and ...
Aug 9, 2025 · This paper describes how the even Goldbach conjecture was confirmed to be true for all even numbers not larger than 4·10 18 .
[79]
Recherches sur diverses applications de l'Analyse infinitesimale à la ...
Recherches sur diverses applications de l'Analyse infinitesimale à la théorie des Nombres. · Volume: 19, page 324-369 · ISSN: 0075-4102; 1435-5345/e ...Missing: 1837 | Show results with:1837
[80]
Number Field -- from Wolfram MathWorld
The totality of all expressions that can be constructed from r by repeated additions, subtractions, multiplications, and divisions is called a number field.
[81]
https://eudml.org/doc/147076
[82]
[PDF] Algebraic Number Theory - James Milne
Feb 11, 2008 · ˘ ideals in Dedekind domains factor uniquely into products of prime ideals, and. ˘ rings of integers in number fields are Dedekind domains,.
[83]
Gaussian Integer -- from Wolfram MathWorld
and rearrangements. The units of Z[i] are +/-1 and +/-i . One definition of the norm of a Gaussian integer is its complex modulus. |a+ib|=sqrt(a^2+b^2). (2) ...
[84]
[PDF] TRACE AND NORM 1. Introduction Let L/K be a finite extension of ...
Among elementary applications, the trace can be used to show some number is not in a field and the norm can be used to show some number in L is not a perfect ...
[85]
[PDF] dirichlet's unit theorem - keith conrad
Introduction. Dirichlet's unit theorem describes the structure of the unit group of orders in a number field. Theorem 1.1 (Dirichlet, 1846).Missing: source | Show results with:source
[86]
Discriminant -- from Wolfram MathWorld
### Summary of Discriminant for Algebraic Number Fields
[87]
[PDF] Dedekind Domains
All this becomes quite important in algebraic number theory. The classical approach to prime factorization and study of fractional ideals in Dedekind domains.
[88]
[PDF] cyclotomic extensions - keith conrad
The important algebraic fact we will explore is that cyclotomic extensions of every field have an abelian Galois group; we will look especially at cyclotomic ...
[89]
[PDF] ideal factorization - keith conrad
Every nonzero proper ideal in the integers of a number field admits unique factorization into a product of nonzero prime ideals.
[90]
[PDF] 2 Primes in extensions - OU Math
This chapter is about the following basic question: given an extension of number fields L/K and a prime ideal p in OK, how does pOL factor into prime ideals ...
[91]
[PDF] Algebraic Number Theory - Columbia Math Department
Jul 4, 2015 · Fractional ideals can be thought of as “ideals with a denominator”: Definition. (Fractional Ideals). A fractional ideal a is an A-submodule of K ...<|separator|>
[92]
[PDF] Algebraic Number Theory Lecture Notes - Joshua P. Swanson
Dec 9, 2015 · 31 Definition. If I,J ⊂ K are fractional ideals, say I | J if there is an ideal I0 ⊂ R such that J = II0. Equivalently (using the existence ...
[93]
[PDF] 14 The Minkowski bound and finiteness results - MIT Mathematics
Oct 25, 2017 · The ideal class group of OK is finite. Proof. By Theorem 14.16, each ideal class is represented by an ideal of norm at most mK, and by Lemma ...
[94]
Finiteness of the Class Group via Geometry of Numbers - William Stein
The explicit bound in the theorem is called the Minkowski bound, and I think it is the best known unconditional general bound (though there are better bounds in ...<|separator|>
[95]
The Hilbert class field - Kiran S. Kedlaya
In class field theory, the phrase “ L / K is unramified” is conventionally interpreted to mean that L / K is unramified over all finite places in the usual ...
[96]
[PDF] The Class Number Problem - Imperial College London
Sep 21, 2012 · There are exactly 9 imaginary quadratic fields with class number one, namely: Q(. √. −1),. Q(. √. −2), Q(. √. −3), Q(. √.
[97]
[PDF] pell's equation, ii - keith conrad
If x2 − dy2 = ±2, then the ratio (x + y. √ d)/(x − y. √ d) is a unit in Z[. √ d]. ... m2 − 2: when m = 2, the fundamental unit of Z[. √. 2] is 1 +. √. 2, with ...
[98]
[PDF] The Hasse-Minkowski Theorem - Digital Commons @ UConn
Mar 8, 2006 · The Hasse–Minkowski theorem concerns the classification of quadratic forms over global fields (i.e., finite extensions of either Q or ...
[99]
[PDF] Sums of two squares and lattices - Keith Conrad
One of the basic results of elementary number theory is Fermat's two-square theorem. Theorem 1 (Fermat, 1640). An odd prime p is a sum of two squares if and ...
[100]
[PDF] The Three-Square Theorem and its Application
This was answered by the following classical theorem which is called the Three-. Square-Theorem or the Gauss-Legendre Theorem (cf. M. B. Nathanson. [N96]).Missing: source | Show results with:source
[101]
[PDF] pythagorean triples - keith conrad
Let k = x + y and ` = y, so k>`> 0, (k, `) = 1, and k 6≡ ` mod 2. Thus (k2 − `2,2k`, k2 + `2) is a primitive triple, so finding Pythagorean triples whose legs ...
[102]
Modular elliptic curves and Fermat's Last Theorem
Modular elliptic curves and Fermat's Last Theorem from Volume 141 (1995), Issue 3 by Andrew Wiles. No abstract available for this article.
[103]
[PDF] The Mordell-Weil Theorem for Elliptic Curves
Sep 3, 2012 · The Mordell-Weil theorem is a fundamental result in the arithmetic of elliptic curves defined over a number field K, describing the structure ...
[104]
[PDF] Examples of Mordell's Equation - Keith Conrad
In 1920,. Mordell [10] showed that for each nonzero k ∈ Z, y2 = x3 + k has finitely many integral solutions. Rational solutions are a different story: there may ...
[105]
[PDF] SIEGEL'S THEOREM OVER Q 1. Introduction An elliptic curve over ...
Jul 21, 2016 · An elliptic curve over Q is a nonsingular projective curve defined over Q that has genus. 1 and a specified rational point O, which is denoted ...
[106]
[PDF] HENRI DARMON AND ANDREW GRANVILLE - McGill University
This conjecture may be deduced from the abc-conjecture (see Subsection 5.2). There are five 'small' solutions (x,y,z) to the above equation: l + 23 = 32, 25 ...
[107]
A Mean Value Theorem in Geometry of Numbers - jstor
A MEAN VALUE THEOREM IN GEOMETRY OF NUMBERS. By CARL LUDWIG SIEGEL. (Received December 8, 1944). I. Let R be the space of the n-dimensional real vectors x ...Missing: original | Show results with:original
[108]
[PDF] A Method for Obtaining Digital Signatures and Public-Key ...
R.L. Rivest, A. Shamir, and L. Adleman. ∗. Abstract. An encryption ... to join the public-key cryptosystem and to deposit his public encryption procedure.
[109]
[PDF] New Directions in Cryptography - Stanford Electrical Engineering
DIFFIE. AND. HELLMAN: NEW. DIRECTIONS. IN CRYPTOGRAPHY. 653 of possible keys. Though the problem is far too difficult to be laid to rest by such simple methods ...
[110]
[PDF] Elliptic Curve Cryptosystems - Evervault
Abstract. We discuss analogs based on elliptic curves over finite fields of public key cryptosystems which use the multiplicative group of a finite field.
[111]
[PDF] Use of Elliptic Curves in Cryptography - Victor S. Miller - Evervault
We discuss the use of elliptic curves in cryptography. In particular, we propose an analogue of the. Diffie-Hellmann key exchange protocol which appears to be ...Missing: paper | Show results with:paper
[112]
[PDF] Hiding Information and Signatures in Trap'door Knapsacks
The original easy-to-solve knapsack vector can meet any condition, such as ... MERKLE AND HELLMAN: TRAPDOOR. KNAPSACKS. 529 density of approximately l/l ...
[113]
[PDF] A polynomial time algorithm for breaking the basic Merkle-Hellman ...
The algorithm analyzes given numbers to find a trapdoor pair, allowing the solution of equations in polynomial time, thus finding cleartexts.
[114]
[PDF] Algorithms for Quantum Computation: - Discrete Log and Factoring
This paper gives algorithms for the discrete log and the factoring problems that take random polynomial time on a quantum computer (thus giving the first ...
[115]
[PDF] A ring-based public key cryptosystem - NTRU
ABSTRACT. We describe NTRU, a new public key cryptosystem. NTRU features reasonably short, easily created keys, high speed, and low memory requirements.
[116]
[PDF] A Public-Key Cryptosystem Based On Algebraic Coding Theory
In this paper we propose a public key cryptosystem which is based on the theory of algebraic codes. II. Description of the System. We base our system on the ...
[117]
[PDF] “Polynomial Codes over Certain Finite Fields”
A paper by: Irving Reed and Gustave Solomon presented by Kim Hamilton. March 31, 2000. Page 2. Significance of this paper: • Introduced ideas that form the ...
[118]
[PDF] GENERATOR*
flipping a fair coin. 1. Two pseudo-random sequence generators. In this paper, two pseudo-random sequence generators are defined and their properties discussed.Missing: original | Show results with:original
[119]
https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards
[120]
[PDF] A Polynomial Time, Numerically Stable Integer Relation Algorithm
Jul 14, 1992 · It is proved in this paper that the PSLQ algorithm terminates with a relation in a number of iterations that is bounded by a polynomial in n.
[121]
[PDF] Ramanujan and modular forms - UCLA Mathematics
What follows is a selection of three topics from Ramanujan's work that involve mod- ular forms, along with informal descriptions of some of their further ...
[122]
The Berry phase and the Aharonov-Bohm effect on optical activity
The Berry phase is proportional to the magnetic flux through the closed contour, or helical structure, according to the Aharonov-Bohm (AB) effect [6]. Therefore ...
[123]
Zeta function regularization in Casimir effect calculations and J.S. ...
May 31, 2012 · Abstract page for arXiv paper 1205.7032: Zeta function regularization in Casimir effect calculations and J.S. Dowker's contribution.
[124]
[PDF] Symmetry Relationships Between Crystal Structures
... groups, the isomorphic subgroups, and discloses cross-connections to number theory. Another appendix gives some insight into a few physico- chemical aspects ...
[125]
The arithmetic topology of genetic alignments
Jan 25, 2023 · We propose a novel mathematical paradigm for the study of genetic variation in sequence alignments.
[126]
Number theory and evolutionary genetics
Aug 3, 2023 · An unexpected link between pure mathematics and genetics, that reveals key insights into the structure of neutral mutations and the evolution of organisms.
[127]
The Queen of Mathematics - Gresham College
Lecture confirming Carl Friedrich Gauss's attribution of number theory as the "queen of mathematics."
[128]
ADRIEN-MARIE LEGENDRE
Biography from MacTutor History of Mathematics archive, detailing Legendre's contributions and noting that his 1798 book "Essai sur la théorie des nombres" was the first to include the term "number theory" in its title, helping to establish the modern terminology.