Fundamental theorem of arithmetic

Every natural number greater than 1 has a unique prime factorisation, up to permutation of the factors.

Every nonzero non-unit (not 1 or -1) integer has a unique prime factorisation, up to permutation of the factors and replacement of some factors by their associates.

An integral domain for which the above holds (substituting `irreducible' for `prime'; I think it matters) is called a `unique factorisation domain'. In all UFDs, an element is prime iff it is irreducible.

Every principal ideal domain (and hence every Euclidean domain) is a unique factorization domain.

Claim: Every natural number N, N>1, has a unique prime factorization.

i.e. N may be written in exactly one way as N=p₁p₂p₃...p_r,
where p_i is prime and p₁ ≤ p₂ ≤ p₃ ≤ ... ≤ p_r. Note: WLOG, we are ordering the prime numbers in order of their magnitude. They may, course, be ordered in any way we choose, and several of the prime numbers may be equal. For example, 100=2*2*5*5. We simply seek to place the primes in some standard order.

Proof: First, we'll show that any natural number N>1 can be written as a product of prime numbers.

Assume that N cannot be written as a product of prime numbers. Let N be the first number which cannot be written as a product of one or more primes. (Thus, all smaller numbers may be written as products of primes). N, therefore, is not prime, or it would already be a product of prime numbers. N must be divisible by some number 1 < K < N and we may write N=KM. Since both K and M are smaller than N, they may be written as products as primes:
K=k₁k₂...k_i, and M=m₁m₂...m_j. But then N would be KM=k₁k₂...k_im₁m₂...m_j, which is a product of prime numbers, contradicting our assumption.

Therefore, all natural numbers may be written as products of primes.

Now that we know all natural numbers may somehow be factored into primes, let's suppose that there are some natural numbers which may be factored into primes at least two distinct ways. Let's choose some N which is the smallest number which may be factored into primes 2 different ways. Let these 2 prime factorizations be:

N=a₁a₂...a_i, and
N=b₁b₂...b_j.
Please note that these two factorizations have no primes in common. If they did, we would divide them out and get two equal factorizations of an even smaller number, but N is the smallest number with two distinct factorizations, so this is not possible.

Assume a₁ > b₁ and consider the number
M = N - b₁a₂...a_i = (a₁-b₁)a₂...a_i.
M is clearly a smaller number than N.

1. Expand (a₁-b₁) into primes c₁c₂...c_k so M may be written as

M = c₁c₂...c_ka₂...a_i.

2. Now find M a different way. Use the other prime factorization given for N above:

M = N - b₁a₂...a_i = (b₁b₂...b_j)-(b₁a₂...a_i)
= b₁(b₂...b_j-a₂...a_i)
= b₁d₁d₂...d_l,

where d₁d₂...d_l is the prime factorization of(b₂...b_j-a₂...a_i).

We need to show that these two factorizations of M, which is smaller than N, are distinct, to find our contradiction. First observe that b₁ does appear in the second factorization. To show that it is not in the first factorization, recall that b₁ is not equal to any of the a_i in the first factorization. Furthermore, b₁ does not divide (a₁-b₁) because if it did, we could write (a₁-b₁) = k*b₁, or a₁ = (k+1)(b₁), which contradicts the fact that a₁ is prime. Therefore it cannot appear among the d's. Thus these two prime factorizations of M are distinct. This contradicts our assumption that N was the smallest such number.

Since there is no smallest number with two distinct prime factorizations, by the Well-Ordering Principle of the Natural Numbers (aka the Well Ordering Theorem), there must be no such numbers.

---

Taken from homework assignment from class titled "Fundamental Properties of Spaces and Functions: Part 1" at the University of Iowa, 2002.