can $n$ have more than $\dfrac{n}{2} + 1$ divisors?

76 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.