# Prime factorization

For a positive integer , the **prime factorization** of is an expression for 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 where is any natural number, the are prime numbers, and the are their positive integral exponents.

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

## Contents

## 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, is a factor of , and is a factor of . In these cases, a good strategy is to choose the number accordingly to make factoring easier.

## Example

Consider the number .

- Because the last two digits of the given number are a multiple of , we can rewrite as . Note that is not even, so we move on.
- Because the sum of digits of is a multiple of 9, we can rewrite as . Note that the sum of digits of is not a multiple of 3, so we move on.
- Because does not end in or , we skip as a factor. As for , after long division, we note that , so we can rewrite as . However, when doing long division again, is not a multiple of , so we move on.
- Note that is not a factor of , so we can move on. In fact, because , we can declare as prime and stop.

Thus, the prime factorization of is .

## Problems

### Introductory

- Practice Problems from Alcumus
- Prime Factorization (Prealgebra, Number Theory)

- 2000 AIME I Problems/Problem 1

## Resources

### Books

### Games