Second remaining learning notes

level Time Co., LTD. , Only consider $p$ Is an odd prime number .
$x^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}p)$

On secondary surplus
The proof in the link is very good .
determine $n\in [1,p-1]$ Is it a quadratic residual method ： If it doesn't exist $x^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}p)$, be $n^{\frac{p-1}{2}}\equiv -1$; If there is , be $n^{\frac{p-1}{2}}\equiv (\sqrt{n}{)}^{p-1}\equiv 1$

$x\in [1,\frac{p-1}{2}]$ The square module of each number of $p$ Different from each other ,$x$ And $p-x$ The square module of $p$ identical .

yyb！
Add why Find with primitive root $x^2\equiv n(\mathrm{m}\mathrm{o}\mathrm{d}p)$ Of $x$ when , Make $g^a\equiv n$, If there is a solution , that $a$ It must be an even number ：
First there is $(g^b{)}^2\equiv g^{2b}\equiv g^a$, Then there must be $2b\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$, therefore $a$ It must be an even number . It can also be seen that $b$ There are two solutions , One is $\frac{a}{2}$, One is $\frac{a+p-1}{2}$

solution ： Random $a\in [0,p)$, Make $w=a^2-n$, If $w$ There is no secondary residue , be $(a+\sqrt{w}{)}^{\frac{p+1}{2}}$ It's a set of solutions , You can put $\sqrt{w}$ Overloaded as imaginary units .

Several important conclusions （ Not in the sense of modulo odd prime numbers 0 term ）：
Second surplus * Second surplus = Second surplus
Second surplus * Non quadratic residue = Non quadratic residue
Non quadratic residue * Non quadratic residue = Non quadratic residue

The proof can be obtained by multiplying according to Legendre sign .

So there is a corollary ：$x\ast k^{-1}$ It's the second surplus Equivalent to $x\ast k$ It's the second surplus .