Prime Factorization and Perfect Powers

Welcome back. In our previous lessons, we established the absolute centrality of the Fundamental Theorem of Arithmetic (FTA). We used it to prove the uniqueness of prime factorization and then leveraged that uniqueness to derive formulas for counting the number of divisors of an integer, $τ (n)$ , and calculating their sum, $σ (n)$ .

Today, we will dig deeper into the structure revealed by prime factorization. Specifically, we will focus on the exponents of the primes. As you will see, the pattern of these exponents provides a definitive signature for identifying special classes of numbers, namely perfect squares, perfect cubes, and other higher powers. This lesson will equip you with a fundamental technique for solving a wide range of problems in number theory by analyzing the "shape" of a number's factorization.

1. The Signature of a Perfect Square

Let's begin with the most common case: perfect squares. What makes a number a perfect square from the perspective of its prime factors?

Consider a number $m$ , and its prime factorization $m = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ . If we square this number, we get:
$m^{2} = (p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}})^{2} = p_{1}^{2 a_{1}} p_{2}^{2 a_{2}} \dots p_{k}^{2 a_{k}}$
Notice what happened: every exponent in the prime factorization of $m^{2}$ is an even number. This gives us one direction of our characterization.

The other direction is just as straightforward. Suppose we have an integer $n$ whose prime factorization has only even exponents, say $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$ , where each $e_{i}$ is even. This means we can write each $e_{i} = 2 f_{i}$ for some integer $f_{i} \geq 0$ . Substituting this back gives:
$n = p_{1}^{2 f_{1}} p_{2}^{2 f_{2}} \dots p_{k}^{2 f_{k}} = (p_{1}^{f_{1}} p_{2}^{f_{2}} \dots p_{k}^{f_{k}})^{2}$
This shows that $n$ is the square of the integer $p_{1}^{f_{1}} p_{2}^{f_{2}} \dots p_{k}^{f_{k}}$ .

Therefore, we have a complete characterization: An integer $n > 1$ is a perfect square if and only if every exponent in its prime factorization is even.

This simple observation is surprisingly powerful. The following image provides some concrete examples of this principle in action.

This table demonstrates how the square root of a number can be found by taking prime factors with half the exponent. For example, since $144 = 2^4 \cdot 3^2$, its square root is $2^{4/2} \cdot 3^{2/2} = 2^2 \cdot 3^1 = 12$.

The following resource formalizes this idea concisely.

2 Divisibility, Primes & Unique Factorization

This excerpt from lecture notes by Donald L. King at UCI formalizes the connection we just discussed, along with other direct consequences of unique factorization.

Please read point 3 of Corollary 2.23. This states the "if and only if" condition for a number being a perfect square based on its prime exponents. Note how the brief justification provided, (consider a = b^2 then µi = 2νi), captures the essence of our derivation.

2. A Link to the Number of Divisors

In our last lesson, we found that for $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ , the number of divisors is $τ (n) = (e_{1} + 1) \dots (e_{k} + 1)$ . This formula provides an entirely different, yet equivalent, way to characterize perfect squares.

Consider the question: for which numbers $n$ is $τ (n)$ an odd number?
For the product $(e_{1} + 1) (e_{2} + 1) \dots (e_{k} + 1)$ to be odd, every single factor $(e_{i} + 1)$ must be odd. This, in turn, means that every exponent $e_{i}$ must be even.

We have just discovered a beautiful and classic result: An integer $n$ is a perfect square if and only if it has an odd number of positive divisors. This bridges the topic of our previous lesson with today's. A famous problem illustrates this concept perfectly.

Olympiad Number Theory Through Challenging Problems

This classic problem from an AoPS resource provides a memorable application of the connection between perfect squares and the number of divisors.

Read Example 1.3.1, often known as the "Locker Problem" or "Jailer Problem." Follow the logic: a door (or locker) is left open if it's toggled an odd number of times. This occurs only if the door's number has an odd number of divisors. The author then uses the \tau(n) formula to prove this is true precisely for perfect squares.

3. Generalization and a Powerful Notation: p-adic Valuation

The logic we used for perfect squares generalizes directly to any power. An integer $n$ is a perfect cube if and only if all exponents in its prime factorization are divisible by 3. In general:

An integer $n$ is a perfect $k$ -th power if and only if every exponent in its prime factorization is a multiple of $k$ .

To work with these exponents more formally, especially in the context of Olympiad problems, we introduce a crucial piece of notation.

The p-adic valuation of an integer n, denoted $v_{p} (n)$ , is the exponent of the prime $p$ in the unique prime factorization of $n$ .

For example, if $n = 72 = 2^{3} \cdot 3^{2}$ , then:

$v_{2} (72) = 3$
$v_{3} (72) = 2$
$v_{5} (72) = 0$
$v_{p} (72) = 0$ for any prime $p$ other than 2 or 3.

This notation is extremely useful. The following resource introduces it formally and proves its most basic properties.

Olympiad Number Theory Through Challenging Problems

To formalize our discussion of exponents, we introduce this standard and powerful notation used throughout number theory.

