MetaMath '22

Kod određivanja kvadratnih ostataka, korisno nam je definirati takozvani \textbf{Legendreov simbol}. Za prirodan broj $a$ i prost broj $p$ označavamo Legendreov simbol sa $$\bigg( \frac{a}{p} \bigg)$$ i njegova je vrijednost $1$ ukoliko je $a$ kvadratni ostatak modulo $p$, $0$ ukoliko $p$ dijeli $a$ te $-1$ inače. \begin{enumerate} \item Dokažite svojstvo Legendreovog simbola koje se naziva \textit{Eulerov kriterij}: ako je $p$ neparan prost broj koji ne dijeli prirodan broj $a$, onda vrijedi $$\bigg( \frac{a}{p} \bigg) \equiv a^{\frac{p-1}{2}} (mod \, p).$$ \item Dokažite svojstvo Legendreovog simbola koje se naziva \textit{Gaussov zakon reciprociteta}: ako su $p$ i $q$ različiti neparni prosti brojevi, onda vrijedi $$\bigg( \frac{p}{q} \bigg) = \bigg( \frac{q}{p} \bigg) \cdot (-1)^{\frac{(p-1)(q-1)}{4}}.$$ \end{enumerate}