Divisibility & Factors

In this post i will discuss the following problems-

Number of Factors

Number of Even factors and Odd factors

Sum of all Factors

Sum of all Even or Odd Factors

Number of factors

Let us say we are given a number N. If we write N in form of a product of prime numbers, it would look like the following-

\(N = a^p*b^q*c^r\)

a,b,c are my prime numbers and p,q,r are their respective powers. Then the number of factors are

Number of Factors = (p+1)(q+1)(r+1)


Example
Say \(N = 2^5*3^4*5^2\)

Then the total number of factors = (5+1)(4+1)(2+1)= 90

The way it is worked out is pure Permutation & Combination principle in action.

a) There are five 2's. So there are 6 ways of selecting. We can select one 2 or two 2's or three 2's.... five 2's. And we can also select none. So thats why 6 ways selection.

b) Similarly for four 3's there are 5 ways of selection.

c) Similarly for two 5's there are 3 ways of selection.

Total ways of selection = Total Number of factors

Number of Even or Odd factors

We can use the similar selection principle described above.We will take the same example to find out the number of even factors.

If it has to be an even factor it must have at least one 2 as a factor. So using the same logic now we can only select 2's in 5 ways. The selection of 3's & 5's remain the same i.e 5 & 3.

Number of Even factors = 5*5*3 = 75.

Similarly we can find the odd factors in the same way. We cannot select any 2's. So only 1 way to select 2's, five ways of selecting 3's & three ways of selecting 5.

Number of Odd factors= 1*5*3 = 15.

Sum of all factors

If we take the number N.
\(N = a^p*b^q*c^r\)

Sum of all factors = \((1+a+a^2+a^3......+a^p)(1+b+b^2+b^3......+b^q)(1+c+c^2+c^3+....+c^r)\)
Example
Say \(N = 2^5*3^4*5^2\)

Sum of all factors = \((1+2+2^2+2^3+2^4+2^5)(1+3+3^2+3^3+3^4)(1+5+5^2)\)

Sum of all Even Factors = \((2+2^2+2^3+2^4+2^5)(1+3+3^2+3^3+3^4)(1+5+5^2)\)

Sum of all Odd Factors = \((1)(1+3+3^2+3^3+3^4)(1+5+5^2)\)

In sum of all even numbers I must have at least one 2 otherwise some of the factors will be odd. Thats why we neglected the 1 term in \((1+2+2^2+2^3+2^4+2^5)\).
For sum of odd factors we cannot have even a single 2. So we deleted the total array of powers of 2. And we are left with \((1)(1+3+3^2+3^3+3^4)(1+5+5^2)\).

Takeway

The techniques discussed above are nothing new or standalone. They are derived from basic principles of Permutation Combination, which I will discuss later. Always remember one thing, you have your basics right, you will have a field-day in GRE Math section.