Fact-checked by Grok 2 weeks ago

Divisor

In mathematics, a divisor of an integer n, also known as a factor, is an integer d such that n is evenly divisible by d, meaning there exists an integer k for which n = d \cdot k with no remainder.^[1] This relation is denoted d \mid n. Divisors can be positive or negative; for example, the divisors of 6 include \pm[1](/page/1), \pm2, \pm3, \pm[6](/page/6).^[1] Every non-zero integer has a finite number of divisors, and 1 and -[1](/page/1) divide every integer, while every integer divides 0 and itself.^[2] Divisors form the foundation of number theory, enabling the unique prime factorization of positive integers greater than 1, where each prime power in the factorization contributes to the complete set of divisors.^[3] For instance, if n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} in prime factorization, the positive divisors of n are all products of the form p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k} where $0 \leq b_i \leq a_i for each i.^[1] This structure underpins key concepts like the greatest common divisor (GCD), the largest positive integer dividing two or more numbers, and the least common multiple (LCM), which is their product divided by the GCD.^[4] Two important arithmetic functions associated with divisors are the divisor function \tau(n) (or d(n)), which counts the number of positive divisors of n, and the sum-of-divisors function \sigma(n), which sums them.^[5] For the prime factorization above, \tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1).^[6] These functions have applications in analyzing integer properties, such as identifying perfect numbers (where \sigma(n) = 2n)^[7] and studying the distribution of primes. Divisibility and divisors also play crucial roles in cryptography, modular arithmetic, and solving Diophantine equations.^[8]

Divisors in Integers

Definition

In number theory, an integer d is a divisor of an integer n (also called a factor of n) if there exists an integer k such that n = d \cdot k; this relation is denoted by d \mid n.^[9]^[8] The quotient k = n/d is then an integer, expressing n as the product of the divisor and the quotient.^[10] Divisors of n include both positive and negative integers that satisfy the condition, with the units \pm 1 dividing every integer since n = (\pm 1) \cdot (\pm n).^[1] Proper divisors of n are the positive divisors excluding n itself.^[11] A common notation in number theory is \sigma(n) for the sum of the positive divisors of n, which will be explored further in the context of the divisor function.^[6] This divisibility relation extends naturally to concepts like the greatest common divisor of two integers, the largest positive integer dividing both.^[12]

Properties

The divisibility relation on the set of positive integers, denoted a \mid b if there exists an integer k such that b = ak, forms a partial order. This relation is reflexive, as every integer divides itself (a \mid a); antisymmetric, since if a \mid b and b \mid a, then a = b; and transitive, meaning that if a \mid b and b \mid c, then a \mid c.^[13] Bézout's identity states that for any integers a and b not both zero, there exist integers x and y such that ax + by = \gcd(a, b), where \gcd(a, b) is the greatest common divisor of a and b. This linear combination property underscores the structure of the integers as a principal ideal domain.^[14] Euclid's lemma asserts that if a prime p divides the product ab of two integers a and b, then p divides a or p divides b. This fundamental result underpins unique prime factorization in the integers.^[15] Every positive integer n has finitely many divisors, with the number of divisors d(n) satisfying d(n) = O(\sqrt{n}), as divisors typically pair such that each divisor d \leq \sqrt{n} corresponds to n/d \geq \sqrt{n}.^[16] If d \mid n and e \mid n, then \operatorname{lcm}(d, e) \mid n, since the least common multiple of two divisors of n must itself divide n. Additionally, \gcd(d, e) \mid d and \gcd(d, e) \mid e, as the greatest common divisor divides each of its arguments.^[17]

Examples

To illustrate the concept of divisors in integers, consider the number 12. Its complete set of divisors includes both positive and negative integers: ±1, ±2, ±3, ±4, ±6, ±12, since each divides 12 evenly (e.g., 12 ÷ 3 = 4, an integer).^[13] In number theory contexts, however, only positive divisors are conventionally considered to simplify analysis and focus on magnitude, so the divisors of 12 are listed as 1, 2, 3, 4, 6, 12.^[13] The proper divisors, or aliquot parts, of an integer exclude the number itself; for example, the proper divisors of 28 are 1, 2, 4, 7, 14, which sum to 28 and hint at its status as a perfect number where the sum equals the original value.^[7] Not every integer divides another; for instance, 5 does not divide 12 because 12 ÷ 5 = 2.4, which is not an integer.^[13] Divisors often appear in pairs (d, n/d) whose product equals n, providing a visual way to enumerate them—for 12, these pairs are (1, 12), (2, 6), and (3, 4).^[13] One systematic method to list all divisors is via the prime factorization of n, such as 12 = 2² × 3¹, from which combinations of exponents yield the divisors.^[18]

Number-Theoretic Concepts

Greatest Common Divisor

The greatest common divisor (GCD) of two integers a and b, denoted \gcd(a, b), is defined as the largest positive integer d that divides both a and b without leaving a remainder. This d is unique up to sign, but by convention, the positive value is taken, ensuring \gcd(a, b) = \gcd(|a|, |b|).^[12] The GCD satisfies key properties, including commutativity \gcd(a, b) = \gcd(b, a) and invariance under subtraction: \gcd(a, b) = \gcd(a, b - ka) for any integer k.^[19] These properties stem from the fact that any common divisor of a and b must also divide b - ka, preserving the set of common divisors.^[8] The Euclidean algorithm provides an efficient method to compute \gcd(a, b), assuming a \geq b > 0, by iteratively replacing a with b and b with a \mod b until b = 0, at which point \gcd(a, b) = a.^[20] This process originates from Euclid's Elements (circa 300 BCE), where it is presented as finding the "greatest common measure" of two lengths through successive subtractions or divisions.^[21] For example, to compute \gcd(48, 18):

