1.5: Congruencias

En esta sección desarrollaremos algunos aspectos de la teoría de la divisibilidad y congruencias.

Si

\(a = \prod p^{\alpha}\)y\(b = \prod p^{\beta}\)

entonces se ve fácilmente que

\((a, b) = \prod p^{\text{min}(\alpha, \beta)}\)mientras\([a, b] = \prod p^{\text{max} (\alpha, \beta)}.\)

De estos se deduce fácilmente eso\((a, b) \cdot [a, b] = a \cdot b\). Lo dejamos como ejercicio para demostrar que

\((a, b) = \dfrac{1}{a} \sum_{a = 1}^{a - 1} \sum_{\beta = 1}^{a - 1} e^{2\pi i \dfrac{b}{a} \alpha \beta}.\)

La notación\(a \equiv b\) (mod\(m\)) para\(m\ |\ (a - b)\) se debe a Gauss. Las propiedades más bien obvias de esta congruencia son\(a \equiv a\)\(a \equiv b \Rightarrow b \equiv a\),,\(a \equiv b\) y\(b \equiv c \Rightarrow a \equiv c\), es decir,\(\equiv\) una relación de equivalencia. También se demuestra fácilmente que\(a \equiv b\) y\(c \equiv d\) juntos implican\(ac \equiv bd\); en particular\(a \equiv b \Rightarrow ka \equiv kb\). Sin embargo, lo contrario no es cierto en general. Así\(2 \times 3 = 4 \times 3\) (mod 6) no implica\(2 \equiv 4\) (mod 6). Sin embargo, si\((k, m) = 1\) lo que\(ka \equiv kb\) implica\(a \equiv b\).

Otro resultado importante es el siguiente.

Teorema

Si\(a_1, a_2, ..., a_{\varphi(m)}\) forman un completo sistema de residuos mod\(m\) entonces también lo hace\(aa_1\),\(aa_2\),...,\(aa_{\varphi(m)}\) siempre que\((a, m) = 1\).

Prueba

Tenemos\(\varphi(m)\) residuos. Si dos de ellos son congruentes\(aa_i \equiv aa_j\),\(a(a_i - a_j) \equiv 0\). Pero\((a, m) = 1\) para eso\(a_i \equiv a_j\).

Una aplicación de estas ideas es al importante teorema de Euler:

Teorema

Si\((a, m) = 1\) entonces\(a^{\varphi(m)} \equiv 1\) (mod\(m\)).

Prueba

Ya que\(a_1, a_2, ..., a_{\varphi(m)}\) son congruentes a\(aa_1\)\(aa_2\),,..., en\(aa_{\varphi(m)}\) cierto orden, sus productos son congruentes. De ahí

\(a^{\varphi(m)} a_1 a_2 \cdot\cdot\cdot a_{\varphi(m)} \equiv a_1 a_2 \cdot\cdot\cdot a_{\varphi(m)}\)

y el resultado sigue.

Un caso especial de primordial importancia es el\(m = p\) caso en el que tenemos

\((a, p) = 1 \Longrightarrow a^{p - 1} \equiv 1\)(mod\(p\))

Multiplicando por\(a\) tenemos para todos los casos\(a^p \equiv a\) (mod\(p\)). Otra prueba de este resultado va por inducción\(a\); tenemos

\((a + 1)^p = a^p + {p \choose 1} a^{p - 1} + \cdot\cdot\cdot + 1 \equiv a^p \equiv a\)(mod\(p\))

También se podría utilizar el teorema multinomial y considerar\((1 + 1 + \cdot\cdot\cdot + 1)^p\).

Otra prueba más va al considerar el número de\(p\) -gones convexos regulares donde cada borde puede ser coloreado en uno de unos colores. El número de tales polígonos es\(a^p\), de los cuales a son monocromáticos. De ahí\(a^p − a\) que no sean monocromáticos y estos vienen en conjuntos de\(p\) cada uno por rotación a través\(\dfrac{2\pi n}{p}, n = 1,2, ..., p−1\). La idea detrás de esta prueba tiene una aplicabilidad considerable y volveremos a por lo menos otra aplicación un poco más tarde. También dejamos como ejercicio la tarea de encontrar una prueba similar del teorema de Euler.

