Fact-checked by Grok 2 weeks ago

Fundamental theorem of arithmetic

The Fundamental Theorem of Arithmetic, also known as the unique factorization theorem or prime factorization theorem, asserts that every integer greater than 1 can be expressed as a product of one or more prime numbers, and this representation is unique up to the ordering of the factors.^[1] This means that for any such integer n, there exist distinct primes p_1, p_2, \dots, p_k and positive integers e_1, e_2, \dots, e_k such that n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, with no other combination of primes yielding the same product disregarding order.^[1] The theorem's two core components—existence and uniqueness—have distinct historical origins. The existence of prime factorizations for all integers greater than 1 traces back to Euclid's Elements (circa 300 BCE), where Propositions 31 and 32 in Book VII demonstrate that every composite number has a prime divisor, allowing factorization into primes by repetition, building on the infinitude of primes established earlier in the text.^[2] However, the uniqueness of this factorization was not fully proven until Carl Friedrich Gauss provided a rigorous demonstration in 1801 (composed in 1798) as Article 16 of his seminal work Disquisitiones Arithmeticae, marking the first complete and systematic proof of the theorem.^[2] Earlier attempts at uniqueness, such as those by 17th-century mathematicians like Jean Prestet, fell short of full rigor.^[3] Proofs of the theorem typically rely on foundational results in divisibility and induction. Existence follows by strong mathematical induction: base case for primes is trivial, and for composites, repeated division by the smallest prime factor yields a prime factorization.^[1] Uniqueness invokes Euclid's lemma—if a prime p divides a product ab, then p divides a or b—to show that any two factorizations must share the same primes with identical exponents, often using the well-ordering principle to avoid infinite descent.^[1] This theorem underpins the classification of the ring of integers \mathbb{Z} as a unique factorization domain, a concept generalized in abstract algebra.^[2] Beyond pure mathematics, the Fundamental Theorem of Arithmetic has profound applications across fields. It forms the basis for efficient algorithms in computing greatest common divisors via the Euclidean algorithm and enables primality testing, while the computational hardness of factoring large semiprimes directly supports public-key cryptography systems like RSA, where security relies on the theorem's uniqueness but the practical intractability of reverse-engineering factorizations.^[4] In number theory, it facilitates solutions to Diophantine equations and theorems like the Four-Square Theorem, highlighting its enduring role as a foundational pillar of arithmetic and its extensions.^[2]

Statement and Concepts

Formal Statement

The Fundamental Theorem of Arithmetic states that every positive integer greater than 1 can be expressed as a product of one or more prime numbers, and this representation is unique up to the order of the factors.^[5] This theorem applies specifically to positive integers n > 1; the integer 1 is excluded as a unit (neither prime nor composite), while negative integers are addressed by applying the theorem to their absolute values, thereby extending the result to all non-zero integers.^[6] The unique prime factorization is conventionally denoted in canonical form as

n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k},

where the p_i are distinct primes (typically ordered increasingly) and each exponent a_i \geq 1 is a positive integer.^[7] For illustration, the integer 12 admits the factorization $12 = 2^2 \times 3^1, which is unique regardless of factor ordering.^[1]

Prime Numbers and Factorization

A prime number is defined as a positive integer greater than 1 that has no positive divisors other than 1 and itself.^[8] This definition ensures that primes serve as the indivisible building blocks for constructing all larger positive integers through multiplication. For example, 2, 3, 5, and 7 are primes, while 4 is not, as it is divisible by 2 in addition to 1 and itself.^[9] In the ring of integers \mathbb{Z}, the concepts of prime elements and irreducible elements coincide. An element p \in \mathbb{Z} (non-zero and non-unit) is irreducible if whenever p = ab for a, b \in \mathbb{Z}, then either a or b is a unit; it is prime if whenever p divides a product bc, then p divides b or c. In \mathbb{Z}, every prime is irreducible, and every irreducible is prime, specifically the elements \pm q where q is a positive prime.^[10] This equivalence holds in \mathbb{Z} but not necessarily in other integral domains, where irreducibles may fail to be prime, highlighting the special structure of the integers.^[11] The process of prime factorization involves repeatedly dividing a composite positive integer by the smallest prime divisor until only primes remain, expressing the number as a product of these primes. For instance, starting with 30, divide by 2 to get 15, then by 3 to get 5, yielding $30 = 2 \times 3 \times 5. This method breaks down any composite number greater than 1 into primes, implying the existence of infinitely many primes to factor arbitrarily large integers, though the infinitude is not established here.^[12] In \mathbb{Z}, the units are precisely \pm 1, the only elements with multiplicative inverses in the ring. These units play a key role in factorization by allowing associate elements—such as p and -p for a prime p—to be considered equivalent up to units, ensuring that factorizations are unique modulo signs and ordering.^[13]

