Kvadratický zbytek

Celé číslo se nazývá kvadratický modulo zbytek, pokud je srovnání řešitelné [1] : $A$ $m$

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

Pokud uvedené srovnání není řešitelné, pak se číslo nazývá kvadratický nezbytkový modulo . Řešení výše uvedeného srovnání znamená vzít druhou odmocninu v kruhu tříd zbytků . $A$ $m$

Kvadratické zbytky jsou široce používány v teorii čísel , praktické aplikace našly také v akustice [2] , kryptografii , teorii grafů (viz Paleyův graf ) a dalších oblastech činnosti.

Představa o kvadratickém zbytku může být také zvažována pro libovolný kruh nebo pole . Například kvadratické zbytky v konečných polích .

Rozdíly v terminologii

Matematická encyklopedie a řada dalších zdrojů definují kvadratický zbytek jako číslo, pro které existuje řešení kongruence . Jiné zdroje (například G. Hasse. Lectures on Number Theory, 1953) uvádějí další požadavek, aby číslo bylo coprime s . Některé zdroje obecně zvažují pouze případ lichého primárního modulu [3] [4] . V obou posledně uvedených případech je nula vyloučena. $A$ $x^{2}\equiv a{\pmod {m))$ $A$ $m$

Příklady

Čísla a jsou kvadratické zbytky modulo any, protože kongruence a vždy mají řešení , resp. $a=0$ $a=1$ $x^{2}\equiv 0{\pmod {m))$ $x^{2}\equiv 1{\pmod {m))$ $x=0$ $x=1$

Důsledek : Protože existují pouze dvě třídy zbytků pro modul a jakékoli číslo modulo 2 je kvadratický zbytek. $m=2$ $[0]_{2}$ $[1]_{2},$

Modulo 3, existují tři třídy zbytků: Jejich čtverce spadají do tříd zbytků , resp. To ukazuje, že čísla ze tříd a jsou kvadratické zbytky a čísla ze třídy (například ) jsou kvadratické nezbytky 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\tečky$

Teorie kvadratických zbytků je široce používána, zejména při studiu možných celočíselných hodnot kvadratických forem . Zvažte například rovnici:

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

Vyplývá z ní, že druhé mocniny čísel však dávají pouze zbytky modulo 5 , tedy 3 je kvadratické nezbytkové modulo 5. Z toho vyplývá, že výše uvedená rovnice nemá řešení v celých číslech [5] . $x^{2}\equiv 3{\pmod {5)).$ $0.1.2.3.4$ $0,1,4;$

Obecné čtvercové srovnání tvaru , kde čísla jsou coprime a nejsou děliteli modulu , lze prozkoumat následovně: je nalezeno řešení srovnání , pak se původní čtvercové srovnání vynásobí, aby se získalo srovnání tvaru: zbývá určit [6], zda je kvadratický zbytek 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$

Vlastnosti

Eulerovo kritérium : Ať je to jednoduché. Číslo, ke kterému je připojeno, je kvadratický modulo zbytek právě tehdy, když [1] : $p>2$ $p$ $p$ $a^{(p-1)/2}\equiv 1\pmod{p},$

a je kvadratický nezbytkový modulo p tehdy a jen tehdy

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

Kvadratický zákon reciprocity
Kvadratické zbytky relativně prvotřídní vzhledem k modulu tvoří multiplikativní podskupinu zbytkového kruhu indexu 2, konkrétně:
- srážka × srážka = srážka;
- nezbytky × reziduum = nezbytky.
- nezůstatek × nezůstatek = srážka.

Množství

Modulo

Mezi nenulovými čísly jsou pro primární modul přesně kvadratické zbytky a nezbytky. $1,2,...,p-1$ $p\geq3$ $\frac{p-1}{2}$ $\frac{p-1}{2}$

Důkaz

