Reszta kwadratowa
W matematyce , a dokładniej w arytmetyce modularnej , liczba naturalna q jest kwadratową resztą modulo p, jeśli ma pierwiastek kwadratowy w arytmetyce modularnej modułu p . Innymi słowy, q jest kwadratową resztą modulo p, jeśli istnieje liczba całkowita x taka, że:
x2≡q(modp){\ Displaystyle {x ^ {2}} \ equiv q {\ pmod {p}}}![{\ Displaystyle {x ^ {2}} \ equiv q {\ pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/148251f0996fa22d562d122226cb74367e332b3d)
.
W przeciwnym razie mówimy, że q jest kwadratowym nieresztynowym modulo p
Przykłady
Na przykład :
- modulo 4, reszty kwadratowe są liczbami całkowitymi przystającymi do 2 2 ≡ 0 2 = 0 lub do (± 1) 2 = 1, zatem niereszty kwadratowe są przystające do 2 lub 3;
- modulo 2, dowolna liczba całkowita jest resztą kwadratową;
- modulo p , dowolna wielokrotność p jest resztą kwadratową. Z tego powodu niektórzy autorzy wykluczają wielokrotności p z definicji, a nawet narzucają, że p i q są względnie pierwsze .
Modulo dowolna liczba całkowita
Modulo an integer n > 0 , klasa x 2 zależy tylko od klasy x , więc reszty kwadratowe są resztami otrzymanymi z dzielenia euklidesowego x 2 przez n przez zmianę x in lub w dowolnym zbiorze n kolejnych liczb całkowitych, jak ( tj. d. jeśli n jest parzyste i jeśli n jest nieparzyste).
{0,1,...,nie-1}{\ Displaystyle \ lewo \ {0,1, \ kropki, n-1 \ prawo \}}
{⌊-nie2⌋+1,⌊-nie2⌋+2,...,⌊nie2⌋}{\ Displaystyle \ lewo \ {\ lewo \ lfloor {\ Frac {-n} {2}} \ prawo \ rfloor +1, \ lewo \ lfloor {\ Frac {-n} {2}} \ prawo \ rfloor +2 , \ dots, \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor \ right \}}
{-nie2+1,...,nie2}{\ Displaystyle \ lewo \ {- {\ Frac {n} {2}} + 1, \ kropki, {\ Frac {n} {2}} \ prawo \}}
{-nie-12,...,nie-12}{\ Displaystyle \ lewo \ {- {\ Frac {n-1} {2}}, \ kropki, {\ Frac {n-1} {2}} \ prawo \}}![{\ Displaystyle \ lewo \ {- {\ Frac {n-1} {2}}, \ kropki, {\ Frac {n-1} {2}} \ prawo \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca44f6882de360c30838abac5e72d011303c0731)
Możemy nawet ograniczać się do , ponieważ .
x∈{0,1,...,⌊nie2⌋}{\ Displaystyle x \ in \ lewo \ {0,1, ..., \ lewo \ lfloor {\ Frac {n} {2}} \ prawo \ rfloor \ prawo \}}
(-x)2=x2{\ Displaystyle \ lewo (-x \ prawej) ^ {2} = x ^ {2}}![{\ Displaystyle \ lewo (-x \ prawej) ^ {2} = x ^ {2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d10284cc18c947e3c4831752edd47aa826ee60c4)
Ponadto 0 i 1 są zawsze resztami kwadratowymi.
Przykład:
Poniższa tabela z resztami kwadratowymi modulo 10 dobrze pokazuje symetrię i pokazuje, że możemy się do tego ograniczyć .
x∈{0,1,...,5}{\ Displaystyle x \ in \ {0,1, ..., 5 \}}![{\ Displaystyle x \ in \ {0,1, ..., 5 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe9e3bdb20bf49d21307ccd17d93cd938c34957e)
x-4-3-2-1012345x26941014965{\ Displaystyle {\ początek {tablica} {| 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 {cyjan} 9} & {\ color {blue} 4} & {\ color {green} 1} & {\ color {red} 0} & {\ color {green} 1} & {\ color {blue} 4} & {\ color {cyjan} 9} & {\ color {magenta} 6} & {\ color {brown} 5 } \ end {tablica}}}
Niech a i b będą dwiema liczbami całkowitymi pierwszymi między nimi. Liczba całkowita x jest kwadratową resztą mod ab, jeśli (i oczywiście tylko wtedy, gdy) jest kwadratową resztą zarówno mod a, jak i mod b .
x{\ displaystyle x}![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
Demonstracja
Jeśli i , niech (według chińskiego twierdzenia o resztach ) będzie liczbą całkowitą taką, że i . Wtedy i dlatego (według lematu Gaussa ) .
x≡u2modw{\ Displaystyle x \ equiv u ^ {2} {\ bmod {a}}}
x≡v2modb{\ Displaystyle x \ equiv v ^ {2} {\ bmod {b}}}
w{\ displaystyle w}
w≡umodw{\ displaystyle w \ equiv u {\ bmod {a}}}
w≡vmodb{\ displaystyle w \ equiv v {\ bmod {b}}}
x≡w2modw{\ Displaystyle x \ equiv w ^ {2} {\ bmod {a}}}
x≡w2modb{\ Displaystyle x \ equiv w ^ {2} {\ bmod {b}}}
x≡w2modwb{\ Displaystyle x \ equiv w ^ {2} {\ bmod {ab}}}![{\ Displaystyle x \ equiv w ^ {2} {\ bmod {ab}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00bb4b72f22aa7a68c0769ca16afa7e2eb124773)
Właściwość ta pozwala zredukować wyznaczanie reszt kwadratowych modulo dowolną liczbę całkowitą do liczby reszt modulo potęgi liczb pierwszych, które pojawiają się w jego rozkładzie .
Niech p będzie nieparzystą liczbą pierwszą. Dla każdej liczby całkowitej n , o symbolu Legendre'a ( n / s ), to wartość definicji:
(niep)={0 gdyby nie jest podzielna przez p+1 gdyby nie nie jest podzielna przez p i jest kwadratową resztą modulo p-1 gdyby nie nie jest resztą modulo kwadratową p.{\ Displaystyle \ lewo ({\ Frac {n} {p}} \ prawej) = {\ rozpocząć {przypadków} \; \; \, 0 & {\ tekst {si}} n {\ tekst {jest podzielna przez} } p \\ + 1 & {\ text {si}} n {\ text {nie jest podzielne przez}} p {\ text {i jest kwadratową resztą modulo}} p \\ - 1 & {\ text {si} } n {\ text {nie jest kwadratową resztą modulo}} p. \ end {przypadki}}}![{\ Displaystyle \ lewo ({\ Frac {n} {p}} \ prawej) = {\ rozpocząć {przypadków} \; \; \, 0 & {\ tekst {si}} n {\ tekst {jest podzielna przez} } p \\ + 1 & {\ text {si}} n {\ text {nie jest podzielne przez}} p {\ text {i jest kwadratową resztą modulo}} p \\ - 1 & {\ text {si} } n {\ text {nie jest kwadratową resztą modulo}} p. \ end {przypadki}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17bb6f4c8baf68a40ad3bd201ed3d92977f7b3bd)
Zgodnie z kryterium Eulera jest ona przystająca modulo p do n ( p –1) / 2 . Gauss lemat dostarcza inny wyraz.
Kwadratowa prawo wzajemności pozwala na obliczenie (-1 / s ), (2 / s ), a jeśli q jest kolejnym nieparzystą liczbą pierwszą, ( q / p ) jako funkcję ( p / q ). Zapewnia na przykład dla danej liczby całkowitej n kryterium liczby pierwszej p w kategoriach modulo 4 n klas kongruencji , które określa, czy n jest resztą kwadratową modulo p . Twierdzenie arytmetyczny pozwala wywnioskować, że jeśli n nie jest kwadratem , istnieje nieskończona liczba bodźców modulo których n nie jest kwadratowa pozostałości, i że dla każdej skończonego zbioru , istnieje nieskończenie wiele liczb takie, że każdy element jest kwadratem .
S⊂Z{\ displaystyle S \ subset \ mathbb {Z}}
p{\ displaystyle p}
S{\ displaystyle S}
modp{\ displaystyle {\ bmod {p}}}![{\ displaystyle {\ bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1460330b9d39cce63f1625732fd347e4a92fda9)
Modulo 2 r przy r ≥ 3, reszty kwadratowe wynoszą 0, a liczby całkowite postaci 4 k (8 m + 1).
Dla p prime odd, każda liczba całkowita niepodzielna przez p, która jest kwadratem mod p jest również kwadratem mod p r - w rzeczywistości grupa jednostek (ℤ / p r ℤ) × ℤ / p r ℤ jest cykliczna , generowana przez [α (1 + p ) mod p r ] gdzie [α mod p ] jest generatorem (ℤ / p ℤ) × , lub jeśli [(α (1 + p )) s mod p ] = [α s mod p ] jest kwadratem, to s jest parzyste - a resztami kwadratowymi mod p r są p k n przy k ≥ r lub ( n / p ) = 1 i k nawet < r .
Lokalizacja
Niech p będzie nieparzystą liczbą pierwszą. Najmniejsza liczba całkowita N jest kwadratowa pozostałość modulo p kontroli i nawet jeśli , .
nie<1+p{\ displaystyle n <1 + {\ sqrt {p}}}
p≢1(mod8){\ displaystyle p \ not \ equiv 1 {\ pmod {8}}}
nie<p25+12p15+33{\ Displaystyle n <p ^ {\ Frac {2} {5}} + 12p ^ {\ Frac {1} {5}} + 33}![{\ Displaystyle n <p ^ {\ Frac {2} {5}} + 12p ^ {\ Frac {1} {5}} + 33}](https://wikimedia.org/api/rest_v1/media/math/render/svg/463a579243224c58ab37d57e043db0e03dbbb3ca)
Bardziej ogólnie, przypuszczamy, że dla wszystkiego , dla dowolnej wystarczająco dużej liczby pierwszej p , ta liczba całkowita n jest mniejsza niż .
ε>0{\ displaystyle \ varepsilon> 0}
pε{\ displaystyle p ^ {\ varepsilon}}![{\ displaystyle p ^ {\ varepsilon}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10ab6c7633b2292db8a171e02b1075054448b91c)
Uwagi i odniesienia
(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu w
angielskiej Wikipedii zatytułowanego
„ Quadraticaining ” ( patrz lista autorów ) .
-
Gauss , § 96 i 105.
-
(w) Kenneth Ireland i Michael Rosen , Klasyczne wprowadzenie do współczesnej teorii liczb , Springer , al. " GTM " ( N O 84);1990( czytaj online ) , s. 50.
-
(w) Steve Wright, Quadratic Residues and Non-Residues: Wybrane tematy Springer al. "Lecture Notes in matematyki" ( N O 2171),2016( arXiv 1408.0235 , czytaj online ), Twierdzenia 4.2 i 4.3 oraz „ Patterns of kwadratowych reszt i nieresztek dla nieskończenie wielu liczb pierwszych ”, J. Number Theory , tom. 123 n o 1,2007, s. 120-132 ( DOI 10.1016 / j.jnt.2006.06.003 ). Aby uzyskać jednoczesne uogólnienie tych dwóch twierdzeń, zobacz to ćwiczenie poprawione z lekcji „Wprowadzenie do teorii liczb” na Wikiversity .
-
Pascal Boyer, mały towarzysz liczb i ich zastosowań , Paryż, Calvage i Mounet,2019, 648 str. ( ISBN 978-2-916352-75-6 ) , Arytmetyka ℤ, rozdz. I.3.2 („Reszty kwadratowe: zastosowania”), str. 47-49.
-
Dowód bez twierdzenia o arytmetycznej progresji, patrz (dla n ∈ ℕ) Ireland and Rosen 1990 , str. 57-58 (rozdz. 5, § 2, th. 3) lub (dla n ∈ ℤ) to poprawione zadanie z lekcji „Wprowadzenie do teorii liczb” na Wikiversity .
-
W kwestiach pokrewnych patrz „ twierdzenie Grunwalda-Wanga ” i (nie) „ Czy istnieje liczba niekwadratowa, qui jest resztą kwadratową każdej premii? » , W MathOverflow .
-
Dokładniej, względna gęstość asymptotyczna D (w zbiorze liczb pierwszych) nieskończonego zbioru rozwiązań jest różna od zera i można ją wyrazić prosto: łatwo redukujemy (usuwając z S zbędne elementy) do przypadku, w którym nie ma iloczyn elementów S jest kwadratem różnym od iloczynu pustego i udowadniamy wtedy, że D = 2 - | S | , używając ilościowej wersji twierdzenia o postępie arytmetycznym : patrz Wright 2016 (th. 4.9) lub (en) R. Balasubramanian (en) , F. Luca i R. Thangadurai, „ On the exact degree of over ” , Proc. Gorzki. Matematyka. Soc. , vol. 138,p{\ displaystyle p}
Q(w1,w2,...,wℓ){\ displaystyle \ mathbb {Q} ({\ sqrt {a_ {1}}}, {\ sqrt {a_ {2}}}, \ ldots, {\ sqrt {a _ {\ ell}}})}
Q{\ displaystyle \ mathbb {Q}}
2010, s. 2283-2288 ( DOI 10.1090 / S0002-9939-10-10331-1 ), lub dowód (znacznie prostszy) ćwiczenia poprawionego na wspomnianej już Wikiwersytecie .
Zobacz też
Powiązane artykuły
Linki zewnętrzne
- (en) Eric W. Weisstein , „ Quadratic Residue ” , na MathWorld
- (en) Walter D. Stangl , „ Counting Squares in ℤ n ” , Math. Mag. , vol. 69, n o 4,1996, s. 285-289 ( czytaj online )
-
CF Gauss , Arithmetic Research ( czytaj online ), § 101 i 102
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">