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?
Best Answer
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$.