Factors of a Number

A divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A composite number is a positive integer that has at least one positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number.
Literally prime means ‘of first importance’ and composite means ‘made up of various parts or elements’. Now what a composite number made up of? Prime numbers! All composite numbers can be written as a product of prime factors. This is called as the standard form of a composite number. We can say thatprime numbers are the basic building blocks of all numbers.
For example, 42 can be written as 2 * 3 * 7 and 50 can be written as 2 * 5^{2}
Always keep in mind that 1 is neither prime nor composite. But why 1 is neither prime nor composite?
In number theory, the fundamental theorem of arithmetic states that every integer greater than 1 is either prime itself or can be uniquely written as a product of prime numbers. Take the case of 90. Theorem states that 90 is either a prime or a product of primes. By factorization, we get 90 as product of primes. 90 = 2 * 3* 3 * 5. It also says that the combination of primes will be unique (if we disregard the order of primes). Means 90 can be written as 5 * 3 * 3 * 2 or 3 * 2 * 3 * 5 or any combination we can form using the prime. But there will be always one 2, two 3s and one 5 in the expression, which is unique to 90. If we treat 1 as a prime, then we can bring in any number of ones. We can write 90 as 5 * 3 * 3 * 2 * 1 and 5 * 3 * 3 * 2 * 1 * 1 which are both valid expression for 90 and this violate the unique factorization requirement of fundamental theory. So one is not considered as a prime and as one cannot be represented as a product of primes and hence one is not composite too.
Zero is neither a prime number nor a composite number. It cannot be a prime because it has an infinite number of factors and cannot be composite because it cannot be expressed by multiplying prime numbers.
We can get lot of information related to a number from its standard form. Here we go
Number of factors of a number
If a number N can be represented as P_{1}^{a} * P_{2}^{b} * P_{3}^{c} where P_{1}, P_{2}, P_{3} are prime factors of N then number of factors of N can be found as (a + 1) * (b + 1) * (c + 1).
50 = 2 * 5^{2}, so number of factors of 50 = (1+1) * (2+1) =6. Which are 1, 2, 5, 10, 25and 50. These are various combinations of the prime factors 2, 5 and 5.
Similarly, 792 = 2^{3}* 3^{2}* 11, number of factors = (3+1) * (2+1) * (1+1) = 24
You can see how extensively we use divisibility rules here. For the above problem it won’t take much time to see the number 792 has a factor 2 (ending with even number), factor 4 (last 2 digits divisible by 4), factor 8 (last 3 digits divisible by 8 ), factor 3 (sum of digits divisible by 3), factor 9 (sum of digits divisible by 9) and factor 11 (difference between sum of digits at odd place and sum of digits at even place is zero or multiple of 11, here 0).
To find the standard form divide the number with its prime factors (take highest power of each prime) till we get unity. Then group the powers of all prime factors we used in each step to get the standard form. Confused? It is easy with examples J
Take 544; By using the divisibility rules we can easily see 2, 4, 8 are factors of 544. Take the highest power of each prime (here 8 ) for division.
544/8 = 68, divisible by 2, 4 and 17. Take the highest power of each prime
68/ (4 * 17) = 1.
544 = 8 * 4 * 17 = 2^{5 }* 17
Number of factors = 6 * 2 = 12
Need one more? Take 1080; Applying divisibility rules, we get 2, 3, 4, 5, 8, 9 divides the number. Take the highest power of each prime (here 8, 5, 9) for division.
1080 / (8 * 5 * 9) = 3 (can stop dividing here as we got a prime, no need to write an obvious step to get unity by dividing with the same prime!)
1080 = 8 * 5 * 9 * 3 = 2^{3}* 3^{3}* 5
Number of factors = (3 + 1) * (3 + 1) * (1 + 1) = 4 * 4 * 2 = 32
Sum of factors of a number
40 = 2^{3} * 5, number of factors = (3 + 1) * (1 + 1) = 4 * 2 = 8.
Sum of the factors = 1 + 2 + 4 + 8 + 5 + 10 + 20 + 40 = 90
This is same as (2^{0} + 2^{1} + 2^{2} + 2^{3}) (5^{0} + 5^{1}) = 15 * 6 = 90.
Find the sum of all the powers of each prime numbers, starting from 0 to the highest power contained in the standard form. Product of all such sums will give us the sum of the factors.
Here also it is easy to understand with examples, so here we go.
We have already seen that 1080 = 2^{3} * 3^{3 }* 5
In this case, sum of the factors will be (2^{0 }+ 2^{1} + 2^{2} + 2^{3}) * (3^{0 }+ 3^{1} + 3^{2} + 3^{3}) * (5^{0} + 5^{1})
= 15 * 40 * 6 = 3600
This also explains how we find the numbers of factors. It is the product of the number of factors in each bracket (here, 4 * 4 * 2 = 32).
Product of factors of a number
N = P_{1}^{a} * P_{2}^{b} * P_{3}^{c }
Then the product of all the factors of N = N ^{(a + 1) (b + 1) (c + 1)/2}
e.g. 50 = 2 * 5^{2}; Product of all factors of 50 = 50 ^{(6) / 2} = 50^{3}
Number of odd factors
To get the number of odd factors, ignore the powers of 2.
Take 1080, 1080 = 2^{3} * 3^{3} * 5
Number of odd factors of 1080 = (3 + 1) * (1 + 1) = 4 * 2 = 8, here we considered only the powers of 3 and 5 to get the number of odd factors.Sum of odd factors of a number
Sum of factors of 1080 = (2^{0 }+ 2^{1}+ 2^{2}+ 2^{3}) * (3^{0}+ 3^{1}+ 3^{2}+ 3^{3}) * (5^{0}+ 5^{1}), where each term in the expansion represents a factor of 1080.
We need at least one 2 to get an even factor. Remove all terms that has a 2 in it and we will remove all even factors. Even factors in 1080 are 2^{1}, 2^{2}and 2^{3}. The only power of 2 remaining is 2^{0 }(=1), which can be removed as it will not make any impact. Means, you ignore all powers of 2 to get the sum of all odd factors.
Now we need to remove even factors from the expression so that the result will be the sum of all odd factors.
Sum of odd factors of 1080 = (3^{0}+ 3^{1}+ 3^{2}+ 3^{3}) * (5^{0}+ 5^{1}) = 240
Number of even factors of a number
Let a number is of the form, N = 2^{a} * P_{2}^{b} * P_{3}^{c}…
Then Number of even factors of N = a * (b + 1) * (c + 1) …
For e.g. 1080 = 2^{3 } * 3^{3} * 5
Number of even factors of 1080 = 3 * (3 + 1) * (1 + 1) = 24Sum of even factors of a number
To get the sum of the even factors we need to ensure that all the terms in the expression for the sum of factors are even. All members in the 2’s bracket except 2^{0}will give an even number. Remove 2^{0 }from the group and that’s all it takes!
For e.g. 1080 = 2^{3 } * 3^{3} * 5
Sum of even factors of 1080 = (2^{1} + 2^{2 }+ 2^{3}) * (3^{0 }+ 3^{1} + 3^{2 }+ 3^{3}) * (5^{0 }+ 5^{1}) = 3360Other conditions
What if we are asked to find the sum and number of factors of 1080 which are divisible by 15?
We don’t have to use anything else other than the logic we used for odd and even factors. We know number of terms in the expression is the number of factors. So when a condition is given, number of factors is the number of terms in the expression satisfying the given condition and considers only those factors to get the sum.
1080 = (2^{0 }+ 2^{1}+ 2^{2}+ 2^{3}) * (3^{0}+ 3^{1}+ 3^{2}+ 3^{3}) * (5^{0}+ 5^{1})
Now 15 = 3 * 5, so we need to ensure that every term in the expression has a 3 and 5 in it. Now look at the bracket of 3 and find the terms that don’t yield a 3 in the expression. Also check for bracket of 5 for the terms that don’t give us a 5. 3^{0}and 5^{0}are the culprits. Remove those entries and we get the expression we need.
Sum of factors of 1080 which are divisible by 15
= (2^{0 }+ 2^{1}+ 2^{2}+ 2^{3}) * (3^{1}+ 3^{2}+ 3^{3}) * (5^{1})
= 15 * 39 * 5 = 2730Find the sum of factors of 544 which are perfect squares
544 = 8 * 4 * 17 = 2^{5 }* 17
Our expression, (2^{0}+ 2^{1}+ 2^{2}+ 2^{3}+2^{4 }+2^{5}) (17^{0}+17^{1})
Ensure all terms in the expression satisfy the condition, perfect squares. So each term in the expression should be of even power. We have to remove all odd powers in the expressionRequired sum is (2^{0}+ 2^{2 }+2^{4}) (17^{0}) = 21.
Number of factors = 3 * 1 (number of terms in each bracket) = 3.For the number 1000 find the below values
The number of divisors = (3 + 1) * (3 + 1) = 16 (as 1000 = 2^{3}* 5^{3})
The product of divisors = 1000^{16/2 }= 1000^{8}
The sum of divisors= (2^{0}+ 2^{1}+ 2^{2}+ 2^{3}) (5^{0 }+ 5^{1}+ 5^{2}+ 5^{3}) = 2340The sum and number of odd divisors
we need to remove all factors that can yield a 2 from the two’s bracket.
Sum of odd factors = ( 2^{0}) * (5^{0}+ 5^{1}+ 5^{2}+ 5^{3}) = 156
Number of odd factors = 1 * 4 = 4The sum and number of even divisors
We need to remove all factors that cannot yield a 2 from the two’s bracket (which is 2^{0})
Sum of even factors = (2^{1}+ 2^{2}+ 2^{3}) (5^{0}+ 5^{1}+ 5^{2}+ 5^{3}) = 2184
Number of even factors = 3 * 4 = 12The sum and number of divisors which are perfect squares
We need to remove all the factors which are not perfect squares
Sum of factors which are perfect squares = (2^{0}+ 2^{2 }) (5^{0}+ 5^{2}) = 130
Number of factors which are perfect squares = 2 * 2 = 4The sum and number of divisors which are not perfect squares
Total sum – sum of divisors which are perfect squares = 2340 – 130 = 2210
Total factors – number of divisors which are perfect squares = 16 – 4 = 12The sum and number of divisors which are divisible by 125
We need to remove all the factors that cannot yield 125 (125 = 5^{3})
Sum of factors which are divisible by 125 = (2^{0}+ 2^{1}+ 2^{2}+ 2^{3}) (5^{3}) = 1875
Number of factors which are divisible by 125 = 4 * 1 = 4The sum and number of divisors which are divisible by 100
100 = 2^{2 }* 5^{2 }
We need to remove all factors that cannot yield a 2^{2 }from two’s bracket and also remove all factors that cannot yield a 5^{2 }from five’s bracket.
Sum of factors which are divisible by 100 = (2^{2}+ 2^{3}) (5^{2}+ 5^{3}) = 1800
Number of factors which are divisible by 125 = 2 * 2 = 4Co Primes
We will end this chapter with a very useful concept, co primes. A co prime is a number which has no common prime numbers in their standard form. 20 = 2^{2 }* 5 and 21 = 7 * 3, no common primes hence 20 and 21 are co primes. (Two consecutive integers will always be co prime)
The number of integers co prime to a positive integer n, within the range [1, n1], is given by Euler's phi function (phi)
If a number N = P_{1}^{a} * P_{2}^{b }* P_{3}^{c} then phi(N) = N ( 1  1/ P_{1}) ( 1  1/ P_{2}) ( 1  1/ P_{3})
Consider 6, 6 = 2 * 3
Phi (6) = 6 (1 – 1/2) (1 – 1/3) = 6 *1/2 * 2/3 = 2, means there are 2 numbers between 1 and 6 which are co prime to 6. (1 and 5). The numbers 1 and 1 are coprime to every integer, and they are the only integers to be co prime with 0.Take another example, 24; 24 = 2^{3} * 3
phi(24) = 24 ( 1 – 1/2) (1 – 1/3) = 24 * 1/2 * 2/3 = 8. There are 8 numbers between 1 and 24 which are co prime to 24. (1, 5, 7, 11, 13, 17, 19, 23)One more example, 36; 36 = 2^{2 }* 3^{2}
phi(36) = 36 ( 1 – 1/2) (1 – 1/3) = 36 * 1/2 * 2/3 = 12 . There are 12 numbers less than 36 and co prime to 36. (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35)If a and b are relatively prime, then
 2^{a} 1 and 2^{b} 1 are also relatively prime.
 There exist integers x and y such that ax + by = 1 (Bézout’s identity)
 Any powers a^{j} and b^{k} are also co prime.
Happy Learning :)