\begin{align*} \gcd(48, 18) &= \gcd(18, 48 \mod 18) = \gcd(18, 12), \\ \gcd(18, 12) &= \gcd(12, 18 \mod 12) = \gcd(12, 6), \\ \gcd(12, 6) &= \gcd(6, 12 \mod 6) = \gcd(6, 0) = 6. \end{align*}

Thus, \gcd(48, 18) = 6. The algorithm's time complexity is O(\log \min(a, b)), making it practical for large integers.^[22] The extended Euclidean algorithm extends this process to find integers x and y such that ax + by = \gcd(a, b), embodying Bézout's identity, which states that the GCD is the smallest positive integer expressible as a linear combination of a and b. This is achieved by back-substituting the divisions from the standard algorithm; for the earlier example, $48 \cdot (-1) + 18 \cdot 3 = 6, so x = -1 and y = 3.^[23] Bézout's identity, while named after Étienne Bézout's 18th-century work on polynomials, traces its roots to the Euclidean algorithm's constructive nature.^[24] A fundamental relation involving the GCD is \gcd(a, b) \cdot \operatorname{lcm}(a, b) = |a b|, where \operatorname{lcm}(a, b) is the least common multiple of a and b. This identity arises because the prime factorizations of a and b combine such that the GCD captures the minimum exponents and the LCM the maximum, with their product yielding the exponents in a b.^[25] Computationally, the GCD can also be found via prime factorization, though this is less efficient for large numbers compared to the Euclidean method.^[12]

Divisor Function

The divisor function \sigma_k(n) is an arithmetic function that sums the k-th powers of the positive divisors of a positive integer n, defined as \sigma_k(n) = \sum_{d \mid n} d^k.^[26] Special cases include \sigma_0(n) = \tau(n), which counts the number of positive divisors of n, and \sigma_1(n) = \sigma(n), which gives the sum of the positive divisors of n.^[26] These functions arise naturally from the divisors of n and play a central role in analytic number theory.^[27] The functions \sigma_k(n) are multiplicative for any fixed integer k \geq 0, meaning that if m and n are coprime positive integers, then \sigma_k(mn) = \sigma_k(m) \sigma_k(n).^[26] This property follows from the unique prime factorization of integers. Given the prime factorization n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}, the formulas are \tau(n) = \prod_{i=1}^r (a_i + 1) and \sigma_k(n) = \prod_{i=1}^r \left( \sum_{j=0}^{a_i} p_i^{j k} \right), with the special case for k=1 yielding \sigma(n) = \prod_{i=1}^r \frac{p_i^{a_i + 1} - 1}{p_i - 1}.^[27] These expressions enable efficient computation of the functions for numbers with known factorization. In the study of perfect numbers, the sum-of-divisors function \sigma(n) is key: a positive integer n is perfect if \sigma(n) = 2n, or equivalently, if the sum of its proper divisors equals n.^[28] This condition highlights the balance between a number and its divisors, with even perfect numbers linked to Mersenne primes via the Euclid-Euler theorem.^[28] The average order of the divisor function \tau(n) is \log n, as established by Dirichlet's theorem on the sum \sum_{m \leq x} \tau(m) = x \log x + (2\gamma - 1)x + O(\sqrt{x}), where \gamma is the Euler-Mascheroni constant; this implies that \tau(n) grows logarithmically on average up to x.^[29]

Prime Divisors and Factorization

In number theory, the Fundamental Theorem of Arithmetic establishes that every integer greater than 1 can be expressed as a product of prime numbers, and this factorization is unique up to the order of the factors. This theorem, first rigorously proved by Carl Friedrich Gauss in his 1801 work Disquisitiones Arithmeticae, forms the foundation for much of elementary number theory by guaranteeing a canonical decomposition of integers into their prime building blocks.^[30]^[31] Prime divisors of a positive integer n > 1 are the distinct prime numbers that appear in its prime factorization. For instance, the prime divisors of 12 are 2 and 3, as 12 decomposes into these primes raised to positive powers. These primes are precisely the irreducible elements in the ring of integers \mathbb{Z}, where an irreducible element is a non-unit that cannot be factored into a product of two non-units. In \mathbb{Z}, every irreducible element is prime, meaning that if such an element divides a product, it divides at least one of the factors; this equivalence holds because \mathbb{Z} is a unique factorization domain.^[32] The multiplicity of a prime divisor refers to the exponent in the prime power factorization of n. For example, in the factorization of 12, the multiplicity of 2 is 2, and the multiplicity of 3 is 1. More generally, any integer n > 1 can be written as

n = \prod_{i=1}^k p_i^{a_i},

where the p_i are the distinct prime divisors of n and each a_i \geq 1 is the multiplicity of p_i. This representation underscores the uniqueness asserted by the Fundamental Theorem and enables derivations such as the multiplicative divisor function, which counts the total number of divisors from these exponents.^[32]

Algebraic Generalizations

Divisors in Rings

