Factional Factors

The Fundamental Theorem of Arithmetic

We started a series on counting principles earlier this year. We first considered the most basic principles, namely the multiplication and addition principles. Then we looked at how permutations differ from combinations, considering some basic patterns of both including the elements of Pascal’s triangle. Next, we turned our attention to permutations of special kinds, including circular permutations and permutations of non-distinct objects. Then last week we considered combinatorial arguments and binomial identities. We are now poised to consider some ideas related to factors of numbers. I had thought I would be able to include the technique of partitions also in this post. However, I will tackle that in the next post.

In an earlier post we had looked at the ideas related to factors of numbers. But that was many months ago. So let us start here as though we are addressing these issues for the first time. We begin with the observation that every natural number, except 1, is either a prime number or a composite number. As a reminder, a prime number is one whose factors are only 1 and itself. A number that has a factor other than 1 and itself is said to be a composite number. While it would seem that 1 satisfies the condition for being a prime number, 1 is not considered to be prime. Why is this the case?

The fundamental theorem of arithmetic states that every natural number greater than 1 is either a prime number or can be expressed as a unique product of prime numbers, disregarding the order of the primes. We must admit that this theorem, like many in mathematics, is a kind of after-thought. It was introduced specifically to exclude 1 from the set of primes. And this is because including 1 in the set of primes creates more problems than it solves. This is because 1 is the multiplicative identity element. That is, the product of any number and 1 is the number itself. This means that, if we allow 1 to be defined as a prime number, we could write

Hence, any idea of a unique prime factorization would go into the gutter! However, nothing is gained by defining 1 to be a prime number. Hence, we exclude 1 from the set of primes. What this means is that every natural number greater than 1 can be written with a unique prime factorization, disregarding the order of the primes. For example,

Since multiplication is commutative, the order in which we multiply the prime numbers does not matter.

Number of Factors of N

Let us consider, for example, the number 450. We can determine the factors by using a method like that indicated in the diagram at the start of this post. However, for large numbers this may be an onerous task. However, we can resort to prime factorization and write 450 as

We can see that there are 5 prime factors with two of them being repeated twice. Hence, from what we have learned earlier, there are

ways of permuting these prime factors. However, all of them give the product of 450. Hence, if we disregard the order in which we multiply the prime factors, the prime factorization of 450 is unique and can be written as

Let us consider the factors of 450. They are 1, 2, 3, 5, 6, 9, 10, 15, 18, 25, 30, 45, 50, 75, 90, 150, 225, and 450. Hence, 450 has 18 distinct factors. Some of them are odd, like 1, 3, 5, 9, 15, 25, 45, 75, and 225. The others are even, like 2, 6, 10, 18, 30, 50, 90, 150, and 450. We can see that there are 9 factors that are odd and 9 that are even. That is curious because 9 + 9 = 18. Perhaps there is something here.

Let us consider the other prime factors. There are factors that are not divisible by 3, such as 1, 2, 5, 10, 25, and 50. There are factors that are divisible by 3 but not divisible by 9, such as 3, 6, 15, 30, 75, and 150. And there are factors that are divisible by 9, such as 9, 18, 45, 90, 225, and 450. We can see that there are 6 of each such factors and 6 + 6 + 6 = 18. In a similar way, the factors not divisible by 5 are 1, 2, 3, 6, 9, and 18. The factors divisible by 5 but not by 25 are 5, 10, 15, 30, 45, and 90. And the factors divisible by 25 are 25, 50, 75, 150, 225, and 450. Once again, there are 6 of each and 6 + 6 + 6 = 18. Surely there is some significance to this. Perhaps we can get a pattern by considering a number with fewer distinct factors.

Let us consider the number 18. It has 6 distinct factors, namely 1, 2, 3, 6, 9, and 18. Of these, 3 are odd, namely 1, 3, and 9, and 3 are even, namely 2, 6 and 18. Also 2 are not divisible by 3, namely 1 and 2, 2 are divisible by 3, but not by 9, namely 3 and 6, and 2 are divisible by 9, namely 9 and 18. We will now invoke the fact that 1 is the multiplicative identity element and that, for any natural number n, n⁰ = 1. Since the prime factorization of 18 is 2¹3², any factor of 6 can have as its factors 2⁰, giving an odd number, or 2¹, giving an even number. In a similar way, any factor of 18 can have as its factor 3⁰, giving a number not divisible by 3, or 3¹, giving a number divisible by 3, but not by 9, or 3², giving a number divisible by 9. In other words, there. So, since we had 2¹ in the prime factorization of 18, there are 1 + 1 = 2 ways of including 2 in the factor, either exclude it, giving an odd number, or include it, giving an even number. And since we had 3² in the prime factorization of 19, there are 2 + 1 = 3 ways of including 3 in the factor, exclude it completely, giving a number not divisible by 3, include only one 3, giving a number divisible by 3 but not by 9, or include both 3s, giving a number divisible by 9.

