Gauss-lemmája a másodfokú maradékokról

Gauss-lemmája lehetővé teszi annak meghatározását, hogy egy szám másodfokú maradék -e, modulo egy prímszám .

Megfogalmazás

Vegyünk egy egyszerű és természetes . Nézzük meg a modulo számok maradékát . Legyen köztük nagyobb maradvány, mint , akkor ( itt a Legendre szimbólumot használjuk ). $p$ $a$ $(a,p)=1$ $a,2\cdot a,3\cdot a,\dots {\frac {p-1}{2}}\cdot a$ $p$ $v$ $\frac{p}{2}$ $\left({\frac {a}{p}}\right)=(-1)^{v}$

Bizonyítás

Nézzük a munkát . Cseréljük le a modulo -nál nagyobb számokat -ra . Ezután kivesszük a bal oldalon , és megkapjuk néhány modulo szám szorzatát , amelyek különbözőek a modulo ( ), és a maradékot kisebbnek adjuk meg , így ez a szorzat összehasonlítható a -val . Ezután lerövidíthetjük az összehasonlítást, és megkapjuk azt . Euler kritériuma szerint . [egy] $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}$ $p$ $(-1)\cdot (pk\cdot a)$ ${\megjelenítési stílus (-1)^{v))$ ${\frac {p-1}{2}}$ $p$ $p$ $(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}}$

Jegyzetek

↑ Davenport G. Magasabb aritmetika. Bevezetés a számelméletbe . — ISBN 539701298X . — ISBN 9785397012980 . Archiválva : 2017. szeptember 30. a Wayback Machine -nál