Los teoremas de Fermat y Euler también pueden verse convenientemente desde un punto de vista teórico grupal. Los números enteros relativamente primos\(m\) y\(< m\) forman un grupo bajo multiplicación mod\(m\). Lo principal a verificar aquí es que cada elemento tiene una inversa en el sistema. Si buscamos una inversa para una formamos\(aa_1, aa_2, ..., aa_{\varphi(m)}\). Ya hemos visto que estos son\(\varphi(m)\) números incongruentes mod\(m\) y relativamente primos a\(m\). Así, una de ellas debe ser la unidad y el resultado sigue.

Ahora recuperamos la prueba de Euler de la de Lagrange que afirma que si\(a\) es un elemento de un grupo\(G\) de orden\(m\), entonces\(a^m = 1\). En nuestro caso esto significa\(a^{\varphi(m)} \equiv 1\) o\(a^{p−1} \equiv 1\) si\(p\) es un prime.

Los enteros bajo\(p\) forman un campo con respecto a + y\(\times\). Muchos de los resultados importantes de la teoría de números se basan en el hecho de que la parte multiplicativa de este grupo (que contiene\(p − 1\) elementos) es cíclica, es decir, existe un número\(g\) (llamado raíz primitiva de\(p\)) tal que\(1 = g^0, g^10,g^2, ... , g^{p−1}\) son incongruentes mod\(p\). Este hecho no es trivial pero omitimos la prueba. Un resultado teórico de grupo más general en el que está contenido establece que cada campo finito es automáticamente abeliano y su grupo multiplicativo es cíclico.

En el anillo de polinomios con coeficientes en un campo se mantienen muchos de los teoremas de la teoría elemental de ecuaciones. Por ejemplo si\(f(x)\) es un polinomio cuyos elementos son clases de residuo mod\(p\) entonces\(f(x) \equiv 0\) (mod\(p\)) tiene como máximo\(p\) soluciones. Además si\(r\) es una raíz entonces\(x − r\) es un factor. Por otro lado, no es cierto que\(f(x) \equiv 0\) (mod\(p\)) tenga al menos una raíz.

Ya que\(x^p − x \equiv 0\) tiene en la mayoría de\(p\) las raíces tenemos la factorización

\(x^p - x \equiv x(x - 1)(x - 2) \cdot\cdot\cdot (x - p + 1)\)(mod\(p\))

Comparando coeficientes de\(x\) tenemos\((p - 1)! \equiv -1\) (mod\(p\)) que es el teorema de Wilson.

Cayley dio una prueba geométrica del teorema de Wilson de la siguiente manera. Considera el número de p-gones dirigidos con vértices de un p-gon regular. (Ver Figura 3.)

Hay\((p - 1)!\) en número de los cuales\(p - 1\) son regulares. De ahí que los no regulares estén\((p - 1)! - (p - 1)\) en número y estos vienen en conjuntos de\(p\) por rotación. De ahí

\((p - 1)! - (p - 1) \equiv 0\)(mod\(p\))

y

\((p - 1)! + 1 \equiv 0\)(mod\(p\))

sigue.

También se puede dar una prueba geométrica que simultáneamente rinde tanto

Los teoremas de Fermat y Wilson y sugerimos como problema encontrar tal prueba.

El teorema de Wilson arroja una condición necesaria y suficiente para la primalidad:\(p\) es primo si y sólo si\((p − 1)! \equiv −1\), pero esto no es un criterio práctico.

Congruencias con Raíces Dadas