Historical Development

Ancient and Early Modern Ideas

The concepts central to the fundamental theorem of arithmetic, particularly the role of prime numbers and factorization, trace their origins to ancient Greek mathematics. Euclid, in his Elements composed around 300 BCE, provided the first systematic treatment of primes, proving their infinitude through a proof by contradiction in Book IX, Proposition 20: assuming a finite number of primes leads to the construction of a new prime not in the list, via the product of existing primes plus one.^[14] He also established foundational tools for factorization in Book VII, where the Euclidean algorithm computes the greatest common divisor of two integers, enabling the repeated decomposition of numbers into prime factors, though without an explicit statement on uniqueness.^[15] In ancient Indian mathematics, similar intuitive understandings of factorization emerged independently, often in the context of solving Diophantine equations. Aryabhata, writing in the 5th century CE in his Aryabhatiya, developed the kuttaka method for finding integer solutions to linear equations like by = ax + c, which relies on gcd computations akin to Euclid's algorithm and implicitly incorporates prime factorization to resolve coprimality conditions.^[16] By the 12th century, Bhaskara II expanded these ideas in his Lilavati and Bijaganita, applying factorization techniques to indeterminate problems such as Pell's equation px^2 + 1 = y^2 (for specific p like 61 and 67), where he derived large solutions by breaking down numbers into prime components, demonstrating practical use without formal uniqueness claims.^[17] Medieval Islamic mathematicians built on these traditions by refining divisibility and arithmetic operations. Al-Karaji, active in the late 10th and early 11th centuries, explored divisibility rules in his al-Kafi fi al-hisab, including methods to check divisibility by 9 (via digit sums) and 11 (via alternating sums), which facilitated factorization processes in computational contexts but stopped short of proving unique prime decompositions.^[18] During the early modern period in Europe, interest in primes intensified, though full rigor on uniqueness remained elusive. Pierre de Fermat, in the 17th century, advanced number theory by proving that primes of the form $4n+1 are uniquely sums of two squares and demonstrating factorizations of large composites like 2027651281 = 44021 × 46061, using methods that highlighted prime properties without addressing overall uniqueness for all integers.^[19] René Descartes, in his 1637 La Géométrie, applied divisibility principles to factor polynomials—such as noting that factors' constant terms divide the original's—extending these heuristics to integer cases in correspondence, though primarily focused on algebraic rather than pure number-theoretic uniqueness.^[20]

Formulation by Euler and Gauss

While Leonhard Euler and other 18th-century mathematicians, such as Joseph-Louis Lagrange, implicitly relied on the uniqueness of prime factorization in their number-theoretic work—for instance, Euler in his development of the Riemann zeta function via the Euler product formula—the first explicit and rigorous proof of this uniqueness was not provided until Carl Friedrich Gauss.^[21] This approach would show that any supposed counterexample to uniqueness would lead to an infinite descending chain of positive integers, which is impossible, though the formalization came later. Carl Friedrich Gauss further solidified the theorem's status in his seminal 1801 work Disquisitiones Arithmeticae, where he presented a complete proof encompassing both existence and uniqueness of prime factorization.^[22] Gauss explicitly termed it the "fundamental theorem of arithmetic," highlighting its central role as the cornerstone of integer arithmetic, from which many other results in the field derive.^[21] In Article 16, he stated that every composite number resolves into prime factors in exactly one way (up to order), criticizing contemporaries for often assuming this without proof and providing a deduction based on Euclid's lemma.^[22] In the 19th century, Peter Gustav Lejeune Dirichlet extended implications of the theorem through his 1837 work on primes in arithmetic progressions, where the unique factorization underpins the Euler product representation of Dirichlet L-functions.^[23] This allowed Dirichlet to prove the infinitude of primes in coprime arithmetic progressions by showing the L-function's non-vanishing at s=1, relying on the theorem to ensure the multiplicative structure over primes.^[23] Such developments underscored the theorem's broader analytical applications. The terminology evolved from earlier phrases like "theorem on the decomposition of numbers," used in 18th-century texts, to Gauss's enduring "fundamental theorem of arithmetic," reflecting its foundational importance and gaining widespread adoption in subsequent literature.^[22]

Proof

Existence of Prime Factorization

