Number System: Factors and Coprimes

Number system is a very important chapter and you can find good number of questions in various competitive exams.  Important formulas are the following.
A number can be written in its prime factorization format.  For example 100 = 22 x 52

Formula 1: The number of factors of a number

(p+1).(q+1).(r+1)... where N = ap x bq x cr ...

Example: Find the number of factors of 100.
Ans: We know that 100 = 22 x 52
So number of factors of 100 = (2 +1 ).(2 +1) =  9.
Infact the factors are 1, 2, 4, 5, 10, 20, 25, 50, 100

Formula 2: The sum of factors of a number

$\displaystyle\frac{{{{\rm{a}}^{{\rm{p + 1}}}}{\rm{ - 1}}}}{{{\rm{a - 1}}}}{\rm{ \times }}\frac{{{{\rm{b}}^{{\rm{q + 1}}}}{\rm{ - 1}}}}{{{\rm{b - 1}}}}{\rm{ \times }}\frac{{{{\rm{c}}^{{\rm{r + 1}}}}{\rm{ - 1}}}}{{{\rm{c - 1}}}}...$ where $N = {a^p} \times {b^q} \times {c^r} \times ...$

Example: Find the sum of the factors of 72
Ans: 72 can be written as $({2^3} \times {3^2}).$
Sum of all the factors of 72 = $(\displaystyle\frac{{{2^{{\rm{3 + 1}}}}{\rm{ - 1}}}}{{{\rm{2 - 1}}}} \times \displaystyle\frac{{{3^{{\rm{2 + 1}}}}{\rm{ - 1}}}}{{{\rm{3 - 1}}}})$= 15 x 13= 195

Formula 3: The number of ways of writing a number as a product of two number

$\displaystyle\frac{{\rm{1}}}{{\rm{2}}}{\rm{ \times }}\left[ {{\rm{(p + 1)}}{\rm{.(q + 1)}}{\rm{.(r + 1)}}...} \right]$ (if the number is not a perfect square)
If the number is a perfect square then two conditions arise:
1.  The number of ways of writing a number as a product of two distinct numbers = $\displaystyle\frac{{\rm{1}}}{{\rm{2}}}{\rm{ \times }}\left[ {{\rm{(p + 1)}}{\rm{.(q + 1)}}{\rm{.(r + 1)}}...{\rm{ - 1}}} \right]$
2.  The number of ways of writing a number as a product of two numbers and those numbers need not be distinct= $\displaystyle\frac{{\rm{1}}}{{\rm{2}}}{\rm{ \times }}\left[ {{\rm{(p + 1)}}{\rm{.(q + 1)}}{\rm{.(r + 1)}}...{\rm{ + 1}}} \right]$

Example: Find the number of ways of writing 140 as a product of two factors
Ans: The prime factorization of 140 = ${2^2} \times 5 \times 7$
So number of ways of writing 140 as a product of two factors = $\displaystyle\frac{{\rm{1}}}{{\rm{2}}}{\rm{ \times }}\left[ {{\rm{(p + 1)}}{\rm{.(q + 1)}}{\rm{.(r + 1)}}...} \right]$  = $\displaystyle\frac{{\rm{1}}}{{\rm{2}}} \times \left[ {(2{\rm{ + 1}}).(1{\rm{ + 1}}).(1{\rm{ + 1}}).} \right] = 6$

Example: Find the number of ways of writing 144 as a product of two factors subjected to the following conditions a. Both factors should be different b. Both factors need not be different.

Ans: The prime factorization of 144 = ${2^4} \times {3^2}$
a. If both factors are different, then total ways = $\displaystyle\frac{{\rm{1}}}{{\rm{2}}}{\rm{ \times }}\left[ {{\rm{(p + 1)}}{\rm{.(q + 1)}}{\rm{.(r + 1)}}...{\rm{ - 1}}} \right]$ = $\displaystyle\frac{{\rm{1}}}{{\rm{2}}} \times \left[ {(4{\rm{ + 1}}).(2{\rm{ + 1}}){\rm{ - 1}}} \right]$ = 7

If both factors need not be different, then total ways = $\displaystyle\frac{{\rm{1}}}{{\rm{2}}}{\rm{ \times }}\left[ {{\rm{(p + 1)}}{\rm{.(q + 1)}}{\rm{.(r + 1)}}...{\rm{ + 1}}} \right]$ = $\displaystyle\frac{{\rm{1}}}{{\rm{2}}} \times \left[ {(4{\rm{ + 1}}).(2{\rm{ + 1}}){\rm{ + 1}}} \right]$ = 8

Formula 4: The number of co-primes of a number