In commutative rings with identity, the concept of divisibility generalizes from the integers. Let R be a commutative ring with multiplicative identity $1. An element a \in R divides an element b \in R, denoted a \mid b, if there exists some c \in R such that b = a c.^[33] This relation captures the intuitive notion that a is a "factor" of b, but unlike in the integers, it may not lead to unique factorizations in general rings.^[34] Units play a central role in understanding divisibility, as they are the elements that have multiplicative inverses within the ring. An element u \in R is a unit if there exists v \in R such that u v = [1](/page/1).^[35] In the ring of integers \mathbb{Z}, the units are precisely [1](/page/1) and [-1](/page/−1), since these are the only integers whose inverses are also integers.^[36] Units divide every element of the ring, as u \mid b holds for any b \in R by taking c = b v.^[37] Two elements a, b \in R are associates if each divides the other, i.e., a \mid b and b \mid a.^[34] This equivalence relation means b = a u for some unit u \in R, so associates differ only by multiplication by a unit. In \mathbb{Z}, $2 and -2 are associates because -2 = 2 \cdot (-1) and -1 is a unit.^[33] Associates are considered "essentially the same" up to units in the context of factorization.^[38] A complication in general commutative rings is the presence of zero divisors, which disrupt the straightforward divisibility seen in the integers. A non-zero element a \in R is a zero divisor if there exists a non-zero b \in R such that a b = 0.^[39] Rings without zero divisors are called integral domains, where the cancellation law holds: if a c = b c and c \neq 0, then a = b.^[40] For example, the ring \mathbb{Z}/6\mathbb{Z} has zero divisors like $2 and $3, since $2 \cdot 3 = 0 \mod 6, contrasting with \mathbb{Z}, which is an integral domain.^[41] Divisors in rings are closely tied to principal ideals, which provide a geometric view of divisibility. The principal ideal generated by a \in R is the set (a) = \{ r a \mid r \in R \}, consisting of all multiples of a.^[42] In commutative rings, a \mid b if and only if (b) \subseteq (a), linking the order of divisibility to ideal containment.^[43] In unique factorization domains like \mathbb{Z}, factorization into irreducibles is unique up to associates and units.^[44]

Divisor Lattices

In number theory, the set of positive divisors of a positive integer n, denoted D(n), equipped with the partial order of divisibility (where d \leq e if d divides e), forms a partially ordered set called the divisor poset. This poset is a finite distributive lattice, with the greatest common divisor functioning as the meet operation and the least common multiple as the join operation.^[45] Formally, in the lattice L(D(n)), the supremum and infimum of any pair of divisors d, e \in D(n) are defined by

\sup\{d, e\} = \operatorname{lcm}(d, e), \quad \inf\{d, e\} = \operatorname{gcd}(d, e).

This structure inherits distributivity from the properties of gcd and lcm over the integers, ensuring that meets distribute over joins and vice versa.^[46]^[47] When n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} with distinct primes p_i and nonnegative integers a_i, the divisor lattice L(D(n)) is isomorphic to the direct product of k chains, each of length a_i + 1. Each chain corresponds to the exponents of a single prime in the divisors of n, reflecting the unique prime factorization theorem.^[47]^[48] The lattice L(D(n)) is graded, admitting a rank function \rho: D(n) \to \mathbb{N}_0 that assigns to each divisor d = p_1^{b_1} \cdots p_k^{b_k} the value \rho(d) = b_1 + \cdots + b_k, known as the total number of prime factors of d counted with multiplicity (denoted \Omega(d)). The height of the lattice, which is the length of the longest chain from the bottom element 1 to the top element n, equals \rho(n) = \Omega(n). This rank function facilitates the study of chains, antichains, and Möbius inversion within the lattice.^[48]^[49]

Applications in Ideal Theory

In ring theory, the concept of divisibility extends from elements to ideals in commutative rings with identity. For ideals I and J in such a ring, I divides J if there exists an ideal K such that J = I K; in domains where ideals multiply appropriately, this is equivalent to J \subseteq I.^[50] This notion generalizes the integer case, where one integer divides another if the latter is a multiple of the former, allowing ideal theory to capture factorization properties beyond principal elements.^[50] Principal ideal domains (PIDs) provide a setting where this divisibility aligns closely with element-wise behavior. A PID is an integral domain in which every ideal is principal, meaning it is generated by a single element, which acts as a "divisor" for the ideal.^[51] Examples include the integers \mathbb{Z} and polynomial rings over fields like k, where unique factorization of elements into irreducibles holds, and thus ideals inherit similar properties.^[51] In PIDs, the divisibility of ideals reduces to that of their generators, simplifying computations and preserving many number-theoretic analogies.^[50] Beyond PIDs, Dedekind domains introduce non-principal ideals while maintaining strong divisibility structures. A Dedekind domain is an integrally closed Noetherian domain of dimension one, where every nonzero proper ideal factors uniquely into a product of prime ideals, up to ordering.^[52] This unique factorization theorem for ideals ensures that divisibility is well-defined and multiplicative, even when ideals are not principal, enabling the study of arithmetic in rings like rings of integers of number fields.^[53] Unlike PIDs, Dedekind domains allow for non-trivial ideal classes, but the prime ideal factorization provides a robust framework for divisor-like relations.^[52] Fractional ideals extend this framework to capture "divisors" that may involve denominators, forming a group under multiplication. In a Dedekind domain R, a fractional ideal is an R-submodule of the fraction field K that is finitely generated and such that some nonzero element of K multiplies it into an integral ideal of R.^[54] The set of nonzero fractional ideals forms a free abelian group generated by the prime ideals, with principal fractional ideals (generated by single elements of K) as a subgroup.^[55] The divisor class group, or ideal class group, is the quotient of this group by the principal subgroup, measuring the failure of unique element factorization by classifying invertible ideals up to principal multiples; its order is the class number, which is 1 precisely when the domain is a PID.^[54] A concrete illustration occurs in the Gaussian integers \mathbb{Z}, the ring of integers of \mathbb{Q}(i), which is a Dedekind domain. The principal ideal (2) factors as (1+i)^2, since $2 = -i (1+i)^2 and -i is a unit, demonstrating how the prime 2 ramifies into the square of the prime ideal (1+i).^[56] This ramification highlights non-principal behavior in ideal divisibility, as (1+i) is prime but not principal in a way that mirrors integer primes directly.^[56]