Dejar\(a_1\),\(a_2\),...,\(a_k\) ser un conjunto de distintas clases de residuos (mod\(n\)). Si existe un polinomio con coeficientes enteros tales que\(f(x) \equiv 0\) (mod\(m\)) tenga raíces\(a_1\),\(a_2\),...,\(a_k\) y no otros, llamamos a este conjunto compatible (mod\(n\)). Deje que el número de conjuntos compatibles (mod\(n\)) sea denotado por\(C(n)\). Ya que el número de subconjuntos del conjunto que consta de 0, 1, 2,...\(2^n\),\(n - 1\) es, llamamos\(c(n) = \dfrac{C(n)}{2^n}\) al coeficiente de comatiblidad de\(n\).

Si\(n = p\) es un primo entonces la congruencia

\((x - a_1) (x - a_2) \cdot\cdot\cdot (x - a_k) \equiv 0\)(mod\(n\))

tiene precisamente las raíces\(a_1, a_2, ..., a_n\). De ahí\(c(p) = 1\). En un artículo reciente M. M. Chokjnsacka Pnieswaka ha demostrado que\(c(4) = 1\) mientras\(c(n) < 1\) para\(n = 6, 8, 9, 10\). Eso lo demostraremos\(c(n) < 1\) por cada compuesto\(n \ne 4\). También podemos probar que el valor promedio de\(c(n)\) es cero, es decir,

\(\text{lim}_{n \to \infty} \dfrac{1}{n} (c(1) + c(2) + \cdot\cdot\cdot c(n)) = 0\)

Ya que\(c(n) = 1\) para\(n = 1\) y\(n = p\) consideramos solo el caso donde\(n\) es compuesto. Supongamos entonces que la factorización prima única de\(n\) viene dada por\(p_{1}^{\alpha_1} p_{2}^{\alpha_2} \cdot\cdot\cdot\) con

\(p_{1}^{\alpha_1} > p_{2}^{\alpha_2} > \cdot\cdot\cdot\)

Considerar por separado los casos

(1)\(n\) tiene más de un divisor primo, y

(2)\(n = p^{\alpha}, \alpha > 1\).

En caso (1) podemos escribir

\(n = a \cdot b\),\((a, b) = 1, a > b > 1.\)

Ahora lo demostramos si\(f(a) \equiv f(b) \equiv 0\) entonces\(f(0) \equiv 0\).

Comprobante. Vamos\(f(x) = c_0 + c_1 + \cdot\cdot\cdot + c_m x^m\). Entonces

\(0 \equiv af(b) \equiv ac_0\)(mod\(n\)) y

\(0 \equiv bf(a) \equiv bc_0\)(mod\(n\)).

Ahora ya que\((a, b) = 1\) existen\(r\),\(s\), tal\(ar + bs = 1\) que para que\(c_0 (ar + bs) \equiv 0\) y\(c_0 \equiv 0\).

En caso (2) podemos escribir

\(n = p^{\alpha - 1} p.\)