Please read the section titled Definition and Basic Theorems. Focus on understanding the definition of v_p(m) and the proofs of the two key theorems for products and sums: v_p(ab) = v_p(a) + v_p(b) If v_p(a) > v_p(b), then v_p(a+b) = v_p(b). (This is sometimes called the "ultrametric property".)

Using this notation, we can rephrase our central finding much more elegantly:

An integer $n$ is a perfect $k$ -th power if and only if for every prime $p$ , $v_{p} (n) \equiv 0 (mod k)$ .

4. Applications in Problem Solving

This characterization is not just a theoretical curiosity; it's a practical tool. Let's apply it to a couple of problems.

Problem 1: Prove that if $a, b$ are coprime positive integers such that $ab$ is a perfect square, then both $a$ and $b$ must be perfect squares.

Proof using p-adic valuation:
Let $n = ab$ . We are given that $n$ is a perfect square. This means that for any prime $p$ , $v_{p} (n)$ is even.
From the properties of p-adic valuation, we know $v_{p} (n) = v_{p} (ab) = v_{p} (a) + v_{p} (b)$ .
We are also given that $g cd (a, b) = 1$ . This implies that for any prime $p$ , $p$ cannot divide both $a$ and $b$ . In terms of p-adic valuation, this means that for any $p$ , at least one of $v_{p} (a)$ or $v_{p} (b)$ must be 0.

Now, let's consider an arbitrary prime $p$ .
- If $p$ divides $a$ , then it cannot divide $b$ , so $v_{p} (b) = 0$ . In this case, $v_{p} (a) = v_{p} (a) + 0 = v_{p} (a) + v_{p} (b) = v_{p} (ab)$ . Since $v_{p} (ab)$ is even, $v_{p} (a)$ must be even.
- If $p$ does not divide $a$ , then $v_{p} (a) = 0$ .
This shows that for any prime $p$ , $v_{p} (a)$ is even. By our characterization, this means $a$ is a perfect square. An identical argument holds for $b$ . This completes the proof.

Problem 2 (A Structural Result): Prove that every integer $n > 1$ can be uniquely written in the form $n = s^{2} k$ , where $s$ is a positive integer and $k$ is a square-free integer. (A number is square-free if none of its prime factors have an exponent greater than 1).

Proof Sketch:
Let the prime factorization of $n$ be $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{m}^{e_{m}}$ .
By the division algorithm, each exponent $e_{i}$ can be written as $e_{i} = 2 q_{i} + r_{i}$ , where $q_{i}$ is the quotient and the remainder $r_{i}$ is either 0 or 1.

We can now rewrite the factorization of $n$ :
$n = p_{1}^{2 q_{1} + r_{1}} p_{2}^{2 q_{2} + r_{2}} \dots p_{m}^{2 q_{m} + r_{m}}$
By grouping terms, we get:
$n = (p_{1}^{2 q_{1}} p_{2}^{2 q_{2}} \dots p_{m}^{2 q_{m}}) \cdot (p_{1}^{r_{1}} p_{2}^{r_{2}} \dots p_{m}^{r_{m}})$
Now, examine the two parts:
1. The first part is $(p_{1}^{q_{1}} p_{2}^{q_{2}} \dots p_{m}^{q_{m}})^{2}$ . This is clearly a perfect square. Let's call it $s^{2}$ .
2. The second part is $p_{1}^{r_{1}} p_{2}^{r_{2}} \dots p_{m}^{r_{m}}$ . Since each exponent $r_{i}$ is either 0 or 1, this number is square-free. Let's call it $k$ .
Thus, we have shown that $n = s^{2} k$ . The uniqueness of this representation follows directly from the uniqueness of prime factorization. This problem, which comes from an exercise in the UCI notes, is a great example of how analyzing exponent parity allows us to decompose numbers into structurally significant parts.

Conclusion

In this lesson, we have seen how the exponents within a prime factorization provide a powerful lens for understanding the structure of integers.

Key Takeaways:

An integer $n$ is a perfect $k$ -th power if and only if every exponent in its prime factorization is divisible by $k$ .
As a special case, $n$ is a perfect square if and only if all its prime exponents are even.
This connects to our previous lesson: a number is a perfect square if and only if it has an odd number of divisors.
The p-adic valuation, $v_{p} (n)$ , provides a formal and efficient notation for the exponent of a prime $p$ in the factorization of $n$ .
Using this framework, we can prove important properties, such as the fact that if two coprime numbers multiply to a square, they must themselves be squares.

So far in this module, we have established the existence and uniqueness of prime factorization and used it to analyze divisors and powers. The common thread is the prime number. But what do we know about the set of primes itself? Is it finite, or does it go on forever? In our next lesson, we will address this fundamental question by studying one of the most celebrated proofs in all of mathematics: Euclid's argument for the infinitude of primes.

Recommended resources

1. The Signature of a Perfect Square

2. A Link to the Number of Divisors

3. Generalization and a Powerful Notation: p-adic Valuation

4. Applications in Problem Solving

Conclusion