Resíduo quadrático

Em matemática , mais precisamente na aritmética modular , um número natural $q$ é um resíduo quadrático módulo $p$ se ele tem uma raiz quadrada na aritmética modular de módulo $p$ . Em outras palavras, $q$ é um resíduo quadrático módulo $p$ se existe um inteiro $x$ tal que:

{\ displaystyle {x ^ {2}} \ equiv q {\ pmod {p}}}

Caso contrário, dizemos que $q$ é um módulo não residual quadrático $p$

Exemplos

Por exemplo :

módulo 4, os resíduos quadráticos são os inteiros congruentes a 2 2 ≡ 0 2 = 0 ou a (± 1) 2 = 1, portanto, os não resíduos quadráticos são aqueles congruentes a 2 ou 3;
módulo 2, qualquer número inteiro é um resíduo quadrático;
módulo p , qualquer múltiplo de p é um resíduo quadrático. Por esse motivo, alguns autores excluem os múltiplos de p da definição e até impõem que p e q sejam coprimos .

Módulo qualquer inteiro

Módulo um inteiro $n > 0$ , a classe de $x$ 2 depende apenas daquela de $x$ , então os resíduos quadráticos são os restos obtidos na divisão euclidiana de $x$ 2 por $n$ variando $x$ em , ou em qualquer conjunto de $n$ inteiros consecutivos, como ( ou seja, d. se $n$ for par e se $n$ for ímpar). ${\ displaystyle \ left \ {0,1, \ dots, n-1 \ right \}}$ ${\ displaystyle \ left \ {\ left \ lfloor {\ frac {-n} {2}} \ right \ rfloor +1, \ left \ lfloor {\ frac {-n} {2}} \ right \ rfloor +2 , \ dots, \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor \ right \}}$ ${\ displaystyle \ left \ {- {\ frac {n} {2}} + 1, \ dots, {\ frac {n} {2}} \ right \}}$ ${\ displaystyle \ left \ {- {\ frac {n-1} {2}}, \ dots, {\ frac {n-1} {2}} \ right \}}$

Podemos até nos limitar a , desde então . ${\ displaystyle x \ in \ left \ {0,1, ..., \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor \ right \}}$ ${\ displaystyle \ left (-x \ right) ^ {2} = x ^ {2}}$

Além disso, 0 e 1 são sempre resíduos quadráticos.

Exemplo:

A tabela abaixo de resíduos quadráticos do módulo 10 mostra bem a simetria e mostra que podemos nos restringir a . ${\ displaystyle x \ in \ {0,1, ..., 5 \}}$

{\ displaystyle {\ begin {array} {| c | c | c | c || c | c | c |} x & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\\ hline x ^ {2} & {\ color {magenta} 6} & {\ color {cyan} 9} & {\ color {blue} 4} & {\ color {green} 1} & {\ color {red} 0} & {\ color {green} 1} & {\ color {blue} 4} & {\ color {cyan} 9} & {\ color {magenta} 6} & {\ color {brown} 5 } \ end {array}}}

Deixe $um$ e $B Seja$ dois inteiros privilegiada entre eles. Um inteiro $x$ é um resíduo quadrático $mod ab$ se (e, claro, somente se) é um resíduo quadrático de ambos $mod$ $a$ e $mod$ $b$ . $x$

Demonstração

Se e , seja (pelo Teorema do Restante Chinês ) um inteiro tal que e . Então, e portanto (pelo lema de Gauss ) . ${\ displaystyle x \ equiv u ^ {2} {\ bmod {a}}}$ ${\ displaystyle x \ equiv v ^ {2} {\ bmod {b}}}$ $C$ ${\ displaystyle w \ equiv u {\ bmod {a}}}$ ${\ displaystyle w \ equiv v {\ bmod {b}}}$ ${\ displaystyle x \ equiv w ^ {2} {\ bmod {a}}}$ ${\ displaystyle x \ equiv w ^ {2} {\ bmod {b}}}$ ${\ displaystyle x \ equiv w ^ {2} {\ bmod {ab}}}$

Esta propriedade permite reduzir a determinação dos resíduos quadráticos do módulo qualquer inteiro à dos resíduos do módulo das potências dos números primos que aparecem na sua decomposição .

Módulo, um número primo ímpar

Seja $p$ um número primo ímpar. Para qualquer número inteiro $n$ , o símbolo de Legendre $( n / p )$ vale, por definição:

{\ displaystyle \ left ({\ frac {n} {p}} \ right) = {\ begin {cases} \; \; \, 0 & {\ text {si}} n {\ text {é divisível por} } p \\ + 1 & {\ text {si}} n {\ text {não é divisível por}} p {\ text {e é um módulo de resíduo quadrático}} p \\ - 1 & {\ text {si} } n {\ text {não é um módulo de resíduo quadrático}} p. \ end {casos}}}

De acordo com o critério de Euler , é congruente módulo $p$ a $n ( p -1) / 2$ . O lema de Gauss fornece outra expressão.

