Prime Power Decomposition

# 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)
$$n = p_{1}^{e_{1}}p_{2}^{e_{2}}p_{3}^{e_{3}}...p_{k}^{e_{k}}$$

Where ei ≥ 1, pi is prime, and pi ≠ pj. There shouldn't exist a pi = pj, otherwise the product of pi and pj can be expressed as follows: piei pjej = piei + 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 = 31 * 71 * 131, where p1 = 3, p2 = 7, p3 = 13, and e1, e2, e3, = 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 = 24 * 32 * 71, where p1 = 2, p2 = 3, p3 = 7, and e1 = 4, e2 = 2, and e3, = 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)
\begin{align} n = p_{1}^{e_{1}}p_{2}^{e_{2}}p_{3}^{e_{3}}...p_{k}^{e_{k}} \quad m = p_{1}^{f_{1}}p_{2}^{f_{2}}p_{3}^{f_{3}}...p_{k}^{f_{k}} \end{align}

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

It follows thus that:

(3)
$$(n, m) = p_{1}^{g_{1}}p_{2}^{g_{2}}p_{3}^{g_{3}}...p_{k}^{g_{k}}$$

Where gi = min(ei, fi).

## 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 = 31 * 71 * 131
1008 = 24 * 32 * 71

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 = 20 * 31 * 71 * 110 131
1008 = 24 * 32 * 71 * 110 130

First notice the min(e1, f1) = min(0, 4) = 0. Thus g1 = 0. It follows that the min(e2, f2) = min(1, 2) = 1. Thus g2 = 1. We continue onward and can write the greatest common factor of 273 and 1008 such that:

(273, 1008) = 20 * 31 * 71 * 110 * 130.

Expanding this out we obtain:

(273, 1008) = 21

# Theorem: An integer n is a mth 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:
(4)
\begin{align} a^m = (p_1^{e_1 / m}p_2^{e_2 / m}...p_k^{e_k / m})^m \\ a^m = (p_1^{e_1 / m})^m (p_2^{e_2 / m})^m...(p_k^{e_k / m})^m \\ a^m = p_1^{e_1}p_2^{e_2}...p_k^{e_k} \end{align}
• Hence $n = a^m$, and n is an mth power.