N=$\phi (N) = {a^p}.{b^q}.{c^r}...$ can be written as $N \times \left( {1 - \dfrac{1}{a}} \right) \times \left( {1 - \dfrac{1}{b}} \right) \times \left( {1 - \dfrac{1}{c}} \right)...$

Example: Find the number of co-primes to 144 which are less than that of it
Ans: The prime factorization of 144 = ${2^4} \times {3^2}$
The number of co-primes which are less than that of 144 = $144 \times \left( {1 - \displaystyle\frac{1}{2}} \right) \times \left( {1 - \displaystyle\frac{1}{3}} \right)$ = 48

Formula 5: The sum of co-primes of a number

N= $\phi (N) \times \displaystyle\frac{N}{2}$

Example: Find the sum of all the co-primes of 144
Ans: The sum of co-primes of the 144 = $\phi (N) \times \displaystyle\frac{N}{2}$ = 48 x $\displaystyle\frac{{144}}{2}$ = 3456

Formula 6: The number of ways of writing a number N as a product of two co-prime numbers

= ${2^{n - 1}}$ where n=the number of prime factors of a number.

Example: Find the number of ways of writing 60 as a product of two co - primes

Ans: The prime factorization of 60 = ${2^2} \times 3 \times 5$
The number of ways of writing 60 as a product of two co - primes = ${2^{3 - 1}}$ = 4

Formula 7: Product of all the factors

${N^{\left( {\displaystyle\frac{\text{Number of factors}}{2}} \right)}}$ = ${N^{\left( {\displaystyle\frac{{(p + 1).(q + 1).(r + 1)....}}{2}} \right)}}$

Example: Find the product of all the factors of 50

Ans: Prime factorization of 50 = $2 \times {5^2}$
Product of all the factors of 50 = ${50^{\displaystyle\frac{{(1 + 1).(2 + 1)}}{2}}} = {50^3}$

Level - 2

1. P is the product of all the factors of 15552.  If P = ${12^N} \times M$, where M is not a multiple of 12, then find the value of M.  [M and N are positive Integers]
Ans: 15552 = ${2^6} \times {3^5}$
Product of all the factors of 15552 = ${\left( {{2^6} \times {3^5}} \right)^{\displaystyle\frac{{(6 + 1).(5 + 1)}}{2}}} = {2^{126}} \times {3^{105}}$
$\Rightarrow$${\left( {{2^2}} \right)^{63}} \times {3^{63}} \times {3^{42}}$ = ${12^{63}} \times {3^{42}}$
So M = ${3^{42}}$

2. Let M be the set of all the distinct factors of the number N=${6^5} \times {5^2} \times 10$,Which are perfect squares.  Find the product of the elements contained in the set M.

N = ${6^5} \times {5^2} \times 10$ = ${2^6} \times {3^5} \times {5^3}$
Even powers of 2 available: ${2^0},{2^2},{2^4},{2^6}$
Even powers of 3 available: ${3^0},{3^2},{3^4}$
Even powers of 5 available: ${5^0},{5^2}$
Therefore number of factors of the number N that are perfect squares = 4 x 3 x 2 = 24
Product of the elements contained in M
= ${2^{\left( {2 + 4 + 6} \right) \times 6}} \times {3^{\left( {2 + 4} \right) \times 8}} \times {5^{2 \times 12}} = {2^{72}} \times {3^{48}} \times {5^{24}}$

3. In a hostel there are 1000 students in 1000 rooms.  One day the hostel warden asked the student living in room 1 to close all the doors of the 1000 rooms.  Then he asked the person living in room 2 to go to the rooms which are multiples of his room number 2 and open them.  After he ordered the 3rd student to reverse the condition of the doors which are multiples of his room number 3.  If He ordered all the 1000 students like the same, Finally how many doors of those 1000 rooms are in open condition?

We understand that a door is in open or in close condition depends on how many people visited the room.
If a door is visited by odd number of persons it is in close condition, and is visited by even number of persons it is in open condition.
The number of people who visit a certain door is the number of factors of that number.  Let us say room no: 24 is visited by 1, 2, 3, 4, 6, 8, 12, 24 which are all factors of 24. Since the number of factors are even this door is in open condition.
we know that the factors of a number N=${a^p}.{b^q}.{c^r}...$ are (p+1).(q+1).(r+1)...
From the above formula the product is even if any of p, q, r... are odd, but the product is odd when all of p, q, r are even numbers.
If p, q, r ... are all even numbers then N=${a^p}.{b^q}.{c^r}...$ is a perfect square.
So for all the perfect squares below 1000 the doors are in closed condition.
There are 31 perfect squares below 1000 so total doors which are in open condition are (1000-31)= 969

