Factors and its applications  Anubhav Sehgal, NMIMS Mumbai

Key note 1
N = a^p * b^q * c^r * ... where a,b,c,.. are DISTINCT PRIMES. then,
 Total number of factors(f) = (p + 1)(q + 1)(r + 1)..
Also, if N = 2^p * b^q * c^r * ... form then,
 Number of even factors = p*(q + 1)(r + 1)...
 Number of odd factors = (q + 1)(r + 1).. i.e. ignore the power of 2 and calculate for the rest.
example : N = 20 20 = 2^2 * 5^1
Total number of factors = (2 + 1)(1 + 1) = 6
Even factors = 2*(1 + 1) = 4
Odd factors = (1 + 1) = 2 = Total – EvenPractice Question : Find the number of odd, even and total factors for :
i) N = 360
ii) N = 105
Answer :
i) Total : 24 , Even : 18 , Odd = 6 ;
ii) Total : 8, Even : 0 , Odd : 8Key note 2
N = a^p * b^q * c^r * ... where a,b,c are DISTINCT PRIMES then,
 Sum of all the factors = {[a^(p + 1)  1][b^(q + 1)  1]...}/(a  1)(b  1)..
This can also be written as: (1 + a + a^2 + .. + a^p)(1 + b + b^2 + ..b^q)..
NOTE : Sum of powers of prime starting from 1
2^0 + 2^1 + 2^2 + 2^3 = (2^4  1)/(2  1) = 15
3^0 + 3^1 + 3^2 = (3^3  1)/(3  1) = 13
Example : N = 10 = 2^1 * 5^1
Sum of all the factors = [2^(1 + 1)  1][5^(1 + 1)  1] / [(2  1)(5  1) = (4  1)(25  1)/(1)(4) = 18
Factors of 10 = {1,2,5,10} = Sum = 18 = Verified.The second form of the sum of factors of N is a product of sum of power of primes from 0 to n that occur in its prime factorization.
Hence if sum = S is given. We try to write it as product of sums of powers of primes and match it with standard form to find the N.
Now For a particular N, S = constant.
But for a particular S, N may or may not be unique or may not even exist.
For this you need practice and acquaintance with
1 + 2 + 4 = 7 = 2^3  1
1 + 5 + 25 = 31
1 + 7 = 8 while 1 + 7 + 49 = 57
You need to work with them multiples times and their product combinations to be familiar with this.example: If sum of all factors of N is 18. 18 = 3*6 = (2^0 + 2^1)(5^0 + 5^1)
=> N = 2^1 * 5^1 = 10.
No other factorization of 18 would give such a form so N = 10 only.Practice Question:
i) Find sum of all factors of 120
ii) If sum of all the factors of N is 31. Find N.
Answer :
(i) 120 = 2^3 * 3 * 5
Sum of factors = (16  1)(9  1)(25  1)/(2  1)(3  1)(5  1) = 360
(ii) Sum of factors = 31 = (2^0 + 2^1 + 2^2 + 2^3 + 2^4) OR (5^0 + 5^1 + 5^2) Hence N = 2^4 or 5^2 = 16 or 25Key note 3
N = a^p * b^q * c^r * ... where a, b, c are DISTINCT PRIMES then,
i) Number of factors of N that are perfect squares ( [p/2] + 1)( [q/2] + 1)( [r/2] + 1)... where [.] is Greatest Integer Function which gives the greatest integer less than or equal to value inside it. [2.5] = 2 ; [integer] = integer itself ; [2.5] = 3
ii) Number of factors of N that are perfect cubes ( [p/3] + 1)( [q/3] + 1)( [r/3] + 1) ...The Logic behind the formula : For perfect squares we have 2^0,2^1,...,2^10 available(similarly for other powers) and to keep a factor perfect square we can use : 2^0 or 2^2 or 2^4 .. or 2^10 which is basically 0 to 10 in steps of 2 So [10/2] + 1 = 6 = { 0,2,4,6,8,10 } Similarly for perfect cubes.
Example : N = 2^2 * 3^3 * 4^4 * 5^5
N = 2^10 * 3^3 * 5^5
Factors that are perfect square = ( [10/2] + 1)( [3/2] + 1)( [5/2] + 1)
= ( 5 + 1 )( 1 + 1) ( 2 + 1)
= 6 * 2 * 3 = 36
Factors that are perfect cube = ( [10/3] + 1)( [3/3] + 1)( [5/3] + 1)
= (3 + 1)( 1 + 1)( 1 + 1)
= 4 * 2 * 2 = 16Key note 4
i) Number of ways in which N can we written as a sum of consecutive natural numbers is equal to (No of odd factors  1)
Logic : Let the k consecutive numbers be a, a+1, a+2,..
N = Sum = k/2 * [a + a + (k  1)]
= k/2 * [ 2a + (k  1)
= k * [ a + (k  1)/2 ]
So k is a factor of N and (k  1) must be even for N to be an integer => k must be odd => k must be an ODD factor of N But if k = 1 then we can't call it sum of "consecutive" So No of odd factors of N  1ii) Number of ways in which N can we written as a sum of consecutive INTEGERS = 2 * (Number of odd factors)  1
Example: Find the number of ways 105 can be written as sum of consecutive i) Natural numbers ii) Integers.
105 = 3 * 5 * 7
Number of odd factors = 2 * 2 * 2 = 8 so, answer for part i) = 8  1 = 7 and part ii) 2 * 8  1 = 15Let’s look at the logic behind this
Take one of the odd factors ,say, 5 Now, 5 * 21 = 105
So what we do is we take one number as 21 and split remaining 4 on either side of 21 as 19, 20 , [21] , 22 , 23 And these form the sum = 105 and stay consecutiveKey note 5
i) Product of all factors of N is given by : N^(f/2) where f is the number of factors of N
example : N = 10 Factors = 1, 2, 5, 10
So these factors form N in pairs from extreme ends : 1 * 10 = 10 ; 2 * 5 = 10
So product of all factors = 1 * 2 * 5 * 10 = (1 * 10) * (2 * 5) = 10^2 = 10^(4/2)
Always like this.ii) Sum of all numbers less than N and co prime to it is given by: N * E(N)/2 where E(N) is the Euler number.
example : N = 2^2 * 3^3 * 5^5
E(N) = N*(1  1/a)(1  1/b)(1  1/c)... where a, b, c are the DISTINCT primes in prime factorization of N
So in our case E(N) = 2^2 * 3^3 * 5^5 * (1  1/2)(1  1/3)(1  1/5)
= 2^2 * 3^3 * 5^5 * 1/2 * 2/3 * 4/5
= 2^4 * 3^2 * 5^4
= 16 * 9 * 625 = whatever it is.
So sum of all numbers less than N and co prime to N = N * E(N)/2
Substitute the values.Key note 6
i) Perfect squares have odd number of factors.
N = perfect square = a^even * b^even * c^even... where a, b, c are distinct primes
Number of factors = (even + 1) * (even + 1) * (even + 1) ... = odd * odd * odd = odd
Only squares of prime have exactly 3 factors.[Because they are just a^2 form where a is the prime]ii) Factors of N^2 less than N but not a factor of N is given as : (Factors of N^2  1)/2  (Factors of N) + 1
One of the factors of N^2 is N. By extension all factors of N are factors of N^2 too.
We need those factors of N^2 that are less than N yet not a factor of N
By symmetry half of the factors of N^2 shall lie below and half above N about the vertex point N itself. So first part is that division to reach below N part. Then second part removes Factors of N from it.When in first part we divide about N and subtract factors of N we subtract N once[Factors of N includes N itself as well] which was already not counted. Hence +1 for that in the end.example : Find the number of factors of 144 that are less than 12 but not a factor of N
12 = 2^2 * 3 => f(12) = 3 * 2 = 6
144= 2^4 * 3^2 => f(144) = 5 * 3 = 15 (15  1)/2  6 + 1 = 2Ordered and Unordered Sets, in simple words, can be seen as follows :
Ordered sets : If for a given situation, a set of n elements satisfies the problem solution then all permutations of those n elements that satisfy the problem solution are to be counted as different i.e. a, b is treated different than b, a ; a, b, c is counted different from a, c, b or b, a, c or b, c, a or c, a, b or c, b, a If all these permutations satisfy our question statement and each element is to be considered uniquely then we take the ordered sets while when they need not be uniquely identified for our problem then we take unordered sets.
Unordered sets : If for a given situation, a set of n elements satisfies the problem solution then any permutation of that set satisfying the problem solution should be considered as the same and not counted again.
a, b is same as b, a and a, b, c is same as other (3!  1) = 5 permutations.example: Saying product of three numbers is N. Find the number of ways is finding unordered sets while saying a * b * c = N. Find the number of ways is indicative of ordered sets. Otherwise you go by what is explicitly asked from you.
Key note 7
Number N as a product of its two factors.
f : Total number of factors of N.
N = a * bN is a perfect square :
If N is a perfect square it contains one solution as N = a * a = a^2 and rest are (a, b) distinct format.
Hence, Ordered(distinct) = (f  1)
Ordered(not necessarily distinct) = f
Unordered(distinct) = (f  1)/2
Unordered(not necessarily distinct) = (f  1)/2 + 1 OR (f + 1)/2N is not a perfect square
Ordered(any case) = f
Unordered(any case) = f/2Example : N = 100 = 2^2 * 5^2
f = 3 * 3 = 9
100 = a * b
Then if a is some factor of 100, then b = 100/(that factor) and vice versa. Hence we have as many (a, b) sets satisfying the equation as are the number of factors of N.
But since N = 100 = perfect square hence it has one solution: 10, 10 counted twice. 1 * 100, 100 * 1, 2 * 50, 50 * 2, ... 10(first) * 10(second), 10(second) * 10(first) So,
Ordered(distinct) = f  1 = 8
Ordered(not necessarily distinct) = f = 9
Unordered(distinct) = (f  1)/2 = 4
Unordered(not necessarily distinct) = (f  1)/2 + 1 OR (f + 1)/2 = 5Key note 8
Number of ways to resolve N into product of two coprimes = 2^(n  1) where n is the number of distinct primes in the prime factorization of N.example : N = 12 = 2^2 * 3 Then, answer = 2^(2  1) = 2 ; As there are two primes : 2 and 3 in factorization of N
We can see that as : 1 * 12 : Coprime
2 * 6 : HCF(2,6) = 2
3 * 4 : Coprime
2 sets.Key note 9
Number of ways to resolve N into product of three co primes.
Example: N = 2^3 * 3^2 * 5^4
N = abc such that HCF (a, b, c) = 1 i.e. they are coprime.
a = 2^x1 * 3^y1 * 5^z1
b = 2^x2 * 3^y2 * 5^z2
c = 2^x3 * 3^y3 * 5^z3x1 + y1 + z1 = 3 => 5C2 ways. Out of this when none of them is zero needs to be removed as in that case HCF would not be 1.
So, 5C2  1 = 9 ways
Similarly, x2 + y2 + z2 = 2 => 4C2 = 6 ways. With none of them zero the equation cannot hold for nonnegative integers. Hence nothing is to be subtracted.
Also, x3 + y3 + z3 = 4 => 6C2  3 = 12 waysOrdered = 9 * 6 * 12 = 648
Unordered = (648  3!/2! * 4)/3! + 4 = 110
[1,1,n ; 3,3,x ; 25,25,y ; 75,75,z ] being the 4 triplets to be removed for unordering]