Demostramos eso\(f(p^{\alpha - 1}) \equiv 0\) e\(f(0) \equiv 0\) implicamos\(f(kp^{\alpha - 1} \equiv 0\),\(k = 2, 3, ... .\)

Comprobante. Ya que\(f(0) \equiv 0\), tenemos\(c_0 \equiv 0\),

\(f(x) \equiv c_1 + c_2 x^2 + \cdot\cdot\cdot + c_m x^m\), y

\(f(p^{\alpha - 1}) \equiv c_1 p^{\alpha - 1} \equiv 0\)(mod\(p^{\alpha}\)),

para que\(c_1 \equiv 0\) (mod\(p\)). Pero ahora\(f(kp^{\alpha - 1} \equiv 0\), según se requiera.

Sobre Secuencias Relativamente Primas Formadas por Polinomios Interating (Lambek y Moser)

Bellman ha planteado recientemente el siguiente problema. Si\(p(x)\) es un polinomio irreducible con coeficientes enteros y\(p(x) > x\) para\(x > c\), demostrar que {\(p^n (c)\)} no puede ser primo para todos los grandes\(n\). No nos proponemos resolver este problema sino queremos hacer algunas observaciones.

Si\(p(x)\) es un polinomio con coefcientes enteros, entonces también lo es la\(k^{\text{th}}\) iteración definida recursivamente por\(p^0 (x) = x\),\(p^{p + 1} (x) = p(p^k (x))\). Si\(a\) y\(b\) son enteros entonces

\[p^k (a) \equiv p^k (b)\ \ \ \ (\text{mod }(a - b))\]

En particular para\(a = p^n (c)\) y\(b = 0\) tenemos\(p^{k + n} (c) \equiv p^k (0)\) (mod\(p^n(c)\)).

De ahí

\[(p^{k + n} (c), p^n (c)) = (p^k(0), p^n(c)).\]

Llamaremos a una secuencia {\(a_n\)},\(n \ge 0\), relativamente primo si\((a_m, a_n) = 1\) para todos los valores de\(m, n\), con\(m \ne n\). A partir del 5.2 obtenemos

Teorema 1

{\(p^n (c)\)},\(n \ge 0\), es relativamente primo si y solo si es\((p^k(0), p^n(c)) = 1\) para todos\(k \ge 0\),\(n \ge 0\)

De lo siguiente inmediatamente un resultado de Bellman: Si\(p^k(0) = p(0) \ne 1\) para\(k \ge 1\) y si\((a, p(0)) = 1\) implica\((p(a), p(0)) = 1\) entonces {\(p^n(a)\)},\(n \ge a\) es relativamente primo cuando sea\((c, p(0)) = 1\).

Ahora construiremos todos los polinomios\(p(x)\) para los cuales {\(p^n(c)\)},\(n \ge 0\), es relativamente primo para todos\(c\). Según el Teorema 1,\({p^k(0)} = \pm 1\) para todos\(k \ge 1\), como si se viera fácilmente tomando\(n = k\) y\(c = 0\). Pero entonces {\(p^k(0)\)} debe ser una de las siguientes seis secuencias:

1, 1, 1,...

1, -1, 1,...

1, -1, -1,...

-1, 1, 1,...

-1, 1, -1,...

-1, -1, 1,...

se ve fácilmente que la solución general de\(p(x)\) (con coeficientes enteros) de\(m\) ecuciones

\(p(a_k) = a_{k +1}\),\(k = 0, 1, 2, ..., m - 1.\)

se obtiene a partir de una solución particular de\(p_1 (x)\) la siguiente manera.

\[p(x) = p_1 (x) + (x - a_1) (x - a_2) \cdot\cdot\cdot (x - a_{k - 1}) \cdot Q(x),\]\

donde\(Q(x)\) es cualquier polinomio con coeficientes enteros.

Teorema 2

{\(p^n (c)\)},\(n \ge 0\), es relativamente primo para todos\(c\) si y solo si\(p(x)\) pertenece a una de las siguientes seis clases de polinomios.

\(1 + x (x - 1) \cdot Q(x)\)

\(1 - x - x^2 + x(x^2 - 1) \cdot Q(x)\)

\(1 - 2x^2 + x(x^2 - 1) \cdot Q(x)\)

\(2x^2 - 1 + x(x^2 - 1) \cdot Q(x)\)

\(x^2 - x - 1 + x(x^2 - 1) \cdot Q(x)\)

\(-1 + x(x + 1) \cdot Q(x)\)

Prueba

En vista de (5.3) solo necesitamos verificar que las soluciones particulares producen las seis secuencias dadas anteriormente.

Sobre la distribución de residuos cuadráticos

Un gran segmento de la teoría de números se puede caracterizar considerándolo como el estudio del primer dígito a la derecha de los enteros. Así, un número es divisible por\(n\) si su primer dígito es cero cuando el número se expresa en base\(n\). Dos números son congruentes (mod\(n\)) si sus primeros dígitos son los mismos en base\(n\). La teoría de los residuos cuadráticos se refiere a los primeros dígitos de los cuadrados. De particular interés es el caso donde la base es un primo, y nos limitaremos a este caso.

Si se toma por ejemplo\(p = 7\), entonces con congruencias (mod 7) tenemos\(1^2 \equiv 1 \equiv 6^2\),\(2^2 \equiv 4 \equiv 5^2\), y\(3^2 \equiv 2 \equiv 4^2\); obviamente,\(0^2 \equiv 0\). Así, 1, 2, 4 son cuadrados y 3, 5, 6 son no cuadrados o no residuos. Si\(a\) es un residuo de\(p\) escribimos

\((\dfrac{a}{p}) = + 1\)

mientras que si\(a\) es un no-residuo escribimos

\((\dfrac{a}{p}) = - 1\)

Para\(p\ |\ c\) escribimos\((\dfrac{c}{p}) = 0\). Esta notación se debe a Legendre. Para\(p = 7\) la secuencia\((\dfrac{a}{p})\) es así

+ - + - - -.

\(p = 23\)Porque resulta ser

+ + + - + - + - + - - + - - + - + - - - -.

La situación se aclara si volvemos a adoptar el punto de vista teórico grupal. Las clases de residuo (mod\(p\)) forman un campo, cuyo grupo multiplicativo (que contiene\(p − 1\) elementos) es cíclico. Si\(g\) es un generador de este grupo entonces los elementos pueden ser escritos\(g^1, g^2, ..., g^{p−1} = 1\). Las potencias pares de\(g\) son los residuos cuadráticos; forman un subgrupo de índice dos. Las potencias impares de\(g\) son los no residuos cuadráticos. Desde este punto de vista queda claro

res\(\times\) res = res, res\(\times\) nonres = nonres, nonres\(\times\) nonres = res.

Además 1/\(a\) representa el inverso único de\(a\) (mod\(p\)) y será un residuo o no residuo de acuerdo como un sí mismo es un residuo o no residuo.

El teorema central en la teoría de los residuos cuadráticos y de hecho uno de los resultados más centrales de la teoría de números es la Ley de Reciprocidad Cuadrática probada por primera vez por Gauss alrededor de 1800. Afirma que

Conduce a un algoritmo para decidir el valor de\((\dfrac{p}{q})\).

Se han dado más de 50 pruebas de esta ley incluyendo pruebas recientes de Zassen-haus y de Lehmer. En la primera prueba de Gauss (dio siete) hizo uso del siguiente lema, que nos dice que sólo pudo probar con considerable dificultad. Para\(p = 1\) (mod 4) el menor no residuo de no\(p\) exceda\(2\sqrt{p}+1\). Los resultados que queremos discutir hoy son en parte mejoras de este resultado y más generalmente se preocupan por la distribución de la secuencia de + y −'s in\((\dfrac{a}{p})\),\(a = 1, 2, ..., p − 1\).

En 1839 Dirichlet, como subproducto de su investigación del número de clases de formas cuadráticas, estableció el siguiente teorema: Si\(p \equiv 3\) (mod 4) entonces entre los enteros\(1, 2, ..., \dfrac{p−1}{2}\), hay más residuos que no residuos. Aunque esta es una afirmación elemental sobre los enteros, todas las pruebas publicadas, incluidas las recientes dadas por Chung, Chowla, Whitman, Carlitz y Moser, involucran series de Fourier. Landau estaba bastante ansioso por tener una prueba elemental. Aunque Whitman y Carlitz han dado resultados algo relacionados, el resultado de Dirichlet es bastante aislado. Por lo tanto, no se conoce ningún resultado no trivial similar para otros rangos.

En 1896 Aladow, en 1898 von Sterneck, y en 1906 Jacobsthall, abordaron la cuestión de cuántas veces aparecen las combinaciones ++, +−, −+ y −−−. Mostraron que cada una de las cuatro posibilidades aparecía, como cabría esperar, con frecuencia 1/4. En 1951 Perron volvió a examinar la pregunta y demostró que resultados similares se mantienen si, en lugar de enteros consecutivos, se consideran enteros separados por una distancia\(d\). J. B. Kelly demostró recientemente un resultado que, en términos generales, muestra que los residuos y no residuos se caracterizan por esta propiedad. Jacobsthall también obtuvo resultados parciales para los casos de 3 residuos consecutivos y no residuos. Dejar\(R_n\) y\(N_n\) ser el número de bloques de residuos\(n\) consecutivos y no residuos respectivamente. Uno podría conjeturar eso\(R_n \thicksim N_n \thicksim \dfrac{p}{2^n}\). Entre los que contribuyeron a esta pregunta se encuentran Vandiver, Bennet, Dorge, Hopf, Davenport y A. Brauer. Quizás el resultado más interesante es el de A. Brauer. Demostró eso para\(p > p_0 (n)\),\(R_n > 0\) y\(N_n > 0\). Vamos a esbozar parte de su prueba. Depende de un resultado muy interesante de Van der Waerden (1927). Dado\(k\),\(\ell\), existe un entero\(N = N(k, \ell)\) tal que si uno separa los enteros\(1, 2, ..., N\) en\(k\) clases de cualquier manera, al menos una de las clases contendrá una progresión aritmética de longitud l. Hay una serie de preguntas sin respuesta al respecto teorema al que volveremos en una sección posterior.

Volviendo a la obra de Brauer, demostraremos que demuestra que todos los primos grandes tienen, digamos, 7 residuos consecutivos. Uno separa los números\(1, 2, ..., p − 1\) en 2 clases, residuos y no residuos. Si\(p\) es lo suficientemente grande una de estas clases contendrá, según el teorema de Van der Waerden, 49 términos en progresión aritmética, digamos

\(a, a + b, a + 2b, ..., a + 48b.\)

Ahora si\(\dfrac{a}{b} = c\) entonces tenemos 49 números consecutivos del mismo carácter cuadrático, a saber

\(c, c + 1, c + 2, ..., c + 48.\)

y el resultado es completo.

La prueba de la existencia de no residuos es considerablemente más complicada. Además, es interesante señalar que la existencia de bloques s como + − + − − no\(\cdot\cdot\cdot\) está cubierta por estos métodos.

Volvemos ahora a la pregunta planteada por Gauss. ¿Qué se puede decir sobre el menor no residuo\(n_p\) de un prime? Dado que 1 es un residuo, la pregunta correspondiente sobre los residuos es “¿cuál es el residuo primo más pequeño\(r_p\) de\(p\)?”. Estas preguntas fueron atacadas en la década de 1920 por varios matemáticos entre ellos Nagel, Schur, Polya, Zeitz, Landau, Vandiver, Brauer y Vinogradov. Nagel, por ejemplo, demostró que para\(p \ne 7\), 23,\(n_p < \sqrt{p}\). Polya y Schur demostraron que

\(\sum_{n = a}^{b} (\dfrac{n}{p}) < \sqrt{p} \log p.\)

Esto implica que nunca hay más que residuos\(\sqrt{p} \log p\) consecutivos o no residuos y que varían mucho más que\(\sqrt{p} \log p\) tener aproximadamente tantos residuos como no residuos. Utilizando este resultado y algunos teoremas sobre la distribución de primos, Vinogradov demostró que para\(p > p_0\),

\(n_p < p^{\dfrac{1}{2\sqrt{e}}} \log ^2 p < n^{.303}.\)

Comprobando a través de la prueba de Vinogradov encontramos que por su método el\(p_0\) es excesivamente grande, digamos\(p_0 > 10^{10^{10}}\). Sin embargo, a pesar de numerosos intentos este resultado de Vinogradov no ha mejorado mucho.

En 1938 Erd\(\ddot{o}\) s y Ko mostraron que la existencia de pequeños no residuos estaba íntimamente relacionada con la inexistencia del Algoritmo Euclideo en campos cuadráticos. Esto llevó a Brauer, Hua, Min a reexaminar la cuestión de los límites explícitos para el menor no residuo. Brauer ya en 1928 había demostrado una serie de tales resultados, típico de los cuales es que para todos\(p \equiv 1\) (mod 8),

\(n_p < (2p)^{.4} + 3 (2p)^{.2} + 1\)

y Hua y Min demostraron, por ejemplo, que para\(p > e^{250}\),

\(n_p < (60 \sqrt{p})^{.625}\).

Los primos pequeños (menores de 10,000,000) fueron considerados por Bennet, Chatland, Brauer, Moser y otros.

Muy recientemente, Linnik, Chowla, Erd\(\ddot{o}\) s y Ankeny han aplicado a estos problemas la hipótesis extendida no probada de Riemann. Así, por ejemplo, Ankeny utilizó la hipótesis extendida de Riemann para probarlo\(n_p \ne O(\log ^2 p)\). En sentido contrario Pillai (1945) lo demostró\(p \ne o(\log \log p)\). Usando primero la hipótesis de Riemann, y luego algunos resultados profundos de Linnik sobre primos en progresión aritmética, Friedlander y Chowla mejoraron esto a\(n_p \ne o(\log p)\).

Recientemente ha habido una serie de resultados en una dirección algo diferente de Brauer, Nagel, Skolem, Redei y Kanold. El método de Redei es particularmente interesante. Utiliza un análogo geométrico proyectivo finito del teorema fundamental de Minkowski sobre cuerpos con√vex para demostrar que para\(p \equiv 1\) (mod 4), al menos\(\dfrac{1}{7}\) de los números hasta\(\sqrt{p}\) son residuos y al menos 1 no son residuos. Nuestras propias contribuciones recientes a la teoría van en esta línea. Vamos a esbozar algunos de estos trabajos.

Considera primero la celosía de puntos en un cuadrado de lado\(m\). Buscamos una estimación para\(V(m)\), el número de puntos de celosía visibles en el cuadrado. Al igual que en el párrafo anterior encontramos

\([m]^2 = V(m) + V(\dfrac{m}{2}) + \cdot\cdot\cdot\)

e invertir por la fórmula de inversión de Mobius rinde

\(V(m) = \sum_{d \ge 1} \mu (d) [\dfrac{m}{d}]^2\).

Como antes esto lleva a la estimación asintótica

\(V(m) \thicksim \dfrac{6}{\pi^2} m^2.\)

Sin embargo, podemos obtener estimaciones explícitas para\(v(m)\) también. En efecto, a partir de la fórmula exacta para\(V(m)\) arriba se puede demostrar que para todos\(m\),\(V (m) > .6m^2\). Ahora tomamos\(m = [\sqrt{p}]\). Por razonablemente grande\(p\) tendremos\(V([\sqrt{p}]) > .59m^2\). Ahora con cada punto de celosía visible\((a, b)\) asociamos el número\(\dfrac{a}{b}\) (mod\(p\)). Ahora mostramos que distintos puntos visibles corresponden a números distintos. Por lo tanto si\(\dfrac{a}{b} = \dfrac{c}{d}\) entonces\(ad \equiv bc\). Pero\(ad < p\) y\(bc < p\). De ahí\(ad = bc\) y\(\dfrac{a}{b} = \dfrac{c}{d}\). Sin embargo\((a, b) = (c, d) = 1\) para que\(a = c\) y\(b = d\).

Ya que tenemos al menos .59 números distintos representados por fracciones\(\dfrac{a}{b}\),\(a < \sqrt{p}\),\(b < \sqrt{p}\), al menos .09 de estos corresponderán a no residuos. Si\(R\) denota el número de residuos\(< \sqrt{p}\) y\(N\) el número de no residuos\(< \sqrt{p}\), entonces\(R + N = \sqrt{p}\) y\(2RN > .09p\). Resolver estas desigualdades da\(R, N > .04 \sqrt{p}\). Esto es más débil que el resultado de Nagel pero tiene la ventaja de mantener los primos\(p \equiv 3\) (mod 4) así como\(p \equiv 1\) (mod 4). Así, las excepciones resultan ser sólo los primos 7 y 23. Para primos\(p \equiv 1\) (mod 4), −1 es un no residuo y esto se puede usar junto con el método anterior para obtener resultados más fuertes. También se puede usar la existencia de muchos no residuos <\(\sqrt{p}\) para probar la existencia de un pequeño no residuo, pero los resultados obtenibles de esta manera no son tan fuertes como el resultado de Vinogradov.