N is an integer which has 201400 positive divisors. What is the most number of (distinct) primes which are a divisor of N ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Can you explain your argument in more details? Why does N have at most 7 distinct prime factors? Also, how do you know that 7 is the maximum and not just an upper bound?
Log in to reply
Sure. A number k = p 1 a 1 p 2 a 2 … p n a n has, of course, ∏ i = 1 n ( a i + 1 ) divisors. Hence, if a number has 201400 divisors, its factors are in one of the following forms:
1) p 1 7 p 2 2 4 p 3 1 8 p 4 5 2
2) p 1 1 p 2 3 p 3 2 4 p 4 1 8 p 5 5 2
3) p 1 1 p 2 3 p 3 4 p 4 4 p 5 1 8 p 6 5 2
4) p 1 1 p 2 1 p 3 1 p 4 2 4 p 5 1 8 p 6 5 2
5) p 1 1 p 2 1 p 3 1 p 4 4 p 5 4 p 6 1 8 p 7 5 2
Note that these are the only expressions in which ∏ i = 1 n ( a i + 1 ) = 2 0 4 1 0 0 , and so the maximum number of prime factors of N is 7 . In general, if a number has p 1 a 1 p 2 a 2 … p n a n divisors, it has at most ∑ i = 1 n a i prime factors (check this for yourself).
Log in to reply
Thanks! There certainly are more cases than those that you listed, for example N = p 1 2 0 1 3 9 9 . Fortunately, one does not have to list them all. Perhaps, the easiest way to rigorously prove this is by contradiction.
Suppose N has at least 8 prime factors, then (by the formula for the number of divisors that you quoted) 2 0 1 4 0 0 is a product of at least 8 factors, all greater than 1 . This implies that the total sum of the powers of all primes in the prime decomposition of 2 0 1 4 0 0 is at least 8 (at least one for each factor). But it is 3 + 2 + 1 + 1 = 7 . This contradiction means that our assumption was false, so N can have no more than 7 prime factors.
One still has to show that 7 can be achieved, which is easy to do by an explicit example.
Let N = p1^a1 p2^a2 .....*pn^an (p1,p2...,pn are distinct prime numbers and a1,a2... are natural numbers may or may not be equal.) Then 201400 = (a1+1)(a2+1).....(an+1)= 2×19×53×2×2×5×5 As on L.H.S. there are 7 factors; 7 is the answer. Note : a1,...,an are just powers not the primes so we can distribute those powers to atmost 7 distinct primes
In this question you need to find the # of distinct prime factors. Lets work backwards. The number of factors is found by (a+1)(b+1)(c+1)....where 2 a x 3 b x 5 c ... So all we need to do is factorize 201400 and find the number of prime factors.
When you factorize 201400, you get 2 3 x 5 2 x 1 9 x 5 3 . That means there are 7 (not distinct) prime factors of 201400 so there are 7 distinct prime factors of that number.
Note that 2 0 1 4 0 0 = 2 3 ⋅ 5 2 ⋅ 1 9 ⋅ 5 3 . Since the number of divisors of an integer is the product of one more than each of the exponents in the prime factorization of the integer, there will be at most 7 distinct prime divisors of N .
Assume that the prime factorisation of N is p 1 b 1 p 2 b 2 p 3 b 3 p 4 b 4 . . . p k b k , where p 1 , p 2 , . . . , p k are unique primes and b 1 , b 2 , . . . , b k are positive integers. Then the number of factors of N can be written as:
( b 1 + 1 ) ( b 2 + 1 ) ( b 3 + 1 ) . . . ( b k + 1 ) = 2 0 1 4 0 0 = 1 9 1 × 5 3 1 × 2 3 × 5 2
Adding up the exponents of each prime factor of 2 0 1 4 0 0 gives us the maximum number of distinct primes that divide N which is: 1 + 1 + 3 + 2 = 7 .
If a number is divisible by a prime number, it means the prime number is in the prime decomposition of that number. Let the biggest number of primes that divide N be D .
⇒ N = x 1 a 1 × x 2 a 2 … × x D a D .
Then, remembering the tau formula for number of divisors: t ( N ) = ( a 1 + 1 ) × ( a 2 + 1 ) … ( a D + 1 ) = 2 0 1 4 0 0 = 2 × 2 × 2 × 5 × 5 × 1 9 × 5 3
Now, we see that we want D to be the biggest possible value. Therefore, we want the most amount of parenthesis possible.
Then, looking at the prime decomposition of 2 0 1 4 0 0 , we clearly see that the most amount of parenthesis possible is seven parenthesis (remember a i > 1 for i = 1 , 2 , … , D ).
Therefore, the biggest possible value for D is 7 , so the most number of distinct primes which are divisors of N are 7 .
I'll try to express this:
If a number is factorized in the form p 1 a ⋅ p 2 b ⋅ … ⋅ p n k , for some k and n (integers), then it's quantity of divisors is equal to ( a + 1 ) ( b + 1 ) … ( k + 1 ) . Note that 2 0 1 4 0 0 = 2 0 1 4 ⋅ 1 0 0 = 2 ⋅ 2 ⋅ 2 ⋅ 5 ⋅ 5 ⋅ 1 9 ⋅ 5 3 . As it is given that 2 0 1 4 0 0 is the quantity of divisors, and maximizing, we say that the prime factorization of the number is p 1 1 ⋅ p 2 1 ⋅ p 3 1 ⋅ p 4 4 ⋅ p 5 4 ⋅ p 6 1 8 ⋅ p 7 5 2 . We've maximized, and we got 7 different primes. Thus, our final answer is 7 .
Problem Loading...
Note Loading...
Set Loading...
201400 may be factorized as 2 3 × 5 2 × 1 9 × 5 3 . Since we seek the most number, we treat this as simple 2 × 2 × 2 × 5 × 5 × 1 9 × 5 3 , which has 7 factors and thus N has at most 7 distinct prime divisors.