Broader Contexts

Divisors in Polynomials

In polynomial rings over a field, the concept of divisibility extends the integer case by incorporating the structure of polynomials and their degrees. For polynomials f, g, h \in k, where k is a field, f divides g if there exists h \in k such that g = f h.^[57] This relation is foundational in k, which is an integral domain, ensuring that if f and g are nonzero and f divides g, then h is uniquely determined up to units in k, which are the nonzero constants in k.^[58] A key property of k is its status as a unique factorization domain (UFD), where every nonzero non-unit polynomial factors uniquely into irreducible polynomials, up to units and ordering.^[59] Irreducible polynomials in k play the role analogous to prime numbers in \mathbb{Z}, meaning that if an irreducible p divides a product f g, then p divides f or g.^[60] This uniqueness theorem guarantees that any factorization f = p_1^{e_1} \cdots p_m^{e_m} into irreducibles p_i (each monic, by convention) is unique except for the order of factors.^[61] When considering polynomials with integer coefficients, \mathbb{Z}, the content of a polynomial f = a_n x^n + \cdots + a_0 is defined as the greatest common divisor of its coefficients \gcd(a_0, \dots, a_n), denoted c(f).^[62] A polynomial is primitive if c(f) = 1. Gauss's lemma states that the product of two primitive polynomials in \mathbb{Z} is primitive, which implies that \mathbb{Z} is a UFD, as any polynomial f \in \mathbb{Z} can be written as f = c(f) \cdot \tilde{f} where \tilde{f} is primitive, and \tilde{f} factors uniquely into irreducibles over \mathbb{Q} that remain irreducible over \mathbb{Z}.^[63] For example, x^2 + 5x + 6 = (x+2)(x+3) is primitive and factors into irreducibles. Divisibility in k also respects degrees: if f divides g with f \neq 0, then \deg(g) = \deg(f) + \deg(h).^[57] This additive property follows from the leading coefficient behavior in the product g = f h, where the degree of the product equals the sum of the degrees for nonzero polynomials.^[58] The division algorithm underpins these concepts: for any f, d \in k with d \neq 0, there exist unique q, r \in k such that f = q d + r and either r = 0 or \deg(r) < \deg(d).^[64] If d is monic (leading coefficient 1), the algorithm proceeds via long division, ensuring q and r have coefficients in k.^[65] For instance, dividing x^3 + 2x^2 - x + 1 by the monic x^2 + x - 1 yields quotient x + 1 and remainder -x + 2. This enables the Euclidean algorithm for computing greatest common divisors in k, defined as monic polynomials of maximal degree dividing both inputs.^[66]

Divisors in Geometry and Number Fields

In algebraic geometry, divisors on curves generalize the concept of zeros and poles of functions to formal combinations of points. A Weil divisor on a smooth projective curve X over an algebraically closed field is a formal \mathbb{Z}-linear combination D = \sum_{P \in X} n_P P, where n_P \in \mathbb{Z} are integers and only finitely many are nonzero.^[67] These divisors form an abelian group under addition, denoted \mathrm{Div}(X). Principal divisors arise from rational functions f \in k(X)^\times, defined as \mathrm{div}(f) = \sum_{P \in X} v_P(f) P, where v_P(f) is the valuation at P; the set of principal divisors, \mathrm{Prin}(X), is a subgroup of \mathrm{Div}(X).^[68] The degree of a divisor D = \sum n_P P on such a curve is defined as \deg(D) = \sum n_P, providing an invariant under the action of rational functions since \deg(\mathrm{div}(f)) = 0 for any f. This degree function relates to intersection theory, where for a curve embedded in projective space, the degree measures intersections with hyperplanes, capturing topological and arithmetic properties like the genus through the Riemann-Hurwitz formula. In the context of number fields, divisors extend to ideals in the ring of integers \mathcal{O}_K of a number field K. The ideal class group \mathrm{Cl}(K) is the quotient of the group of fractional ideals by principal ideals, quantifying the failure of unique factorization into elements; for Dedekind domains like \mathcal{O}_K, every nonzero ideal factors uniquely into prime ideals, but elements may not, with \mathrm{Cl}(K) trivial precisely when \mathcal{O}_K is a principal ideal domain.^[69] The Riemann-Roch theorem connects divisors to the geometry of the curve via the dimension of Riemann-Roch spaces. For a divisor D on a smooth projective curve X of genus g, the space L(D) = \{ f \in k(X) \mid \mathrm{div}(f) + D \geq 0 \} \cup \{0\} consists of rational functions with poles bounded by D, and the theorem states \dim L(D) - \dim L(K - D) = \deg(D) - g + 1, where K is the canonical divisor. This determines the dimension of sections of line bundles associated to D, enabling computations of the Picard group \mathrm{Pic}^0(X) = \mathrm{Div}^0(X)/\mathrm{Prin}(X), which parametrizes degree-zero line bundles.^[70] On elliptic curves, which are genus-one curves with a specified base point O, divisors play a central role in the group structure. The Mordell-Weil group E(k) of rational points on an elliptic curve E over a field k is finitely generated by the Mordell-Weil theorem, and it is isomorphic to \mathrm{Pic}^0(E), where degree-zero divisors modulo principals correspond to translations by points: the divisor P + (-P) - 2O is principal for P \in E(k), reflecting the group law. For example, the Riemann-Roch theorem simplifies to \dim L(D) = \deg(D) for \deg(D) \geq 1, allowing explicit computation of ranks and generators in the Mordell-Weil group via descent methods on associated divisors.

