Residuo quadratico
In matematica , più precisamente in aritmetica modulare , un numero naturale q è un quadratico residuo modulo p se ha una radice quadrata in aritmetica modulare di modulo p . In altre parole, q è un residuo quadratico modulo p se esiste un intero x tale che:
X2≡q(modp){\ displaystyle {x ^ {2}} \ equiv q {\ pmod {p}}}.
Altrimenti, diciamo che q è un non residuo quadratico modulo p
Esempi
Per esempio :
- modulo 4, i residui quadratici sono gli interi congruenti a 2 2 ≡ 0 2 = 0 oppure a (± 1) 2 = 1 quindi i non residui quadratici sono quelli congruenti a 2 o 3;
- modulo 2, qualsiasi numero intero è un residuo quadratico;
- modulo p , qualsiasi multiplo di p è un residuo quadratico. Per questo motivo, alcuni autori escludono i multipli di p dalla definizione e persino impongono che p e q BE coprimi .
Modulo qualsiasi numero intero
Modulo un intero n > 0 , la classe di x 2 dipende solo da quella di x , quindi i residui quadratici sono i resti ottenuti nella divisione euclidea di x 2 per n variando x in , o in qualsiasi insieme di n numeri interi consecutivi, like ( cioè d. se n è pari e se n è dispari).
{0,1,...,non-1}{\ displaystyle \ sinistra \ {0,1, \ punti, n-1 \ destra \}}{⌊-non2⌋+1,⌊-non2⌋+2,...,⌊non2⌋}{\ 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 \}} {-non2+1,...,non2}{\ displaystyle \ left \ {- {\ frac {n} {2}} + 1, \ dots, {\ frac {n} {2}} \ right \}}{-non-12,...,non-12}{\ displaystyle \ left \ {- {\ frac {n-1} {2}}, \ dots, {\ frac {n-1} {2}} \ right \}}
Possiamo anche limitarci a , da allora .
X∈{0,1,...,⌊non2⌋}{\ Displaystyle x \ in \ left \ {0,1, ..., \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor \ right \}}(-X)2=X2{\ displaystyle \ sinistra (-x \ destra) ^ {2} = x ^ {2}}
Inoltre, 0 e 1 sono sempre residui quadratici.
Esempio:
La tabella seguente dei residui quadratici modulo 10 mostra bene la simmetria e mostra che possiamo limitarci a .
X∈{0,1,...,5}{\ displaystyle x \ in \ {0,1, ..., 5 \}}
X-4-3-2-1012345X26941014965{\ 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}}}
Lasciate un e B siano due interi privilegiata tra di loro. Un intero x è un residuo quadratico mod ab se (e ovviamente solo se) è un residuo quadratico sia di mod a che di mod b .
X{\ displaystyle x}
Dimostrazione
Se e , sia (per il Teorema cinese del resto ) un numero intero tale che e . Allora, e quindi (dal lemma di Gauss ) .
X≡u2moda{\ Displaystyle x \ equiv u ^ {2} {\ bmod {a}}}X≡v2modb{\ Displaystyle x \ equiv v ^ {2} {\ bmod {b}}}w{\ displaystyle w}w≡umoda{\ Displaystyle w \ equiv u {\ bmod {a}}}w≡vmodb{\ Displaystyle w \ equiv v {\ bmod {b}}}X≡w2moda{\ Displaystyle x \ equiv w ^ {2} {\ bmod {a}}}X≡w2modb{\ Displaystyle x \ equiv w ^ {2} {\ bmod {b}}}X≡w2modab{\ Displaystyle x \ equiv w ^ {2} {\ bmod {ab}}}
Questa proprietà permette di ridurre la determinazione dei residui quadratici modulo qualsiasi intero a quella dei residui modulo le potenze dei numeri primi che compaiono nella sua scomposizione .
Modulo un numero primo dispari
Sia p un numero primo dispari. Per ogni numero intero n , il simbolo di Legendre ( n / p ) vale, per definizione:
(nonp)={0 Se non è divisibile per p+1 Se non non è divisibile per p ed è un residuo quadratico modulo p-1 Se non non è un residuo modulo quadratico p.{\ displaystyle \ left ({\ frac {n} {p}} \ right) = {\ begin {case} \; \; \, 0 & {\ text {si}} n {\ text {è divisibile per} } p \\ + 1 & {\ text {si}} n {\ text {non è divisibile per}} p {\ text {ed è un residuo quadratico modulo}} p \\ - 1 & {\ text {si} } n {\ text {non è un residuo quadratico modulo}} p. \ end {cases}}}Secondo il criterio di Eulero , è congruente modulo p per n ( p -1) / 2 . Il lemma di Gauss fornisce un'altra espressione.
La legge quadratica della reciprocità ci permette di calcolare (–1 / p ), (2 / p ) e, se q è un altro numero primo dispari, ( q / p ) in funzione di ( p / q ). Fornisce ad esempio, per un dato intero n , un criterio sul numero primo p in termini di classi di congruenza modulo 4 n , che determina se n è un residuo quadratico modulo p . Il teorema della progressione aritmetica permette di dedurre che se n non è un quadrato perfetto , esiste un'infinità di numeri primi modulo che n non è un residuo quadratico, e che per ogni insieme finito esiste un'infinità di numeri primi tale che ogni elemento di è un quadrato .
S⊂Z{\ displaystyle S \ subset \ mathbb {Z}}p{\ displaystyle p}S{\ displaystyle S}modp{\ displaystyle {\ bmod {p}}}
Modulo 2 r con r ≥ 3, i residui quadratici sono 0 e gli interi della forma 4 k (8 m + 1).
Per p primo dispari, qualsiasi numero intero non divisibile per p che è un quadrato mod p è anche un quadrato mod p r - infatti, il gruppo di unità (ℤ / p r ℤ) × di ℤ / p r ℤ è ciclico , generato da [α (1 + p ) mod p r ] dove [α mod p ] è un generatore di (ℤ / p ℤ) × , o se [(α (1 + p )) s mod p ] = [α s mod p ] è un quadrato allora s è pari - e i residui quadratici mod p r sono p k n con k ≥ r , o ( n / p ) = 1 e k anche < r .
Posizione
Sia p un numero primo dispari. Il più piccolo intero n non è un quadratiche rollover residuo p controlli e anche se , .
non<1+p{\ displaystyle n <1 + {\ sqrt {p}}}p≢1(mod8){\ displaystyle p \ not \ equiv 1 {\ pmod {8}}}non<p25+12p15+33{\ displaystyle n <p ^ {\ frac {2} {5}} + 12p ^ {\ frac {1} {5}} + 33}
Più in generale, ipotizziamo che per ogni cosa , per ogni numero primo p sufficientemente grande, questo intero n sia minore di .
ε>0{\ displaystyle \ varepsilon> 0}pε{\ displaystyle p ^ {\ varepsilon}}
Note e riferimenti
(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in
inglese intitolato
" Quadratic residue " ( vedere l'elenco degli autori ) .
-
Gauss , § 96 e 105.
-
(in) Kenneth Ireland e Michael Rosen , A Classical Introduction to Modern Number Theory , Springer , al. " GTM " ( n . 84);1990( leggi in linea ) , p. 50.
-
(in) Steve Wright, Quadratic Residues and Non-Residues: Selected Topics Springer al. "Appunti di matematica" ( n o 2171),2016( arXiv 1408.0235 , leggi online ), Teoremi 4.2 e 4.3, e " Modelli di residui quadratici e non residui per infinitamente molti numeri primi ", J. Teoria dei numeri , vol. 123, n o 1,2007, p. 120-132 ( DOI 10.1016 / j.jnt.2006.06.003 ). Per una generalizzazione simultanea di questi due teoremi, vedere questo esercizio corretto dalla lezione "Introduzione alla teoria dei numeri" su Wikiversità .
-
Pascal Boyer, Piccolo compagno dei numeri e delle loro applicazioni , Parigi, Calvage e Mounet,2019, 648 p. ( ISBN 978-2-916352-75-6 ) , Aritmetica di ℤ, cap. I.3.2 ("Residui quadratici: applicazioni"), p. 47-49.
-
Per una dimostrazione senza il teorema della progressione aritmetica, vedere (per n ∈ ℕ) Irlanda e Rosen 1990 , p. 57-58 (cap. 5, § 2, th. 3) o (per n ∈ ℤ) questo compito corretto dalla lezione "Introduzione alla teoria dei numeri" su Wikiversità .
-
Su questioni correlate, vedi " teorema Grunwald-Wang " e (in) " Esiste un numero non quadrato, qui è il residuo quadratico di ogni premio? » , Su MathOverflow .
-
Più precisamente, la densità asintotica relativa D (nell'insieme dei numeri primi) dell'insieme infinito di soluzioni è diversa da zero e può essere espressa semplicemente: riduciamo facilmente (rimuovendo da S gli elementi ridondanti) al caso in cui no il prodotto degli elementi di S è un quadrato separato dal prodotto vuoto , e dimostriamo che allora D = 2 - | S | , usando la versione quantitativa del teorema della progressione aritmetica : vedi Wright 2016 (th. 4.9) o (en) R. Balasubramanian (en) , F. Luca e R. Thangadurai, “ On the exact degree of over » , Proc. Amaro. Matematica. Soc. , vol. 138,p{\ displaystyle p} Q(a1,a2,...,aℓ){\ displaystyle \ mathbb {Q} ({\ sqrt {a_ {1}}}, {\ sqrt {a_ {2}}}, \ ldots, {\ sqrt {a _ {\ ell}}})}Q{\ displaystyle \ mathbb {Q}}2010, p. 2283-2288 ( DOI 10.1090 / S0002-9939-10-10331-1 ), oppure la prova (molto più semplice) dell'esercizio corretto su Wikiversità già citato.
Vedi anche
Articoli Correlati
link esterno
- (it) Eric W. Weisstein , " Quadratic Residue " , su MathWorld
- (en) Walter D. Stangl , " Conteggio dei quadrati in ℤ n " , Matematica. Mag. , vol. 69, n o 4,1996, p. 285-289 ( leggi in linea )
-
CF Gauss , Arithmetic Research ( leggi online ), § 101 e 102
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">