1
$\begingroup$

How do I know that $n \neq k^3$ if $n, k$ are natural numbers and $n$ has exactly 999 divisors?

I came across this fact, but it doesn't look intuitive at all. Is there a way to prove this? Presumably, I would need to use some basic number theory, but I'm not really sure where to start.

$\endgroup$
  • $\begingroup$ I think you mean: how do I know such a number n can exist, as not all n that have the first property will have the second. $\endgroup$ – user645636 Apr 1 '19 at 17:38
  • $\begingroup$ @RoddyMacPhee: to be honest, I think Masie's formulation is clearer than yours. $\endgroup$ – TonyK Apr 1 '19 at 17:38
  • $\begingroup$ Then you don't know nath @TonyK $\endgroup$ – user645636 Apr 1 '19 at 18:11
  • $\begingroup$ @RoddyMacPhee: yo mama don't know nath! $\endgroup$ – TonyK Apr 1 '19 at 18:31
  • $\begingroup$ my mothers dead. anyways I give up. $\endgroup$ – user645636 Apr 1 '19 at 18:32
3
$\begingroup$

Suppose, $n$ has the prime factorization $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. Number of divisors of $n$ can be given by $(\alpha_1+1)(\alpha_2+1)\cdots (\alpha_k+1)$, which is $999$ here. $n$ to be a perfect cube, we need all $\alpha_i=3\cdot x_i$, for some $x_i\in\mathbb{N}$. That means $$(\alpha_1+1)(\alpha_2+1)\cdots (\alpha_k+1)=(3x_1+1)(3x_2+1)\cdots (3x_k+1)$$ But, product of two numbers of the form $(3t+1)$ is also $(3t+1)$, and using induction we have the above number to be of the form $3t+1$. But, $999\equiv 0\pmod{3}$. Hence, it is not possible to exist $\alpha_i$ s for which the equation $$(\alpha_1+1)(\alpha_2+1)\cdots (\alpha_k+1)=999$$ holds.

$\endgroup$
  • $\begingroup$ What's the logic behind (a1+1)...(ak+1)=999? Is that just some formula to find the number of divisors? Is there a way to prove that formula? $\endgroup$ – Masie Apr 1 '19 at 18:36
  • $\begingroup$ Yes, it's a standard formula in ENT. It's known as $\tau$(tau) function, see this post. $\endgroup$ – tarit goswami Apr 1 '19 at 18:40
  • $\begingroup$ Got it, thanks! $\endgroup$ – Masie Apr 1 '19 at 18:51
1
$\begingroup$

Hint: Prove that if $n=k^3$ for some integer $k$, then the number of divisors of $n$ is one more than a multiple of $3$. (E.g., $2^3$ has $4$ divisors, $6^3$ has $16$ divisors, $100^3$ has $49$ divisors, ...) Since $999$ is not one more than a multiple of $3$, if $n$ has $999$ divisors then it cannot equal $k^3$ for any integer $k$.

To prove this, consider the prime decomposition of $k$. We can write $$k=p_1^{\alpha_1}\cdots p_t^{\alpha_t}$$ for some distinct primes $p_1,\dots,p_t$. Then a factor of $k^3$ looks like $$p_1^{\beta_1}\cdots p_t^{\beta_t}$$ where each $\beta_i$ satisfies $0 \leq \beta_i\leq 3\alpha_t$. How many such factors are possible?

$\endgroup$

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.