Historical Development

The concept of a divisor originated in ancient Greek mathematics, with Euclid's Elements (circa 300 BCE) providing the foundational treatment of divisibility among integers and introducing the Euclidean algorithm to compute the greatest common divisor (GCD) of two lengths or numbers.^[71] This algorithm, based on repeated division and remainders, established a systematic approach to determining common divisors and underpins much of later number theory.^[72] Euclid also anticipated the Fundamental Theorem of Arithmetic, asserting that every integer greater than 1 factors uniquely into primes, though a fully rigorous proof came later.^[73] Medieval mathematicians built on these ideas, notably Leonardo Fibonacci in his Liber Abaci (1202), which introduced trial division as a practical method for integer factorization and promoted Hindu-Arabic numerals for computational efficiency in divisibility problems.^[74] Fibonacci's work disseminated ancient results to Europe, emphasizing factorization in commercial arithmetic and solving Diophantine equations involving divisors. In the 19th century, challenges to unique factorization in algebraic number rings prompted Richard Dedekind to develop ideal theory in 1871, generalizing divisors as ideals to restore unique factorization in Dedekind domains.^[75] Dedekind's approach addressed failures of the Fundamental Theorem in extensions like the cyclotomic integers, where ordinary elements do not factor uniquely.^[76] Concurrently, Bernhard Riemann's 1857 paper on abelian functions employed divisors on Riemann surfaces to formulate the Riemann-Roch theorem, quantifying the dimension of spaces of meromorphic functions with prescribed divisor constraints.^[77] The 20th century saw Emmy Noether abstracting divisor concepts within ring theory during the 1920s, defining ideals and modules rigorously and characterizing rings where unique factorization holds via ascending chain conditions.^[78] Noether's framework generalized Dedekind's ideals to arbitrary commutative rings, influencing modern algebra.^[79] Divisor class groups, introduced by Dedekind but refined in this era, measure the deviation from principal ideal domains in number fields and became central to class field theory.^[80] In algebraic geometry, André Weil's 1930s works, including his foundations for varieties over finite fields, integrated divisors into intersection theory and zeta functions, paving the way for scheme theory.^[81]

References

