完全剰余系をwilsonの定理で応用する
数学の記事を書く練習がしたくて、なんかないかなと考えたときに、６月くらいに書いて、X(旧twitter)に投稿したレポートみたいなものを思い出したので、せっかくなのでそれで練習してみます。ただ、１週間くらいで書いた内容なのであまり内容は期待しないでください。
1．はじめに
僕はwilsonの定理がとても好きで、今回はその応用を考えようと思います。そのため、wilsonの定理を
$p$が素数$\Longleftrightarrow(p-1)!\equiv(p-1) \pmod{p}$
としてではなく、
$p$は素数$\Longrightarrow p$の完全剰余系の積が$p$と合同
と捉えなおすことで応用しやすくしました。
発想の過程をわかりやすくするために個々の結果を見ているので、内容の薄さに反して補題が少し多いです。
2.補題ども
以下、この記事では特に断りがないとき法$p$とする($p$は奇素数)。とりあえず完全剰余系を定義しときます。
ある自然数$ｍ$に対して、$m$個の元からなる集合$\{a_{1},a_{2},…a_{m}\}$が、任意の$i,j$に対して$a_{i}\not\equiv a_{j} \pmod{m}$ を満たすとき、この集合を法を$ｍ$とした完全剰余系という。
上の定義はようするに、法$ｍ$で0から$ｍ-1$に等しい$ｍ$個の元からなる集合を完全剰余系と呼ぶ、ということです。
では早速、完全剰余系の例を一つ見てみましょう。
$ (p,q)=1、s \in \mathbb{Z} $のとき、
$ \{s+qk | k=0,1,…,p-1\} $は法を$p$とした完全剰余系となる。
これの証明は数論始めたての人にはいい演習になるし、ある程度モジュラー算術に慣れている人なら簡単だと思うので飛ばします。
今回はこの補題の完全剰余系に注目して進めます。
さて、これとwilsonの定理を合わせようとして少し実験すると次の補題2が自然と思い浮かびます。
$q|p-1$のとき、
$(\frac{p-1}{q})! \cdot (\frac{(p-1)(q-1)}{q})! \equiv (-1)^{ \frac{p-1}{q}+1 }$
$\begin{align} (p-1)! &\equiv\prod_{i=1}^{\frac{p-1}{q}}(p-iq)\cdot\prod_{i=1}^{\frac{(p-1)(q-1)}{q}}(p+iq) \quad (\because 補題1) \\&\equiv (\frac{p-1}{q})! \cdot (-q)^{\frac{p-1}{q}} \cdot (\frac{(p-1)(q-1)}{q})! \cdot q^{\frac{(p-1)(q-1)}{q}} \\&\equiv (\frac{p-1}{q})! \cdot (\frac{(p-1)(q-1)}{q})! \cdot (-1)^{\frac{p-1}{q}} \quad(\because Fermatの小定理) \\ ここで&wilsonの定理を用いると、\\ (\frac{p-1}{q})! \cdot &(\frac{(p-1)(q-1)}{q})! \equiv (-1)^{ \frac{p-1}{q}+1 } (\square) \end{align}$
この証明は補題1の$k$を少しずらして、$p$を消し、少し計算するといったものです。
ここでwilsonの定理を紹介したいんですが、Eulerの規準とともに紹介したいため補題6で紹介します。
さて、この証明を読んで賢い読者の諸君はお気づきだろうが、(一回言ってみたかった)この証明はちょっと回りくどく、ついでに$\frac{1}{q}$を$\frac{r}{q}$に拡張できそうですよね。実際次のように簡単に拡張できます。
$q|p-1,0 \lt r \lt q$のとき、
$(\frac{r(p-1)}{q})! \cdot (\frac{(q-r)(p-1)}{q})! \equiv (-1)^{\frac{r(p-1)}{q}+1}$
$\begin{align}(\frac{r(p-1)}{q})! \cdot (\frac{(q-r)(p-1)}{q})! &\equiv \prod_{i=1}^{\frac{r(p-1)}{q}}i \cdot \prod_{i=1}^{\frac{(q-r)(p-1)}{q}}i \\&\equiv (-1)^{\frac{r(p-1)}{q}} \cdot \prod_{i=1}^{\frac{r(p-1)}{q}}(p-i) \cdot \prod_{i=1}^{\frac{(q-r)(p-1)}{q}}i \\&\equiv (-1)^{\frac{r(p-1)}{q}} \cdot (p-1)! \\&\equiv (-1)^{\frac{r(p-1)}{q}+1} \quad (\because wilsonの定理) (\square) \end{align}$
これらに$q=2$を代入すると次の結果がわかります。
$(( \frac{p-1}{2} )!)^{2} \equiv (-1)^{ \frac{p+1}{2} }$
(正直wilsonの定理は本体と同じくらいこの形でも見かける。)
これは僕が小６のはじめくらいにwilsonの定理に出会い魅了され、半年くらい調べたときの数少ない(たった２つ!!)結果の一つであり、あれから4年、少し一般化した形でこれを紹介できたとても感慨深いです。
3.平方剰余に関する補題ども
まず平方剰余について簡単に説明します。
$x^{2} \equiv a$
が解を持つとき、 $a$が法$p$について平方剰余であるといいます。
また、legendre記号()とは、
$(\frac{a}{p})= \begin{eqnarray} \left\{ \begin{array}{l} 1 (aが平方剰余)\\-1 (aが平方非剰余)\\ 0 (p|a) \\ \end{array} \right. \end{eqnarray}$
で定義される記号です。
平方剰余に関する有名な結果として次の補題があります。
法を$p$とした平方剰余は、$0^{2}$,$1^{2}$,$2^{2}$$\cdots$,$ (\frac{p-1}{2})^{2}$の$\frac{p+1}{2}$個からなる。
$\begin{align} i^{2} &\equiv (p-i)^{2}より、 \frac{p-1}{2} \lt i のときはp-iに置き換えればよいため、\\ 0 \leq i \leq & \frac{p-1}{2}としても一般性を失わない。\\ i^{2} &\equiv j^{2} (i \lt j,0\leq i,j \leq \frac{p-1}{2}) と仮定すると、\\j^{2}-i^{2} &\equiv (j-i)(j+i) \\ &\equiv 0 \\しかし、& 0 \lt j-i \leq \frac{p-1}{2},0 \lt j+i \lt pより \\ j-i,&j+i \equiv 0 よってi^{2} \not\equiv j^{2}となり矛盾。 つまりi \equiv jとなる。\\題意&を示せた。 (\square) \end{align}$
$p$が素数$\Longleftrightarrow (p-1)! \equiv (p-1) \pmod{p}$
証明は有名なので概要だけ書く。
$n$とその逆元$\frac{1}{n}$とのペアを作ると、$n \equiv \frac{1}{n}$となる$n \equiv 1,p-1$をのぞいた$\frac{p-1}{2}$個のペアができる。そのため$(p-1)! \equiv 1^{\frac{p-1}{2}}\cdot 1 \cdot (p-1) \equiv (p-1)$
$(\frac{a}{p})\equiv a^{ \frac{p-1}{2} }$
これはwilsonの定理の証明で$n$と$\frac{1}{n}$を$n$と$\frac{a}{n}$に変えて考えれば求められます。
これらには、ほかにも原始根を使った証明もあります。
以下、簡略化のため次の集合を用います。
$A_{ \gt 0}=\{r | (\frac{r}{p})=1,0 \lt r \leq p-1\},A_{ \geq0 }=A_{ \gt 0} \cup {0}$
補題4を平方剰余で書き換えると補題5より次のようなものになります。
$\begin{align}\prod_{r \in A_{ \geq 0} }^{n}r \equiv (-1)^{ \frac{p+1}{2} }\end{align}$
これをさらに拡張できないか考え、補題１を$s \not\equiv 0$の場合で利用すると、次の面白い結果が得られます。
$s \not\equiv 0,s \in \mathbb{Z}$のとき
$\begin{align} 2\prod_{s \in A_{ \geq 0},r\not\equiv s^{2} }(s^{2}-r)\equiv (-1) \end{align}$
$\begin{align}補題1&を用いて m\equiv -\frac{s}{q}とおくと、(q \not\equiv 0) \\(-1) &\equiv (p-1)! (\because wilsonの定理)\\&\equiv \prod_{k=0,k\not\equiv m}^{p-1}(s+qk)\\&\equiv \prod_{k=1,k\not\equiv m}^{ \frac{p-1}{2} }(s+qk)(s-qk) \cdot s \cdot (s-qm) \\&\equiv \prod_{k=1,k\not\equiv m}^{ \frac{p-1}{2} }(s^{2}-q^{2}k^{2}) \cdot s \cdot (s-qm) \\&\equiv 2 \prod_{s \in A_{ \geq 0},r\not\equiv s^{2} }(s^{2}-r)\quad(\because s-qm \equiv 2s)\quad(\square) \end{align}$
もちろん$q=1$の場合だけで十分だけど、そうでないほうが発想源として便利だと思ったのでそうしませんでした。
この式を見ると、$s$と$q$に依存していて、さらに2という数字が特徴的だということがわかりますよね。なるべく対称性を保ちつつ変数を減らすために$s$に$1,2,\cdots,\frac{p-1}{2}$を代入して全てかけると次の結果が得られます。
$\begin{align}(-1)^{ \frac{p-1}{2} } \equiv 2^{ \frac{p-1}{2} } \cdot \prod_{r,t \in A_{ \gt 0},r \lt t }(r-t)^{2} \cdot \prod_{r \in A_{ \gt 0}}r \cdot (-1)^{ \frac{(p-1)(p-3)}{8} }\end{align}$
$\begin{align}\prod_{s=1}^{ \frac{p-1}{2} }(2\prod_{s \in A_{ \geq 0},r\not\equiv s^{2} }(s^{2}-r))&\equiv \prod_{s=1}^{ \frac{p-1}{2} }(2s^{2}\prod_{s \in A_{ \gt 0},r\not\equiv s^{2} }(s^{2}-r)) \\&\equiv 2^{ \frac{p-1}{2} } \cdot \prod_{r \in A_{ \gt 0}}r \cdot \prod_{r,t \in A_{ \gt 0},r \neq t }(r-t)\\&\equiv 2^{ \frac{p-1}{2} } \cdot \prod_{r \in A_{ \gt 0}}r \cdot \prod_{r,t \in A_{ \gt 0},r \lt t }(r-t)(t-r) \\&\equiv 2^{ \frac{p-1}{2} } \cdot \prod_{r \in A_{ \gt 0}}r \cdot \prod_{r,t \in A_{ \gt 0},r \lt t }(r-t)^{2} \cdot (-1)^{ {}_( \frac{p+1}{2}-1 ) \mathrm{ C }_2 }\quad(\because 補題5)\\&\equiv 2^{ \frac{p-1}{2} } \cdot \prod_{r,t \in A_{ \gt 0},r \lt t }(r-t)^{2} \cdot \prod_{r \in A_{ \gt 0}}r \cdot (-1)^{ \frac{(p-1)(p-3)}{8} }\quad(\square)\end{align}$
これを眺めていると見慣れた形に気付くと思います。そうです、$2^{ \frac{p-1}{2} }$です。これと補題7を合わせれば$(\frac{2}{p})$が求められそうですよね。ではこれを求めるために次の結果を示していきましょう。
$\begin{align}\prod_{r,t \in A_{ \gt 0},r \lt t }(r-t)^{2} \equiv ((\frac{p-1}{2})!)^{p-3} \end{align}$
$\begin{align} \prod_{r,t \in A_{ \gt 0},r \lt t }(r-t)^{2} &\equiv\prod_{0 \lt a \lt b \leq \frac{p-1}{2} }(a-b)^{2}(a+b)^{2}\\ここで\prod_{0 \lt a \lt b \leq \frac{p-1}{2} }&(a-b)^{2}をa-bの値ごとに分けて計算すると、\\ \prod_{0 \lt a \lt b \leq \frac{p-1}{2} }(a-b)^{2} &\equiv \prod_{i=1}^{ \frac{p-1}{2} }((i^{ \frac{p-1}{2}-i }))^{2}\\ &\equiv \prod_{i=1}^{ \frac{p-1}{2} }i^{p-1-2i} となり、\end{align}$
\begin{align}\\ \prod_{0 \lt a \lt b \leq \frac{p-1}{2} }(a+b)^{2}をa+b=lの値ごとに分けて計算すると、\end{align} \begin{align}\\
(i)2 \lt l \leq \frac{p-1}{2}&のとき\\ 2 \not\mid lで、(a,b)&=(l,l-1),\cdots,(\frac{l-1}{2},\frac{l+1}{2})となり\\&l^{2}は\frac{l-1}{2}個出てきて、\\ 2 \mid lで、(a,b)&=(l,l-1),\cdots,(\frac{l}{2}-1,\frac{l}{2}+1)となり\\ &\frac{l}{2}-1個出てくる。\end{align}
\begin{align}\\ \\ (ii)\frac{p-1}{2} &\lt l \leq p-2のとき\\ 2 \not\mid lで、(a,b)&=(l-\frac{p-1}{2},\frac{p-1}{2}),\cdots,(\frac{l-1}{2},\frac{l+1}{2})となり\\ &\frac{p-l}{2}個出てきて、\\ 2 \mid lで、(a,b)&=(l-\frac{p-1}{2},\frac{p-1}{2}),\cdots,(\frac{l}{2}-1,\frac{l}{2}+1)となり\\ &\frac{p-l-1}{2}個出てくる。\end{align}
$\begin{align} \\\\&lとp-lをペアにしようとすると、\\&lの最小値は3だが最大値がp-2のためp-2のペアがないが、\\&(i)でl=2を代入すると0個になるため、ペアがあると考えて計算しても\\&特に問題はない。\\&よってlとp-l(2\leq l \leq \frac{p-1}{2})をペアにすると、\end{align}$ $\begin{align}\\2 \not\mid lで、l^{l-1} \cdot (p-l)^{p-(p-l)-1} &\equiv l^{l-1} \cdot (l-p)^{l-1}\\ &\equiv l^{2l-2}\\ 2 \mid lで、l^{l-2 \cdot (p-l)^{p-(p-l)}} &\equiv l^{l-2} \cdot (l-p)^{l}\\ &\equiv l^{2l-2} となる。\end{align}$
$\begin{align} \therefore \prod_{0 \lt a \lt b \leq \frac{p-1}{2} }(a+b)^{2}&\equiv \prod_{i=1}^{ \frac{p-1}{2} }l^{2l-2} \quad(\because 2 \cdot 1-1=0)\\ \therefore \prod_{r,t \in A_{ \gt 0},r \lt t }(r-t)^{2} &\equiv \prod_{0 \lt a \lt b \leq \frac{p-1}{2} }(a-b)^{2}(a+b)^{2} \\ &\equiv \prod_{l=1}^{\frac{p-1}{2}}l^{p-3} \\ &\equiv ((\frac{p-1}{2})!)^{p-3} \quad (\square) \end{align}$
(この証明は、やっていることは単純だけど場合分けが多いせいで少し複雑になっているので、自分ではあまり好きではないです。)
さて、それでは$(\frac{2}{p})$を求めましょう。
$\begin{align} (\frac{2}{p})=(-1)^{ \frac{ p^{2}-1 }{8} }\end{align}$
$\begin{align}補題10,11より、 (-1)^{ \frac{ p-1 }{2} } &\equiv 2^{ \frac{p-1}{2} } \cdot \prod_{r,t \in A_{ \gt 0},r \lt t }(r-t)^{2} \cdot \prod_{r \in A_{ \gt 0}}r \cdot (-1)^{ \frac{(p-1)(p-3)}{8} }\\&\equiv 2^{ \frac{p-1}{2} } \cdot ((\frac{p-1}{2})!)^{p-3} \cdot (( \frac{p-1}{2} )!)^{2} \cdot (-1)^{ \frac{(p-1)(p-3)}{8} }\\&\equiv 2^{ \frac{p-1}{2} }\cdot (-1)^{ \frac{(p-1)(p-3)}{8} }\quad(\because Fermatの小定理)\\\therefore補題7より\quad(\frac{2}{p}) &\equiv 2^{ \frac{p-1}{2} }\\&\equiv (-1)^{ \frac{ p-1 }{2} }\cdot (-1)^{ \frac{(p-1)(p-3)}{8} }\\&\equiv (-1)^{ \frac{ p^{2}-1 }{8} }\quad(\square) \end{align}$
４．おわりに
さて、どうだったでしょうか。まあ、第２補充法則示すだけだったらガウスの補題を使ったほうがめちゃくちゃ楽で、ついでに相互法則まで示せるのでそっちのほうがいいんですが、今回はそこはメインじゃないので別にいいです。ここからいろいろなところに応用できそうなんですが、そこはまた機会があればやります。不備がありそうだったら気軽に言ってください。
この記事を高評価した人
この記事に送られたバッジ
投稿者