The existence part of the fundamental theorem of arithmetic asserts that every positive integer greater than 1 can be expressed as a finite product of prime numbers.^[24] This factorization may consist of a single prime (for prime numbers themselves) or a product of multiple primes, possibly with repetitions. The number 1 is excluded from this statement, as it has no prime factors by definition, while prime numbers trivially factorize as themselves.^[25] One standard proof of existence proceeds by strong mathematical induction on the integer n > 1. For the base case, when n = 2, the number 2 is prime and thus factors as itself. Assume the statement holds for all integers k with $1 < k < n; that is, each such k has at least one prime factor. Now consider n. If n is prime, it factors as itself. If n is composite, then n = a b where $1 < a < n and $1 < b < n. By the inductive hypothesis, a has a prime factor p, and since a divides n, it follows that p divides n. Thus, n has a prime factor, and repeating the process on the quotient n/p (which is smaller than n) yields a complete prime factorization by induction.^[24] An alternative proof relies on the well-ordering principle of the natural numbers, which states that every nonempty subset of positive integers has a least element. To show every n > 1 has a prime factorization, first note that the set of positive divisors of n is nonempty (containing 1 and n) and thus has a least element d > 1. This d must be prime, as any proper divisor of d would be a smaller positive divisor of n, contradicting minimality. Dividing n by this prime p = d gives a quotient q = n/p < n, and applying the argument recursively to q produces a decreasing sequence of positive integers that must terminate (by well-ordering) at 1, yielding a finite product of primes equaling n.^[24] Note that the infinitude of primes follows as a consequence of the existence of prime factorizations, via Euclid's argument that the product of all primes plus one must have a new prime factor.

Uniqueness of Prime Factorization

The uniqueness of the prime factorization in the fundamental theorem of arithmetic relies on Euclid's lemma, a key result in integer divisibility. Euclid's lemma states that if a prime number p divides the product ab of two integers a and b, then p divides a or p divides b.^[26] To prove Euclid's lemma, assume without loss of generality that p does not divide a. Then \gcd(a, p) = 1, since p is prime. By Bézout's identity, there exist integers x and y such that ax + py = 1. Multiplying through by b yields abx + pby = b. Since p divides ab, it divides the left side, and thus p divides pby, implying p divides b. This establishes the lemma.^[26] (Hardy & Wright, 2008, Theorem 3) With Euclid's lemma in hand, the uniqueness proof proceeds by assuming the existence of prime factorizations (as established previously) and showing they must coincide. Consider an integer n > 1 with two purported factorizations:

n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} = q_1^{b_1} q_2^{b_2} \cdots q_m^{b_m},

where the p_i and q_j are distinct primes, and all exponents a_i, b_j \geq 1. Without loss of generality, assume the primes are ordered increasingly: p_1 < p_2 < \cdots < p_k and similarly for the q_j. (Hardy & Wright, 2008, Theorem 4) To equate the primes and exponents, apply Euclid's lemma repeatedly to show the multisets \{ p_1 (with multiplicity a_1), ..., \{ p_k (with multiplicity a_k) } and \{ q_1 (with multiplicity b_1), ..., \{ q_m (with multiplicity b_m) } are identical. First, consider the smallest prime p_1 from the left factorization. Since p_1^{a_1} divides n, it divides the product q_1^{b_1} \cdots q_m^{b_m}. By Euclid's lemma applied to p_1 dividing this product, p_1 must divide some q_j^{b_j}, and since p_1 is prime, p_1 = q_j. Thus, p_1 appears in the right factorization.^[27] Next, compare exponents for this prime. Since p_1^{a_1} divides q_1^{b_1} \cdots q_m^{b_m} and p_1 = q_j for some j, repeated application of Euclid's lemma shows a_1 \leq b_j (as higher powers require divisibility by the prime multiple times). Symmetrically, considering the right factorization shows b_j \leq a_1, so a_1 = b_j. Now "cancel" this common factor by dividing both sides by p_1^{a_1}, yielding reduced factorizations for n / p_1^{a_1} on both sides. The primes p_2, \dots, p_k and the remaining q's (excluding the matched q_j) must then match by induction on the number of distinct primes or the size of n. This step-by-step cancellation equates all primes and exponents, confirming the multisets are the same. (Hardy & Wright, 2008, Theorem 4) In the ring of integers \mathbb{Z}, the only units are \pm 1, so any factorization is unique up to multiplication by units (i.e., signs) and the order of factors. Thus, the prime factorization of |n| determines that of n uniquely, disregarding signs and permutations. (Hardy & Wright, 2008, §2.4)

Alternative Uniqueness Proofs

One alternative approach to uniqueness utilizes the method of infinite descent, but standard presentations rely on principles akin to Euclid's lemma to handle both primes and their multiplicities fully.^[24] Another perspective draws an analogy to factorization in the polynomial ring \mathbb{Z}, which is a unique factorization domain because \mathbb{Z} is (via Gauss's lemma). For constant polynomials n \in \mathbb{Z}, factorization in \mathbb{Z} reduces to that in \mathbb{Z}, illustrating how the integer case underpins more general structures, though the proof for \mathbb{Z} is foundational and not derived from polynomials. (Hardy & Wright, 2008, §8.1)

