Kvadratisk rest

Ett heltal kallas en kvadratisk modulo- rest om jämförelsen är lösbar [1] : $a$ $m$

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

Om den angivna jämförelsen inte går att lösa kallas talet en kvadratisk icke- restmodulo . Att lösa jämförelsen ovan innebär att ta kvadratroten i ringen av restklasser . $a$ $m$

Kvadratiska rester används i stor utsträckning inom talteorin , de har även funnit praktiska tillämpningar inom akustik [2] , kryptografi , grafteori (se Paley-grafen ) och andra verksamhetsområden.

Konceptet med en kvadratisk rest kan också övervägas för en godtycklig ring eller fält . Till exempel kvadratiska rester i finita fält .

Skillnader i terminologi

Mathematical Encyclopedia och ett antal andra källor definierar en kvadratisk rest som ett tal för vilket det finns en kongruenslösning . Andra källor (till exempel G. Hasse. Lectures on Number Theory, 1953) anger ett ytterligare krav på att talet är coprime med . Vissa källor överväger i allmänhet endast fallet med en udda primmodul [ 3] [4] . I båda de senare fallen är noll utesluten från beaktande. $a$ $x^{2}\equiv a{\pmod {m))$ $a$ $m$

Exempel

Siffrorna och är kvadratiska rester modulo någon, eftersom kongruenserna och alltid har lösningar och resp. $a=0$ $a=1$ $x^{2}\equiv 0{\pmod {m))$ $x^{2}\equiv 1{\pmod {m))$ $x=0$ $x=1$

Följd : Eftersom det bara finns två restklasser för en modul, och vilket tal som helst är modulo 2 en kvadratisk rest. $m=2$ $[0]_{2}$ $[1]_{2},$

Modulo 3, det finns tre klasser av rester: Deras kvadrater faller in i klasserna av rester , respektive. Detta visar att siffrorna från klasserna och är kvadratiska rester, och talen från klassen (till exempel ) är kvadratiska icke-rester modulo 3. $[0]_{3},[1]_{3},[2]_{3}.$ ${\displaystyle [0]_{3},[1]_{3},[1]_{3))$ $[0]_{3}$ $[1]_{3}$ $[2]_{3}$ $2,5,8,-1,-4\dots$

Teorin om kvadratiska rester används i stor utsträckning, särskilt för att studera möjliga heltalsvärden av kvadratiska former . Tänk till exempel på ekvationen:

x^{2}-5y^{2}=3

Därav följer att Kvadraterna av siffror ger dock bara rester modulo 5 , det vill säga 3 är en kvadratisk icke-rester modulo 5. Det följer att ovanstående ekvation inte har några lösningar i heltal [5] . $x^{2}\equiv 3{\pmod {5)).$ $0.1.2.3.4$ $0,1,4;$

En generell kvadratjämförelse av formen där talen är coprime och inte är divisorer av modulen kan undersökas enligt följande: lösningen av jämförelsen hittas, sedan multipliceras den ursprungliga kvadratjämförelsen med för att få en jämförelse av formen: Det återstår att bestämma [6] om är en kvadratisk rest modulo . $ax^{2}\equiv b{\pmod {m)),$ $a,b$ $m,$ $a^{{-1}}$ $ax\equiv 1{\pmod {m)),$ $a^{-1},$ $x^{2}\equiv a^{-1}b{\pmod {m)).$ $a^{-1}b$ $m$

Egenskaper

Eulers kriterium : Låt det vara enkelt. Ett nummer ett coprime till är en kvadratisk modulo-rest om och endast om [1] : $p>2$ $sid$ $sid$ $a^{(p-1)/2}\equiv 1\pmod{p},$

och är en kvadratisk icke-rester modulo p om och endast om

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

Kvadratisk lag om ömsesidighet
Kvadratiska rester relativt prime till modulen bildar en multiplikativ undergrupp av restringen av index 2, i synnerhet:
- avdrag × avdrag = avdrag;
- non-residue × residual = icke-rest.
- icke-rester × icke-rester = avdrag.

Kvantitet

Modulo

Bland icke-nolltal finns det för en primmodul exakt kvadratiska rester och icke-rester. $1,2,...,p-1$ $p\geq3$ $\frac{p-1}{2}$ $\frac{p-1}{2}$

Bevis

Eftersom det räcker med att visa att det bland talen inte finns några jämförbara modulo . $x^2 \equiv (px)^2 \pmod{p}$ $0^2, 1^2, 2^2, \dots, \left({\frac{p-1}{2}}\right)^2$ $sid$

