7
$\begingroup$

Find all positive integers $n$ such that $n$ is divisible by all the positive integers less than or equal to $\sqrt{n}$

My thought: If n is a positive integer, let d(n) denote the number of positive divisors of n and I will find n such that $d(n) \ge 2\sqrt{n} - 1$

$\endgroup$
  • $\begingroup$ If n≥4,n must be even as 2 must be a divisor.More generally, if $n \geq p^2$, $p$ must divide $n$ $\endgroup$ – lab bhattacharjee Sep 19 '12 at 16:55
10
$\begingroup$

By manual testing, $n=1$, $n=2$, $n=4$, $n=6$, $n=8$ have the desired property and are the only numbers $<9$ with it.

Let $n$ be a natural number that is divisible by all natural numbers $\le \sqrt n$. So if we let $a=\lfloor \sqrt n\rfloor$ then $a$ and $a-1$ (if $>0$) are by divisors of $n$. If we additionally assume $n\ge 9$ then $a\ge 3$. Since $a$ and $a-1$ are relatively prime, $a^2-a=a(a-1)$ divides $n$. Thus $n=k(a^2-a)$ for some $k$. Clearly $k>1$ because $n\ge a^2$. Hence $(a+1)^2>n\ge 2a^2-2a$, i.e., $0\ge a^2-4a=(a-4)a$. This implies $a\le 4$. If $a=3$ we find $9\le n<16$ and $n$ must be a multiple of $2$ and $3$. We need only check $n=12$, which gives a solution. If on the other hand $a=4$, then $16\le n<25$ and $n$ is a multiple of $3$ and $4$. We need only check $n=24$, which gives a solution.

Thus the positive integers with the property are precisely $$1, 2, 3, 4, 6, 8, 12, 24.$$

$\endgroup$
  • $\begingroup$ n=24 satisfied the condition $\endgroup$ – tangkhaihanh Sep 19 '12 at 17:02
  • $\begingroup$ @tangkhaihanh: Yeah, I noticed a sign error in my proof as soon as I read the finished post - tnanks for the hint $\endgroup$ – Hagen von Eitzen Sep 19 '12 at 17:05
  • $\begingroup$ @HagenvonEitzen Could you please explain by what assumption a and a-1 are divisors of n? (as you said in the third sentence of the second paragraph) Thanks! $\endgroup$ – Gaurang Tandon Nov 24 '15 at 8:50
0
$\begingroup$

A104588 Product of primes less than or equal to sqrt(n).

1, 1, 1, 2, 2, 2, 2, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210, 210

http://oeis.org/A104588

seems to be larger than $n$ for $n > 48$, so there is a very finite number of cases to test.

That is not a complete proof but it does explain one reason the result should be a short list of small $n$.


Another sledgehammer is http://oeis.org/A003418

A003418 a(n) = least common multiple (lcm) of $\{1, 2, ..., n\}$

1, 1, 2, 6, 12, 60, 60, 420, 840, 2520, 2520, 27720, 27720, 360360, 360360, 360360, 720720, 12252240, 12252240, 232792560, 232792560, 232792560, 232792560, 5354228880, 5354228880, 26771144400, 26771144400, 80313433200, 80313433200

which becomes much larger than $n^2$ according to the remark

An assertion equivalent to the Riemann hypothesis is: $| \log(a(n)) - n | < \sqrt{n} \log(n)^2$ (for $n \geq 3$).

$\endgroup$

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.