[1]
[PDF] NUMBER THEORY 1. Divisor A divisor of an integer n, also called a ...
Nov 13, 2016 · A divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder.
[2]
[PDF] Math 127: Division
We say that b divides a if there exists an integer k such that a = kb. The number b is called a divisor or factor of a, and the number a is called a multiple ...
[3]
[PDF] Chapter 4 Number Theory
Definition: Suppose that a and b are integers. Then a divides b if b = an for some integer n. a is called a factor or divisor of b. b is called a multiple of a ...
[4]
[PDF] Number Theory - FSU Math
(1) The greatest common divisor of a and b, denoted GCD (a, b), is the largest positive integer d such that d|a and d|b. (2) The least common multiple of a and ...
[5]
[PDF] NUMBER THEORY, PART 1 1. Divisors Definition. The sigma ...
Divisors. Definition. The sigma function σ(n) is defined as the sum of the divisors of the positive integer n. The divisor function τ(n) is defined as the ...
[6]
Divisor Functions
Divisor Functions. Definition. The sum of divisors function is given by. $$\sigma(n) = \sum_{d \mid n}. As usual, the notation " $d \mid n$ ...Missing: properties | Show results with:properties
[7]
[PDF] An Introduction to Number Theory Prime Numbers and Their ...
A key concept of number theory is divisibility. Being able to determine divisibility will help in advanced division, determining the greatest common factor and ...
[8]
[PDF] Overview of Number Theory Basics Divisibility
Given integers a > 0 and b > 0, we define gcd(a, b) = c, the greatest common divisor (GCD), as the greatest number that divides both a and b. Example gcd(256, ...
[9]
[PDF] Elementary Number Theory (1) - Introduction to Cryptography CS 355
Definition. Given integers a and b, with a ≠ 0, a divides b. (denoted a|b) if ∃ integer k, s.t. b = ak. a is called a divisor of b, and b a multiple of a.<|control11|><|separator|>
[10]
[PDF] The Greatest Common Divisor By Doron Zeilberger Obvious (but ...
Definition: The set of divisors of an integer n, Div(n), is the set of all integers m such that m is a divisor of n. Div(n) = {m; n/m is an integer} .
[11]
[PDF] NUMBER SYSTEMS Number theory is the study of the integers. We ...
Notice that every integer n > 1 has at least two positive divisors, namely 1 and n (these are sometimes called the trivial divisors of n). If d | n and 1 <d<n, ...
[12]
[PDF] 2.2 The Greatest Common Divisor 1. Definitions 2. Theorems
Divisible: An integer b is said to be divisible by an integer a 6= 0, written a|b, if there exists some integer c such that b = ac. common divisor: An integer d ...<|control11|><|separator|>
[13]
Divisor -- from Wolfram MathWorld
### Summary of Divisor Properties in Integers
[14]
Bézout's Identity -- from Wolfram MathWorld
Jones, G. A. and Jones, J. M. "Bezout's Identity." §1.2 in Elementary Number Theory. Berlin: Springer-Verlag, pp. 7-11, 1998. Referenced on Wolfram|Alpha.Missing: source | Show results with:source
[15]
Euclid's Lemma -- from Wolfram MathWorld
### Summary of Euclid's Lemma
[16]
Divisor Function -- from Wolfram MathWorld
### Summary of Number of Divisors from Divisor Function (MathWorld)
[17]
Least Common Multiple -- from Wolfram MathWorld
### Summary of Properties Relating LCM and GCD to Divisors
[18]
Perfect Number -- from Wolfram MathWorld
Perfect numbers are positive integers n such that n=s(n), (1) where s(n) is the restricted divisor function (i.e., the sum of proper divisors of n), ...<|control11|><|separator|>
[19]
Number Theory Summary
. Finding all the divisors of a large integer without a huge number of trial divisions generally requires knowing its prime factorization. This can be a ...
[20]
[PDF] Greatest Common Divisors
The greatest common divisor of two integers is the largest integer that divides both of them. It's denoted as (a, b).
[21]
Book VII - Euclid's Elements - Clark University
If a number measures two numbers, then it also measures their greatest common measure. Proposition 3: To find the greatest common measure of three given numbers ...
[22]
3.3 GCDs and The Euclidean Algorithm
This is called the Euclidean Algorithm after Euclid of Alexandria because it was included in the book(s) of The Elements he wrote in around 300BCE. We don't ...<|separator|>
[23]
3.3 The Euclidean Algorithm
The Euclidean Algorithm is an important theoretical tool as well as a practical algorithm. Here is how it works.
[24]
2.4 The Bezout Identity - Mathematics and Computer Science
A representation of the gcd d of a and b as a linear combination a x + b y = d of the original numbers is called an instance of the Bezout identity .Missing: source | Show results with:source
[25]
It is not “Bézout's identity” - arXiv
Jun 21, 2024 · An increasing number of mathematicians have been calling this “Bézout's identity”, “Bézout's lemma” or even “Bézout's theorem”.Missing: citation | Show results with:citation
[26]
https://dlmf.nist.gov/27.2
[27]
DLMF: §27.2 Functions ‣ Multiplicative Number Theory ‣ Chapter ...
It is the special case k = 2 of the function d k ⁡ ( n ) that counts the number of ways of expressing n as the product of k factors, with the order of factors ...
[28]
https://math.gordon.edu/ntic/ntic2017/section-perfect-nums.html
[29]
NTIC Perfect Numbers - Mathematics and Computer Science
If \sigma(n)=kn for some integer k, then we say that n is k-perfect. Or, if \sigma(n)>2n, then n is abundant. If \sigma(n)<2n, we say n is deficient.
[30]
[PDF] 10. Average orders Now that we have defined some arithmetic ...
Mar 8, 2017 · d(n) = xlog x + (2γ − 1)x + O(x1/2). In particular the average order of d(n) is log n. Proof. We have. ∑ n ...
[31]
[PDF] Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic Every integer greater than one can be expressed uniquely ... theory by Gauss, in 1798, in his Disquisitiones Arithmeticae.
[32]
Disquisitiones arithmeticae : Gauss, Carl Friedrich, 1777-1855
Aug 11, 2018 · Disquisitiones arithmeticae. by: Gauss, Carl Friedrich, 1777-1855. Publication date: 1801. Topics: Number theory. Publisher: Lipsiae : In ...Missing: fundamental | Show results with:fundamental<|control11|><|separator|>
[33]
[PDF] Introduction to the Theory of Numbers
Nov 21, 2014 · ... HARDY. AND. E. M. WRIGHT. Principal and Vice-Chancellor of the ... divisor of WL” implies “1 is a divisor of n” ', or, what is the same ...
[34]
[PDF] Divisibility and Principal Ideal Domains Divisibility. Suppose that R ...
Divisibility. Suppose that R is an integral domain with unit. If a, b ∈ R, then we say that a divides b if there exists an element c ∈ R such that b = ac.
[35]
[PDF] Section III.3. Factorization in Commutative Rings
Mar 22, 2024 · In this section, we introduce the concepts of divisibility, irreducibility, and prime elements in a ring. We define a unique factorization ...
[36]
[PDF] An Introduction to Commutative Rings
Definition 7 (Unit). An element x ∈ A is a unit if there exists y ∈ A such that xy = 1. Since x is uniquely determined by y, ...
[37]
[PDF] Notes on Ring Theory - Mathematics
Feb 1, 2007 · Definition: divisibility in a ring. Thus units clearly divide every element of the ring. In a commutative ring, it is easy to show that every ...<|control11|><|separator|>
[38]
[PDF] 4. Commutative rings I
[1] Divisibility and ideals can certainly be discussed without the assumption of commutativity, but the peripheral.
[39]
[PDF] ASSOCIATE ELEMENTS IN COMMUTATIVE RINGS Let R be a ...
Abstract. Let R be a commutative ring with identity. For a, b ∈ R define a and b to be associates, denoted a ∼ b, if a|b and b|a, so a = rb and b = sa.
[40]
[PDF] 3. Commutative rings - Brandeis
A zero divisor is a nonzero element a ∈ R so that ab = 0 for some b %= 0 in R. A ring with no zero divisors is called a domain (or integral domain). Lang uses ...
[41]
https://www.math.lsu.edu/~madden/M7210fall2012/lec20121026-Units-ZeroDiv.pdf
[42]
[PDF] M7210 Lecture 28 Friday October 26, 2012 Commutative Rings III
Oct 26, 2012 · Definition. Let A be a commutative ring and let a ∈ A. i) a is called a unit if a 6= 0A and there is b ∈ A such that ab = 1A. ii) a is called a ...
[43]
[PDF] Ideals and Subrings
Apr 8, 2018 · Definition. Let R be a commutative ring, and let a ∈ R. The principal ideal generated by a is hai = {ra | r ∈ R}. For example, in the ring ...
[44]
IAAWA Ideals and Quotient Rings - UTK Math
Therefore, satisfies the definition of an ideal. 🔗 If is a commutative ring, then an ideal of the form ⟨ a ⟩ = { a r : r ∈ R } is called a principal ideal .
[45]
[PDF] Unique Factorization Domains
A Unique Factorization Domain (UFD) is an integral domain R in which every nonzero element r ∈ R which is not a unit has the following properties. 1 r can be ...
[46]
[PDF] Notes on Lattice Theory J. B. Nation University of Hawaii
We say that P is isomorphic to Q, written P ∼= Q, if there is a map f : P → Q which is one-to-one, onto, and both f and f−1 are order preserving, i.e., x ≤ y ...
[47]
[PDF] Lattice theory - Stanford Concurrency Group
The natural numbers ordered by x|y is a lattice with lcm and gcd as join and meet. To axiomatize the theory of lattices requires more than just the axioms of ...
[48]
[PDF] The Number of Meets between Two Subsets of a Lattice haye a least ...
Let L be a lattice of divisors of an integer (isomorphically, a direct product ... 1 L 1 and a product of chains is a distributive lattice, theorem 1 follows ...
[49]
[PDF] Lecture Notes on Algebraic Combinatorics - Jeremy Martin
Sep 19, 2025 · rank function r : P → Z, one can choose the rank of any single ... the divisor lattice Dn.) Proposition 1.3.6 (Unique factorization ...
[50]
[PDF] Partially Ordered Sets and their Möbius Functions I
Jun 10, 2014 · Example: The Divisor Lattice. Given n ∈ P the corresponding divisor lattice is. Dn = {d ∈ P : d|n} partially ordered by c ≤Dn d if and ...<|control11|><|separator|>
[51]
[PDF] NOTES ON IDEALS 1. Introduction Let R be a commutative ring ...
Definition 6.9. An integral domain in which all ideals are principal is called a principal ideal domain, which is abbreviated to PID. Example 6.10. The ...
[52]
[PDF] Principal Ideal - UC Berkeley math
Principal Ideal. Domains. P I D. Definition A ring. 12 is a principal ideal domain it. Y. R is an integral domain. I CR ideal. I. Ca. For. C. Every ideal of R ...
[53]
[PDF] Math 154. Unique factorization in Dedekind domains
For this we will use the prime ideal factorization in Dedekind domains. Since every nonzero proper ideal is a product of finitely many maximal ideals, to ...
[54]
[PDF] 3 Unique factorization of ideals in Dedekind domains
Sep 17, 2015 · In a Dedekind domain every nonzero fractional ideal I has a unique factorization I = Qp pvp(I) into prime ideals. Conversely, one can show that ...
[55]
[PDF] NOTES ON DEDEKIND RINGS Contents 1. Fractional ideals 1 2 ...
The class group C(R) is the Abelian group of isomorphism classes of invertible fractional ideals of R. If this group is finite, its order is the class number of ...
[56]
[PDF] ideal factorization - keith conrad
Using some concepts from commutative algebra allows for another approach to unique factorization of ideals that is applicable more broadly. Proofs in this ...<|separator|>
[57]
[PDF] the gaussian integers - keith conrad
A Gaussian integer has even norm if and only if it is a multiple of 1 + i. Proof. Since N(1 +i) = 2, any multiple of 1 +i has even norm. Conversely, suppose m+ ...Missing: ideal ramification
[58]
[PDF] Divisibility in F[x]
(1) If f divides g, then if c is a nonzero element of F, cf | g. (2) Every divisor of g has degree less than or equal to that of g. Definition 18.2. A ...
[59]
[PDF] Math 412. Polynomial Rings over a Field.
THEOREM 4.14: Every non-constant polynomial in F[x] can be factored into irreducible poly- nomials. This factorization is essentially unique in the sense that ...
[60]
[PDF] Factorization in Polynomial Rings - Columbia Math Department
Moreover, the factorization is unique up to mul- tiplying by units, in the sense that, if q1,...,q` are irreducible polynomials such that f = p1 ···pk = q1 ···q` ...
[61]
[PDF] A.2 Polynomial Algebra over Fields
The division algorithm is required to do that. Checking multiplicative associativity and distributivity also requires some care. For the integers we found that ...
[62]
[PDF] 1 Factorization of Polynomials - Harvard SEAS
Nov 6, 2017 · Thm (Unique Factorization of Polynomials): Every f(x) ∈ F[x] can be written as a product of irreducible polynomials f(x) = g1(x)g2(x)···gk(x), ...
[63]
[PDF] M373K Lecture Notes - UT Math
Apr 18, 2013 · So we may write f = dg where d ∈ Z is the content of f and q is primitive. Lemma 1.1. The product of primitive polynomials is primitive. Proof.
[64]
[PDF] Introduction to Modern Algebra
Mar 21, 2024 · Lemma 45.25. Gauss's Lemma. If D is a UFD, then a product of two primitive polynomials in D[x] is again primitive.
[65]
Polynomials | Department of Mathematical Sciences
[Division Algorithm] For any polynomials f(x) and g(x) in F[x], with g(x) 0, there exist unique polynomials q(x),r(x) F[x] such that. f(x) = q(x)g(x) + r(x) ...
[66]
[PDF] Lecture 6 1 Overview 2 Polynomial Division Algorithm
Feb 27, 2012 · Since we are working in general ring R we need to assume the polynomial we are dividing on is monic to guarantee that we do not face the awkward.
[67]
[PDF] Number Theory for Polynomials
If F is a field and m(x) is a monic polynomial over F, we let F[x]/(m(x)) denote the set of all congruence classes of polynomials modulo m(x). Then F[x]/(m(x)).
[68]
[PDF] FOUNDATIONS OF ALGEBRAIC GEOMETRY CLASS 18
Dec 2, 2005 · A Weil divisor is said to be effective if nY ≥ 0 for all Y. In this case we say D ≥ 0, and by D1 ≥ D2 we mean D1 − D2 ≥ 0. The support of a ...<|control11|><|separator|>
[69]
[PDF] FOUNDATIONS OF ALGEBRAIC GEOMETRY CLASSES 28 AND 29
Weil divisors obviously form an abelian group, denoted Weil X. For example, if X is a curve (such as the Spec of a Dedekind domain), the Weil divisors are ...
[70]
[PDF] Algebraic Number Theory - Columbia Math Department
Jul 4, 2015 · Hence we obtain the unique factorization of ideals in the ring of integers, though we do not have unique factorization of elements. Theorem 3.
[71]
[PDF] Divisors and the Riemann-Roch theorem - UC Berkeley math
If D denotes the divisor (∞) − (0), then `(D) is the dimension of the space of holomorphic functions with at most a pole of order 1 in ∞ and a zero in 0; this ...
[72]
[PDF] Euclid's Algorithm for the Greatest Common Divisor
It was probably the standard “textbook” for geometry for more than 1500 years in western Europe and continues to influence the way geometry is taught to this ...
[73]
[PDF] Greatest Common Divisor: Algorithm and Proof
Aug 9, 2019 · An algorithm for finding the greatest common divisor of two numbers appears in Euclid's Elements. 2.1 Historical Background. There is almost ...
[74]
[PDF] Some fundamental theorems in Mathematics
Jul 22, 2018 · Criteria for the current list of 272 theorems are whether the result can be formulated elegantly, whether it is beautiful or useful and ...
[75]
[PDF] Introduction to Factorization and Primality Testing - Penn State
§5 Trial division was first described by Fibonacci in his book “Liber Abaci” of 1202. ... The history of factorization methods related to searching for t ...
[76]
[PDF] Dedekind's 1871 Version of the Theory of Ideals
Mar 19, 2004 · In the 1871 version, after showing that every prime ideal is simple, he remarks, in passing, that "we will therefore speak only of prime ideals ...
[77]
[PDF] Dedekind's 1871 version of the theory of ideals∗ - andrew.cmu.ed
Mar 19, 2004 · In the 1871 version, after showing that every prime ideal is simple, he remarks, in passing, that “we will therefore speak only of prime ideals ...
[78]
[PDF] The Riemann-Roch Theorem and Geometry, 1854-1914
In the 1850s (see his [1857] and Laugwitz [1996]) Riemann put together a theory of complex functions de ned on some 2-dimensional domain, which might be any ...
[79]
[PDF] What are discrete valuation rings? What are Dedekind domains?
Dec 3, 2019 · The modern version is largely due to Emmy Noether who in the 1920s studied and char- acterized Dedekind domains as a general type of ring for ...
[80]
[PDF] On Emmy Noether and Her Algebraic Works
In the second period from 1920-1926, she concentrated on the theory of mathematical rings. She developed the abstract and conceptual approach to algebra ...
[81]
[PDF] Algebraic Number Theory - UCSB Math
It becomes clear from his Preface that Number Theory was Neukirch's favorite subject in mathematics. He was enthusiastic about it, and he was also.<|control11|><|separator|>
[82]
[PDF] the weil conjectures for elliptic curves - UChicago Math
It is then throughout the 20th century, with the advent of highly influential number theorists and algebraic geometers such as Louis Mordell and André Weil,.