Residuo cuadrático

Un número entero se denomina residuo de módulo cuadrático si la comparación se puede resolver [1] : $a$ $metro$

x^{2}\equiv a{\pmod {m)).

Si la comparación indicada no se puede resolver, entonces el número se denomina módulo cuadrático sin residuos . Resolver la comparación anterior significa sacar la raíz cuadrada en el anillo de clases de residuos . $a$ $metro$

Los residuos cuadráticos son ampliamente utilizados en teoría de números , también han encontrado aplicaciones prácticas en acústica [2] , criptografía , teoría de grafos (ver gráfico de Paley ) y otros campos de actividad.

El concepto de residuo cuadrático también se puede considerar para un anillo o campo arbitrario . Por ejemplo, residuos cuadráticos en campos finitos .

Diferencias en la terminología

La Enciclopedia Matemática y otras fuentes definen un residuo cuadrático como un número para el cual hay una solución de congruencia . Otras fuentes (por ejemplo, G. Hasse. Lectures on Number Theory, 1953) indican un requisito adicional de que el número es coprimo con . Algunas fuentes generalmente consideran solo el caso de un módulo primo impar [3] [4] . En los dos últimos casos, el cero queda excluido de la consideración. $a$ $x^{2}\equiv a{\pmod {m))$ $a$ $metro$

Ejemplos

Los números y son residuos cuadráticos módulo cualquiera, ya que las congruencias y siempre tienen soluciones y, respectivamente. $un=0$ $un=1$ $x^{2}\equiv 0{\pmod {m))$ $x^{2}\equiv 1{\pmod {m))$ $x=0$ $x=1$

Corolario : dado que solo hay dos clases de residuos para un módulo, y cualquier número de módulo 2 es un residuo cuadrático. $metro=2$ ${\ estilo de visualización [0] _ {2}}$ ${\ estilo de visualización [1] _ {2},}$

Módulo 3, hay tres clases de residuos: Sus cuadrados caen en las clases de residuos , respectivamente. Esto muestra que los números de las clases y son residuos cuadráticos, y los números de la clase (por ejemplo, ) son residuos cuadráticos módulo 3. ${\ estilo de visualización [0]_{3},[1]_{3},[2]_{3}.}$ ${\ estilo de visualización [0]_{3},[1]_{3},[1]_{3))$ ${\ estilo de visualización [0] _ {3}}$ ${\ estilo de visualización [1] _ {3}}$ ${\ estilo de visualización [2] _ {3}}$ $2,5,8,-1,-4\puntos$

La teoría de los residuos cuadráticos se aplica ampliamente, en particular, al estudio de posibles valores enteros de formas cuadráticas . Considere, por ejemplo, la ecuación:

{\ estilo de visualización x^{2}-5y^{2}=3}

De ello se deduce que Sin embargo, los cuadrados de los números dan solo residuos módulo 5 , es decir, 3 es un módulo 5 cuadrático sin residuos. Se sigue que la ecuación anterior no tiene soluciones en números enteros [5] . $x^{2}\equiv 3{\pmod {5)).$ $0.1.2.3.4$ ${\ estilo de visualización 0,1,4;}$

Una comparación de cuadrados general de la forma donde los números son coprimos y no son divisores del módulo se puede investigar de la siguiente manera: se encuentra la solución de la comparación , luego la comparación del cuadrado original se multiplica por para obtener una comparación de la forma: Queda por determinar [6] si es un residuo cuadrático módulo . $hacha^{2}\equiv b{\pmod {m)),$ $a, b$ $metro,$ $un^{{-1}}$ $hacha\equiv 1{\pmod {m)),$ ${\ estilo de visualización a^{-1},}$ $x^{2}\equiv a^{-1}b{\pmod {m)).$ ${\ estilo de visualización a ^ {-1} b}$ $metro$

Propiedades

Criterio de Euler : Que sea simple. Un número con el que es coprimo es un residuo de módulo cuadrático si y solo si [1] : $pag>2$ $pags$ $pags$ $a^{(p-1)/2}\equiv 1\pmod{p},$

y es un módulo p cuadrático sin residuos si y solo si

a^{(p-1)/2}\equiv -1\pmod{p}.

ley cuadrática de reciprocidad
Los residuos cuadráticos relativamente primos al módulo forman un subgrupo multiplicativo del anillo de residuos de índice 2, en particular:
- deducción × deducción = deducción;
- no residuo × residual = no residuo.
- no residuo × no residuo = deducción.

Cantidad

Módulo

Entre los números distintos de cero , para un módulo primo hay residuos y no residuos exactamente cuadráticos . ${\ estilo de visualización 1,2,...,p-1}$ $p\geq3$ $\frac{p-1}{2}$ $\frac{p-1}{2}$

Prueba

Ya que, basta mostrar que entre los números no existen módulos comparables . $x^2 \equiv (px)^2 \pmod{p}$ $0^2, 1^2, 2^2, \puntos, \left({\frac{p-1}{2}}\right)^2$ $pags$

