Fall 2016, problem 30

Let $ d(n)$ be the number of positive divisors of the natural number $ n$ (this includes $1$). Find all $ n$ such that $ \frac {n} {d(n)}=p$ where $ p$ is a prime number.


5 years ago

Factor $n$ as $\prod_{i=1}^\infty p_i^{m_i}$, where $p_i$ is the $i^{th}$ prime. This means $d(n)=\prod_{i=1}^\infty (m_i+1)$.

For a rational numer $q$, define the weight of $q$, $wt(q)$, to be the number of prime factors of its numerator minus that of its denominator. This is independent of how $q$ is represented. It is easy to see $wt(ab)=wt(a)+wt(b)$. Also, when $m$ is a positive integer, $wt(m)\le \log_2(m)$, with equality iff $m$ is a power of 2.

We are searching for $n$ such that $wt(\frac{n}{d(n)})=1$. Using the factorization for $n$, the formula for $d(n)$, and the additivitiy of $wt$, we get $$ wt(\frac{n}{d(n)})=\sum_{i=1}^\infty m_i-wt(m_i+1) $$

Each of the summands is nonnegative (since $m_i-wt(m_i+1)\ge m_i-\log_2(m_i+1)\ge 0$), so if any are $\ge 2$, the whole sum is as well. It is easy to verify that $j-wt(j+1)\ge 2$ whenever $j\ge 4$, again using the inequality $j-wt(j+1)\ge j-\log_2(j+1)$. Therefore, in order to have $wt(\frac{n}{d(n)})=1$, it must be the case that

Each $m_i\le 3$.

Furthermore, exactly one of the summands is 1, while the others are zero. Since $j-wt(j+1)$ is 1 when $j=2,3$, and is 0 when $j=0,1$, this means

Exactly one $m_i>1$.

With this knowledge, let's examine $$ \frac{n}{d(n)}=\frac{2^{m_1}\cdot 3^{m_2}\cdots p_k^{m_k}}{(m_1+1)(m_2+1)\cdots(m_k+1)} $$ Since each $m_i\le 3$, the denominator only contains 2's, 3's and 4's. In order for $\frac{n}{d(n)}$ to be a prime, there cannot be more than one large prime in the numerator, where large means at least 5.

$n$ can only have one prime factor which is 5 or more.

Combining the last three observations, we concude $n$ is of the form $2^{m_1}3^{m_2}$ or $2^{m_1}3^{m_2}p$, where one of $m_i$ is 2 or 3 and the other is 0 or 1, and $p\ge 5$ is prime. This leaves only 16 cases, which can be checked by brute force. The results are this: $n$ is a solution iff

  • $n=8,9,12,18, 24$, or

  • $n=8p$ or $n=12p$, where $p\ge 5$ is prime.

you can also have n = 3p

Kumar 5 years ago

If n= 3p then d(n) =4 and n/d(n) cannot be p !

michel 5 years ago