Number System Practice Gym by Anubhav Sehgal (NMIMS, Mumbai)  Part 14

What is the HCF of [(11111… written 105 times), (11111… written 104 times)]?
Take a smaller example.
HCF (11111, 1111) = HCF (11111 – 1111, 1111) = HCF (10000, 1111)
by HCF (a, b) = HCF (a – b, b) where a > b.
HCF(10000, 1111) = HCF (1, 10000) = 1 by Euclidean Algorithm for a = b * q + r.You can check for other examples as well to reach the generalization that,
HCF [(11111… (n + 1) times), (11111… n times)] = 1.A natural number N is having a total of 21 composite factors. What is the minimum and maximum number of prime factors of N?
The factors of N will comprise of three types of factors
 1 is the factor of every number.
 Some prime factors, say x.
 Some composite factors = 21(given).
Total number of factors = 1 + x + 21.
Case 1 Let there be just 1 prime factor. Total factors = 23.
This can be generated by p^22 where p is a prime.
So minimum number of prime factors of N = 1.
We can also generalize here that it is possible to make any number of factors with the help of just one prime factor. Like we need a 100 factors we can get it from p^99 where p is a prime number.Case 2 Note here that x < = 4. If x = 5, then minimum number of total factors = (1 + 1) * (1 + 1) * (1 + 1) * (1 + 1) * (1 + 1) = 32
as any such N will be at least a * b * c * d * e form where a, b, c, d and e are distinct primes having unit power.
So, 1 + 5 + 21 = 27 is not possible.
Let’s check x = 4. Total factors = 1 + 4 + 21 = 26
26 factors using four primes. 26 = 2 * 13.
Minimum contribution of any distinct prime is a factor of 2 as p^1 will give a (1 + 1) = 2 multiplier into total number of factors. Thus we can have a maximum of only two primes here to get 26 factors where N = a * b^12.Moving ahead, let us check for x = 3.
Total factors = 1 + 3 + 21 = 25 = 5 * 5
This again by following similar logic can be obtained through two primes at max as N = a^4 * b^4.
Three primes are not possible as 5 * 5 cannot be further broken into factors > = 2.Checking for x = 2,
Total factors = 1 + 2 + 21 = 24 = 2 * 12 = 3 * 8 = 4 * 6
Numerous possibilities to obtain a total of 24 factors with two primes:N = a * b^11 OR a^2 * b^7 OR a^3 * b^5.
Hence maximum value of x = 2 while minimum already seen as 1.IMPORTANT: Total number of factors = 1 + Prime factors + Composite factors.
Find the smallest odd positive integer that has the same number of divisors as the number 360.
360 = 2^3 * 3^2 * 5
Number of divisors = 4 * 3 * 2 = 24.
24 = 8 * 3 = 6 * 4 = 6 * 2 * 2 = 4 * 3 * 2 = 2 * 2 * 2 * 3.Ideally we should start with the way that spreads it in maximum number of prime factors. However, this may not give the final result we need, and we will be required to check the number thus obtained for being the smallest one or not.
Taking the 2 * 2 * 2 * 3 case
N = p * q * r * s^2
To have the lowest possible value of N, we should take lowest possible values of p, q, r and s and assign higher powers to lowest possible prime.
Note here we need odd positive integer so we cannot take prime as 2.
Lowest possible four primes = 3, 5, 7, 11.
Lowest N = 5 * 7 * 11 * 3^2.
Now we could trade off by increasing power of lowest prime and eliminating the largest prime.Let’s look at three prime option.
4 * 3 * 2 => 3^3 * 5^2 * 7. So we have multiplied an addition 3 * 5 (= 15) and removed 11.
So not what we need to do.
You could check for 6 * 2 * 2 also but closer powers give smaller number as a general priniciple.So our lowest number will be 5 * 7 * 11 * 3^2 = 99 * 35 = 3500 – 35 = 3465 [Also note the calculation methods being employed].
If a is the smallest positive integer that is a multiple of 147 and has exactly 147 positive integral divisors, including 1 and itself, the value of a/147 is?
a is divisible by 147 = 3 * 7^2. So two of the primes in a’s factorization are 3, 7.
Also, a has 147 positive integral divisors.
147 = 3 * 7 * 7 => a = p^2 * q^6 * r^6 where p, q, r are distinct primes.
To make the value of a small, we assign r = 2, q = 3 and p = 7.
So, a = 7^2 * 3^6 * 2^6.
Therefore, a/147 = 2^6 * 3^5.How many factors of 1080 will be divisible by 10 but not divisible by 30?
1080 = 2^3 * 3^3 * 5
10 = 2 * 5
30 = 2 * 3 * 5For, the factor to be divisible by it must have 2 * 5 in it. So taking that out from 1080, we are left with: 2^2 * 3^3.
Now with 2 * 5 taken out, we must ensure that a 3 is not taken out else the factor will become divisible by 30.
So we can only take 3 factors namely 2^0, 2^1 and 2^2 out of the (2 + 1)(3 + 1) = 12 factors of this remaining number.
Answer: 3 factors = 2 * 5 * (2^0), 2 * 5 * (2^1), 2 * 5 * (2^2) = 10, 20, 40.How many natural numbers less than 200 will have 12 factors?
12 = 2 * 6 = 3 * 4 = 2 * 2 * 3
Case 1
2 * 6 => p * q^5
Take q = 2 and out values of other primes.
32 * 3, 32 * 5 only are less than 200: 2 values.
q = 3 alone takes above 200 so no need to check further.Case 2
3 * 4 => p^2 * q^3
q = 2 => 8 * 9 only.
q = 3 => 27 * 4 only.Case 3
2 * 2 * 3 => p * q * r^2
r = 2 => 4 * 3 * 5, 4 * 3 * 7, 4 * 3 * 11, 4 * 3 * 13, 4 * 5 * 7: 5 values.
r = 3 => 9 * 2 * 5, 9 * 2 * 7, 9 * 2 * 11: 3 values.
r = 5 => 25 * 2 * 3: 1 value.
None further.
Total: 2 + 1 + 1 + 5 + 3 + 1 = 13 values.How many three digit numbers will have a total of 3 factors?
Only squares of primes have exactly three factors namely 1, p, p^2 where p is a prime.
11^2 = 121
13^2 = 169
…
31^2 = 961
11, 13, 17, 19, 23, 29, 31: 7 numbersHow many natural numbers less than 100 have exactly 2 factors?
Only primes have two factors which is 1 and the number itself.
There are 25 primes in the range 199.
Hence the answer will be 25.
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}N = 2^8 * 3^10 * 5^8 * 7^2. How many factors of N are multiples of 360 but not a multiple of 540?
N = 2^8 * 3^10 * 5^8 * 7^2.
360 = 2^3 * 3^2 * 5
540 = 2^2 * 3^3 * 5Let us call 360 the Important (I) and 540 the Unimportant (UI).
In such questions, we look at each prime’s individual powers.
Deficiency: The primes that have power less in I as compared to UI must be restricted for the factor of N to be power of that prime in I to less than power of that prime in UI.
Surplus: While, the primes that have power more in I as compared to UI must have the power of that prime greater than power of that prime in UI but less than equal to the power of that prime in N.So, here prime 3 has a deficiency case and prime 2 has a surplus case for 360.
So any factor of N that is a multiple of 360 but not a multiple of 540 must be of the form:
2^w * 3^x * 5^y * 7^z where w = 3 to 8, x = 2, y = 1 to 8 and z = 0 to 2.
So number of such factors = (8 – 3 + 1) * (1) * (8 – 1 + 1) * (2 – 0 + 1) = 6 * 1 * 8 * 3 = 144N = 2^8 * 3^10 * 5^8 * 7^2. How many factors of N are factor of 360 but not a factor of 540?
Looking in the similar way,
w = 3, x = 0 to 2, y = 0 to 1, z = 0
1 * 3 * 2 * 1 = 6 such factors.
Note here the idea would be to keep power of each prime greater than UI and equal to I for surplus case while less than equal to I in case of deficiency. Also, a prime not present in I but present in UI or N would not be considered as it’s a case of being a factor.Shorter approach for above 2 questions:
360 = 2^3 3^2 5 and 540 = 2^2 3^3 5.
So their LCM = 2^3 3^3 5 and HCF = 2^2 3^2 5.
(i) Required number factors is = number of factors of 360  number of factors of both 360 and 540 (i.e. their HCF) = 4 * 3 * 2  3 * 3 * 2 = 6.
(ii) Required number of factors = factors of N which are multiple of 360  factors of N which are multiples of both 360 and 540 (i.e. LCM) = 6 * 9 * 8 * 3  6 * 8 * 8 * 3 = 144.