Sea tal número para y . $x^2 \equiv y^2 \pmod{p}$ $x \ no = y$ $0 \le x,y \le \frac{p-1}{2}$

Dado que , entonces y, en vista del hecho de que es simple, y , tenemos , lo cual es imposible porque $p\mid (x^{2}-y^{2})$ $p\mid (xy)(x+y)$ $pags$ $0<|xy|<p$ $p\mid (x+y)$ $x+y \le p-1$

Por lo tanto, los residuos cuadráticos distintos de cero forman un subgrupo de índice 2 en el grupo multiplicativo del anillo . $\mathbb {Z} _{p}$

Módulo arbitrariamente

Walter Stangl introdujo una fórmula en 1996 para calcular el número de residuos cuadráticos módulo arbitrariamente . [7] $norte$

Sea la descomposición canónica del número . Entonces la siguiente fórmula es verdadera para el número de residuos cuadráticos módulo $n = 2^t {p_1}^{d_1} {p_2}^{d_2} \puntos {p_k}^{d_k}$ $norte$ $s(n)$ $norte$

$s(n) = \left\lpiso{\frac{2^{t-1}+5}{3}}\right\rpiso \prod \limits_{i=1}^{k} {\left\lpiso{ \frac{{p_i}^{d_i + 1} + 2 p_i + 2}{2(p_i + 1)}}\right\rpiso}$

Distribución

Cantidad en el intervalo

Sea simple, . Denote por el número de residuos cuadráticos módulo entre los números . $pag>3$ $Q<pag$ ${R_p}(Q)$ $pags$ $1, \puntos, Q$

I. M. Vinogradov demostró que , donde . ${R_p}(Q) = \frac{Q}{2} + \theta \frac{\sqrt{p} \ln{p}}{2}$ $|\theta|<1$

De esto se deduce que en intervalos arbitrarios de longitud suficientemente grande (tal que ) habrá una igualdad asintótica , es decir, los residuos y no residuos cuadráticos serán asintóticamente iguales. $\sqrt{p} \ln{p} = o(Q(p))$ ${R_p}(Q) \sim \frac{Q}{2}$

Módulo sin residuos cuadrático mínimo

Indicar por el mínimo módulo cuadrático positivo sin residuos . $T(p)$ $pags$

De la desigualdad (ver la sección "cantidad en el intervalo"), se sigue directamente que , es decir, . ${R_p}(Q) \le \frac{Q}{2} + \frac{\sqrt{p} \ln{p}}{2}$ ${R_p}(\left\lpiso{\sqrt{p} \ln{p}}\right\rpiso + 1) \le \left\lpiso{\sqrt{p} \ln{p}}\right\rpiso$ $T(p) \le \sqrt{p} \ln{p} + 1$

Como resultado de una investigación más profunda, Vinogradov demostró que . $T(p) \le p^{\frac{1}{2\sqrt{e}}} \left({\log{p}}\right)^2$

Hay una hipótesis propuesta por Vinogradov que . $T(p)=o(p^{\varepsilon}) \para todos \varepsilon > 0$

Si la hipótesis de Riemann es correcta, entonces . $T(p) = O({\ln^2}{p})$

Véase también

Símbolo de Legendre
Consulte la secuencia OEIS A096008 para obtener una lista de residuos cuadráticos.

Notas

↑ 1 2 Enciclopedia Matemática, 1979 , p. 785-786.
↑ Walker, R. El diseño y aplicación de elementos difusores acústicos modulares . Departamento de Investigación de la BBC. Consultado el 25 de octubre de 2016. Archivado desde el original el 27 de marzo de 2016. (indefinido)
↑ Vinogradov, 1952 , Capítulo 5.
↑ MathWorld: residuo cuadrático . Archivado desde el original el 16 de febrero de 2017. (indefinido)
↑ Nesterenko, 2008 , pág. 83.
↑ Davenport G. Aritmética superior. Introducción a la teoría de números.. - M. : Nauka, 1965. - S. 59. - 176 p.
↑ Stangl, Walter D. (octubre de 1996), Counting Squares in ℤ n , Mathematics Magazine , volumen 69 (4): 285–289, doi : 10.2307/2690536 , < http://www.maa.org/sites/default /files/Walter_D22068._Stangl.pdf > Archivado el 24 de diciembre de 2015 en Wayback Machine .

Literatura

Vinogradov I.M. Fundamentos de la teoría de números . - M. - L. : GITTL, 1952. - 180 p.
Residuo cuadrático // Enciclopedia matemática (en 5 volúmenes). - M .: Enciclopedia soviética , 1979. - T. 2.
Nesterenko Y. V. Teoría de los números. - M. : Centro Editorial "Academia", 2008. - S. 132-133. — 272 págs. — ISBN 9785769546464 .