Happy factorizing

N N is an integer which has 201400 positive divisors. What is the most number of (distinct) primes which are a divisor of N N ?


The answer is 7.

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.

7 solutions

Andres Saez
Dec 25, 2013

201400 may be factorized as 2 3 × 5 2 × 19 × 53 2^3 \times 5^2 \times 19 \times 53 . Since we seek the most number, we treat this as simple 2 × 2 × 2 × 5 × 5 × 19 × 53 2 \times 2 \times 2 \times 5 \times 5 \times 19 \times 53 , which has 7 \boxed{7} factors and thus N N has at most 7 distinct prime divisors.

Can you explain your argument in more details? Why does N N have at most 7 7 distinct prime factors? Also, how do you know that 7 7 is the maximum and not just an upper bound?

Alexander Borisov - 7 years, 5 months ago

Log in to reply

Sure. A number k = p 1 a 1 p 2 a 2 p n a n k = p_1^{a_1} p_2^{a_2} \ldots p_n^{a_n} has, of course, i = 1 n ( a i + 1 ) \prod_{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 24 p 3 18 p 4 52 p_1^{7}p_2^{24}p_3^{18}p_4^{52}

2) p 1 1 p 2 3 p 3 24 p 4 18 p 5 52 p_1^{1}p_2^{3}p_3^{24}p_4^{18}p_5^{52}

3) p 1 1 p 2 3 p 3 4 p 4 4 p 5 18 p 6 52 p_1^{1}p_2^{3}p_3^{4}p_4^{4}p_5^{18}p_6^{52}

4) p 1 1 p 2 1 p 3 1 p 4 24 p 5 18 p 6 52 p_1^{1}p_2^{1}p_3^{1}p_4^{24}p_5^{18}p_6^{52}

5) p 1 1 p 2 1 p 3 1 p 4 4 p 5 4 p 6 18 p 7 52 p_1^{1}p_2^{1}p_3^{1}p_4^{4}p_5^{4}p_6^{18}p_7^{52}

Note that these are the only expressions in which i = 1 n ( a i + 1 ) = 204100 \prod_{i=1}^n (a_i + 1) = 204100 , and so the maximum number of prime factors of N N is 7 \boxed{7} . In general, if a number has p 1 a 1 p 2 a 2 p n a n p_1^{a_1} p_2^{a_2} \ldots p_n^{a_n} divisors, it has at most i = 1 n a i \sum_{i=1}^n a_i prime factors (check this for yourself).

Andres Saez - 7 years, 5 months ago

Log in to reply

Thanks! There certainly are more cases than those that you listed, for example N = p 1 201399 . N=p_1^{201399}. Fortunately, one does not have to list them all. Perhaps, the easiest way to rigorously prove this is by contradiction.

Suppose N N has at least 8 8 prime factors, then (by the formula for the number of divisors that you quoted) 201400 201400 is a product of at least 8 8 factors, all greater than 1 1 . This implies that the total sum of the powers of all primes in the prime decomposition of 201400 201400 is at least 8 8 (at least one for each factor). But it is 3 + 2 + 1 + 1 = 7. 3+2+1+1=7. This contradiction means that our assumption was false, so N N can have no more than 7 7 prime factors.

One still has to show that 7 7 can be achieved, which is easy to do by an explicit example.

Alexander Borisov - 7 years, 5 months ago
Aryan C.
Dec 25, 2013

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

Anne Hao
Dec 25, 2013

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 2^{a} x 3 b 3^{b} x 5 c 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 2^{3} x 5 2 5^{2} x 19 19 x 53 53 . That means there are 7 (not distinct) prime factors of 201400 so there are 7 distinct prime factors of that number.

Lee Wall
Feb 9, 2014

Note that 201400 = 2 3 5 2 19 53 201400 = 2^{3} \cdot 5^{2} \cdot 19 \cdot 53 . 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 \boxed{7} distinct prime divisors of N N .

Muhammad Shariq
Jan 2, 2014

Assume that the prime factorisation of N N is p 1 b 1 p 2 b 2 p 3 b 3 p 4 b 4 . . . p k b k 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 p_1,p_2,...,p_k are unique primes and b 1 , b 2 , . . . , b k b_1,b_2,...,b_k are positive integers. Then the number of factors of N N can be written as:

( b 1 + 1 ) ( b 2 + 1 ) ( b 3 + 1 ) . . . ( b k + 1 ) = 201400 = 1 9 1 × 5 3 1 × 2 3 × 5 2 (b_1+1)(b_2+1)(b_3+1)...(b_k+1)=201400=19^1 \times 53^1 \times 2^3 \times 5^2

Adding up the exponents of each prime factor of 201400 201400 gives us the maximum number of distinct primes that divide N N which is: 1 + 1 + 3 + 2 = 7 1+1+3+2=\boxed{7} .

Andres Fabrega
Dec 27, 2013

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 N be D D .

N = x 1 a 1 × x 2 a 2 × x D a D \Rightarrow N = x_{1}^{a_{1}} \times x_{2}^{a_{2}} \ldots \times x_{D}^{a_{D}} .

Then, remembering the tau formula for number of divisors: t ( N ) = ( a 1 + 1 ) × ( a 2 + 1 ) ( a D + 1 ) = 201400 = 2 × 2 × 2 × 5 × 5 × 19 × 53 t(N) = ( a_{1} +1 ) \times ( a_{2} +1 ) \ldots ( a_{D} +1 ) = 201400 = 2 \times 2 \times 2 \times 5 \times 5 \times 19 \times 53

Now, we see that we want D D to be the biggest possible value. Therefore, we want the most amount of parenthesis possible.

Then, looking at the prime decomposition of 201400 201400 , we clearly see that the most amount of parenthesis possible is seven parenthesis (remember a i > 1 a_{i} > 1 for i = 1 , 2 , , D i = 1 , 2 , \ldots , D ).

Therefore, the biggest possible value for D D is 7 7 , so the most number of distinct primes which are divisors of N N are 7 \boxed{7} .

I'll try to express this:

If a number is factorized in the form p 1 a p 2 b p n k p^{a}_1 \cdot p^{b}_2 \cdot \ldots \cdot p^{k}_n , for some k k and n n (integers), then it's quantity of divisors is equal to ( a + 1 ) ( b + 1 ) ( k + 1 ) (a + 1)(b + 1)\ldots(k + 1) . Note that 201400 = 2014 100 = 2 2 2 5 5 19 53 201400 = 2014\cdot100 = 2\cdot2\cdot2\cdot5\cdot5\cdot19\cdot53 . As it is given that 201400 201400 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 18 p 7 52 p^{1}_1 \cdot p^{1}_2 \cdot p^{1}_3 \cdot p^{4}_4 \cdot p^{4}_5 \cdot p^{18}_6 \cdot p^{52}_7 . We've maximized, and we got 7 7 different primes. Thus, our final answer is 7 \boxed {7} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...