Positive integer $n$ is divisible by a cube, if it has three prime divisors and at least seven divisors $p^k$ ($p$ prime and $k$ positive integer).

Question

Problem. Let $n$ be a positive integer that has exactly three prime divisors, and at least seven divisors of the form $p^k$, where $p$ is a prime, and $k$ is a positive integer. Prove that $n$ must be divisible by the cube of an integer that is larger than 1.

This is a problem (Quick Check 3 Chapter 1.2) from A Walk Through Combinatorics by Miklós Bóna, and comes after the discussions on the Pigeon-hole principle and Generalized Pigeon-hole principle.

(Note: I don't have much background on Number Theory and also unsure if my attempts even lead to the correct solution)

---

The following are my current attempts and progress, and also some clarifications on the problem:

• Let $\alpha$, $\beta$, and $\gamma$ be the three prime divisors of $n$, then $$n=\alpha \ell, \quad n=\beta \ell, \quad \text{and} \quad n=\gamma \ell$$ for some integers $\ell$ which are not necessarily the same for each instance. Now, I think it follows from the prime factorization theorem that $$n = (\alpha \beta \gamma)\cdot \ell$$ for some integer (I am unsure if this actually follows).
• Also, $n$ has at least seven prime divisors $p^k$, so for $i\in [7]$ $$n = p_i^{k_i}\cdot \ell_i$$ I tried to equate each of these prime divisors, for example $p_1^{k_1}\cdot \ell_1 = p_2^{k_2}\cdot \ell_2$. Then, since the factor $p_1^{k_1}$ from the left side may not have came from $p_2^{k_2}$ on the right then it must have come from $\ell_2$ (and vice-versa); generalizing this, I think it must follow that $$n=\left(\prod_1^7 p_i^{k_i} \right)\cdot c $$ for some integer $c$.
• Continuing from the two previous points $$(\alpha\beta\gamma)\cdot \ell = \left(\prod_1^7 p_i^{k_i} \right)\cdot c$$

From this point, I no longer know what to do. Do we then assume the contrary? That there is no cube which divides $n$? Also, can we assume from the problem that the three prime divisors of $n$ must be distinct from each other, and also distinct from the seven $p^k$ divisors?

Answer 1

Assume the opposite, and arrive at a contradiction.

If $n$ has exactly three prime divisors, it is of the form $n=p_1^{k_1}p_2^{k_2}p_3^{k_3}$. Now assume that no cube divides $n$. That means each $k_i \in \{1,2\}$, lest $p_i^3$ (a cube) is a divisor of $n$.

In this case, the divisors of the form $p^k$ are just $p_1,p_1^2,p_2,p_2^2,p_3,p_3^2$. There are only $6$ of them. But the probem requires that there be at least $7$ divisors of that form, so at least one of the $p_i$ must have an exponent $k_i \ge 3$. Hence, $n$ must be divisible by a cube of that $p_i$, and $p_i$ is a prime number larger than $1$.

Answer 2

I’d state the solution using the pigeonhole principle. Let $n=p_1^{k_1} p_2^{k_2} p_3^{k_3}.$. Then any number of the form $p_i^k, 1 \leq k \leq k_i$, divides $n$.

There are at least $7$ such divisors and only $3$ primes to choose from, so for some $j$ we must have $p_j^k$ for at least three different positive integers $k$, which means $p_j^k$ divides $n$ for some $k \ge 3$. But that, in turn, means $p_j^3$ divides $n$ and we are done.

Answer 3

Let's make this simpler.

• $n$ has exactly $3$ prime divisors.

Let them by $p,q,r$ so $n = p^aq^br^c$ for natural numbers $a,b,c$.

• $n$ has at least $7$ divisors of the for $p^k$ where $k \ge 1$.

That may seem complex but $p^1, p^2, p^3, ...., p^a$ are exactly $a$ such divisors. $q^1, q^2, ...., q^b$ are $b$ more and $r^1,...., r^c$ are $c$ more. And those are all such divisors. And other divisors of $p^aq^br^c$ must be either $1$ or some combination of at least two primes.

So $n$ has exactly $a+b+c$ such divisors. So all this is saying is $a+b+c \ge 7$.

• $n$ is divisble by a cube larger than $1$.

At this point, let's ask how can that not be possible.

We should note that if $a \ge 3$ then $n=p^aq^br^c = p^3\times p^{a-3}p^bq^c$ so $p^3|n$ and a perfect cube divides $n$.

Likewise if $b\ge 3$ or $c \ge 3$ then $q^3$ or $r^3$ will be a perfect cube factor.

So in order to have no perfect cubes (other than $1$) factors we must have $a < 3; b < 3; c< 3$.

But $a+b + c \ge 7$.

.......