Kvadratisk rest

Et heltal kaldes en kvadratisk modulo- rest, hvis sammenligningen er løselig [1] : $-en$ $m$

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

Hvis den angivne sammenligning ikke kan løses, kaldes tallet en kvadratisk non-residue modulo . At løse sammenligningen ovenfor betyder at tage kvadratroden i ringen af restklasser . $-en$ $m$

Kvadratiske rester er meget brugt i talteori , de har også fundet praktiske anvendelser inden for akustik [2] , kryptografi , grafteori (se Paley-graf ) og andre aktivitetsområder.

Konceptet med en kvadratisk rest kan også overvejes for en vilkårlig ring eller et vilkårligt felt . For eksempel kvadratiske rester i endelige felter .

Forskelle i terminologi

The Mathematical Encyclopedia og en række andre kilder definerer en kvadratisk rest som et tal , for hvilket der er en kongruensløsning . Andre kilder (f.eks. G. Hasse. Lectures on Number Theory, 1953) angiver et yderligere krav om, at tallet er coprime med . Nogle kilder betragter generelt kun tilfældet med et ulige primmodul [3] [4] . I begge sidstnævnte tilfælde er nul udelukket fra overvejelse. $-en$ $x^{2}\equiv a{\pmod {m))$ $-en$ $m$

Eksempler

Tallene og er kvadratiske rester modulo enhver, da kongruenserne og altid har løsninger og hhv. $a=0$ $a=1$ $x^{2}\equiv 0{\pmod {m))$ $x^{2}\equiv 1{\pmod {m))$ $x=0$ $x=1$

Konsekvens : Da der kun er to restklasser for et modul, og ethvert tal er modulo 2 en kvadratisk rest. $m=2$ $[0]_{2}$ $[1]_{2},$

Modulo 3, der er tre klasser af rester: Deres kvadrater falder ind under klasserne af rester , hhv. Dette viser, at tallene fra klasserne og er kvadratiske rester, og tallene fra klassen (for eksempel ) er kvadratiske ikke-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$

Teorien om kvadratiske rester er bredt anvendt, især til studiet af mulige heltalsværdier af kvadratiske former . Overvej for eksempel ligningen:

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

Det følger heraf , at kvadraterne af tal giver dog kun rester modulo 5 , det vil sige, at 3 er en andengrads ikke-rest modulo 5. Det følger, at ovenstående ligning ikke har nogen løsninger i heltal [5] . $x^{2}\equiv 3{\pmod {5)).$ $0.1.2.3.4$ $0,1,4;$

En generel kvadratsammenligning af formen, hvor tallene er coprime og ikke er divisorer af modulet , kan undersøges som følger: løsningen af sammenligningen findes, derefter ganges den oprindelige kvadratsammenligning med for at opnå en sammenligning af formen: Det tilbage for at bestemme [6] , om er 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$

Egenskaber

Eulers kriterium : Lad det være enkelt. Et tal en coprime til er en kvadratisk modulo-rest , hvis og kun hvis [1] : $p>2$ $s$ $s$ $a^{(p-1)/2}\equiv 1\pmod{p},$

og er en kvadratisk ikke-rest modulo p hvis og kun hvis

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

Kvadratisk lov om gensidighed
Kvadratiske rester relativt prime til modulet danner en multiplikativ undergruppe af restringen af indeks 2, især:
- fradrag × fradrag = fradrag;
- non-residue × residual = non-residue.
- ikke-rest × ikke-rest = fradrag.

Mængde

Modulo

Blandt ikke-nul tal , for et primmodul er der nøjagtigt kvadratiske rester og ikke-rester. $1,2,...,p-1$ $p\geq3$ $\frac{p-1}{2}$ $\frac{p-1}{2}$

Bevis

Da det er tilstrækkeligt at vise, at der blandt tallene ikke er nogen sammenlignelige modulo . $x^2 \equiv (px)^2 \pmod{p}$ $0^2, 1^2, 2^2, \dots, \left({\frac{p-1}{2}}\right)^2$ $s$

