# Integers Expressed as a Product of Primes

Sometimes, it may be useful to write an integer in terms of its *prime power decomposition*. Recall that any positive integer > 1 can be written as a product of primes, and specifically, that product is unique. Hence the prime power decomposition of a positive integer greater than 1 will also be unique.

For an integer n > 1, the prime power decomposition of that integer is expressed such that:

(1)Where e_{i} ≥ 1, p_{i} is prime, and p_{i} ≠ p_{j}. There shouldn't exist a p_{i} = p_{j}, otherwise the product of p_{i} and p_{j} can be expressed as follows: p_{i}^{ei} p_{j}^{ej} = p_{i}^{ei + ej}, for 1 ≤ i ≤ k, 1 ≤ j ≤ k.

## Example 1

**Determine the prime power decomposition of 273.**

Our first prime, 2 does not divide 273. However 3 | 273. Thus we obtain 273 = 3 * 91. 91 is no longer divisible by 3, and is also not divisible by 4, 5, or 6. 7 | 91 though, hence we obtain 273 = 3 * (7 * 13). Note that 3, 7, and 13 are all primes, so we are done.

Hence, the prime power decomposition of 273 = 3^{1} * 7^{1} * 13^{1}, where p_{1} = 3, p_{2} = 7, p_{3} = 13, and e_{1}, e_{2}, e_{3}, = 1.

## Example 2

**Determine the prime power decomposition of 1008.**

First notice that 2 | 1008. Hence 1008 = 2 * 504. It should be rather clear that 2 | 504 as well, hence 1008 = 2 * 2 * 252. Again, 2 | 252, hence we obtain 1008 = 2 * 2 * 2 * 126. 2 | 126, so we obtain 1008 = 2 * 2 * 2 * 2 * 63. 2 does not divide 63, but 3 | 63, so we obtain 1008 = 2 * 2 * 2 * 2 * 3 *21. 3 | 21, we we obtain 1008 = 2 * 2 * 2 * 2 * 3 * 3 * 7. 7 is prime, so we are done.

Hence, the prime power decomposition for 1008 = 2^{4} * 3^{2} * 7^{1}, where p_{1} = 2, p_{2} = 3, p_{3} = 7, and e_{1} = 4, e_{2} = 2, and e_{3}, = 1.

# Determining the Greatest Common Factor with Prime Power Decomposition.

Suppose we have two integers, n and m who prime power decompositions are as followed:

(2)Where the set of p starts with p_{1} being the smallest prime number between n and m when they are decomposed, and p_{k} is the largest prime between the integers n and m when they're decomposed. Also e_{1} ≥ 0, and f_{1} ≥ 0. Thus, it follows that for the set of primes P = {2, 3, 5, 7, …}, p_{i} and p_{i+1} are relatively consecutive.

It follows thus that:

(3)Where g_{i} = min(e_{i}, f_{i}).

## Example 3

**Determine the greatest common factor of 273 and 1008.**

We found in examples 1 and 2, that the prime decompositions of 273 and 1008 are:

273 = 3^{1} * 7^{1} * 13^{1}

1008 = 2^{4} * 3^{2} * 7^{1}

Let's rewrite these prime power decompositions in successive primes starting at the minimum prime between 273 and 1008, and ending at the greatest prime between 273 and 1008. These are 2 and 13 respectively. We thus will obtain:

273 = 2^{0} * 3^{1} * 7^{1} * 11^{0} 13^{1}

1008 = 2^{4} * 3^{2} * 7^{1} * 11^{0} 13^{0}

First notice the min(e_{1}, f_{1}) = min(0, 4) = 0. Thus g_{1} = 0. It follows that the min(e_{2}, f_{2}) = min(1, 2) = 1. Thus g_{2} = 1. We continue onward and can write the greatest common factor of 273 and 1008 such that:

(273, 1008) = 2^{0} * 3^{1} * 7^{1} * 11^{0} * 13^{0}.

Expanding this out we obtain:

(273, 1008) = 21

# Theorem: An integer n is a m^{th} power if all exponents in its prime power decomposition are divisible by k.

**Proof:**Suppose that $n = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$. If $e_1, e_2, ..., e_k$ are all divisible by m, then let $a = p_1^{e_1 / m}p_2^{e_2 / m}...p_k^{e_k / m}$. Hence it follows that:

- Hence $n = a^m$, and n is an m
^{th}power.