CAT Number Theory - Interesting question

This is an interesting question from Number Theory. Slightly unconventional, but interesting nevertheless.

Question

The sum of the factors of a number is 124. What is the number?

Correct Answer

Number could be 48 or 75

Explanatory Answer
This video gives the solution for this question. Given below the video is the explanation (in words)

Any number of the form p^aq^br^c will have (a+1) (b+1)(c+1) factors, where p, q, r are prime. (This is a very important idea)

For any number N of the form p^aq^br^c, the sum of the factors will be (1 + p¹ + p² + p³+ …+ p^a) (1 + q¹ + q² + q³+ …+ q^b) (1 + r¹ + r² + r³+ …+ r^c).

Sum of factors of number N is 124. 124 can be factorized as 2² * 31. It can be written as 4 * 31, or 2 * 62 or 1 * 124.

2 cannot be written as (1 + p¹ + p² …p^a) for any value of p.

4 can be written as (1 + 3)

So, we need to see if 31 can be written in that form.

The interesting bit here is that 31 can be written in two different ways

31 = (1 + 2¹ + 2²+ 2³ + 2⁴)

31 = ( 1 + 5 + 5²)

Or, the number N can be 3 * 2⁴ or 3 * 5². Or N can be 48 or 75.

CAT Number Theory - Final few questions

Have given below few more questions on Number Theory

1. A 4-digit number of the form aabb is a perfect square. What is the value of a-b?
2. LCM of three numbers is equal to 1080; HCF of the three numbers is equal to 2. How many such triplets are possible?
3. N leaves a remainder of 4 when divided by 33, what are the possible remainders when N is divided by 55?

Number theory questions - Factors II

Two more questions in Number Theory. These are also focused on finding the number of factors of a given number.  

Question 1

How many factors of the number 2^8 * 3^6 * 5^4 * 10^5 are multiples of 120?

Question 2 

Number N = 2^6 * 5^5 * 7^6 * 10^7; how many factors of N are even numbers?

Correct Answers

Question 1: 11 * 6 * 9 = 594

Question 2: 1183

Explanations

1. How many factors of the number 2^8 * 3^6 * 5^4 * 10^5 are multiples of 120?

The prime factorization of 2⁸ * 3⁶ * 5⁴ * 10⁵ is 2¹³ * 3⁶ * 5⁹

For any of these factors questions, start with the prime factorization. Remember that the formulae for number of factors, sum of factors, are all linked to prime factorization.

120 can be prime-factorized as 2³ * 3 * 5

All factors of 2¹³ * 3⁶ * 5⁹ that can be written as multiples of 120 will be of the form 2³ * 3 * 5 * K

2¹³ * 3⁶ * 5⁹ = 2³ * 3 * 5 * K => K = 2¹⁰ * 3⁵ * 5⁸

The number of factors of N that are multiples of 120 is identical to the number of factors of K.

Number of factors of K = (10+1) (5+1) * (8+1) = 11 * 6 * 9 = 594

Alternative approach

Any factor of 2¹³ * 3⁶ * 5⁹  will be of the form 2^p * 3^q * 5^r . When we are trying to find the number of factors without any constraints, we see that

p can take values 0, 1, 2, 3, ….13 – 14 values

q can take values 0, 1, 2, …6 – 7 values

r can take values 0, 1, 2, 3,….9 – 10 values

So, the total number of factors will be 14 * 7 * 10.

This is just a rehash of our formula (a+1) ( b + 1) ( c +1)

In this scenario we are looking for factors of 2¹³ * 3⁶ * 5⁹ that are multiples of 120. These will also have to be of the form 2^p * 3^q * 5^r. But as 120 is 2³ * 3 * 5, the set of values p, q, r can take are limited.

p can take values 3, ….13 – 11 values

q can take values 1, 2, …6 – 6 values

r can take values 1, 2, 3,….9 – 9 values

So, the total number of factors that are multiples of 120 will be 11 * 6 * 9 = 594.

2. Number N = 2^6 * 5^5 * 7^6 * 10^7; how many factors of N are even numbers?

The prime-factorization of 2⁶ * 5⁵ * 7⁶ * 10⁷ is 2¹³ * 5¹² * 7⁶

The total number of factors of N = 14*13*7

We need to find the total number of even factors. For this, let us find the total number of odd factors and then subtract this from the total number of factors. Any odd factor will have to be a combination of powers of only 5 and 7.

Total number of odd factors of 2¹³ * 5¹² * 7⁶ = (12+1) * (6 + 1) = 13 * 7

Total number of factors = (13+1) * (12+1) * (6 + 1)

Total number of even factors = 14 * 13 * 7 - 13 * 7

Number of even factors = 13 * 13 * 7 = 1183

Alternative approach

Any factor of 2¹³ * 5¹² * 7⁶  will be of the form 2^p * 5^q * 7^r .

Any even factor of 2¹³ * 5¹² * 7⁶ will also be of the same form, except that p cannot be zero in this case

p can take values 1, 2, 3, ….13 – 13 values

q can take values 0,1, 2, …12 – 13 values

r can take values 0, 1, 2, 3,….5 – 7 values

So, the total number of even factors be 13 * 13 * 7 = 1183

Number Theory - Factors Questions

Number Theory is one of the heavily tested topics in CAT and is probably best to practice a lot of questions in this topic.

This is a very interesting topic to prepare for and a fun topic if you go about it the right way. I have given two questions on Number Theory – on the topic of factors below.

Questions

1. A number N^2 has 15 factors. How many factors can N have?
2. If a three digit number ‘abc’ has 2 factors (where a, b, c are digits), how many factors does the 6-digit number ‘abcabc’ have?

Correct Answer

Question 1: 6 or 8 factors

Question 2: 16 factors

Explanatory Answer

Qn: A number N^2 has 15 factors. How many factors can N have?

Any number of the form p^aq^br^c will have (a+1) (b+1)(c+1) factors, where p, q, r are prime. (This is a very important idea)

N² has 15 factors.

Now, 15 can be written as 1 * 15 or 3 * 5.

If we take the underlying prime factorization of N2 to be p^aq^b, then it should have (a + 1) (b+1) factors. So, N can be of the form

p¹⁴ or p²q⁴

p¹⁴ will have (14+1) = 15 factors

p²q⁴ will have (2+1) * (4 +1) = 15 factors.

Importantly, these are the only two possible prime factorizations that can result in a number having 15 factors.

Qn: If a three digit number ‘abc’ has 2 factors (where a, b, c are digits), how many factors does the 6-digit number ‘abcabc’ have?

To start with ‘abcabc’ = ‘abc’ *1001 or abc * 7*11*13 (This is a critical idea to remember)

‘abc’ has only two factors. Or, ‘abc’ has to be prime. Only a prime number can have exactly two factors. (This is in fact the definition of a prime number)

So, ‘abcabc’ is a number like 101101 or 103103.

’abcabc’ can be broken as ‘abc’ * 7 * 11 * 13. Or, a p * 7 * 11 * 13 where p is a prime.

As we have already seen, any number of the form p^aq^br^c will have (a+1) (b+1)(c+1) factors, where p, q, r are prime.

So, p * 7 * 11 * 13 will have = (1+1)*(1+1)*(1+1)*(1+1) = 16 factors