The number 15 is composite, the product of the primes 3 and 5. Is it also the product of other prime numbers, or is its factorization unique? We can simply try all the primes below 15 and find out, but that doesn't answer the more general question. Is every number a unique product of primes? The answer is yes, and this is known as the "fundamental theorem of arithmetic", or simply "unique factorization".
Let p be a prime that divides the product s×t, while p does not divide s or t. Consider the following somewhat contrived expression:
gcd(p,s)×t
Is it divisible by p? We know that p does not divide s, so gcd(p,s) equals 1. Our expression is the same as 1×t, or t, which is not divisible by p. Now remember that multiplication distributes over gcd, so our expression can be rewritten gcd(pt,st). P still fails to divide this expression - that hasn't changed. Since p divides pt it cannot divide st, and that is a contradiction. Whenever a prime divides evenly into a product, it divides into one of the two operands.
Now return to the question of unique factorization. The following proof has been modified slightly, from the original, to work in arbitrary rings.
Of all the numbers with multiple factorizations, Let n be a number with the shortest factorization. If n is prime, it cannot be the product of other primes. There is no "other" factorization, and that is a contradiction. Hence n is composite, and the lesser factorization of n has at least two primes. The "other" factorization may contain more.
Let p be a prime in the first representation, and q a prime in the second. We don't have to worry about p = q, else we would divide through by p and find another n with two different, shorter factorizations. The primes in the two factorizations are distinct.
Let n = q×t, where t takes up the slack in the second factorization. If p divides evenly into t, write n/p as the product of q and the primes of t/p, using any of the possible factorizations of t/p. At the same time, take p out of the first factorization and write n/p as a shorter product of primes. Since q does not appear in the first list, we found another number with multiple factorizations, and the first factorization contains fewer primes. We've already picked the smallest, so p does not divide t. It obviously doesn't divide q, q being prime. By the previous paragraph, it shouldn't divide q×t either, but it does - a contradiction. hence there is no number with two different factorizations. Every number splits uniquely into a product of primes.