Applications

Integer Representations

The fundamental theorem of arithmetic guarantees that every positive integer greater than 1 can be expressed uniquely as a product of prime numbers, up to the order of the factors. This unique representation is standardized in the canonical form by arranging the primes in non-decreasing order and including their multiplicities as exponents. For example, the integer 12 is canonically factored as $12 = 2^2 \times [3](/page/3), where the primes are listed increasingly.^[28]^[29] Associated with this canonical factorization are two key arithmetic functions that quantify its structure. The function \omega(n) counts the number of distinct prime factors in the factorization of n, so for n = 12, \omega(12) = 2 since the distinct primes are 2 and 3. In contrast, \Omega(n) counts the total number of prime factors counting multiplicity, yielding \Omega(12) = 3 due to the two 2's and one 3. These functions rely directly on the uniqueness provided by the theorem to ensure consistent counts across any valid factorization.^[30]^[28] The number 1 holds a special status in this framework, as it possesses no prime factors and is represented as the empty product, which by convention equals 1. This representation is unique, though the fundamental theorem typically applies to integers greater than 1, treating 1 separately to avoid inconsistencies in factorization.^[31] The theorem extends naturally to all nonzero integers by incorporating the sign. For negative integers, the prime factorization of the absolute value is prefixed with a factor of -1, ensuring uniqueness up to the sign. Thus, -12 is represented as -12 = -[1](/page/1) \times 2^2 \times 3, where the primes remain in canonical order.^[32] Computing these representations algorithmically leverages the theorem's uniqueness to verify completeness. Trial division, a basic method, involves systematically dividing the integer by primes up to its square root, recording factors until the quotient is 1; the uniqueness ensures no alternative factorization exists to check against. Sieve-based approaches, such as adaptations of the Sieve of Eratosthenes, precompute primes to accelerate trial division for multiple integers, again relying on the theorem to confirm the canonical form without redundancy.^[33]^[34]

Arithmetic Operations

The unique prime factorization theorem enables efficient computation of certain arithmetic operations by manipulating exponents in the factorizations of integers. For positive integers a and b with prime factorizations a = \prod p_i^{a_i} and b = \prod p_i^{b_i} (where the product ranges over primes and unspecified exponents are zero), the multiplication operation yields ab = \prod p_i^{a_i + b_i}, as the uniqueness of factorization ensures no additional primes or adjustments are needed.^[35] The greatest common divisor and least common multiple also derive directly from these factorizations: \gcd(a, b) = \prod p_i^{\min(a_i, b_i)}, selecting the lowest exponent for each shared prime, and \lcm(a, b) = \prod p_i^{\max(a_i, b_i)}, taking the highest exponent across both. These formulations stem from the theorem's guarantee that common factors align precisely along prime lines.^[36] A key relation follows: for positive integers a and b, \gcd(a, b) \times \lcm(a, b) = ab, since the sum of minimum and maximum exponents equals the individual exponents for each prime, \min(a_i, b_i) + \max(a_i, b_i) = a_i + b_i. This identity holds for all primes in the factorizations and extends to the absolute values for signed integers.^[5] Addition and subtraction do not preserve prime factorizations in a comparable additive manner, as the result's primes depend on the specific numerical outcome rather than exponent arithmetic alone. They nonetheless interact with factorizations in combinatorial settings, such as binomial coefficients, where Kummer's theorem determines the exponent of a prime p in \binom{n}{k} as the number of carries when adding k and n - k in base p.^[37] For division, when a divides b (i.e., b = a q for integer q), the quotient q inherits the factorization \prod p_i^{b_i - a_i}, with exponents subtracted only where a_i \leq b_i and zero otherwise, preserving the theorem's uniqueness. This applies to positive divisors, with signs handled separately.^[38]

Arithmetic Functions

