ここでは群,環,体の知識を仮定します.
1.有理整数環上のイデアル論
有理整数環 \(\mathbb{Z}\) はユークリッド整域である.また,このことから単項イデアル整域であり,素元分解整域である.\(n\in\mathbb{Z}\) で生成されるイデアルを \((n)\) で表す.
\(a\) が \(b\) を割るとは,\(a=bc\) となる \(c\) が存在することであり \(b|a\) と表す.したがって全ての \(a\) で \(a|0\) となる.
\(\text{g.c.d.}(n,m)\) で \(n\) と \(m\) の最大公約数 ( greatest common divisor ) を表す.\(\text{l.c.m.}(n,m)\) で \(n\) と \(m\) の最小公倍数 ( least common multiple ) を表す.
命題 1.1
\[n|m \Longleftrightarrow (m)\subset (n)\]
\[(n)+(m)=(\text{g.c.d.}(n,m))\ ,\quad (n)\cap(m)=(\text{l.c.m.}(n,m))\]
証明
最初の同値は自明である.残りは \((n)+(m)\) と \((n)\cap(m)\) がそれぞれ \((n)\) と \((m)\) を含む最小のイデアルと, \((n)\) と \((m)\) に含まれる最大のイデアルであることからわかる.
命題 1.1 から明らかに \(n\) と \(m\) が互いに素なら \((n)\cap(m) = (nm)\) が成り立つ.
命題 1.2
整数 \(n,m\) が互いに素であることと \((n)+(m)=(1)\) であることは同値である.
証明
\((n)+(m)=(\text{g.c.d.}(n,m))\) であるから.
命題 1.3
\(d\geq 1\) を整数とする. \(\overline{x}\in\mathbb{Z}/d\mathbb{Z}\) に対して次は同値である.
(1) \(\overline{x}\) が乗法逆元を持つ.
(2) \(\overline{x}\) の代表元 \(x\) が \(d\) と互いに素である.
(3) \(\overline{x}\) が加法に関する巡回群 \(\mathbb{Z}/d\mathbb{Z}\) の生成元である.
証明
(1) \(\Rightarrow\) (2)
\(\overline{x}\) の逆元が \(\overline{y}\) とすると \(xy\equiv 1\mod d\) となるから \(xy+dm =1\) となる整数 \(m\) が存在する.したがって,\((x)+(d)=(1)\) であり \(x\) と \(d\) は互いに素である.
(2) \(\Rightarrow\) (3)
\(1\leq k\leq d\) をとる.\(k\cdot \overline{x}=0\) のとき \(k=d\) であることを示せば良い.\(k\cdot \overline{x}=0\) とすると \(kx=md\) なる \(m\in\mathbb{Z}\) が存在する.したがって \(x\) と \(d\) は互いに素だから \(kx\in (x)\cap (d)=(xd)\) となり,\(k=d\) である.
(3) \(\Rightarrow\) (1)
\(\overline{x}\) が生成元であるから \(k\cdot\overline{x} = 1\) となる \(1\leq k\leq d\) が存在する.したがって,\(\overline{k}\overline{x}=1\) である.
2.オイラー関数とメビウス関数
整数 \(d\geq 1\) に対して \(\varphi(d) = \text{Card}\,(\mathbb{Z}/d\mathbb{Z})^{\times}\) と定める.命題 1.3 から \(\varphi(d)\) は \(1\leq x\leq d\) なる \(d\) と互いに素な \(x\) の個数,または \(\mathbb{Z}/d\mathbb{Z}\) の生成元の個数といえる.
この \(\varphi\) をオイラー ( Euler ) 関数という.
フェルマー ( Fermat ) の小定理
\(a,d\geq 1\) が互いに素であるとき,
\[a^{\varphi(d)} \equiv 1\mod d\]
証明
命題 1.3 より \(\overline{a}\in (\mathbb{Z}/d\mathbb{Z})^{\times}\) であるから.
明らかに素数 \(p\) に対して \(\varphi(p)=p-1\) である.
また,\(\varphi(p^f)=p^f-p^{f-1}\) である.なぜならば,整数 \(1\leq x\leq p^e\) が \(p^e\) と互いに素でないとは \(x\) が \(p\) で割り切れることであり,このような整数は \(\{1\cdot p\ ,\ 2\cdot p,\ \cdots \ ,\ p^{f-1}\cdot p\}\) で尽くされ,\(p^{f-1}\) 個存在するからである.
命題 2.1
\(a,b\geq 1\) を互いに素な整数とすると,
\[\varphi(ab)=\varphi(a)\varphi(b)\]
が成り立つ.また,このことから,整数 \(n\geq 1\) の素因子を \(\{p_1,\cdots,p_r\}\) とすると,
\[\varphi(n)=n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_r}\right)\]
証明
中国剰余定理より,
\begin{eqnarray}
&&\mathbb{Z}/(ab)\mathbb{Z} \cong \mathbb{Z}/a\mathbb{Z} \times \mathbb{Z}/b\mathbb{Z} \\
&&\quad \Longrightarrow (\mathbb{Z}/(ab)\mathbb{Z})^{\times} \cong (\mathbb{Z}/a\mathbb{Z})^{\times} \times (\mathbb{Z}/b\mathbb{Z})^{\times}
\end{eqnarray}
よって,\(\varphi(ab)=\varphi(a)\varphi(b)\) である.また \(n=p_1^{f_1}\cdots p_r^{f_r}\) とおけば,
\begin{eqnarray}
\varphi(n) &=& \varphi(p_1^{f_1})\cdots \varphi(p_r^{f_r}) \\
&=& (p_1^{f_1}-p_1^{f_1-1})\cdots (p_r^{f_r}-p_r^{f_r-1}) \\
&=& p_1^{f_1}\cdots p_r^{f_r}\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_r}\right)
\end{eqnarray}
命題 2.2
\(n\geq 1\) を整数とする.このとき,
\[n=\sum_{d|n}\varphi(d)\]
証明
\(d\) を \(n\) の任意の約数とする.このとき,\(\mathbb{Z}/n\mathbb{Z}\) は巡回群なので位数 \(d\) の部分群 \(C_d\) をただ一つ持つ.\(\Phi_d\) を \(C_d\) の生成元全体の集合とする.\(\mathbb{Z}/n\mathbb{Z}\) の任意の元はある部分群 \(C_d\) の生成元だから,
\[n = \text{Card}\,(\mathbb{Z}/n\mathbb{Z}) = \sum_{d|n}\text{Card}\,(\Phi_d) = \sum_{d|n}\varphi(d)\]
である.ここで巡回群 \(C_d\) は \(\mathbb{Z}/d\mathbb{Z}\) と同型となることを用いた.
メビウス ( Möbius ) 関数 \(\mu\) を次で定義する.
\[\mu(n)=\left\{
\begin{array}{ccc}
0 & (n:\text{non-square-free}) \\
(-1)^k & (n=p_1\cdots p_k)
\end{array}
\right.
\]
命題 2.3
\(n\geq 2\) を整数とする.このとき,
\[\sum_{d|n}\mu(d) = 0\]
証明
\(n=p_1^{e_1}\cdots p_k^{e_k}\) と素因数分解すると,
\begin{eqnarray}
\sum_{d|n}\mu(d) &=& \sum_{0\leq x_i\leq e_i}\mu(p_1^{x_1}\cdots p_k^{x_k}) = \sum_{0\leq x_i\leq 1}\mu(p_1^{x_1}\cdots p_k^{x_k}) \\
&=& \mu(1) + \mu(p_1) + \cdots + \mu(p_k) \\
&&+ \mu(p_1p_2) + \mu(p_1p_3) + \cdots + \mu(p_{k-1}p_{k}) \\
&&+ \cdots + \mu(p_1\cdots p_k) \\
&=& 1-\binom{k}{1}+\binom{k}{2}-\cdots +(-1)^{k-1}\binom{k}{k-1}+(-1)^k \\
&=& (1-1)^k = 0
\end{eqnarray}
命題 2.4 (メビウスの反転公式)
\(f,g:\mathbb{N}\to\mathbb{C}\) が全ての正の整数 \(n\) に対して,
\[f(n) = \sum_{d|n} g(d)\]
となるとき,次が成り立つ.
\[g(n) = \sum_{d|n} \mu\left(\frac{n}{d}\right)f(d)\]
証明
\begin{eqnarray}
\sum_{d|n} \mu\left(\frac{n}{d}\right)f(d)
&=& \sum_{d|n} \sum_{\lambda|d} \mu\left(\frac{n}{d}\right) g(\lambda) \\
&\overset{(\rm{i})}{=}& \sum_{\lambda|n} \sum_{\delta|\frac{n}{\lambda}} \mu\left(\frac{n}{\lambda\delta}\right) g(\lambda) \\
&\overset{(\rm{ii})}{=}& \sum_{\lambda|n} g(\lambda) \sum_{\delta|\frac{n}{\lambda}} \mu(\delta) \\
&\overset{(\rm{iii})}{=}& g(n)\mu(1) = g(n) \\
\end{eqnarray}
(i) : \((d,\lambda)\) が \(\lambda |d|n\) なる整数の組みであることと \(\lambda |n\) かつ \(\frac{d}{\lambda}|\frac{n}{\lambda}\) なる整数の組みであることが同値だから,\(\delta=\frac{d}{\lambda}\) とおけば良い.
(ii) : \(\{\delta \mid \delta|N\} = \{\frac{N}{\delta} \mid \delta|N\}\) だから良い.
(iii) : \(\lambda = n\) のときを除いて,命題 2.3 から \(\sum\mu(\delta)=0\) となるから.
命題 2.4 から全ての \(n\) で \(n = \sum_{d|n} g(d)\) を満たす数論的関数 \(g:\mathbb{N}\to\mathbb{C}\) は \(\varphi\) 以外に存在しないことがわかる.
3.有限体
体 \(K\) が \(\text{ch}\,(K)=p\) であるとき自然な環準同型
\[\varphi:\mathbb{Z}\to\mathbb{K}:1\mapsto 1_{K}\]
を考えると \(\ker\varphi=p\mathbb{Z}\) となり準同型定理より \(\mathbb{Z}/p\mathbb{Z}\cong \text{Im}\,\varphi \subset K\) である.ここで \(K\) は特に整域だから \(p\mathbb{Z}\) は素イデアルであり,このことから \(p\) は素数か \(0\) である.
\(K\) が有限体であるとき \(\text{ch}\,(K)=p>0\) である.
\(\mathbb{Z}/p\mathbb{Z}\) は体であり,\(F_p\) と書くことにする.
命題 3.1
\(K\) を有限体とすれば,素数 \(p\) と整数 \(f\geq 1\) があって
\[\text{Card}\,(K)=p^f\]
証明
\(\text{ch}\,(K)=p\) とするれば \(F_p\cong L\subset K\) なる \(L\) が存在し,これは体の有限次拡大である.\([K:L]=f\) とおくと,\(\text{Card}\,(K)=p^f\) である.
定理 3.2
位数が等しい有限体は同型である.
証明
まず,\(F_p\) の代数閉包 \(\Omega\) の中に位数 \(q=p^f\) の体がただ一つ存在することを示す.フロベニウス ( Frobenius ) 準同型 \(\sigma:x\mapsto x^q\) の不変体 \(K_{\sigma}\subset\Omega\) は位数が \(q\) である.実際,\(x^q-x=0\) は微分が
\[qx^{q-1}-1 = -1\]
だから重根を持たないので,解が \(q\) 個存在するからである.
任意に位数 \(q\) の体 \(K\subset\Omega\) をとると,\(K^{\times}\) は位数が \(q-1\) の乗法群だから任意の \(x\in K^{\times}\) で \(x^{q-1}=1\) すなわち \(x^q=x\) が成り立つから,\(K\subset K_{\sigma}\) であり,\(K\) と \(K_{\sigma}\) は位数が等しいから \(K = K_{\sigma}\) である.これで \(\Omega\) の中に存在する位数 \(q=p^f\) の体は \(K_{\sigma}\) のみであることがわかった.
任意に位数 \(q\) の体 \(K\) を取れば,\(F_p\cong L\subset K\) なる部分体 \(L\) が存在し,\(\Omega\) と \(L\) の代数閉包は同型であるから,\(K\) と同型な \(\Omega\) の部分体が存在し,これは位数が \(q\) だから \(K\cong K_{\sigma}\) である.
命題 3.2 より有限体は位数のみによって定まるから,位数が \(q=p^f\) の有限体を \(F_q\) と表すことにする.
補題 3.3
\(G\) を位数 \(n\) の有限群とする.任意の \(d|n\) なる \(d\) に対して \(x^d=1\) を満たす \(x\) が高々 \(d\) 個ならば \(G\) は巡回群である.
証明
\(d\) を \(n \) の約数とする.\(x\in G\) が位数 \(d\) の元であれば位数 \(d\) の巡回群 \(\langle x\rangle\) が得られる.任意の \(y\in\langle x\rangle\) は \(y^d=1\) を満たすから,仮定より \(y^d=1\) なる \(y\in G\) は \(\langle x\rangle\) の元に限る.特に \(y\in G\) を位数 \(d\) の元とすれば \(y\in \langle x\rangle\) である.\(\langle x\rangle\) の生成元の個数は \(\varphi(d)\) であるから \(G\) の位数 \(d\) の元の個数は \(0\) か \(\varphi(d)\) である.
\(G\) の元の位数は必ず \(n\) を割るから,\(n=\sum_{d|n}\varphi(d)\) より位数 \(d\) の元は必ず存在する.したがって \(d=n\) とおけば \(G\) が巡回群であることがわかる.
定理 3.4
有限体 \(F_q\) に対して乗法群 \(F_q^{\times}\) は位数 \(q-1\) の巡回群である.
証明
体上の \(d\) 次方程式は高々 \(d\) 個しか解を持たないので,補題 3.3 を適用できる.
4.平方剰余
定義 4.1
互いに素な整数 \(a\) と \(p\) に対して \(x^2\equiv a \mod p\) が解を持つとき \(a\) が \(p\) の平方剰余であるという.また,\(a\) が \(p\) の平方剰余でないとき,\(p\) の平方非剰余という.
命題 4.2
\(p\) を奇素数とする.群準同型 \(f\) を
\[f:F_p^{\times}\ni x\mapsto x^{\frac{p-1}{2}} \in F_p^{\times}\]
と定めると,\(\text{Im}\,f = \{\pm 1\}\) かつ \(\ker f = (F_p^{\times})^2:= \{x^2\mid x\in F_p^{\times}\}\) である.
証明
\(x^{\frac{p-1}{2}}\) は \(y^2-1=0\) の解であるから \(x^{\frac{p-1}{2}}=\pm 1\) である.また,\(F_p^{\times}\) は位数 \(q-1\) の巡回群より \(x^{\frac{p-1}{2}}=-1\) なる \(x\in F_p^{\times}\) があるから \(\text{Im}\, f = \{\pm 1\}\) である.
\(F_p^{\times}\) は位数 \(q-1\) の巡回群だから \(x^{\frac{p-1}{2}}=1\) であることと \(x\in (F_p^{\times})^2\) であることとは同値である.よって,\(\ker f = (F_p^{\times})^2\) である.
定義 4.3
\(p\) を奇素数とする.\(a\in\mathbb{Z}\) に対して,
\(a\) が \(p\) で割り切れるならば \(\left(\frac{a}{p}\right)=0\)
\(a\) が \(p\) の平方剰余ならば \(\left(\frac{a}{p}\right)=1\)
\(a\) が \(p\) の平方非剰余ならば \(\left(\frac{a}{p}\right)=-1\)
と定める.これをルジャンドル ( Legendre ) 記号という.
定義から明らかに \(a\equiv a’ \mod p\) であれば,\(\left(\frac{a}{p}\right)=\left(\frac{a’}{p}\right)\) である.
ルジャンドル記号は \(a\) が \(p\) で割り切れる場合を除けば,命題 4.2 で定めた群準同型 \(f:F_p^{\times}\to \{\pm 1\}\) である.このことから容易にわかるように
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\]
が成り立つ.
定理 4.4(オイラー ( Euler ) の規準)
\[\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}}\mod p\]
証明
命題 4.2 から明らかである.
定理 4.5
\(p,q\) を相異なる奇素数とすると,次が成り立つ.
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]
\[\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}\]
\[\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}\]
上から平方剰余の相互法則,第一補充法則,第二補充法則と呼ぶ.
補充法則の証明
第一補充法則はオイラーの規準から明らかである.
第二補充法則について考える.\(\Omega\) を \(F_p\) の代数閉包とし,\(\alpha\in\Omega\) を \(1\) の原始 \(8\) 乗根とする.このとき \(\alpha^4=-1\) より \(\alpha^{2}+\alpha^{-2}=0\) よって \((\alpha+\alpha^{-1})^2=2\) である.したがって,\(y:=\alpha+\alpha^{-1}\in F_p\) かどうかを考えれば良い.
\(p\equiv \pm 1\mod 8\) ならば \(\alpha^p=\alpha^{\pm 1}\) だから
\[y^p=\alpha^p+\alpha^{-p} = \alpha^{\pm 1}+\alpha^{\mp 1} = y\]
ゆえに \(y\) は \(y^{p-1}=1\) の解であり,この方程式の解は \(F_p\) の元のみであるから \(y\in F_p\) である.よって,\(\left(\frac{2}{p}\right)=1\) である.
\(p\equiv \pm 5\mod 8\) ならば \(\alpha^4=-1\) より,
\[y^p=\alpha^p+\alpha^{-p} = \alpha^{\pm 5}+\alpha^{\mp 5} = -(\alpha^{\pm 1}+\alpha^{\mp 1}) = -y\]
ゆえに \(y\) は \(y^{p-1}=-1\) の解であり,\(F_p\) の元はこの方程式を満たさないから \(y\notin F_p\) である.よって,\(\left(\frac{2}{p}\right)=-1\) である.
\(p\ \text{mod}\,8\) が \(\pm 1\) ならば \((-1)^{\frac{p^2-1}{8}}\) は \(1\) であり,\(\pm 5\) ならば \((-1)^{\frac{p^2-1}{8}}\) は \(-1\) であることは容易にわかる.これで第二補充法則が示された.
補題 4.6
\(p,k\) を相異なる奇素数,\(\Omega\) を \(F_p\) の代数閉包,\(\omega\in\Omega\) を \(1\) の原始 \(k\) 乗根とする.\(x\in F_k\) に対してガウス和
\[y=\sum_{x\in F_k}\left(\frac{x}{k}\right)\omega^x\]
に対して \(y^2=(-1)^{\frac{k-1}{2}}k\) かつ \(y^{p-1}=\left(\frac{p}{k}\right)\) が成り立つ.
証明
\[y^2=\sum_{x,z\in F_k}\left(\frac{xz}{k}\right)\omega^{x+z}=\sum_{u\in F_k}\omega^{u}\sum_{t\in F_k}\left(\frac{t(u-t)}{k}\right)\]
\(t\neq 0\) のとき,
\[\left(\frac{t(u-t)}{k}\right) = \left(\frac{-t^2}{k}\right)\left(\frac{1-ut^{-1}}{k}\right) = (-1)^{\frac{p-1}{2}}\left(\frac{1-ut^{-1}}{k}\right)\]
したがって,
\[k=\sum_{u\in F_k}\omega^{u}C_u\ ,\quad C_u = \sum_{0\neq t\in F_k}\left(\frac{1-ut^{-1}}{k}\right)\]
を示せば良い.\(C_0 = \sum_{0\neq t\in F_k}\left(\frac{1}{k}\right) = k-1\) かつ \(u\neq 0\) ならば \(s=1-ut^{-1}\neq 1\) であるから,
\[C_u = \sum_{s\in F_k}\left(\frac{s}{k}\right)-\left(\frac{1}{k}\right) \quad (u\neq 0)\]
命題 4.2 より \(\left(\frac{s}{k}\right)\) は \(\pm 1\) をちょうど半分ずつとるから,\(C_u=-\left(\frac{1}{k}\right)=-1\) である.したがって,
\[\sum_{u\in F_k}\omega^{u}C_u = C_0-\sum_{0\neq u\in F_k}\omega^{u} = k-1-\sum_{0\neq u\in F_k}\omega^{u}\]
\(\omega\) は原始 \(k\) 乗根であるから \(\sum_{0\neq u\in F_k}\omega^{u}=-1\) であり,
\[\sum_{u\in F_k}\omega^{u}C_u = k\]
これで,\(y^2=(-1)^{\frac{k-1}{2}}k\) がわかった.また,\(\left(\frac{p}{k}\right)=\left(\frac{p^2}{k}\right)\left(\frac{p^{-1}}{k}\right)\) より,
\[y^p = \sum_{x\in F_k}\left(\frac{x}{k}\right)\omega^{xp} = \sum_{z\in F_k}\left(\frac{zp^{-1}}{k}\right)\omega^{z} = \left(\frac{p^{-1}}{k}\right)y = \left(\frac{p}{k}\right)y\]
\(y\neq 0\) であるから,\(y^{p-1}=\left(\frac{p}{k}\right)\) がわかった.
相互法則の証明
補題 4.6 より \(y^{2(p-1)}=1\) であるから \(y^2\in F_p\) かつ \(y^{p-1}=\pm 1\) である.また,
\[\left(\frac{y^2}{p}\right)=1 \Leftrightarrow y\in F_p \Leftrightarrow y^{p-1}=1\]
であるから,補題 4.6 より
\[\left(\frac{(-1)^{\frac{k-1}{2}}k}{p}\right)=\left(\frac{y^2}{p}\right)=y^{p-1}=\left(\frac{p}{k}\right)\]
\[\left(\frac{(-1)^{\frac{k-1}{2}}k}{p}\right)=\left(\frac{-1}{p}\right)^{\frac{k-1}{2}}\left(\frac{k}{p}\right)=(-1)^{\frac{p-1}{2}\frac{k-1}{2}}\left(\frac{k}{p}\right)\]
これで,相互法則が示された.
参考文献
・高木貞治,初等整数論講義
・J.-P. Serre,数論講義