Protože stačí ukázat, že mezi čísly nejsou žádné srovnatelné moduly . $x^2 \equiv (px)^2 \pmod{p}$ $0^2, 1^2, 2^2, \tečky, \left({\frac{p-1}{2}}\right)^2$ $p$

Nechť jsou taková čísla pro a . $x^2 \equiv y^2 \pmod{p}$ $x \není = y$ $0 \lex,y \le \frac{p-1}{2}$

Od , pak a vzhledem k tomu, že je to jednoduché, a , máme , což je nemožné, protože $p\mid (x^{2}-y^{2})$ $p\mid (xy)(x+y)$ $p$ $0<|xy|<str$ $p\mid (x+y)$ $x+y \le p-1$

Nenulové kvadratické zbytky tedy tvoří podskupinu indexu 2 v multiplikativní skupině kruhu . $\mathbb {Z} _{p}$

Libovolně modulo

Walter Stangl představil vzorec v roce 1996 pro výpočet počtu kvadratických zbytků modulo libovolně . [7] $n$

Dovolit být kanonický rozklad čísla . Potom následující vzorec platí pro počet kvadratických zbytků modulo $n = 2^t {p_1}^{d_1} {p_2}^{d_2} \tečky {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)}}\pravé\rpodlaží}$

Distribuce

Množství v intervalu

Buďme jednoduché ,. Označte počtem kvadratických zbytků modulo mezi čísly . $p>3$ $Q<p$ ${R_p} (Q)$ $p$ $1, \tečky, Q$

I. M. Vinogradov dokázal, že kde . ${R_p}(Q) = \frac{Q}{2} + \theta \frac{\sqrt{p} \ln{p}}{2}$ $|\theta|<1$

Z toho vyplývá, že v libovolných intervalech dostatečně velkých délek (takových, že ) bude asymptotická rovnost , to znamená, že kvadratické zbytky a nezbytky budou asymptoticky stejné. $\sqrt{p} \ln{p} = o(Q(p))$ ${R_p}(Q) \sim \frac{Q}{2}$

Nejméně kvadratické nezbytkové modulo

Označme minimální kladný kvadratický nezbytkový modulo . $T(p)$ $p$

Z nerovnosti (viz část "množství v intervalu") přímo vyplývá , že , tedy . ${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$

Jako výsledek hlubšího výzkumu Vinogradov dokázal, že . $T(p) \le p^{\frac{1}{2\sqrt{e}}} \left({\log{p}}\right)^2$

Existuje hypotéza předložená Vinogradovem, že . $T(p)=o(p^{\varepsilon}) \forall \varepsilon > 0$

Pokud je Riemannova hypotéza správná, pak . $T(p) = O({\ln^2}{p})$

Viz také

Symbol Legendre
Viz OEIS sekvence A096008 pro seznam kvadratických zbytků.

Poznámky

↑ 1 2 Matematická encyklopedie, 1979 , str. 785-786.
↑ Walker, R. Návrh a aplikace modulárních akustických difuzních prvků . Výzkumné oddělení BBC. Získáno 25. října 2016. Archivováno z originálu dne 27. března 2016. (neurčitý)
↑ Vinogradov, 1952 , kapitola 5.
↑ MathWorld: Quadratic Residue . Archivováno z originálu 16. února 2017. (neurčitý)
↑ Nesterenko, 2008 , str. 83.
↑ Davenport G. Vyšší aritmetika. Úvod do teorie čísel .. - M . : Nauka, 1965. - S. 59. - 176 s.
↑ Stangl, Walter D. (říjen 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 > Archivováno 24. prosince 2015 na Wayback Machine

Literatura

Vinogradov I.M. Základy teorie čísel . - M. - L. : GITTL, 1952. - 180 s.
Quadratic Residue // Mathematical Encyclopedia (v 5 svazcích). - M .: Sovětská encyklopedie , 1979. - T. 2.
Nesterenko Yu. V. Teorie čísel. - M . : Publikační středisko "Akademie", 2008. - S. 132-133. — 272 s. — ISBN 9785769546464 .