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 28 * 36 * 54 * 10is 213 * 36 * 59

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 23 * 3 * 5

All factors of 213 * 36 * 5that can be written as multiples of 120 will be of the form 23 * 3 * 5 * K

213 * 36 * 5= 23 * 3 * 5 * K => K = 210 * 35 * 58

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 213 * 36 * 5will be of the form 2p * 3q * 5r . 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 213 * 36 * 59 that are multiples of 120. These will also have to be of the form 2p * 3q * 5r. But as 120 is 23 * 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 26 * 55 * 76 * 10is 213 * 512 * 76

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 213 * 512 * 76 = (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 213 * 512 * 7will be of the form 2p * 5q * 7r .
Any even factor of 213 * 512 * 76 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

Labels: , , ,

IIM CAT Preparation Tips: Number theory questions - Factors II

Nov 2, 2010

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 28 * 36 * 54 * 10is 213 * 36 * 59

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 23 * 3 * 5

All factors of 213 * 36 * 5that can be written as multiples of 120 will be of the form 23 * 3 * 5 * K

213 * 36 * 5= 23 * 3 * 5 * K => K = 210 * 35 * 58

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 213 * 36 * 5will be of the form 2p * 3q * 5r . 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 213 * 36 * 59 that are multiples of 120. These will also have to be of the form 2p * 3q * 5r. But as 120 is 23 * 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 26 * 55 * 76 * 10is 213 * 512 * 76

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 213 * 512 * 76 = (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 213 * 512 * 7will be of the form 2p * 5q * 7r .
Any even factor of 213 * 512 * 76 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

Labels: , , ,

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home