# How do you do Prime Factorization

When we talked about integer factorization we noticed that integer number can have more than one factorization.

For example, $$${18}={1}\cdot{18}={2}\cdot{9}={3}\cdot{6}={2}\cdot{{3}}^{{2}}$$$.

However, if we use only prime numbers as factors than such factorization is unique (ignoring order of factors).

**Fact.** Every composite number can be uniquely represented as a product of prime factors.

For example, $$${18}={{2}}^{{2}}\cdot{3}$$$. We can write $$${18}={3}\cdot{{2}}^{{2}}$$$, but we only swap factors, so this representation is the same.

To find **prime factorization of a number** we start by dividing number by the smallest prime number (2), then we move to the next prime number until we get prime number in result.

**Example 1.** Find prime factorization of 60.

Try to divide 60 by 2: $$${60}={2}\cdot{30}$$$.

Try to divide 30 by 2: $$${30}={2}\cdot{15}$$$.

Try to divide 15 by 2: not divisible.

Move to the next prime number 3.

Try to divide 15 by 3: $$${15}={3}\cdot{5}$$$.

We are done, because 5 is prime number.

So, $$${60}={2}\cdot{2}\cdot{3}\cdot{5}={{2}}^{{2}}\cdot{3}\cdot{5}$$$.

Next example.

**Example 2.** Find prime factorization of 19980.

Divide 19980 by 2: $$${19980}={2}\cdot{9990}$$$.

Divide 9990 by 2: $$${9990}={2}\cdot{4995}$$$.

Divide 4995 by 2: not divisible.

Try next prime number 3.

Divide 4995 by 3: $$${4995}={3}\cdot{1665}$$$.

Divide 1665 by 3: $$${1665}={3}\cdot{555}$$$.

Divide 555 by 3: $$${555}={3}\cdot{185}$$$.

Divide 185 by 3: not divisible.

Try next prime number 5.

Divide 185 by 5: $$${185}={5}\cdot{37}$$$.

We are done since 37 is prime number.

So, $$${19980}={2}\cdot{2}\cdot{3}\cdot{3}\cdot{3}\cdot{5}\cdot{37}={{2}}^{{2}}\cdot{{3}}^{{3}}\cdot{5}\cdot{37}$$$.

Last example.

**Example 3.** Find prime factorization of 625.

Divide 625 by 2: not divisible.

Divide 625 by 3: not divisible.

Divide 625 by 5: $$${625}={5}\cdot{125}$$$.

Divide 125 by 5: $$${125}={5}\cdot{25}$$$.

Divide 25 by 5: $$${25}={5}\cdot{5}$$$.

We are done since 5 is prime number.

So, $$${625}={5}\cdot{5}\cdot{5}\cdot{5}={{5}}^{{4}}$$$.

Now, it is time to practice.

**Exercise 1.** Find prime factorization of 990.

**Answer**: $$${2}\cdot{{3}}^{{2}}\cdot{5}\cdot{11}$$$.

Slightly harder exercise.

**Exercise 2.** Find prime factorization of 1725.

**Answer**: $$${3}\cdot{{5}}^{{2}}\cdot{23}$$$.

And final exercise.

**Exercise 3.** Find prime factorization of 343.

**Answer**: $$${{7}}^{{3}}$$$.