Gauss lemma om kvadratiska rester

Gauss lemma låter en avgöra om ett tal är en kvadratisk rest modulo ett primtal .

Formulering

Ta en enkel och naturlig sådan att . Låt oss titta på resten av talen modulo . Låt bland dem rester större än , då ( Legendres symbol används här ). $sid$ $a$ $(a,p)=1$ $a,2\cdot a,3\cdot a,\dots {\frac {p-1}{2}}\cdot a$ $sid$ $v$ $\frac{p}{2}$ $\left({\frac {a}{p}}\right)=(-1)^{v}$

Bevis

Låt oss överväga arbetet . Låt oss ersätta talen större än modulo med . Sedan tar vi ut den till vänster och får produkten av några tal modulo , som är olika modulo ( ) och ger en rest mindre än , så denna produkt är jämförbar med . Då kan vi förkorta vår jämförelse med och få det . Enligt Eulers kriterium . [ett] $a\cdot 2a\cdot 3a\cdots {\frac {p-1}{2}}\cdot a\equiv \left({\frac {p-1}{2}}\right)!\cdot a^{\frac {p-1}{2}}{\pmod {p}}$ $k\cdot a$ $\frac{p}{2}$ $sid$ $(-1)\cdot (pk\cdot a)$ ${\displaystyle (-1)^{v))$ ${\frac {p-1}{2}}$ $sid$ $sid$ $(m\pm n)\cdot a\not \equiv 0{\pmod {p))$ $\frac{p}{2}$ $\left({\frac {p-1}{2}}\right)!$ $\left({\frac {p-1}{2}}\right)!$ $(-1)^{v}\equiv a^{(p-1)/2}{\pmod {p))$ $a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {p}}$

Anteckningar

↑ Davenport G. Högre aritmetik. En introduktion till talteori . — ISBN 539701298X . — ISBN 9785397012980 . Arkiverad 30 september 2017 på Wayback Machine