Let $ d(n)$ be the number of positive divisors of the natural number $ n$. Find all $ n$ such that $ \frac {n} {d(n)}=p$ where $ p$ is a prime number Daniel
Problem
Source: Argentina TST IMO 2008 Problem 4
Tags: inequalities, number theory proposed, number theory
23.07.2008 03:35
Suppose $ n = p^rp_1^{r_1}p_2^{r_2}\cdots{p_k^{r_k}}$, where $ p,p_1,p_2,\cdots,p_k$ are distinct primes (WLOG, we assume $ p_1<p_2<\dots<p_k$. Then, \[ n = p\cdot{d(n)} = p(r+1)\left(r_1+1\right)\left(r_2+1\right)\cdots\left(r_k+1\right)\,.\] Therefore, \[ p^{r-1}p_1^{r_1}p_2^{r_2}\cdots{p_k^{r_k}} = (r+1)\left(r_1+1\right)\left(r_2+1\right)\cdots\left(r_k+1\right)\,.\] If $ k=0$, then $ p^{r-1} = r+1$. Hence, $p=2$ and $r=3$, or $ p=3$ and $ r=2$; i.e., $ n=8$ or $n=9$. From now, we assume that $ k \geq 1$. If $ p_1\geq3$, then $ p_i^{r_i} > r_i+1$ for all $ i$. Thus, $ p^{r-1} < r+1$. This occurs when $ r=1$ or $ (p,r) = (2,2)$. However, $ r=1$ leads to $ p_1=2$, a contradiction. Hence, $ p=r=2$. That is, $ p_1=3$. Now, \[ 2\cdot3^{r_1} \leq 3\left(r_1+1\right)\,,\] which occurs if and only if $ k=1$ and $ r_1=1$. Therefore, $ n=12$. If $ p_1=2$ and $ r=1$, then $ 2^{r_1-1} \leq r_1+1$. Therefore, $ r_1 = 1$, $ r_1 = 2$, or $ r_1=3$. However, $ r_1=1$ leads to a contradiction. If $ r_1=2$, then $ p_2=3$. That is, \[ 2\cdot{3^{r_2-1}} \leq r_2+1\,.\] The above inequality forces $ r_2=1$ and $ k=2$. Hence, $ n=12p$. Now, if $ r_1=3$, then $ k=1$. Therefore, $ n=8p$. If $ p_1=2$ and $ r>1$, then $ p^{r-1} \geq r+1$ and $ p_i^{r_i} > r_i+1$ for all $ i>1$. Therefore, \[ 2^{r_1} \leq r_1+1\,.\] Thus, $ r_1 = 1$ is the only solution. This makes $ k=1$ and $ p^{r-1} = r+1$ (which occurs only when $ p=3$ and $ r=2$). Therefore, $ n=18$. In summary, 1) If $ p=2$, then $n=8$ or $ n=12$; 2) If $ p=3$, then $ n=9$, $ n=18$, or $ n=24$; 3) If $ p>3$, then $ n=8p$ or $ n=12p$. EDIT: Thanks yunxiu for notifying an omission.
24.07.2008 18:32
lambruscokid wrote: Let $ d(n)$ be the number of positive divisors of the natural number $ n$. Find all $ n$ such that $ \frac {n} {d(n)} = p$ where $ p$ is a prime number Daniel hi $ n= p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots{p_k^{a_k}} =\prod p_i^{a_i}$ so $ n=(1+a_1)(1+a_2)........(1+a_k)=\prod(1+a_i)$ that mean: $ p=\frac {n} {d(n)} =\frac{\prod p_i^{a_i}} {\prod(1+a_i) }$ $ p=\prod \frac{p_i^{a_i}} {1+a_i}$ ==> $ \prod p_i^{a_i} =p*\prod(1+a_i)$ so $ p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots{p_k^{a_k}} \equiv 0[(1+a_1)(1+a_2)........(1+a_k)]$ and by using Fermat if $ p_i\wedge(1+a_i) =1$ so $ p_i^{a_i} \equiv 1[1+a_i]$ so $ p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots{p_k^{a_k}} \not\equiv 0[(1+a_1)(1+a_2)........(1+a_k)]$ contradiction !! so $ p_i\wedge(1+a_i) \not=1$ that mean $ p_i=1+a_i$ ==> $ p=\prod p_i^{a_i-1}$ ==> p is prime number so $ a_i-1=1$so $ a_i=2$ that mean $ pi=3$ so $ p=3$ and $ n=p_i^{a_i}=3^2=9$ finally $ (n.p)=(9.3)$
24.07.2008 20:03
It is not correct. Batominovski's one is perfect so check it. Daniel
19.01.2013 12:16
Batominovski wrote: In summary, 1) If $ p=2$, then $ n=12$; 2) If $ p=3$, then $ n=9$, $ n=18$, or $ n=24$; 3) If $ p>3$, then $ n=8p$ or $ n=12p$. $n=8$ is a soluton.