Problem: For any integer $d > 0,$ let $f(d)$ be the smallest possible integer that has exactly $d$ positive divisors (so for example we have $f(1)=1, f(5)=16,$ and $f(6)=12$). Prove that for every integer $k \geq 0$ the number $f\left(2^k\right)$ divides $f\left(2^{k+1}\right).$

My Solution: We begin by observing that there must exist a prime $p$ such that $2^k-1=v_p(f(2^n))<v_p(f(2^{n+1}))=2^{\ell}-1$. Otherwise, we have $v_p(f(2^n))\ge v_p(f(2^{n+1}))$ for all prime. But this isn't possible, since $f(2^{n+1})$ has more divisors than $f(2^{n})$ (by definition). Now consider the number $N=\frac{f(2^{n+1})}{p^{2^{\ell-1}}}$. This number has $2^n$ divisors. So we must have $N\ge f(2^n)$. Now consider the number $f(2^n)p^{2^k}$. This number has $2^{n+1}$ divisors. So we must $f(2^n)p^{2^k}\ge N\cdot p^{2^{\ell-1}}\ge f(2^n)p^{2^{\ell-1}}$. Thus we must have $N=f(2^n)$ and $\ell=k+1$. Thus we must have $f(2^n)\mid f(2^{n+1})$.

But If my solution is correct, then we have nothing special about 2. Thus I am skeptic wheteher my proof is correct or not. Can someone please point out any error?

  • $\begingroup$ At the risk of sounding stupid, what is $v_p$? $\endgroup$ – orlp Jun 27 '20 at 18:49
  • $\begingroup$ Sorry for not clarifying this non-standard notation. Suppose $p^a\mid n$ and $p^{a+1}\nmid n$, then $v_p(n)=a$. $\endgroup$ – user180446 Jun 27 '20 at 18:51
  • $\begingroup$ @orlp See $p$-adic order. $\endgroup$ – John Omielan Jun 27 '20 at 18:55
  • $\begingroup$ This is fairly standard notation for the $p$-adic order or valuation, except that it should be $\nu_p$ (Greek letter nu). $\endgroup$ – TonyK Jun 27 '20 at 18:56
  • $\begingroup$ I think that $f(p^k)$ is simply the product of the $(p-1)$th powers of the first $k$ primes. So $f(p^k)$ divides $f(p^{k+1})$ for all primes $p$. $\endgroup$ – TonyK Jun 27 '20 at 18:58

You do use something special about $2$, namely that it is prime:

If you replace $2$ with a different prime $q$, you end up with $$ f(q^n)p^{q^{k+1}-q^k}\ge f(q^{n+1})=Np^{q^{\ell}-q^{\ell-1}}\ge f(q^n)p^{q^{\ell}-q^{\ell-1}},$$ so $k\ge \ell-1$ and again $k=\ell-1$ and $f(q^{n+1})=p^{(q-1)q^k}f(q^n)$.

  • $\begingroup$ So it is true for any prime, not just 2? $\endgroup$ – user180446 Jun 27 '20 at 19:34

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.