Demostrar que $d(n)\leq 2\sqrt{n}$

Question

En el libro de Waclaw Sierpinski Teoría elemental de los números en la página 168 hay el siguiente ejercicio:

"Ejercicios. 1. Demuestra que para los números naturales $n$ tenemos $d(n) \leq 2\sqrt{n}$ ," donde $d(n)$ es el número de divisores de n.

Como pista se da justo debajo: "La prueba se desprende del hecho de que de dos divisores complementarios de un número natural $n$ uno no es siempre mayor que $\sqrt{n}$ .

Entiendo la insinuación pero no sé cómo se puede utilizar para demostrar $d(n)\leq 2\sqrt{n}$ .

Los divisores complementarios son pares de divisores que al multiplicarse dan el número que se quiere dividir. Por ejemplo, el número $120$ tiene los divisores complementarios: \begin{align*} & 1, 120 \\ & 2, 60 \\ & 3, 40 \\ & 4, 30 \\ & 5, 24 \\ & 6, 20 \\ & 8, 15 \\ & 10, 12 \\ \end{align*} ¿Cómo se demuestra que $d(n) \leq 2\sqrt{n}$ ?

Answer 1

Supongamos primero que $n$ no es un cuadrado. Entonces para cada divisor menor que $\sqrt{n}$ hay uno y sólo un divisor "complementario" que es mayor que $\sqrt{n}$ . Por tanto, el número de divisores de $n$ es igual a dos veces el número de divisores de $n$ que son más pequeños que $\sqrt{n}$ .

¿Cuántos divisores pueden $n$ tienen que son más pequeños que $\sqrt{n}$ ? ¿Puede dar un muy trivial ¿se trata de un límite superior a esa cantidad?

El argumento es esencialmente el mismo si $n$ es un cuadrado perfecto, excepto que en ese caso tienes una especial divisor, a saber, $\sqrt{n}$ que no está emparejado con nadie. Sin embargo, el argumento de delimitación debería seguir siendo (esencialmente) el mismo.

Answer 2

La función que envía un divisor $d$ de $n$ hasta el más pequeño de $d$ y $n/d$ es como máximo $2$ -a- $1$ por lo que el tamaño del conjunto de origen es como máximo el doble del tamaño del conjunto de destino. El conjunto fuente es el conjunto de divisores de $n$ y tiene el tamaño $d(n)$ . El conjunto objetivo está formado por (algunos) enteros positivos no mayores que $\sqrt{n}$ por lo que tiene un tamaño máximo de $\sqrt{n}$ . QED.

Answer 3

Consideremos los pares ordenados de divisores complementarios de $n$ , $(d_1,\frac nd_1),(d_2,\frac nd_2),\dots,(d_r,\frac nd_r),(\sqrt n,\sqrt n),(\frac nd_1,d_1),(\frac nd_2,d_2),\dots,(\frac nd_r,d_r)$

donde $d_i\le\sqrt n\quad\forall i=1,2,\dots,r$

Si $n$ no es un cuadrado perfecto excluimos $(\sqrt n,\sqrt n)$ . Sea $S=\{(d_1,\frac nd_1),(d_2,\frac nd_2),\dots,(d_s,\frac nd_s)\}$ sea el conjunto de todos los pares ordenados donde los primeros elementos son $d_i's$ ; $d_s=d_r$ si $n$ no es un cuadrado perfecto y $d_s=\sqrt n$ si $n$ es un cuadrado perfecto. Sea $m$ denotan el número de elementos de $S$ . Está claro que $$d(n)\le2m\dots(1)\Bigl(d(n)\lt2m,\text{if $ n $ is a perfect square and $ d(n)=2m $ if $ n $ is not a perfect square$ \(en inglés, "Bigl") $}$$ El número de elementos de $S$ es igual al número de $d_i's$ . Supongamos que $n$ es divisible por todos los enteros $\le\sqrt n\;$ entonces $d_1=1,d_2=2,d_3=3,\dots d_s=\sqrt n,$ entonces el número de $d_i's$ es $\sqrt n\;$ y por lo tanto el número de $d_i's$ es como máximo $\sqrt n\,$ . Así, para cada número entero $n\ge 1$ el número de $d_i's\le\sqrt n\,$ . Entonces, $$m\le\sqrt n\,\dots(2)$$ Ahora, a partir de la ecuación $(1)$ y $(2)$ obtenemos $$d(n)\le2\sqrt n$$