This site is supported by donations to The OEIS Foundation.

Fundamental theorem of arithmetic

From OeisWiki
Jump to: navigation, search

The fundamental theorem of arithmetic shows that the integers form a unique factorization domain.

Theorem. Each positive integer is the product of prime numbers in only one way (up to ordering.)

Since multiplication in is commutative, it does not matter in what order we state the prime factors. So, for example, the ordered prime factorizations and are not different prime factorizations of 120, but merely different ways of expressing the only prime factorization of 120 that exists.

We could alternatively state the theorem as: given the set of positive integers and its subset of prime numbers , each has a unique prime factorization as a product of . Or we could simply say that is a unique factorization domain.

Or that A000012(n) (the all 1's sequence) counts how many different ways can be expressed as a product of primes.

Proof. For now let's take as axiomatic the fact that each integer has any prime factorization at all.[1] Let's say that actually has two distinct prime factorizations: where the and are primes, and . Since is a divisor of , it must also be a divisor of the product of the primes . But since the are primes and is also prime, this must mean that , with being an integer in the range , and we can therefore remove from one side of the equation and from the other. We can continue this process to the point of removing all until we're left with , something that is absurd (unless , in which case we have the empty product on the right) if all the are in fact primes. Therefore, must be equal to , and the primes are the same primes just perhaps given in a different order.[2]

This theorem is sometimes given as a reason for excluding 1 from the list of primes.[3] Though there are much better reasons to regard 1 as not prime, rigor nevertheless demands that we either handle 1 in some way or amend the theorem to say . The usual handling is to state that 1, as the "empty product," is in fact the product of multiplying zero primes together. Now, 1 is considered a unit, i.e. an invertible (multiplicative inverse) element of the set of positive integers.

As for negative integers, the most straightforward handling is probably to regard all the prime factors as positive and have this prefixed by the unit to accomplish the sign change (this is what Mathematica does). Thus an integer would have its prime factorization prefixed by or . A more complicated but perhaps equally valid way would be to add negative signs to an odd number of the prime factors.

Compare with the frivolous theorem of arithmetic.

Notes

  1. Most books either have this as a previous theorem or at least as a lemma.
  2. B. Fine & G. Rosenberger, Number Theory: An Introduction via the Distribution of the Primes Boston: Birkhaüser (2007) p. 18. The fact that an integer has any factorization at all is given as an earlier lemma. The proof is not unique to this text, but it seems to me to provide the clearest explanation of the proof.
  3. Primefan, Arguments for and against the primality of 1, "The Prosecution" Arguments 1 and 2. Graeme McRae is credited with the counter-arguments that the theorem accepts the commutative property of multiplication, so why can't it accept the multiplicative identity, or understand the exponents as being the lowest necessary?