Let us see if we can generalize this result. Suppose we have the number N. Suppose its prime factorizations is

Then, the number of distinct factors of N will be

Let us put this to the test. For 18 = 2¹3², p₁ = 2, p₂ = 3, a₁ = 1, and a₂ = 2. According to the result, the number of factors should be (1 + 1)(2 + 1) = 6, which is correct. For 450 = 2¹3²5², p₁ = 2, p₂ = 3, p₃ = 5, a₁ = 1, a₂ = 2, and a₃ = 2. According to the result, the number of factors should be (1 + 1)(2 + 1)(2 + 1) = 18, which is correct.

Sum of Factors of N

Now, let us try to find the sum of the factors of a natural number. Consider the number 18. The sum of its factors will be 1 + 2 + 3 + 6 + 9 + 18 = 39. For the number 450, the sum of the factors is 1 + 2 + 3 + 5 + 6 + 9 + 10 + 15 + 18 + 25 + 30 + 45 + 50 + 75 + 90 + 150 + 225 + 450 = 1209. If we attempt to factorize 39 we get 39 = 3 × 13. Similarly 3 × 13 × 31. The repetition of the 3 and 13 seems interesting.

Let us consider another number, say 6, which has a prime factorization of 2¹3¹. The factors are 1, 2, 3 and 6, which add up to 12, which in turn can be written as 3 × 4. Similarly, the factors of 15, which has a prime factorization of 3¹5¹, are 1, 3, 5, and 15, which add up to 24, which is 4 × 6. Also, the factors of 30, which has a prime factorization of 2¹3¹5¹, are 1, 2, 3, 5, 6, 10, 15, and 30, which add up to 72, which is 3 × 4 × 6. We can see that, when 2¹ appears in the prime factorization, the sum of the factors has 3 as a factor. Similarly, when 3¹ appears in the prime factorization, the sum of the factors has 4 as a factor. And when 5¹ appears in the prime factorization, the sum of the factors has 6 as a factor.

Now let us consider some other examples. These are summarized in the table below.

The results are also color coded. 2¹ links with 3, 2² links with 7, 3¹ links with 4, 3² links with 13, 5¹ links with 6, 5² links with 31, and 7¹ links with 8. Of course, if you are familiar with series of powers of natural numbers, you will recognize that

Hence, it seem as though, for a number like, say 42, the sum of the factors can be written as

We can see how this makes sense. The final expression involving a product of three terms can be expanded as follows:

We can, therefore, reach a generalization as follows for any natural number, N. Suppose the prime factorization of N is

Then the sum of the factors of N will be

Consider the number 12,600 = 2³3²5²7¹. According to the result we have just obtained, the sum of all the factors should be (1 + 2 + 3 + 4 + 5)(1 + 3 + 9)(1 + 5 + 25)(1 + 7) =48,360. This is confirmed here. Of course, we could use the previous result to determine that 12,600 has (3 + 1)(2 + 1)(2 + 1)(1 + 1) = 72 factors.

Using the two results we have obtained we can determine how many factors a number has and the sum of those factors without determining what those factors are. So, for example, if we are given the number 174,636,000 = 2⁵3⁴5³7²11¹, we can determine that it has (5 + 1)(4 + 1)(3 + 1)(2 + 1)(1 + 1) = 720 factors, the sum of which is (1 + 2 + 4 + 8 + 16 + 32)(1 + 3 + 9 + 27 + 81)(1 + 5 + 25 + 125)(1 + 7 + 49)(1 + 11) = 813,404,592. We can observe that the terms in each set of parentheses form a geometric sequence with first term 1, which can easily be summed using the formula

In other words, even with extremely large numbers, we can obtain the number of factors and the sum of factors with a few lines of code in a computer.

Looking Ahead

What we have seen in this post is a way of determining the number of factors of a number and the sum of its factors without having to find all the factors. We do need to determine the prime factorization of the number However, this is a straightforward process. Now, we used the fundamental theorem of arithmetic to help us determine both the number of factors and the sum of the factors. While this may not be a theorem that is explicitly named when we are in school, it is something that we use regularly after learning division and factorization. Hence, we used some relatively simple mathematics that we learned in elementary school to unravel the question of the number and sum of factors. While some of the formalism and symbols used might be beyond what a student in elementary can understand, the arithmetic behind it is something that elementary students can understand. This is especially so if we demonstrate how, while expanding the expression for the sum of factors, we need to choose one term from each set of parentheses without repetition.

In the next post, we will tackle the technique of partitioning. In order to set up the post, I will leave you with a question. Given that x, y, and z are natural numbers, how many solutions exist to the equation x + y + z = 100?