Prime Factorization

When dealing with the natural numbers, we often want to factorize them. That is, find numbers that multiply to the original number. A composite number is a number that can be decomposed through factoring.

For example, 6 is a composite number. It can be rewritten as 2 x 3. The number 7, on the other hand, is not composite. The only natural numbers that multiply to 7 are 1 and 7. Because there is still a 7 in the product, we have not decomposed it into smaller numbers.

The number 7 is a prime number. A prime number is a natural number that is divisible by only 2 distinct numbers: itself and 1. Prime numbers are not composite. Every natural number is either prime or composite, except for 1, which is neither.

There are an infinite number of prime numbers. This is an important fact given the goal of this blog, so later on I'm going to describe some of the proofs of this. For reference, all of the primes less than 50 are listed below.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

Because the primes form an infinite sequence, we can index them. For example, lets let denote the prime number for all .

In other words , , , , etc.

We can form a new notation for numbers out of this. There's a theorem that let's us do that, and it's called the fundamental theorem of arithmetic, or FTA. This theorem states that all natural numbers can be uniquely factorized into prime numbers. Let's look at some examples.

The number 12 can be factorized into 2 x 2 x 3, which are all prime numbers. No other number has the same factorization. This can be written compactly using exponents.



Now consider the number 490.



This example showcases rules that we'll need for writing numbers in factorized form. I have included the "3" term, even though it appears zero times in the product 2 x 5 x 7 x 7 = 490. The zero term serves as a placeholder, just as the decimal number 304 also requires a placeholder. I don't include a term for the prime number 11, because a leading zero would be superfluous, just as we don't normally write 032.

For the record, terms like are equal to 1, so they don't affect the product at all. 1 is written as the null product (no prime numbers multiplied together). There is no way of writing zero in this form. Therefore, it is a notation for natural numbers (which doesn't include zero) and not for whole numbers.

In the next few posts, I'm going to discuss this notation in more depth using more symbolic notation and mathematical language, and then go further into what this notation is good for.