(*)平方剰余の相互法則と補充法則
\(a,b\)を整数、\(p,q\)を奇素数とする。
(1)平方剰余の相互法則
\[ QR(p,q)QR(q,p)=\left(-1\right)^{\frac{p-1}{2}\frac{q-1}{2}} \](2)第1補充法則
\[ QR(-1,p)=(-1)^{\frac{p-1}{2}} \](3)第2補充法則
\begin{align*} QR(2,p) & =(-1)^{\frac{p^{2}-1}{8}} \end{align*}(4)積
\[ QR(ab,p)=QR(a,p)QR(b,p) \](1)
略(2)
オイラーの規準より、\[ QR(-1,p)\overset{p}{\equiv}(-1)^{\frac{p-1}{2}} \] となる。右辺は1または-1なので、
\[ QR(-1,p)=(-1)^{\frac{p-1}{2}} \] となり、与式は成り立つ。
(3)
\begin{align*} \left(x+x^{-1}\right)^{p} & =\sum_{k=0}^{p}C(p,k)x^{k}x^{-(p-k)}\\ & =\sum_{k=0}^{\frac{p-1}{2}}C(p,k)x^{k}x^{-(p-k)}+\sum_{k=\frac{p+1}{2}}^{p}C(p,k)x^{k}x^{-(p-k)}\\ & =\sum_{k=0}^{\frac{p-1}{2}}C(p,k)x^{k}x^{-(p-k)}+\sum_{k=0}^{\frac{p-1}{x}}C(p,p-k)x^{p-k}x^{-k}\\ & =\sum_{k=0}^{\frac{p-1}{2}}C(p,k)\left(x^{-(p-2k)}+x^{p-2k}\right) \end{align*} ここで、\(\omega_{8}=e^{\frac{2\pi i}{8}}\)とおくと、\begin{align*} \omega_{8}^{\;n}+\omega_{8}^{\;-n} & =\begin{cases} \sqrt{2} & n\overset{8}{\equiv}\pm1\\ -\sqrt{2} & n\overset{8}{\equiv}\pm3 \end{cases}\\ & =(-1)^{\frac{n^{2}-1}{8}}\sqrt{2} \end{align*} となるので、\(x\)に\(\omega_{8}\)を代入すると、
\begin{align*} l.h.s & =\left(\omega_{8}+\omega_{8}^{\;-1}\right)^{p}\\ & =2^{\frac{p}{2}} \end{align*} \begin{align*} r.h.s & =\sum_{k=0}^{\frac{p-1}{2}}C(p,k)\left(\omega_{8}^{-(p-2k)}+\omega_{8}^{p-2k}\right)\\ & =\sum_{k=0}^{\frac{p-1}{2}}C(p,k)\left((-1)^{\frac{(p-2k)^{2}-1}{8}}\sqrt{2}\right) \end{align*} より、
\begin{align*} 2^{\frac{p-1}{2}} & =\sum_{k=0}^{\frac{p-1}{2}}C(p,k)\left((-1)^{\frac{(p-2k)^{2}-1}{8}}\right)\\ & \overset{p}{\equiv}(-1)^{\frac{p^{2}-1}{8}} \end{align*} オイラーの規準より、
\begin{align*} QR(2,p) & \overset{p}{\equiv}2^{\frac{p-1}{2}}\\ & \overset{p}{\equiv}(-1)^{\frac{p^{2}-1}{8}} \end{align*} なり右辺は1または-1なので、
\[ QR(2,p)=(-1)^{\frac{p^{2}-1}{8}} \]
(4)
\begin{align*} QR(ab,p) & \overset{p}{\equiv}\left(ab\right)^{\frac{p-1}{2}}\\ & =a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\\ & =QR(a,p)QR(b,p) \end{align*} 両辺ともに\(\pm1\)なので\[ QR(ab,p)=QR(a,p)QR(b,p) \]
ページ情報
タイトル | (*)平方剰余の相互法則と補充法則 |
URL | https://www.nomuramath.com/xgwcqk8i/ |
SNSボタン |
2元1次不定方程式の性質
\[
ax+by=c\text{が整数解を持つ}\Leftrightarrow c\text{は}\gcd(a,b)\text{の倍数}
\]
ユークリッドの互除法
\[
\gcd(a,b)=\gcd(b,r)
\]
(*)原始根定理
\[
\varphi(p-1)
\]
n番目の素数の式
\[
P\left(n\right)=1+\sum_{k=1}^{2^{n}}\left\lfloor \sqrt[n]{\frac{n}{\sum_{j=1}^{k}\left\lfloor \cos^{2}\left(\frac{\left(j-1\right)!+1}{j}\pi\right)\right\rfloor }}\right\rfloor
\]