The fundamental theorem of arithmetic plays a central role in the study of multiplicative arithmetic functions, which are functions f: \mathbb{N} \to \mathbb{C} satisfying f(1) = 1 and f(ab) = f(a)f(b) whenever \gcd(a,b) = 1.^[39] This property allows the value of f(n) for any positive integer n to be determined solely from its prime factorization n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, via f(n) = f(p_1^{e_1}) f(p_2^{e_2}) \cdots f(p_k^{e_k}), directly leveraging the uniqueness guaranteed by the theorem.^[39] Without this unique decomposition into primes, computing or even defining such functions consistently across all integers would be infeasible, as alternative factorizations could lead to conflicting values. A prominent example is the Möbius function \mu(n), defined as \mu(n) = (-1)^k if n is square-free with exactly k distinct prime factors, and \mu(n) = 0 otherwise.^[40] Its multiplicativity follows from the prime factorization: for coprime a and b, the primes in ab are the disjoint union of those in a and b, so \mu(ab) = (-1)^{k_a + k_b} = \mu(a)\mu(b) if both are square-free, and zero if either has a squared prime.^[40] The theorem ensures this definition is unambiguous, as the set of distinct primes is uniquely determined. Another key multiplicative function is the sum-of-divisors function \sigma(n) = \sum_{d \mid n} d, which for n = p_1^{e_1} \cdots p_k^{e_k} equals \prod_{i=1}^k (1 + p_i + p_i^2 + \cdots + p_i^{e_i}).^[41] This product form arises because the divisors of n are uniquely generated by choosing exponents from $0toe_i$ for each prime, a direct consequence of the unique factorization; multiplicativity holds since the divisor sums for coprime factors multiply without overlap.^[41] Euler's totient function \phi(n), counting integers up to n coprime to n, is given by \phi(n) = n \prod_{p \mid n} (1 - 1/p), where the product runs over distinct primes dividing n.^[42] The formula relies on inclusion-exclusion over the unique primes: each prime p excludes n/p multiples, and higher intersections correspond to products of distinct primes, uniquely identified by the theorem. For n = p_1^{e_1} \cdots p_k^{e_k}, it simplifies to \phi(n) = n \prod_{i=1}^k (1 - 1/p_i), confirming multiplicativity.^[42] The Dirichlet convolution (f * g)(n) = \sum_{d \mid n} f(d) g(n/d) preserves multiplicativity: if f and g are multiplicative, so is f * g, because the divisors of n decompose uniquely into coprime parts aligning with the prime factors of n.^[43] This operation turns the set of multiplicative functions into a ring under pointwise multiplication and convolution, with the constant function $1(n)=1 as the identity for convolution; the theorem enables explicit computation by reducing sums over divisors to products over primes.^[44] For instance, the Möbius inversion formula, stating that if g = f * 1 then f = g * \mu, inverts sums over divisors using the unique prime structure.^[43]

Generalizations

Unique Factorization Domains

A unique factorization domain (UFD) is an integral domain R in which every non-zero non-unit element can be expressed as a finite product of irreducible elements, and this factorization is unique up to the order of the factors and the association by units./18:_Integral_Domains/18.02:_Factorization_in_Integral_Domains) In such domains, irreducible elements coincide with prime elements, ensuring that the factorization process mirrors the behavior observed in the integers.^[45] The ring of integers \mathbb{Z} is a UFD if and only if the fundamental theorem of arithmetic holds, as the theorem's existence and uniqueness of prime factorizations directly translate to the UFD property in this setting.^[46] This equivalence underscores how the FTA serves as the foundational instance of unique factorization in ring theory. Examples of UFDs include polynomial rings k over a field k, which inherit unique factorization from the field's properties and the ability to perform polynomial division.^[47] Another example is the ring of Gaussian integers \mathbb{Z}, which is a Euclidean domain under the norm N(a + bi) = a^2 + b^2, and thus a UFD.^[48] UFDs can be characterized as integral domains that satisfy the ascending chain condition on principal ideals (ACCP)—meaning every ascending chain of principal ideals stabilizes—and in which every irreducible element is prime.^[49] This condition prevents infinite descending chains of divisors, ensuring the existence of factorizations into irreducibles.^[45]

Polynomials and Other Structures

The polynomial ring k in one indeterminate over a field k is a unique factorization domain (UFD).^[50] This follows from Gauss's lemma, which states that if R is a UFD with field of fractions K, then a polynomial in R is irreducible in R if and only if it is primitive and irreducible in K.^[51] In k, the irreducible elements are precisely the irreducible polynomials, which are prime elements since every irreducible in a UFD is prime.^[52] Thus, every non-constant polynomial factors uniquely as a product of irreducible polynomials, up to multiplication by units, which are the nonzero elements of k.^[53] To factorize polynomials explicitly in rings like \mathbb{Z} or more generally R where R is a UFD, one first extracts the content of the polynomial—the greatest common divisor of its coefficients—yielding f(x) = c \cdot g(x), where c \in R and g(x) is primitive (content 1).^[54] Gauss's lemma ensures that the product of two primitive polynomials is primitive, allowing the primitive part g(x) to be factored uniquely into irreducibles in K, where K is the fraction field of R, and this factorization lifts back to R up to units in R.^[55] The content c factors uniquely in R by assumption, completing the algorithm for unique factorization in R.^[50] Extending to other structures, the ring \mathbb{Z} is itself a UFD, as \mathbb{Z} is a UFD and Gauss's lemma applies iteratively.^[52] Cyclotomic polynomials \Phi_n(x), defined as the minimal polynomials over \mathbb{Q} for primitive nth roots of unity, are irreducible in \mathbb{Q} and hence prime elements in \mathbb{Z} by Gauss's lemma.^[56] In contrast, the polynomial ring k[x, y] in two indeterminates over a field k is also a UFD, but it possesses infinitely many pairwise non-associate irreducible elements, unlike the countable but "effectively finite" primes in \mathbb{Z}.^[57] The unique factorization property extends to applications in number theory, such as Dirichlet's theorem on primes in arithmetic progressions, which asserts that if a and d are coprime positive integers, then there are infinitely many primes congruent to a modulo d.^[23] The proof relies on the unique factorization of ideals (a generalization of the FTA) in the rings of integers of cyclotomic fields \mathbb{Q}(\zeta_d), where \zeta_d is a primitive dth root of unity, to analyze the splitting of primes and the non-vanishing of associated L-functions.^[58]

