# Prime factorization

For a positive integer $n$, the prime factorization of $n$ is an expression for $n$ as a product of powers of prime numbers. An important theorem of number theory called the Fundamental Theorem of Arithmetic tells us that every positive integer has a unique prime factorization, up to changing the order of the terms.

The form of a prime factorization is $n = {p_1}^{e_1} \cdot {p_2}^{e_2}\cdot{p_3}^{e_3}\cdots{p_k}^{e_k}$ where $n$ is any natural number, the $p_{i}$ are prime numbers, and the $e_i$ are their positive integral exponents.

Prime factorizations are important in many ways. One instance is to simplify fractions.

## Techniques

The common method of prime factorization is checking prime numbers, case by case. Use divisibility rules to check if primes (or powers of primes) are a factor and then move up to a different prime if said prime is not a factor. When a prime is a factor, we factor out the prime and check for factors in the resulting number.

Sometimes, we could easily see that a number is a multiple of a composite number or a prime. For instance, $50$ is a factor of $2650$, and $49$ is a factor of $4998$. In these cases, a good strategy is to choose the number accordingly to make factoring easier.

## Example

Consider the number $38052$.

• Because the last two digits of the given number are a multiple of $4$, we can rewrite $38052$ as $2^2 \cdot 9513$. Note that $9513$ is not even, so we move on.
• Because the sum of digits of $9513$ is a multiple of 9, we can rewrite $38052$ as $2^2 \cdot 3^2 \cdot 1057$. Note that the sum of digits of $1057$ is not a multiple of 3, so we move on.
• Because $1057$ does not end in $0$ or $5$, we skip $5$ as a factor. As for $7$, after long division, we note that $1057 = 7 \cdot 151$, so we can rewrite $38052$ as $2^2 \cdot 3^2 \cdot 7 \cdot 151$. However, when doing long division again, $151$ is not a multiple of $7$, so we move on.
• Note that $11$ is not a factor of $151$, so we can move on. In fact, because $13 > \sqrt{151}$, we can declare $151$ as prime and stop.

Thus, the prime factorization of $38052$ is $2^2 \cdot 3^2 \cdot 7 \cdot 151$.