Fundamental theorem of arithmetic

The fundamental theorem of arithmetic is the statement that every positive integer has a unique prime number factorization. For instance, we can write

6936 = 2³ × 3 × 17²

and there is no other such factorization of 6936 into prime numbers, except for reorderings of the above factors.

Knowing the prime number factorization of a number gives complete knowledge about all factors of that number. For instance, the above factorization of 6936 tells us that the positive factors of 6936 are of the form

2^a × 3^b × 17^c

with 0 ≤ a ≤ 3, 0 ≤ b ≤ 1, and 0 ≤ c ≤ 2. This yields a total of 4 × 2 × 3 = 24 positive factors.

Once the prime factorizations of two numbers are known, their greatest common divisor and least common multiple can be found quickly. However if the prime factorizations are not known, the use of Euclid's algorithm is likely to require less calculation than factorizing the two numbers.

The fundamental theorem ensures that multiplicative functions are completely determined by their values on the powers of prime numbers.