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}}$$$.