Lad der være sådanne tal for og . $x^2 \equiv y^2 \pmod{p}$ $x \ikke = y$ $0 \le x,y \le \frac{p-1}{2}$

Siden , da og, i betragtning af det faktum, at det er simpelt, og , vi har , hvilket er umuligt, fordi $p\mid (x^{2}-y^{2})$ $p\mid (xy)(x+y)$ $s$ $0<|xy|<s$ $p\mid (x+y)$ $x+y \le p-1$

Således danner ikke-nul kvadratiske rester en undergruppe af indeks 2 i den multiplikative gruppe af ringen . $\mathbb {Z} _{p}$

Vilkårligt modulo

Walter Stangl introducerede en formel i 1996 til at beregne antallet af kvadratiske rester modulo vilkårligt . [7] $n$

Lad være den kanoniske nedbrydning af tallet . Så er den følgende formel sand for antallet af kvadratiske 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}$

Fordeling

Mængde i intervallet

Lad være enkelt ,. Betegn ved antallet af kvadratiske rester modulo blandt tallene . $p>3$ $Q<p$ ${R_p}(Q)$ $s$ $1, \prikker, Q$

I. M. Vinogradov beviste , at hvor . ${R_p}(Q) = \frac{Q}{2} + \theta \frac{\sqrt{p} \ln{p}}{2}$ $|\theta|<1$

Det følger heraf, at der i vilkårlige intervaller af tilstrækkelig stor længde (sådan ) vil være en asymptotisk lighed , dvs. kvadratiske rester og ikke-rester vil være asymptotisk ens. $\sqrt{p} \ln{p} = o(Q(p))$ ${R_p}(Q) \sim \frac{Q}{2}$

Mindste kvadratisk non-residue modulo

Betegn ved den minimale positive kvadratiske ikke-residue modulo . $T(p)$ $s$

Af uligheden (se afsnittet "mængde i intervallet") følger det direkte, at , dvs. ${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 et resultat af dybere forskning beviste Vinogradov, at . $T(p) \le p^{\frac{1}{2\sqrt{e}}} \left({\log{p}}\right)^2$

Der er en hypotese fremsat af Vinogradov, at . $T(p)=o(p^{\varepsilon}) \foral \varepsilon > 0$

Hvis Riemann-hypotesen er korrekt, så . $T(p) = O({\ln^2}{p})$

Se også

Symbol for Legendre
Se OEIS -sekvens A096008 for en liste over kvadratiske rester.

Noter

↑ 1 2 Mathematical Encyclopedia, 1979 , s. 785-786.
↑ Walker, R. Designet og anvendelsen af modulære akustiske diffuserende elementer . BBC forskningsafdeling. Hentet 25. oktober 2016. Arkiveret fra originalen 27. marts 2016. (ubestemt)
↑ Vinogradov, 1952 , kapitel 5.
↑ MathWorld: Quadratic Residue . Arkiveret fra originalen den 16. februar 2017. (ubestemt)
↑ Nesterenko, 2008 , s. 83.
↑ Davenport G. Højere aritmetik. Introduktion til talteori .. - M . : Nauka, 1965. - S. 59. - 176 s.
↑ Stangl, Walter D. (oktober 1996), Counting Squares in ℤ n , Mathematics Magazine bind 69 (4): 285–289, doi : 10.2307/2690536 , < http://www.maa.org/sites/default /files/Walter_D22068._Stangl.pdf > Arkiveret 24. december 2015 på Wayback Machine

Litteratur

Vinogradov I.M. Grundlæggende om talteori . - M. - L. : GITTL, 1952. - 180 s.
Quadratic Residue // Mathematical Encyclopedia (i 5 bind). - M . : Soviet Encyclopedia , 1979. - T. 2.
Nesterenko Yu. V. Talteori. - M . : Publishing Center "Academy", 2008. - S. 132-133. — 272 s. — ISBN 9785769546464 .