Reziduu quadratic

În matematică , mai precis în aritmetica modulară , un număr natural $q$ este un reziduu pătratic modulo $p$ dacă are o rădăcină pătrată în aritmetica modulară a modulului $p$ . Cu alte cuvinte, $q$ este un reziduu pătratic modulo $p$ dacă există un număr întreg $x$ astfel încât:

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

Altfel, spunem că $q$ este un pătratică non-reziduuri modulo $p$

Exemple

De exemplu :

modulul 4, reziduurile pătratice sunt numerele întregi congruente la 2 2 ≡ 0 2 = 0 sau la (± 1) 2 = 1 prin urmare, non-reziduurile pătratice sunt cele congruente la 2 sau 3;
modulul 2, orice număr întreg este un reziduu pătratic;
modulo p , orice multiplu al lui p este un reziduu pătratic. Din acest motiv, unii autori exclud multiplii lui p din definiție și chiar impun ca p și q să fie coprimi .

Modulo orice număr întreg

Modulo un număr întreg $n > 0$ , clasa lui $x$ 2 depinde doar de cea a lui $x$ , deci reziduurile pătratice sunt resturile obținute în diviziunea euclidiană a lui $x$ 2 cu $n,$ variind $x$ în sau în orice set de $n$ numere întregi consecutive, ca ( adică d. dacă $n$ este par și dacă $n$ este impar). ${\ 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 \}}$

Ne putem limita chiar și la , de vreme ce . ${\ displaystyle x \ in \ left \ {0,1, ..., \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor \ right \}}$ ${\ displaystyle \ left (-x \ right) ^ {2} = x ^ {2}}$

De asemenea, 0 și 1 sunt întotdeauna reziduuri pătratice.

Exemplu:

Tabelul de mai jos al modulo 10 reziduale pătratice arată bine simetria și arată că ne putem limita la . ${\ 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}}}

Fie $a$ și $b$ două numere întregi prime între ele. Un număr întreg $x$ este un rest pătratic $mod ab$ dacă (și, desigur , numai dacă) este un rest pătratic de ambele $mod$ $a$ și $mod$ $b$ . $X$

Demonstrație

Dacă și , să fie (prin teorema chineză Remainder ) un număr întreg astfel încât și . Apoi și , prin urmare, (prin lema lui Gauss ) . ${\ displaystyle x \ equiv u ^ {2} {\ bmod {a}}}$ ${\ displaystyle x \ equiv v ^ {2} {\ bmod {b}}}$ $w$ ${\ 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}}}$

Această proprietate face posibilă reducerea determinării reziduurilor pătratice modulo orice număr întreg la cea a reziduurilor modulo puterile numerelor prime care apar în descompunerea sa .

Modulo un număr prim impar

Fie $p$ un număr prim impar. Pentru orice număr întreg $n$ , simbolul Legendre $( n / p )$ merită, prin definiție:

{\ displaystyle \ left ({\ frac {n} {p}} \ right) = {\ begin {cases} \; \; \, 0 & {\ text {si}} n {\ text {este divizibil cu} } p \\ + 1 & {\ text {si}} n {\ text {nu este divizibil cu}} p {\ text {și este un modul de reziduu pătratic}} p \\ - 1 & {\ text {si} } n {\ text {nu este un reziduu pătratic modulo}} p. \ end {cases}}}

Conform criteriului lui Euler , este modulul congruent $p$ la $n ( p -1) / 2$ . Gauss Lema furnizează o altă expresie.

Legea pătratică a reciprocității ne permite să calculăm (–1 / p ), (2 / p ) și, dacă q este un alt număr prim impar, ( q / p ) în funcție de ( p / q ). Oferă, de exemplu, pentru un număr întreg n , un criteriu privind numărul prim p în termeni de clase de congruență modulo 4 n , care determină dacă $n$ este un reziduu pătratic modulo p . Teorema progresiei aritmetice face posibil să se deducă faptul că , dacă $n$ nu este un pătrat perfect , există o infinitate de amorse modulo care $n$ nu este un reziduu pătratică, și că , pentru orice set finit , există o infinitate de numere prime astfel încât fiecare element al este un pătrat . ${\ displaystyle S \ subset \ mathbb {Z}}$ $p$ $S$ ${\ displaystyle {\ bmod {p}}}$

Modulează o putere a unui număr prim

