2
$\begingroup$

A natural number $n$ has 20 divisors. What's the largest number of different prime divisors that a number $n$ could have?

What I have is $$(\alpha_1+1)(\alpha_2+1)(\alpha_3+1)\cdots(\alpha_k+1)=20$$ where $$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$$ But what's next?..

$\endgroup$
  • $\begingroup$ You want to maximise $k$, so which factorisation of $20$ maximises the number of terms? $\endgroup$ – B. Mehta Jun 11 '17 at 13:59
  • $\begingroup$ $\omega (n) < \frac{\ln n}{\ln \ln n} + O\left(\frac{\ln}{(\ln \ln n )^2}\right)$ and $\Omega(n) \le \log_2 n$ where $\omega(n)$ is the number of distinct prime divisors of $n$ and $\Omega(n)$ is the number of divisors of $n$ with multiplicity. $\endgroup$ – Dando18 Jun 11 '17 at 14:10
  • $\begingroup$ In the text body you can italicize a piece of text by wrapping it with asterisks. Double asterisks give you bold. Alas, that doesn't seem to work in the title, but I think this looks better than using math italics that you had with TeX/MathJax. $\endgroup$ – Jyrki Lahtonen Jun 11 '17 at 16:48
4
$\begingroup$

For your case, the answer is $3$.

In general, if a number has $k$ divisors, what's the maximum number of prime divisors that it could have?

Every integer can be written as the product of different primes raised to some power greater than or equal to $1$, for example $x = {p_1}^{n_1} {p_2}^{n_2} \ldots {p_m}^{n_m}$, with all $n_j \geq 1$. The number of divisors is $k = (n_1 + 1)(n_2 + 1)\ldots(n_m + 1)$. The number of prime divisors is $m$.

$m$ is largest if the $n_j$ are as small as possible: Take $k$, factor it into prime factors, and count the prime factors according to their multiplicity. For example, if a number $x$ has $k = 20 = 2 \cdot 2 \cdot 5$ divisors, it can have at most $3$ prime factors since $2 \cdot 2 \cdot 5$ is the product of three primes. Numbers with $20$ divisors and $3$ prime divisors are the numbers of the form $pqr^4$ where $p$, $q$ and $r$ are distinct primes.

$\endgroup$
1
$\begingroup$

the number of factors in the expression $(\alpha_1+1)(\alpha_2+2)\dots(\alpha_k+1)=20$ is at most the number of prime factors of $20$ with multiplicity, which is $3$.

An example of such a factorization is $2\times2\times 5$ which yields the number $n=2\times 3\times 5^4$ for example.

$\endgroup$
  • $\begingroup$ Sorry, I forgot to say, that these prime numbers should be different. $\endgroup$ – Karagum Jun 11 '17 at 14:05
  • $\begingroup$ yeah, the maximum is $3$, for example $2,3$ and $5$. I just meant that the number of factors in the expression for $20$ is bounded by the number of priome factors of $20$ with multiplicity. $\endgroup$ – Jorge Fernández Hidalgo Jun 11 '17 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.