Fundamental theorem of arithmetic

[6] This failure of unique factorization is one of the reasons for the difficulty of the proof of Fermat's Last Theorem.

The implicit use of unique factorization in rings of algebraic integers is behind the error of many of the numerous false proofs that have been written during the 358 years between Fermat's statement and Wiles's proof.

Proposition 30 is referred to as Euclid's lemma, and it is the key in the proof of the fundamental theorem of arithmetic.

(In modern terminology: every integer greater than one is divided evenly by some prime number.)

Book IX, proposition 14 is derived from Book VII, proposition 30, and proves partially that the decomposition is unique – a point critically noted by André Weil.

While Euclid took the first step on the way to the existence of prime factorization, Kamāl al-Dīn al-Fārisī took the final step[8] and stated for the first time the fundamental theorem of arithmetic.

[9] Article 16 of Gauss's Disquisitiones Arithmeticae is an early modern statement and proof employing modular arithmetic.

Allowing negative exponents provides a canonical form for positive rational numbers.

The canonical representations of the product, greatest common divisor (GCD), and least common multiple (LCM) of two numbers a and b can be expressed simply in terms of the canonical representations of a and b themselves: However, integer factorization, especially of large numbers, is much more difficult than computing products, GCDs, or LCMs.

Then, by strong induction, assume this is true for all numbers greater than 1 and less than n. If n is prime, there is nothing more to prove.

Otherwise, there are integers a and b, where n = a b, and 1 < a ≤ b < n. By the induction hypothesis, a = p1 p2 ⋅⋅⋅ pj and b = q1 q2 ⋅⋅⋅ qk are products of primes.

Suppose, to the contrary, there is an integer that has two distinct prime factorizations.

Let n be the least such integer and write n = p1 p2 ... pj = q1 q2 ... qk, where each pi and qi is prime.

We now have two distinct prime factorizations of some integer strictly smaller than n, which contradicts the minimality of n. The fundamental theorem of arithmetic can also be proved without using Euclid's lemma.

[13] The proof that follows is inspired by Euclid's original version of the Euclidean algorithm.

is the smallest positive integer which is the product of prime numbers in two different ways.

It then follows that As the positive integers less than s have been supposed to have a unique prime factorization,

The latter case is impossible, as Q, being smaller than s, must have a unique prime factorization, and

Therefore, there cannot exist a smallest integer with more than a single distinct prime factorization.

The first generalization of the theorem is found in Gauss's second monograph (1832) on biquadratic reciprocity.

He showed that this ring has the four units ±1 and ±i, that the non-zero, non-unit numbers fall into two classes, primes and composites, and that (except for order), the composites have unique factorization as a product of primes (up to the order and multiplication by units).

[14] Similarly, in 1844 while working on cubic reciprocity, Eisenstein introduced the ring

it can be proven that if any of the factors above can be represented as a product, for example, 2 = ab, then one of a or b must be a unit.

Using these definitions it can be proven that in any integral domain a prime must be irreducible.

Euclid's classical lemma can be rephrased as "in the ring of integers

Multiplication is defined for ideals, and the rings in which they have unique factorization are called Dedekind domains.

Any commutative Möbius monoid satisfies a unique factorization theorem and thus possesses arithmetical properties similar to those of the multiplicative semigroup of positive integers.

The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

The two monographs Gauss published on biquadratic reciprocity have consecutively numbered sections: the first contains §§ 1–23 and the second §§ 24–76.

Footnotes referencing the Disquisitiones Arithmeticae are of the form "Gauss, DA, Art.