Modulo 2 r cu r ≥ 3, reziduurile pătratice sunt 0 și numerele întregi de forma 4 k (8 m + 1).

Pentru p prim impar, orice număr întreg nedivizibil cu p care este un mod pătrat p este, de asemenea, un mod pătrat p r - într-adevăr, grupul de unități (ℤ / p r ℤ) × al lui ℤ / p r ℤ este ciclic , generat de [α (1 + p ) mod p r ] unde [α mod p ] este un generator de (ℤ / p ℤ) × , sau dacă [(α (1 + p )) s mod p ] = [α s mod p ] este un pătrat, atunci s este egal - iar reziduurile pătratice mod p r sunt p k n cu k ≥ r , sau ( n / p ) = 1 și k pare < r .

Locație

Fie $p$ un număr prim impar. Cel mai mic număr întreg $n$ nu este o pătratice modulo reziduuri $p$ controale și chiar dacă , . ${\ displaystyle n <1 + {\ sqrt {p}}}$ ${\ displaystyle p \ not \ equiv 1 {\ pmod {8}}}$ ${\ displaystyle n <p ^ {\ frac {2} {5}} + 12p ^ {\ frac {1} {5}} + 33}$

Mai general, presupunem că pentru orice , pentru orice număr prim suficient de mare $p$ , acest număr întreg $n$ este mai mic decât . $\ varepsilon> 0$ ${\ displaystyle p ^ {\ varepsilon}}$

Note și referințe

(ro) Acest articol este preluat parțial sau în totalitate din articolul Wikipedia engleză intitulat „ Quadratic residue ” (a se vedea lista autorilor ) .

Gauss , § 96 și 105.
(în) Kenneth Ireland și Michael Rosen , A Classical Introduction to Modern Number Theory , Springer , al. „ GTM ” ( nr . 84);1990( citiți online ) , p. 50.
(în) Steve Wright, Cadratic Residues and Non-Residues: Selected Topics Springer al. „Note de curs în matematică” ( nr . 2171),2016( arXiv 1408.0235 , citiți online ), Teoremele 4.2 și 4.3 și „ Modele de reziduuri pătratice și non-reziduuri pentru infinit multe prime ”, J. Theory Number , vol. 123, n o 1,2007, p. 120-132 ( DOI 10.1016 / j.jnt.2006.06.003 ). Pentru o generalizare simultană a acestor două teoreme, vezi acest exercițiu corectat din lecția „Introducere în teoria numerelor” de pe Wikiversitate .
Pascal Boyer, Micul companion al numerelor și al aplicațiilor lor , Paris, Calvage și Mounet,2019, 648 p. ( ISBN 978-2-916352-75-6 ) , Aritmetica lui ℤ, cap. I.3.2 („Reziduuri cuadratice: aplicații”), p. 47-49.
Pentru o dovadă fără teorema progresiei aritmetice, a se vedea (pentru n ∈ ℕ) Irlanda și Rosen 1990 , p. 57-58 (cap. 5, § 2, th. 3) sau (pentru n ∈ ℤ) această sarcină corectată din lecția „Introducere în teoria numerelor” de pe Wikiversitate .
Cu privire la problemele conexe, a se vedea „ teorema Grunwald-Wang ” și (în) „ Există un număr non-pătrat care este reziduul pătratic al fiecărei prime? » , Pe MathOverflow .
Mai precis, densitatea asimptotică relativă D (în mulțimea numerelor prime) a setului infinit de soluții este diferită de zero și poate fi exprimată simplu: reducem cu ușurință (eliminând din S elementele redundante) la cazul în care produsul elementelor lui S este un pătrat în afară de produsul gol și dovedim că atunci, D = 2 - | S | , folosind versiunea cantitativă a teoremei progresiei aritmetice : vezi Wright 2016 (th. 4.9) sau (en) R. Balasubramanian (en) , F. Luca și R. Thangadurai, „ On the exact degree of over ” , Proc. Amar. Matematica. 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 ), sau dovada (mult mai simplă) a exercițiului corectat pe Wikiversitate deja menționat.

Vezi și tu

Articole similare

linkuri externe

(ro) Eric W. Weisstein , „ Quadratic Residue ” , pe MathWorld
(ro) Walter D. Stangl , „ Counting Squares in ℤ n ” , Math. Mag. , vol. 69, nr . 4,1996, p. 285-289 ( citiți online )
CF Gauss , Arithmetic Research ( citiți online ), § 101 și 102