平方剰余
$\hspace{7em}項目1-5,7は別ファイルを読み込みます$
(6)$\ \ $相互法則
$\qquad 第1補充法則 \hspace{2em} \big(\cfrac{-1}{p}\big) \equiv (-1)^{\tfrac{p-1}{2}}$
$定理3でa=-1とおくと$
$-1,-2,\cdots , -s \ \ は法pで、p-1,p-2,\cdots , p-s \ \ と合同$
$これらはすべて\cfrac{p}{2}より大きいから n=s=\cfrac{p-1}{2}$
$例 \big(\cfrac{-1}{11}\big) =(-1)^{\tfrac{11-1}{2}}=(-1)^5=-1$
$\quad 第2補充法則 \hspace{2em} pは奇素数とし、aはpの倍数でないとする。法pにおいて \qquad \big(\cfrac{2}{p}\big) \equiv (-1)^{\tfrac{p^2-1}{8}}$
$定理3の証明2で使った文字をそのまま使って$
$\quad R=r_1+r_2+ \cdots + r_m,\quad T=t_1+t_2+\cdots + t_n \ \ ,A=\Bigl[\cfrac{a}{p}\Bigr]+\Bigl[\cfrac{2a}{p}\Bigr]+\cdots +\Bigl[\cfrac{sa}{p}\Bigr] \ \ とおくと$
$\quad k_ia=\Bigl[\cfrac{k_ia}{p}\Bigr]p+r_i ,\quad l_ja=\Bigl[\cfrac{l_ja}{p}\Bigr]p+t_i \ \ とあらわされるから、すべて加えて$
\[\sum _i k_ia +\sum _j l_ja=\big(\sum _i \Bigl[\cfrac{k_ia}{p}\Bigr]+\sum _j\Bigl[\cfrac{l_ja}{p}\Bigr]\big)p+\sum _ir_i +\sum _jt_j\] $k_1,k_2,\cdots ,k_m,l_1,l_2,\cdots ,l_n \ は \ 1,2,\cdots ,s を並びかえたものだから$
\begin{eqnarray*} (1+2+\cdots +s)a &=&\Big(\Bigl[\cfrac{a}{p}\Bigr]+\Bigl[\cfrac{2a}{p}\Bigr]+\cdots +\Bigl[\cfrac{sa}{p}\Bigr]\big)p+\sum _ir_i +\sum _jt_j\\ &=&Ap+R+T \hspace{25em}(1)\\ \end{eqnarray*} $また、r_1 , r_2, \cdots r_m, (p-t_1) , (p-t_2), \cdots , (p-t_n) も1,2,\cdots ,s を並びかえたものだから$
\begin{eqnarray*} 1+2+\cdots +s &=&r_1 + r_2 + \cdots r_m + (p-t_1) + (p-t_2)+ \cdots +(p-t_n) \\ &=&R+np-T \hspace{27em}(2)\\ \end{eqnarray*} $(1)-(2)より \quad (1+2+\cdots +s )(a-1)=(A-n)p+2T \hspace{17em}(3)$
$とくに \ a=2 \ のときは 1 \leqq k_i \leqq s \ \ より 2 \leqq 2k_i \leqq p-1 < p$
$2k_i をpで割った商は0,\ \ 同様にして 2l_j をpで割った商も0、したがって A=0$
$ゆえに(3)は \ \ s=\cfrac{p-1}{2}\ \ だから $
$\quad \cfrac{1}{2} \times \cfrac{p-1}{2} \times (\cfrac{p-1}{2}+1)\times (2-1)=-np+2T$
$\quad \cfrac{1}{8}(p^2-1)=-n(2s+1)+2T$
$\quad \big(\cfrac{2}{p}\big) \equiv (-1)^n \ \ の値は、nが偶数か奇数かだけで決まるから法2で調べればよい。$
$\quad \cfrac{1}{8}(p^2-1)=n-2ns+2T-2n \equiv n \quad (mod \ \ 2)$
$\quad \therefore n \equiv \cfrac{1}{8}(p^2-1)$
$したがって \big(\cfrac{2}{p}\big) \equiv (-1)^{\tfrac{p^2-1}{8}}$
$例 \big(\cfrac{2}{11}\big) \equiv (-1)^{\tfrac{11^2-1}{8}}=(-1)^{15}=-1$
$\quad 定理4\ \ (相互法則) \hspace{2em} \big(\cfrac{p}{q}\big)\big(\cfrac{q}{p}\big)=(-1)^{\tfrac{p-1}{2}\tfrac{q-1}{2}} \qquad ただし p,qは異なる奇素数$
$(証明)$
$(第1段階)$
$p=2s+1,\ \ q=2t+1 \ \ とおく$
$\quad 1+2+\cdots + s=\cfrac{1}{2}s(s+1)=\cfrac{1}{2} \times \cfrac{p-1}{2} \times \cfrac{p+1}{2}=\cfrac{p^2-1}{8}$
$両辺にq-1をかけて$
$\quad \cfrac{1}{8}(p^2-1)(q-1)=\underbrace{s(s+1)}_{\substack{偶数}}\times \underbrace{\cfrac{q-1}{2}}_{\substack{整数}} \equiv 0 \quad (mod \ \ 2) \hspace{10em}(1)$
$第2補充法則の(3)式より$
$\quad \cfrac{1}{8}(p^2-1)(a-1)=(A-n)p+2T \ \ で \ a=q \ とおくと$
$\quad \cfrac{1}{8}(p^2-1)(q-1)=(A-n)p \quad (mod \ \ 2)$
$(1)より 左辺 \equiv 0 ,\ \ pと2は互いに素だから \ \ A \equiv n \quad (mod \ \ 2)$
$a=q とおいたから$
$\quad A=\Bigl[\cfrac{q}{p}\Bigr]+\Bigl[\cfrac{2q}{p}\Bigr]+\cdots +\Bigl[\cfrac{sq}{p}\Bigr] \equiv n$
$\quad \big(\cfrac{q}{p}\big)=(-1)^n=(-1)^A$
$同様にして$
$\quad B=\Bigl[\cfrac{p}{q}\Bigr]+\Bigl[\cfrac{2p}{q}\Bigr]+\cdots +\Bigl[\cfrac{tp}{q}\Bigr] \ \ とすると$
$\quad \big(\cfrac{p}{q}\big)=(-1)^B$
$したがって$
$\quad \big(\cfrac{p}{q}\big)\big(\cfrac{q}{p}\big)=(-1)^A\ (-1)^B=(-1)^{A+B}$
$座標平面上に、右図のように4点(0,0),(\cfrac{p}{2},0),(\cfrac{p}{2},\cfrac{q}{2}),(0,\cfrac{q}{2})$
$を頂点とする長方形内(境界は含めない)の格子点(x座標,$
$y座標がともに整数となる点のこと)は$
$\quad (1,1),(2,1),\cdots ,(s,1)$
$\quad (1,2),(2,2),\cdots ,(s,2)$
$\hspace{5em} \vdots $
$\quad (1,t),(2,t),\cdots ,(s,t)$
$の全部でst個ある。このst個の格子点を、2点(0,0),(\cfrac{p}{2},\cfrac{q}{2})を通る直線lで類別してみましょう。$
(i)$直線l上$
$\quad lは \ y=\cfrac{q}{p}x \ \ だからl上の点(x,y)が格子点ならば、xはpの倍数でなければならない。$
$\quad ところが \ \ 0 < x < \cfrac{p}{2} \ \ だからxはpの倍数ではない。$
$\quad したがって直線l上には格子点はない。$
(ii)$直線lより下$
$\quad y <\cfrac{q}{p}x \ \ だから$
$\qquad x=1 のとき 0 < y <\cfrac{q}{p} \ \ より\ \ \Bigl[\cfrac{q}{p}\Bigr]個$
$\qquad x=2 のとき 0 < y <\cfrac{2q}{p} \ \ より \ \ \Bigl[\cfrac{2q}{p}\Bigr]個$
$\hspace{5em} \vdots $
$\qquad x=s のとき 0 < y <\cfrac{sq}{p} \ \ より \ \ \Bigl[\cfrac{sq}{p}\Bigr]個$
$\quad したがって全部で、\Bigl[\cfrac{q}{p}\Bigr]+\Bigl[\cfrac{2q}{p}\Bigr]+\cdots +\Bigl[\cfrac{sq}{p}\Bigr]個で、これはAに等しい。$
(iii)$直線lより上$
$\quad x=\cfrac{p}{q}y \ \ として$
$\quad y=1 のとき 0 < x <\cfrac{p}{q} \ \ より \ \ \Bigl[\cfrac{p}{q}\Bigr]個$
$\quad y=2 のとき 0 < x <\cfrac{2p}{q} \ \ より \ \ \Bigl[\cfrac{2p}{q}\Bigr]個$
$\hspace{5em} \vdots $
$\quad y=t のとき 0 < x <\cfrac{tp}{q} \ \ より \ \ \Bigl[\cfrac{tp}{q}\Bigr]個$
$\quad したがって全部で、\Bigl[\cfrac{p}{q}\Bigr]+\Bigl[\cfrac{2p}{q}\Bigr]+\cdots +\Bigl[\cfrac{tp}{q}\Bigr]個で、これはBに等しい。$
(i)(ii)(iii)$より長方形内の格子点の個数はA+B個であることがわかりましたので、st=AB \ \ となります。$
$第1段階と合わせて$
$\qquad \big(\cfrac{p}{q}\big)\big(\cfrac{q}{p}\big)=(-1)^{A+B}=(-1)^{st}=(-1)^{\tfrac{p-1}{2}\tfrac{q-1}{2}}$
$例1\ \ 相互法則をつかって\quad \big(\cfrac{11}{23}\big) の値を求めてみましょう$
$\quad \big(\cfrac{11}{23}\big)\big(\cfrac{23}{11}\big)=(-1)^{\tfrac{23-1}{2}\tfrac{11-1}{2}}=(-1)^{11\times 5}=-1$
$\quad 両辺に\big(\cfrac{23}{11}\big) をかけて \quad \big(\cfrac{11}{23}\big)\big(\cfrac{23}{11}\big)\big(\cfrac{23}{11}\big)=-\big(\cfrac{23}{11}\big) $
$\quad \big(\cfrac{23}{11}\big)\big(\cfrac{23}{11}\big)=\big(\cfrac{23}{11}\big)^2=1\ \ だから$
\begin{eqnarray*} \big(\cfrac{11}{23}\big) &=&-\big(\cfrac{23}{11}\big)\\ &=&-\big(\cfrac{1}{11}\big) \hspace{10em} (23=11 \times 2+1)\\ &=&-1\\ \end{eqnarray*}
$例2\ \ 和暦と西暦がともに素数になるのは最近では、平成29年と西暦2017年でした。$
$\quad \big(\cfrac{29}{2017}\big) の値を求めてみましょう$
$\quad \big(\cfrac{29}{2017}\big)\big(\cfrac{2017}{29}\big)=(-1)^{\tfrac{2017-1}{2}\tfrac{29-1}{2}}=(-1)^{1008 \times 14}=1$
\begin{eqnarray*} \big(\cfrac{29}{2017}\big) &=&\big(\cfrac{2017}{29}\big)\\ &=&\big(\cfrac{16}{29}\big) \hspace{10em} (2017=29 \times 69+16)\\ &=&\big(\cfrac{4}{29}\big)^2\\ &=&1\ \end{eqnarray*}
$相互法則はこのように使われます。$
$\big(\cfrac{11}{23}\big)=-1 \ \ ですから \ \ x^2＝11 \ \ (mod \ \ 23)\ \ をみたすxはありません。$
$\big(\cfrac{29}{2017}\big)=1 \ \ ですから \ \ x^2＝29 \ \ (mod \ \ 2017)\ \ をみたすxはあります。$
$では、どうすればこのxの値が求められるかということになりますが \cdots $
$おそらくうまい方法はないと思われます。(もしあったらごめんなさい)$
$そこで、地道にx=2から代入して調べることになりますが、そこはコンピュータに任せればいいわけです。$
$Visual Basic で計算したところ\ x=958\ でした。もちろん \ 2017-958=1059 \ も解になります。$
メインメニュー に戻る