4.  What is the product of all factors of the number N = ${6^4} \times {10^2}$ which are divisible by 5?
Sol: N = ${6^4} \times {10^2}$ = ${2^6} \times {3^4} \times {5^2}$
Total product of the factors = ${\left( {{2^6} \times {3^4} \times {5^2}} \right)^{\displaystyle\frac{{\left( {6 + 1} \right).\left( {4 + 1} \right).\left( {2 + 1} \right)}}{2}}}$ = ${\left( {{2^6} \times {3^4} \times {5^2}} \right)^{\displaystyle\frac{{105}}{2}}}$
So total product of the factors N which are not multiples of 5 =
${\left( {{2^6} \times {3^4}} \right)^{\displaystyle\frac{{\left( {6 + 1} \right).\left( {4 + 1} \right)}}{2}}}$ = ${\left( {{2^6} \times {3^4}} \right)^{\displaystyle\frac{{35}}{2}}}$
So, total product of the factors of N which are multiples of 5 = $\displaystyle\frac{{{{\left( {{2^6} \times {3^4} \times {5^2}} \right)}^{\displaystyle\frac{{105}}{2}}}}}{{{{\left( {{2^6} \times {3^4}} \right)}^{\displaystyle\frac{{35}}{2}}}}}$ = ${2^{210}} \times {3^{140}} \times {5^{105}}$

5.  Let N = ${2^3} \times {3^{17}} \times {5^6} \times {7^4}$ and M = ${2^{12}} \times {3^5} \times {5^4} \times {7^8}$.  P is total number of even factors of N such that they are not factors of M.  Q is the total number of even factors of M such that they are not factors of N.  Then 2P -Q = ?

Sol:
N = ${2^3} \times {3^{17}} \times {5^6} \times {7^4}$
M = ${2^{12}} \times {3^5} \times {5^4} \times {7^8}$
Calculation of P:
Number of powers of 2 available are 3. i.e., ${2^1}$ to ${2^3}$(all these powers are even)
Since P is the total number of even factors of N such that they are not factors of M, the number of powers of 3 available are 17 - 5 = 12
For combination with each of these 12 powers of 3( i.e., ${3^6}$ to ${3^{17}}$ , number of powers of 5 are 7 ( i.e., ${5^0}$ to ${5^6}$)  and number of powers of 7 are 5 ( i.e.,${7^0}$ to ${7^4}$) available respectively.
Therefore there are 3 x 12 x 7 x 5 = 1260 factors

Now consider powers of 5 that are in N but not in M: ${5^5},{5^6}$

So, for these two powers of 5, the number of powers of 2, 3, and 7 that are available are 3, 6, and 5 respectively.  (Powers of 3 are only 6 (${3^0}$ to ${3^5}$), not 18 as we have already used ${3^6}$ to ${3^{17}}$ in caclulating P)
Therefore, there are 2 x 3 x 6 x 5 = 180 factors
P = 1260 + 180 = 1440
Calculation of Q:
Consider powers of 2 that are in M but not in N: ${2^4},{2^5},{2^6}{.....2^{12}}$
So for these 9 powers of 2, number of even factors of M such that they are not factors of N = 9 x 6 x 5 x 9 = 2430
Consider powers of 7 that are in M but not in N: ${7^5},{7^6},{7^7}$ and ${7^8}$
So for these 4 powers of 7, number of powers of 2, 3, and 5 that are available are 3, 6 and 5.
(Powers of 3 are only 6 (${3^0}$ to ${3^5}$), not 18 as we have already used ${3^6}$ to ${3^{17}}$ in calculating Q and (Powers of 5 are only 5 (${5^0}$ to ${5^4}$), not 7 as we have already used ${5^5}$ to ${5^6}$ in calculating Q))
So number of such factors = 4 x 3 x 6 x 5 = 360
Q = 2430 + 360 = 2790
Therefore, 2P - Q = 2880 - 2790 = 90

Alternative Method:
Many a student asked me to explain this question elaborately.  I think if we use sets this question is easily done.
N = ${2^3} \times {3^{17}} \times {5^6} \times {7^4}$
M = ${2^{12}} \times {3^5} \times {5^4} \times {7^8}$

So by the above diagram, we can see that P is the number of even factors of N which are not factors of M and Q is number of even factors of M which are not factors of N.
Now to calculate common even factors of N and M, we take HCF of N and M which is ${2^3} \times {3^{5}} \times {5^4} \times {7^4}$ ($\because$ take minimum powers of both numbers).
Even factors of above number = 3 × (5 + 1) × (4 + 1) × (4 + 1) = 450 ( $\because$ We have to include atleast one multiple of 2 to make it even number.
Even factors of P = 3 × 18 × 7 × 5 = 1890
Even factors of Q = 12 × 6 × 5 × 9 = 3240
So 2P - Q = 90