References

[1]
[PDF] The Fundamental Theorem of Arithmetic
Jun 14, 2008 · The Fundamental Theorem of Arithmetic says that every integer greater than 1 can be factored uniquely into a product of primes. Euclid's lemma ...Missing: history | Show results with:history
[2]
[PDF] Some fundamental theorems in Mathematics
Jul 22, 2018 · Carl Friedrich Gauss gave in 1798 the first proof in his monograph Disquisitiones Arithmeticae".
[3]
[PDF] Gauss and the First “Rigorous” Proof of the Fundamental Theorem of ...
Feb 10, 2023 · Famously, it is due to the work of Girolamo Cardano (1501–1576) and Rafael. Bombelli (1526–1572) on solving the general cubic equation that ...
[4]
[PDF] Introduction to CS232
Cryptography. — Randomized ... Fundamental Theorem of Arithmetic (FTA): Every integer n ≥ 2 can be written ...
[5]
[PDF] Math 406 Section 3.5: The Fundamental Theorem of Arithmetic
Theorem (The Fundamental Theorem of Arithmetic): Every positive integer greater than 1 ... Suppose there are positive integers greater than 1 which cannot be ...
[6]
[PDF] Fundamental Theorem of Arithmetic - CSUSM
We begin with an important application of Bezout's identity: Proposition 1. If p is a prime number and if p|ab where a, b ∈ Z, then p|a or p|b. Proof ...
[7]
[PDF] 1 Section 1.1
Theorem 3.2 (Fundamental Theorem of Arithmetic): Every positive integer n ... canonical form n = pk1. 1 pk2. 2 ···pkr r where, for i = 1, 2, ..., r each ...
[8]
[PDF] Elementary Number Theory - Joshua
2.1 Definition An integer p ≥ 2 is prime if it has no positive divisors other than 1 and itself. An integer greater than or equal to 2 that is not prime is.
[9]
[PDF] 4 Number Theory I: Prime Numbers - Penn Math
A natural number larger than 1 is called prime if it can be evenly divided only by 1 and itself; other natural numbers greater than 1 are called composite. To ...
[10]
[PDF] 31 Prime elements
An integral domain R is a UFD iff. 1) every non-zero, non-unit element of R is a product of irreducible elements. 2) every irreducible element in R is a prime ...
[11]
[PDF] Math 403 Chapter 18: Irreducibles, Associates, Primes, UFDs
(a) Definition: Suppose D is an integral domain and a, b ∈ D. Then a and b ... (d) Theorem: In an integral domain every prime is irreducible. Proof ...
[12]
Prime Factorization Numbers - University of North Georgia
Prime factorization is a process of writing all numbers as a product of primes. So, for example, say if we have something like the number 20. We can break that ...
[13]
[PDF] Contents 2 Rings - Evan Dummit
The set of units in R is denoted R×. ◦ Example: In Z, there are no zero divisors, and the units are ±1.
[14]
Prime numbers - MacTutor History of Mathematics
By the time Euclid's Elements appeared in about 300 BC, several important results about primes had been proved. In Book IX of the Elements, Euclid proves that ...
[15]
https://mathshistory.st-andrews.ac.uk/Biographies/Euclid/
[16]
Aryabhata - Biography
### Summary of Prime Numbers, Factorization, or Number Theory Contributions
[17]
Bhaskara II - Biography
### Summary of Prime Numbers, Factorization, or Number Theory Contributions by Bhaskara II
[18]
[PDF] Journal of Humanistic Mathematics A Practical Rule of Divisibility By ...
Jul 2, 2025 · In his al-K¯af¯ı f¯ı al-H. is¯ab Ab¯u Bakr Muh. ammad ibn al-H. asan al-Karaji (d. af- ter 1019) uses divisibility by 9 and 11 to check the ...<|separator|>
[19]
Pierre Fermat (1601 - 1665) - Biography - MacTutor
Pierre de Fermat was a French lawyer and government official most remembered for his work in number theory; in particular for Fermat's Last Theorem. He is also ...
[20]
Algebra in Roth, Faulhaber, and Descartes - ScienceDirect.com
Descartes exploited the fact that the constant term of a factor divides that of a polynomial to limit the search for factors. He gave formulas for the ...
[21]
[PDF] Prime Factorization from Euclid to Noether - Keith Conrad
Mar 1, 2023 · Gauss (1801) was the first to prove uniqueness, stating it as. Numerus compositus quicunque unico tantum modo in factores primos resolvi potest.
[22]
Leonhard Euler (1707 - 1783) - Biography - MacTutor
He made decisive and formative contributions to geometry, calculus and number theory. He integrated Leibniz's differential calculus and Newton's method of ...
[23]
[PDF] The Mathematics of Gauss
Disquisitiones Arithmeticae. In 1795, Gauss happened upon the following theorem: Theorem 2.1 ([Gau66], article 108). There exists x such that x2 ...
[24]
[PDF] 18 Dirichlet L-functions, primes in arithmetic progressions
Nov 10, 2016 · We begin with Dirichlet's theorem on primes in arithmetic progressions, a result that predates the prime number theorem by sixty years. Theorem ...
[25]
[PDF] Introduction to the Theory of Numbers
Nov 21, 2014 · ... FUNDAMENTAL THEOREM OF ARITHMETIC IN k(l), /c(i),. AND k(p). 12.1. Algebraic numbers and integers. 12.2. The rational integers, the Gaussian ...
[26]
[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.
[27]
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.11%3A_Unique_Factorization
[28]
https://mathworld.wolfram.com/PrimeFactor.html
[29]
[PDF] On Fermat's method of infinite descent - McGill University
Apr 25, 2013 · The proof of this theorem is credited to Euler, who established it in a series of propositions, with the help of the method of infinite descent.<|control11|><|separator|>
[30]
[PDF] The Fundamental Theorem of Arithmetic
A proof can be given us- ing Mathematical Induction. We do something equivalent, but with more historical import. We introduce a proof technique used by the ...
[31]
[PDF] Factorization in Polynomial Rings - Columbia Math Department
The uniqueness follows as in the proof of uniqueness for. Proposition 1.2: if r1 + (f) = r2 + (f), with each ri either 0 of of degree smaller than deg f, then f ...
[32]
[PDF] =Unique Factorization What Not Everyone Knows - Paul Pollack
Sep 26, 2023 · When it's proved in courses, the Fundamental Theorem is usually established by something isomorphic to the following chain of reasoning.
[33]
Prime Factor -- from Wolfram MathWorld
A prime factor is a factor that is prime, ie, one that cannot itself be factored. In general, a prime factorization takes the form n=p_1^(alpha_1)p_2^(alpha_2) ...Missing: ω(
[34]
The Prime Glossary: Fundamental Theorem of Arithmetic
We can reword the Fundamental Theorem this way: the canonical factorization of an integer greater than one is unique. This theorem (and indeed any theorem ...
[35]
Distinct Prime Factors -- from Wolfram MathWorld
The distinct prime factors of a positive integer n>=2 are defined as the omega(n) numbers p_1 , ..., p_(omega(n)) in the prime factorization.
[36]
[PDF] Math 1365 (Intensive Mathematical Reasoning)
Oct 5, 2023 · The representation of n as a product of primes is called the prime factorization of n. ... The result clearly holds if n = 1, since 1 is the empty ...
[37]
[PDF] A GENTLE INTRODUCTION TO ABSTRACT ALGEBRA - CSUN
(Negative integers less than −1 also factor into a product of primes, except that they have a minus sign in front of the product.) ... prime factorization as well ...
[38]
10.3 Prime Factorization
The unique representation of each integer greater than 1 that is guaranteed by the Fundamental Theorem of Arithmetic (Theorem 10.10) is called the prime ...
[39]
3.2 Prime Numbers
In this section we see this in The Fundamental Theorem of Arithmetic, and explore some interesting statements prime numbers. ... Use trial division to determine ...
[40]
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Raji)/04%3A_Multiplicative_Number_Theoretic_Functions/4.03%3A_The_Mobius_Function_and_the_Mobius_Inversion_Formula
[41]
[PDF] Prime Numbers, GCD, LCM and Euclidean Algorithm
Evaluate the gcd and/or lcm of two positive integers using their prime factorization. ... max(αi,βi) = min(αi,βi), for all i = 1, 2, ... . . . n, Hence αi ...
[42]
[PDF] The Power of a Prime That Divides a Generalized Binomial Coefficient
Such primes lead to a Kummer-like theorem for generalized binomial coefficients: Page 5. The Power of a Prime That Divides a Generalized Coefficient 519.
[43]
[PDF] Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic simply states that each ... If p is prime and ai for 1 ≤ i ≤ k+1, are positive integers, and if p | a1a2... ... 1), then it ...
[44]
[PDF] 1. Multiplicative functions The focus of Math 104B will be on giving ...
To compute a multiplicative function f, by the fundamental theorem of arithmetic, it suffices to know the value of f(pe), where p is a prime number. We have ...
[45]
Number Theory - Multiplicative Functions
An arithmetical function is multiplicative if f ( m n ) = f ( m ) f ( n ) whenever gcd ( m , n ) = 1 , and totally multiplicative or completely multiplicative ...Missing: fundamental | Show results with:fundamental
[46]
3.8 The Euler Phi Function
11 If n is a positive integer with prime factorization pe11pe22⋯pekk, then ϕ(n)=(pe11−pe1−11)(pe22−pe2−12)⋯(pekk−pek−1k). Proof. The proof by induction is left ...
[47]
Chapter 3 Dirichlet series and arithmetic functions - Kiran S. Kedlaya
In this way of thinking, convolution of multiplicative functions corresponds to ordinary multiplication of Dirichlet series:.
[48]
[PDF] Lecture notes on Dirichlet convolution - Rutgers University
Oct 4, 2007 · An arithmetic function f is said to be multiplicative if f (n1n2) = f (n1)f (n2) whenever gcd (n1; n2)=1. We showed earlier that the Euler ...<|control11|><|separator|>
[49]
Section 10.120 (034O): Factorization—The Stacks project
A unique factorization domain, abbreviated UFD, is a domain R such that if x \in R is a nonzero, nonunit, then x has a factorization into irreducibles.
[50]
[PDF] unique factorization domains - Liberty University
Definition 12. A domain D is called a unique factorization domain if the fundamental theorem of arithmetic holds in D. That is, it satisfies the following two ...
[51]
[PDF] Section III.6. Factorization in Polynomial Rings
Apr 20, 2024 · If F is a field, then the polynomial ring F[x] is a Euclidean domain, whence F[x] is a principal ideal domain and a unique factorization domain.
[52]
[PDF] Contents 4 Unique Factorization and Applications - Evan Dummit
Proposition (Z[i] is Euclidean): The Gaussian integers Z[i] are a Euclidean domain, under the norm N(a+bi) = a2 + b2. ◦ Explicitly, given a + bi and c + di in Z ...
[53]
[PDF] Factorization in Domains - Trinity University
R is said to satisfy the ascending chain condition on principal ideals. (ACCP) if every ascending chain of principal ideals in R stabilizes. Note that ACC ...
[54]
[PDF] Math 121. Eisenstein criterion and Gauss' Lemma Let R be a UFD ...
As an application of the method of proof, we will establish a UFD property for polynomial rings in several variables. 1. Gauss' Lemma. Before proving Gauss ...
[55]
[PDF] 9. Gauss Lemma - UCSD Math
Let R be a UFD and let f(x) be a polynomial with coefficients in R. The content of f(x), denoted c(f), is the gcd of the coefficients of f. Example ...
[56]
[PDF] 12. Polynomials over UFDs
Thus, Gauss' lemma more properly concerns the equivalence classes of irreducibles dividing the respective coefficients. Page 4. 184. Polynomials over UFDs.
[57]
[PDF] Polynomials over UFD's - People
Let R be a UFD and let K be the field of fractions of R. Our goal is to compare arithmetic in the rings R[x] and K[x]. We introduce the following notion.
[58]
[PDF] Gauss' lemma. If R is a UFD, then R[x] is a UF
In outline, our proof of Gauss' lemma will say that if F is a field of fractions of R, then any polynomial f ∈ R[x] is in the UFD F[x], and so can be written as.
[59]
[PDF] III.K. Gauss's lemma and polynomials over UFDs Let R be a UFD ...
Gauss's lemma and polynomials over UFDs. Let R be a UFD, and F := F(R) its field of fractions. ... GAUSS'S LEMMA AND POLYNOMIALS OVER UFDS. 173. ∃b ∈ R such ...
[60]
[PDF] 20. Cyclotomic III
The main goal is to prove that all cyclotomic polynomials Φn(x) are irreducible in Q[x], and to see what happens to Φn(x) over Fp when p|n. The irreducibility ...
[61]
[PDF] commutative algebra hw 5 solutions
(1) Let R be a UFD. Show that R[x] has infinitely many pairwise non-associate irreducibles. We imitate Euclid's argument to produce an infinite sequence.
[62]
[PDF] 21. Primes in arithmetic progressions
Dirichlet's theorem is a strengthening of Euclid's theorem that there are infinitely many primes p. Dirichlet's theorem allows us to add the condition that p = ...