A lei quadrática da reciprocidade nos permite calcular (-1 / p ), (2 / p ) e, se q for outro número primo ímpar, ( q / p ) como uma função de ( p / q ). Ele fornece, por exemplo, para um dado inteiro n , um critério sobre o número primo p em termos de classes de congruência do módulo 4 n , que determina se $n$ é um resíduo quadrático do módulo p . O teorema da progressão aritmética permite deduzir que se $n$ não é um quadrado perfeito , existe uma infinidade de módulos primos em que $n$ não é um resíduo quadrático, e que para qualquer conjunto finito existe uma infinidade de números primos tais que cada elemento de é um quadrado . ${\ displaystyle S \ subset \ mathbb {Z}}$ $p$ $S$ ${\ displaystyle {\ bmod {p}}}$

Módulo, uma potência de um número primo

Módulo 2 r com r ≥ 3, os resíduos quadráticos são 0 e os inteiros da forma 4 k (8 m + 1).

Para p número ímpar, qualquer inteiro não divisível por p que é um quadrado mod p também é um quadrado mod p r - de fato, o grupo de unidades (ℤ / p r ℤ) × de ℤ / p r ℤ é cíclico , gerado por [α (1 + p ) mod p r ] onde [α mod p ] é um gerador de (ℤ / p ℤ) × , ou if [(α (1 + p )) s mod p ] = [α s mod p ] é um quadrado, então s é par - e os resíduos quadráticos mod p r são os p k n com k ≥ r , ou ( n / p ) = 1 e k par < r .

Localização

Seja $p$ um número primo ímpar. O número inteiro menor $n$ não é um resíduo quadráticas modulo $p$ controlos e mesmo se , . ${\ displaystyle n <1 + {\ sqrt {p}}}$ ${\ displaystyle p \ not \ equiv 1 {\ pmod {8}}}$ ${\ displaystyle n <p ^ {\ frac {2} {5}} + 12p ^ {\ frac {1} {5}} + 33}$

De maneira mais geral, conjecturamos que para tudo , para qualquer número primo $p$ suficientemente grande, esse inteiro $n$ é menor que . $\ varejpsilon> 0$ ${\ displaystyle p ^ {\ varepsilon}}$

Notas e referências

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado " Resíduo quadrático " ( veja a lista de autores ) .

Gauss , § 96 e 105.
(em) Kenneth Ireland e Michael Rosen , A Classical Introduction to Modern Number Theory , Springer , al. " GTM " ( n o 84);1990( leia online ) , p. 50.
(in) Steve Wright, Quadratic Residues and Non-Residues: Selected Topics Springer al. "Lecture Notes in Mathematics" ( n S 2171),2016( arXiv 1408.0235 , leia online ), Teoremas 4.2 e 4.3, e “ Padrões de resíduos e não-resíduos quadráticos para infinitamente muitos primos ”, J. Teoria dos Números , vol. 123, n o 1,2007, p. 120-132 ( DOI 10.1016 / j.jnt.2006.06.003 ). Para uma generalização simultânea desses dois teoremas, consulte este exercício corrigido da lição "Introdução à teoria dos números" na Wikiversidade .
Pascal Boyer, pequena companheira de números e suas aplicações , Paris, Calvage e Mounet,2019, 648 p. ( ISBN 978-2-916352-75-6 ) , Arithmetic of ℤ, cap. I.3.2 (“Resíduos quadráticos: aplicações”), p. 47-49.
Para uma prova sem o teorema da progressão aritmética, consulte (para n ∈ ℕ) Ireland e Rosen 1990 , p. 57-58 (cap. 5, § 2, th. 3) ou (para n ∈ ℤ) esta atribuição corrigida da lição “Introdução à teoria dos números” na Wikiversidade .
Sobre questões relacionadas, consulte " teorema Grunwald-Wang " e (em) " Existe um número não quadrado qui é o resíduo quadrático de todo prêmio? » , No MathOverflow .
Mais precisamente, a densidade assintótica relativa D (no conjunto dos números primos) do conjunto infinito de soluções é diferente de zero e pode ser expressa de forma simples: reduzimos facilmente (removendo de S os elementos redundantes) para o caso em que não produto dos elementos de S é um quadrado separado do produto vazio , e provamos que então, D = 2 - | S | , usando a versão quantitativa do teorema da progressão aritmética : ver Wright 2016 (th. 4.9) ou (en) R. Balasubramanian (en) , F. Luca e R. Thangadurai, “ On the exact degree of over ” , Proc. Amargo. Matemática. Soc. , vol. 138, $p$ ${\ displaystyle \ mathbb {Q} ({\ sqrt {a_ {1}}}, {\ sqrt {a_ {2}}}, \ ldots, {\ sqrt {a _ {\ ell}}})}$ $\ mathbb {Q}$ 2010, p. 2283-2288 ( DOI 10.1090 / S0002-9939-10-10331-1 ), ou a prova (muito mais simples) do exercício corrigido na Wikiversidade já mencionado.

Veja também

links externos

(en) Eric W. Weisstein , “ Quadratic Residue ” , em MathWorld
(pt) Walter D. Stangl , " Counting Squares in ℤ n " , Math. Mag. , vol. 69, n o 4,1996, p. 285-289 ( ler online )
CF Gauss , Arithmetic Research ( leia online ), § 101 e 102