Låt det finnas sådana siffror för och . $x^2 \equiv y^2 \pmod{p}$ $x \inte = y$ $0 \le x,y \le \frac{p-1}{2}$

Sedan , då och, med tanke på det faktum att det är enkelt, och , vi har , vilket är omöjligt eftersom $p\mid (x^{2}-y^{2})$ $p\mid (xy)(x+y)$ $sid$ $0<|xy|<s$ $p\mid (x+y)$ $x+y \le p-1$

Sålunda bildar andra kvadratiska rester som inte är noll en undergrupp av index 2 i ringens multiplikativa grupp . $\mathbb {Z} _{p}$

Godtyckligt modulo

Walter Stangl introducerade en formel 1996 för att beräkna antalet kvadratiska rester modulo godtyckligt . [7] $n$

Låta vara den kanoniska uppdelningen av numret . Då gäller följande formel för antalet kvadratiska rester modulo $n = 2^t {p_1}^{d_1} {p_2}^{d_2} \dots {p_k}^{d_k}$ $n$ $s(n)$ $n$

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

Distribution

Kvantitet i intervallet

Låt vara enkelt ,. Beteckna med antalet kvadratiska rester modulo bland talen . $p>3$ $Q<p$ ${R_p}(Q)$ $sid$ $1, \prickar, Q$

I. M. Vinogradov bevisade att , där . ${R_p}(Q) = \frac{Q}{2} + \theta \frac{\sqrt{p} \ln{p}}{2}$ $|\theta|<1$

Det följer av detta att i godtyckliga intervall av tillräckligt stor längd (så att ) kommer det att finnas en asymptotisk likhet , det vill säga kvadratiska rester och icke-rester kommer att vara asymptotiskt lika. $\sqrt{p} \ln{p} = o(Q(p))$ ${R_p}(Q) \sim \frac{Q}{2}$

Minst kvadratiska icke-rester modulo

Beteckna med den minimala positiva kvadratiska icke-restmodulo . $T(p)$ $sid$

Av ojämlikheten (se avsnittet "kvantitet i intervallet") följer direkt att , det vill säga . ${R_p}(Q) \le \frac{Q}{2} + \frac{\sqrt{p} \ln{p}}{2}$ ${R_p}(\left\lfloor{\sqrt{p} \ln{p}}\right\rfloor + 1) \le \left\lfloor{\sqrt{p} \ln{p}}\right\rfloor$ $T(p) \le \sqrt{p} \ln{p} + 1$

Som ett resultat av djupare forskning bevisade Vinogradov att . $T(p) \le p^{\frac{1}{2\sqrt{e}}} \left({\log{p}}\right)^2$

Det finns en hypotes som lagts fram av Vinogradov att . $T(p)=o(p^{\varepsilon}) \forall \varepsilon > 0$

Om Riemanns hypotes är korrekt, då . $T(p) = O({\ln^2}{p})$

Se även

Symbol för Legendre
Se OEIS -sekvens A096008 för en lista över kvadratiska rester.

Anteckningar

↑ 1 2 Mathematical Encyclopedia, 1979 , sid. 785-786.
↑ Walker, R. Utformningen och tillämpningen av modulära akustiska spridande element . BBC:s forskningsavdelning. Hämtad 25 oktober 2016. Arkiverad från originalet 27 mars 2016. (obestämd)
↑ Vinogradov, 1952 , kapitel 5.
↑ MathWorld: Kvadratisk rest . Arkiverad från originalet den 16 februari 2017. (obestämd)
↑ Nesterenko, 2008 , sid. 83.
↑ Davenport G. Högre aritmetik. Introduktion till talteori .. - M . : Nauka, 1965. - S. 59. - 176 sid.
↑ Stangl, Walter D. (oktober 1996), Counting Squares in ℤ n , Mathematics Magazine vol. 69 (4): 285–289, doi : 10.2307/2690536 , < http://www.maa.org/sites/default /files/Walter_D22068._Stangl.pdf > Arkiverad 24 december 2015 på Wayback Machine

Litteratur

Vinogradov I.M. Grunderna i talteorin . - M. - L. : GITTL, 1952. - 180 sid.
Quadratic Residue // Mathematical Encyclopedia (i 5 volymer). - M . : Soviet Encyclopedia , 1979. - T. 2.
Nesterenko Yu. V. Talteori. - M . : Publishing Center "Academy", 2008. - S. 132-133. — 272 sid. — ISBN 9785769546464 .