Mastering Number Factors: Count, Sum, and Product

1. The Cornerstone: Prime Factorization

Every problem involving the number, sum, or product of factors begins with one crucial step: prime factorization. This means expressing a composite number as a product of its prime factors.

For instance, to factorize 36, you can use methods like a factor tree or repeated division.

Any number N can be uniquely written in its prime factored form as:

where $p_1,p_2,p_3,\dots$ are distinct prime numbers and $a_1,a_2,a_3,\dots$ are their respective positive integer powers.

This form is the foundation for everything that follows.

2. Finding the Number of Factors

Once you have the prime factorization of a number, finding its total number of factors is straightforward.

Let's say $N=p_1^{a_1}\times p_2^{a_2}$. Any factor of N must be of the form $p_1^x\times p_2^y$.

• The power of the prime $p_1$ in any factor can range from 0 to $a_1$. This gives us $(a_1+1)$ choices for the exponent $x$ (i.e., $0,1,2,\dots ,a_1$).
• Similarly, the power of $p_2$ can range from 0 to $a_2$, giving us $(a_2+1)$ choices for the exponent $y$.

Since you have a computer science background, you can think of this as a simple combinatorial problem. The total number of unique factors is the total number of combinations of these exponents.

Formula for Number of Factors:
If $N=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k}$, then the total number of factors is:

Let's watch a video that explains this concept with examples.

3. Finding the Sum of Factors

The logic for the sum of factors also stems directly from the prime factorization. Consider $N=p_1^{a_1}\times p_2^{a_2}$ again. The sum of all its factors is the result of expanding the following expression:

Each term in this expansion is a unique factor of N, and the full expansion is their sum. Each bracketed term is a finite geometric progression. The sum of a geometric series is given by $\frac{r^{n+1}-1}{r-1}$. Applying this gives us the formula.

Formula for Sum of Factors:
If $N=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k}$, then the sum of its factors is:

Now, let's see this formula in action.

4. Finding the Product of Factors

The method for finding the product of factors is quite intuitive. Let's take the number 36. Its factors are: 1, 2, 3, 4, 6, 9, 12, 18, 36.

If we pair the factors from the ends inwards, notice a pattern:

• $1\times 36=36$
• $2\times 18=36$
• $3\times 12=36$
• $4\times 9=36$
• The middle factor, 6, is left alone. $6=\sqrt{36}$.

The product is $(36\times 36\times 36\times 36)\times 6=36^4\times \sqrt{36}=36^4\times 36^{1/2}=36^{4.5}$.

The number of factors of 36 ($2^2\times 3^2$) is $(2+1)(2+1)=9$.
Notice that $4.5$ is exactly half the number of factors ($9/2$).

This leads to a simple, elegant formula that works for all numbers, whether they are perfect squares or not.

Formula for Product of Factors:
If a number $N$ has $k$ factors, the product of all its factors is:

where $k$ is the total number of factors you calculated in step 2.

This video from Rodha provides an excellent explanation of why this single formula works for both perfect squares (which have an odd number of factors) and non-perfect squares.

5. Comprehensive Example and Variations

Now let's put all three concepts together and also look at a common variation: finding the number of odd and even factors.

Summary of finding odd/even factors:
Let $N=2^a\times p_2^{a_2}\times p_3^{a_3}\times \dots$ (where $p_2,p_3,\dots$ are odd primes).

• Number of Odd Factors: An odd factor cannot have any power of 2 in it. So, we essentially ignore the $2^a$ part and calculate the number of factors for the remaining odd part of the number: $(a_2+1)\times (a_3+1)\times \dots$.
• Number of Even Factors: An even factor must have at least one power of 2. The easiest way to find this is:
  $\text{Total Factors}-\text{Odd Factors}$
  Alternatively, as the video shows, you take the power of 2 as is (don't add 1), and for all other prime powers, you add 1 as usual: $a\times (a_2+1)\times (a_3+1)\dots$.

Conclusion

Excellent work! Today you've added three powerful, formula-based techniques to your arsenal. The process is systematic and relies on a skill you've already been practicing.

Key Takeaways:

• Prime Factorization is King: Always start by expressing the number $N$ as a product of its prime powers: $N=p_1^{a_1}\times p_2^{a_2}\times \dots$.
• Number of Factors: Add 1 to each exponent and multiply the results: $(a_1+1)(a_2+1)\dots$.
• Sum of Factors: Use the geometric series sum for each prime: $\left(\frac{p_1^{a_1+1}-1}{p_1-1}\right)\times \dots$.
• Product of Factors: Raise the number $N$ to the power of (total factors / 2): N^{\text{num_factors}/2}.

In our next lesson, we will wrap up the Arithmetic Foundations module by learning how to determine the unit digit of large exponential expressions. This will bring back the concept of cyclicity we saw in the previous lesson on remainders, showing how these ideas are all interconnected.