Lema lui Gauss asupra reziduurilor pătratice

Lema lui Gauss permite să se determine dacă un număr este un reziduu pătratic modulo un număr prim .

Formulare

Luați un simplu și natural astfel încât . Să ne uităm la resturile de numere modulo . Fie printre ele resturi mai mari decât , atunci ( aici este folosit simbolul Legendre ). $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}$

Dovada

Să luăm în considerare munca . Să înlocuim numerele mai mari decât modulo cu . Apoi îl scoatem din stânga și obținem produsul unor numere modulo , care sunt diferite modulo ( ) și dau un rest mai mic decât , deci acest produs este comparabil cu . Apoi ne putem scurta comparația și obținem asta . După criteriul lui Euler . [unu] $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)$ $(-1)^{v)$ ${\frac {p-1}{2}}$ $p$ $p$ $(m\pm n)\cdot a\nu \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}}$

Note

↑ Davenport G. Aritmetică superioară. O introducere în teoria numerelor . — ISBN 539701298X . — ISBN 9785397012980 . Arhivat pe 30 septembrie 2017 la Wayback Machine