Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic states that every natural number greater than 1 can be uniquely expressed as a product of prime numbers, with the order of multiplication not affecting the uniqueness of the factorization. This concept is rooted in ancient mathematics, having been first hinted at by Euclid in his Elements, but it was rigorously proved by the mathematician Carl Friedrich Gauss in 1801 in his work, Disquisitiones Arithmeticae. Prime numbers, which are numbers greater than 1 that have no divisors other than 1 and themselves, serve as the essential building blocks for all natural numbers. In contrast, composite numbers, like 20, have additional divisors and can be broken down into prime factors.
The theorem not only underlines the significance of prime numbers in number theory but also reveals interesting properties of divisibility, such as if a prime divides a product of natural numbers, it must divide at least one of the factors. The uniqueness of prime factorization is important for practical applications, particularly in cryptography, where the difficulty of factoring large composite numbers into primes is crucial for the security of coded messages. This theorem provides a foundational structure for understanding numbers and their relationships, making it a critical element of mathematical study.
On this Page
Subject Terms
Fundamental Theorem of Arithmetic
The fundamental theorem of arithmetic states that every number can be factored into prime numbers in one and only one way. A version of this unique factorization theorem was originally given by Euclid of Alexandria as Proposition 14 of Book IX in his Elements, a compendium of the most important mathematical facts from geometry and number theory known at the time. It was not until 1801, however, when the German mathematician Carl Friedrich Gauss stated and rigorously proved this theorem in his Disquisitiones Arithmeticae.
The most basic numbers are those used to count: for example, 1, 2, 3, 4, 5,..., which are called the set of natural numbers. Every natural number greater than 1 can be classified as either prime or composite. A prime number cannot be evenly divided by any other natural number except itself and 1; in other words, a prime number p > 1 has only two divisors: 1 and p. Natural numbers that are not prime are called composite. The number 20 is composite because it has divisors other than 1 and itself, namely, 2, 4, 5, and 10, all of which evenly divide 20. In this example, 20 has divisors that are prime numbers (2 and 5); they are called prime factors. Thus, prime numbers may be considered the multiplicative building blocks of the natural numbers.
Because of the way prime numbers are defined in terms of the number by which they are divisible, they have special divisibility properties. One such divisibility property is the following: If a prime number p divides the product ab of two natural numbers a and b, then p divides one of them (or both). This result leads to the more general prime divisibility property: If the prime number p divides the product of natural numbers a1a2a3(an, then p divides at minimum one of the natural numbers a1, a2, a3, …, an. For example, 7 divides the product 6 × 14 × 20 × 56 = 94,080. Hence, 7 must divide one or more of the numbers 6, 14, 20, 56. Also, 7 divides 14 and 7 divides 56.
Because every natural number (prime or composite) can be divided by prime numbers, each number may be written as product of numbers, all of which are prime. (In the case of a prime number, the product is the single prime factor itself.) This fact is the fundamental theorem of arithmetic: Every natural number n ( 2 can be factored into a product of prime numbers
in exactly one way. The prime numbers, p1, p2, p3, …, pn, need not be distinct; for example, 75 = 3 × 5 × 5, a product containing multiple prime factors 5. Also, to say that this prime factorization is done in exactly one way means that rearranging the order of the prime factors does not count as a different factorization; For example, 75 can be factored as 3 × 5 × 5 and also as 5 × 3 × 5. In other words, a prime factorization is unique up to order in that two factorizations are considered the same if the only difference between them is the order of the prime factors.
Since this number theory result states that every natural number has a unique prime factorization, determining this factorization for large composite numbers can be difficult. Therefore, one application of prime factorization is found in cryptography, the study of secure codes.
Bibliography
Burton, David M. "Euclid’s Number Theory." The History of Mathematics: An Introduction. 7th ed. New York: McGraw, 2011.
Pommersheim, James E., Tim K. Marks, and Erica L. Flapan. "The Fundamental Theorem of Arithmetic." Number Theory: A Lively Introduction with Proofs, Applications, and Stories. New York: Wiley, 2010. 216-37.
Silverman, Joseph H. "Factorization and the Fundamental Theorem of Arithmetic." A Friendly Introduction to Number Theory. 4th ed. Upper Saddle River: Pearson, 2013.