Factors
A factor of an integer is an integer which can be multiplied by some integer to produce Then what is the easiest way to find the number of factors of an integer? If the integer is small (say less than 100), we could try and find all of the factors directly, and then count them. However, this quickly becomes tedious, as we work with larger numbers like 1001.
Contents
Definition and Prime Factorization
An integer is said to be a factor (or divisor) of an integer , if there exists an integer such that
In general, the divisors of a number refer to the positive divisors, unless otherwise noted. Since the negative divisors will be the negative of a positive divisor (and vice versa), we shall just consider positive divisors. We also tend to ignore the possibility for any of these numbers to be 0. Also, since our definition above gives us that every integer is a divisor of .
A proper factor of a number is a positive integer that is a factor of other than or 1. Do not confuse this with a proper divisor of , which is any positive integer that is a factor of other than itself. A prime factor of a number is a positive integer that is a factor of and is also prime.
From the definition, factors of a number tend to occur in pairs of the form . This is true except for cases when is a perfect square, in which case
How many factors does have?
We can write as . So the factors are implying has factors.
Every positive integer possesses a unique prime factorization given by , where are distinct prime numbers, and are positive integers.
How many factors does 100 have? What is the prime factorization of 100?
Since , the factors of 100 are Therefore, has 9 factors in all. Note that 100 has an odd number of factors, which means that is a perfect square.
The prime factors of 100 are 2 and 5 and the highest powers of these contained in 100 are 4 and 25, respectively. So we can write the following prime factorization
What is the prime factorization of ?
We start by making a list of factors:
Hence the factors are implying has factors. The prime factors are 2, 3, 5, and 7, each of which is the highest power contained in 210, so 210 has the prime factorization
For small numbers, we see that we can slowly list out all of the factors, and count them directly if we have not made any mistakes. However, when the numbers become larger, it can be difficult to ensure that we have actually found all of the factors. We might miss 1 or 2 if we are not careful.
Number of Factors/Divisors
If , then has divisors.
A proof of this theorem is provided at the end of this section. Let's check it against our previous examples:
- has factors.
- has factors.
- has factors.
The theorem is true in these examples.
How many divisors does the number have?
We have . Hence, from the above discussion, it has divisors.
Note: We can list them out as 1, 2, 4, 8, 16, 5, 10, 20, 40, 80, 25, 50, 100, 200, 400, 125, 250, 500, 1000, 2000. (Can you see why we listed out the divisors this way, instead of in increasing order?)
How many factors does have?
It can be very difficult to solve this by listing the factors out. We can solve this by prime factorization. The prime factorization of is
Each factor is of the form , where and Hence, has choices, has choices, has choices, and has choices.
Using rule of product, we can conclude has factors.
What is the smallest integer that has exactly 14 divisors?
Since , an integer has exactly 14 divisors if it has the form or . The smallest number in the first case and second case are and , respectively. Hence 192 is the smallest integer that has exactly 14 divisors.
Let's prove the theorem at the start of this section.
We will use prime factorization and the rule of product to help us count effectively.
Let the integer have a prime factorization , where are distinct prime numbers, and are positive integers. Let be a divisor of then any prime factor that divides must divide , and hence it must be one of .
Without loss of generality, set . Let the highest power of that divides be . Then, divides , which in turn divides , and hence must divide , which means that . Thus, by considering all the prime factors of , we get that it must have the form where for all .
Conversely, given a number that has the form where for all it is clear that is a divisor of . As such, we have a complete classification of all the divisors.
How many divisors does the number have? From the above classification, we can set up a direct bijection between and sets of integers that satisfy . For each , there are possibilities. Hence, by the product rule, there are going to be divisors in all. The number of divisors of an integer is often denoted as the or , which is the divisor function.
A positive integer is said to be strange if it has an odd number of distinct positive divisors. Find the sum of all positive strange numbers less than or equal to 2016.
Details and Assumptions:
- As an explicit example, 4 is strange because it has 3 distinct positive divisors, namely 1, 2 and 4, while 10 is not strange because it has 4 distinct positive divisors, namely 1, 2, 5 and 10.
Sum of Factors
Given a number , what is the sum of all of its factors?
Normal Method
We first start with looking at small cases, where we can list out all of the factors of a number and add them up.
Find the sum of the factors of .
Since , we know it has factors. Next, find the factors: They are . Now add: which yields the answer as
Find the sum of factors of 50.
Since , we know it has factors. Next, find the factors: They are . Now add: which yields the answer as
Once again, for small numbers, we can slowly list out all the factors, and be certain that we got all of them. However, with larger numbers, finding the factors can get tedious.
Number Theoretical Approach
If , then the sum of the factors of is
A proof of this theorem is provided at the end of this section. Let's check it against our previous examples:
- , and the sum of its factors is .
- , and the sum of its factors is .
The theorem is true in these examples.
What is the sum of factors of
We start with the prime factorization, which is equal to
The sum of all the factors of 1000 is .
Let's check this against the normal method. The factors of 1000 are as follows:
The sum of these terms is
Suppose that the prime factorization of a positive number is
If the sum of all the factors of is what is
By the above formula, the sum of all the factors of the number is
Equating this with gives
Let's now prove the theorem.
In the previous proof for the number of divisors, we were able to classify all of the divisors. In particular, if , then the divisors of the number have the form
The solution to the sum of factors of 1000 hints at how we can do the factoring. For each combination of , if we find the sum of the terms over all possible values of , we will obtain
The terms in the brackets are a geometric progression, whose sum is given by . This is where the term in our formula appears from.
We repeat this procedure, where we sum up over all possible values of , and then , and so on and so forth.
The sum of all of these factors would hence be
Product of Factors
Given a number what is the product of all of its factors?
Normal Method
We first start with looking at small cases, where we can list out all of the factors of a number and multiply them.
What is the product of the factors of 15?
We see that the factors of 15 are 1, 3, 5, and 15. Multiplying them gives 225.
Find the product of the factors of 12.
The factors of 12 are 1, 2, 3, 4, 6 and 12. Prime factorization of each factor gives
Now observe that and each appear twice. and each appear three times. Thus the factors are distributed in a symmetrical manner. Hence multiplying all the factors will give
Once again, for small numbers, we can slowly list out all the factors. However, with larger numbers, findinig the factors can get tedious, and multiplying them could lead to a lot of errors.
Number Theoretic Approach
Suppose we have an integer . It has factors. Then, the product of its factors is
A proof of this theorem is provided at the end of this section. Let's check it against our previous examples:
Find the product of all factors of 7056.
We have , which implies that the number of factors has is
Therefore the product of all its factors is
Consider an integer which has 6 factors. If the product of all its factors is 8000, what is
Using the formula above, we have
Let's now prove the theorem.
Let us denote to be the number of positive divisors has. We want to find a closed form of the product of all positive divisors of
As mentioned, notice that for any divisor of , we have so is also a divisor of
Let's list out all of these.
Taking the product of the pairs of number, the LHS will give us product square. The RHS gives us . Hence, the product of the divisors is .
Additional Problems
Show that an integer has an odd number of divisors if and only if it is a perfect square.
Since , this product is odd if and only if every term is odd, which happens if and only if every value is even, which happens if and only if is a perfect square.
The prime factorization of a positive number is and the sum of all the factors of is Then what is
By the above formula, the sum of all the factors of the number is
Without loss of generality, let then implies Then letting we have which implies Thus,
What is the smallest integer that has exactly 14 divisors?
Since , an integer has exactly 14 divisors if it has the form or . The smallest number in the first case and second case are and , respectively. Hence 192 is the smallest integer that has exactly 14 divisors.
- What is the smallest integer which has exactly 10 divisors?
- What is the smallest integer which has exactly 9 divisors?
- Which integer less than 100 has the most number of factors?
- What is the sum of the factors of 1234?
More Examples
Recap of Properties:
If and then that is, divisibility is transitive.
If and then that is, the set of multiples of an integer is closed under addition and subtraction operations.
By using this property repeatedly, we have the following: if and , then for any integers and . In general, if are multiples of , then
If , then or . Thus, if and , then .
Clearly, for any two integers and , is not always divisible by . But we have the following result, which is called the division algorithm. It is the most important result in elementary number theory.
The Division Algorithm
Let and be integers, and . Then there is a unique pair of integers and , such that
The integer is called the (incomplete) quotient when is divided by , and is called the remainder. Note that the values of has kinds of possibilities: If , then is divisible by .
It is easy to see that the quotient in the division algorithm is in fact the greatest integer not exceeding and the heart of the division algorithm is the inequality about the remainder : . We will go back to this point later on.
The basic method of proving is to factorize into the product of and another integer. Usually, in some basic problems this kind of factorization can be obtained by taking some special value in algebraic factorization equations. The following two factorization formulae are very useful in proving this kind of problems.
If is a positive integer, then
If is a positive odd number, then
Examples:
Prove that is divisible by .
By , we have
Therefore, divides .
Let and be integers such that . Show that
Take and in , and substitute by . Then we have
Thus,
Since
it follows that
By , we have
and we are done.
For a positive integer , let denote the sum of digits of .
Show that if and only if .
Write where and then . We have
For , from we get . So each of the terms on the RHS of is a multiple of so implies that their sum is also a multiple of , that is, . Hence, the result can be obtained easily.
Let be an odd integer. Prove that for any positive integer , is not divisible by .
When the statement is obviously true. For , denote the sum by . Then
Since is a positive odd integer, from we know that for every , is divisible by
Thus, has remainder when divided by , which implies that is not divisible by note that