1

Let $n$ be a natural number. Can $n$ have more than $\dfrac{n}{2}+1$ divisors?

(a) $3$

3 = 1 * 3 (2 divisors)
3/2 + 1 = 2
2 <= 2  [OK]

(b) $4$

4 = 1 * 2 * 2 (3 divisors)
4/2 + 1 = 3
3 <= 3  [OK]

(c) $6$

6 = 1 * 2 * 3 (4 divisors)
6/2 + 1 = 4
3 <= 4  [OK]

...

For me, it seems impossible, but I'm not figuring out a way to proof why. I guess that it is related to the fact that, after $2$, all possible divisors will increase the number more than twice.

Daniel
  • 732
  • Why does $6$ have four divisors, $1,2,3,6$ while $4$ has only $2$ divisors, presumably $1,2$. Are you asking about proper divisors or not? Also, on this site $3/2 \neq 1$-it appears you are using integer division. – Ross Millikan Feb 01 '20 at 04:21
  • well, just pick a large prime number $p$, and since it's a prime number so $p=1 * p$ only 2 diviso, but what about $n/2 + 1$? – trung Feb 01 '20 at 04:24

1 Answers1

3

Let $d(n)$ denote the number of divisors of $n.$

Since divisors appear in pairs, one of which is $\leq \sqrt{n}$ and the other $\geq \sqrt{n},$ this means $d(n) \leq 2\sqrt{n}.$ (When $n$ is a square, the argument would give $d(n) \leq 2\sqrt{n} - 1,$ so it applies there too)

If we had $d(n) > \frac{n}{2} + 1$ then we'd have $$2\sqrt{n} > \frac{n}{2}+1$$ which we can solve as a quadratic in $\sqrt{n}$ to give $$n < 12$$

This means we can resolve it just by checking natural numbers through $11$.

Sidenote: If you include $0$ as a natural number (which is common), then $n=0$ provides an example of a natural number with more than $\frac{n}{2}+1$ divisors.

Brian Moehring
  • 21,088