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)

\begin{equation} n = p_{1}^{e_{1}}p_{2}^{e_{2}}p_{3}^{e_{3}}...p_{k}^{e_{k}} \end{equation}

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^e_i p_j^e_j = p_i^{e_i + e_j}, 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¹ * 7¹ * 13¹, where p₁ = 3, p₂ = 7, p₃ = 13, and e₁, e₂, e₃, = 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⁴ * 3² * 7¹, where p₁ = 2, p₂ = 3, p₃ = 7, and e₁ = 4, e₂ = 2, and e₃, = 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 p₁ 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₁ ≥ 0, and f₁ ≥ 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)

\begin{equation} (n, m) = p_{1}^{g_{1}}p_{2}^{g_{2}}p_{3}^{g_{3}}...p_{k}^{g_{k}} \end{equation}

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¹ * 7¹ * 13¹
1008 = 2⁴ * 3² * 7¹

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⁰ * 3¹ * 7¹ * 11⁰ 13¹
1008 = 2⁴ * 3² * 7¹ * 11⁰ 13⁰

First notice the min(e₁, f₁) = min(0, 4) = 0. Thus g₁ = 0. It follows that the min(e₂, f₂) = min(1, 2) = 1. Thus g₂ = 1. We continue onward and can write the greatest common factor of 273 and 1008 such that:

(273, 1008) = 2⁰ * 3¹ * 7¹ * 11⁰ * 13⁰.

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:

(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 m^th power.