平方剰余の相互法則(2) - エレファント・コンピューティング調査報告

【剰余類】

整数全体の集合を $\mathbb{Z}$ と書きます。整数 $n$ , $x$ に対して $x + n\mathbb{Z} = \{ x + nk | k∈\mathbb{Z} \}$ を $n$ を法とする剰余類といいます。整数 $x$ , $y$ が同じ剰余類 $(x + n\mathbb{Z})$ に属することを $x$ は $n$ を法として $y$ に合同( $x$ , $y$ は $n$ を法として合同)であるといい $x≡y \ (\mathrm{mod} \ n)$ と書きます。

剰余類に

$(x + n\mathbb{Z}) + (y + n\mathbb{Z}) = (x + y) + n\mathbb{Z}$
$-(x + n\mathbb{Z}) = (-x) + n\mathbb{Z}$
$(x + n\mathbb{Z})(y + n\mathbb{Z}) = xy + n\mathbb{Z}$

とすることで足し算、引き算、掛け算を定義することができます。剰余類全体の集合は環になります。これを $n$ を法とする剰余環といい $\mathbb{Z}/n\mathbb{Z}$ と書きます。

【群の定義】

集合 $G$ に演算 $x + y$ が定義されていて、次の条件が成り立っているとき、 $G$ は群であるといいます。

すべての $G$ の元 $x$ , $y$ , $z$ に対して $( x + y ) + z = x + ( y + z )$ (結合法則)
ある $G$ の元 $0$ が存在して、すべての $R$ の元 $x$ に対し $0 + x = x + 0 = x$ が成り立つ。 $0$ を $G$ の単位元という。
すべての $G$ の元 $x$ に対して、 $y + x = x + y = 0$ をみたす $G$ の元 $y$ が存在する。 $y$ を $x$ の逆元といい、 $-x$ と書く。

群 $G$ のすべての元 $x$ 、 $y$ に対して $x + y = y + x$ (交換法則)が成り立つとき、 $G$ は可換群またはアーベル群といいます。

【環の定義】

集合 $R$ に2つの演算、加法 $x + y$ 、乗法 $xy$ が定義されていて、次の条件が成り立っているとき、 $R$ は環であるといいます。

は加法に関して可換群である。すなわち
- (i) すべての $R$ の元 $x$ , $y$ , $z$ に対して $( x + y ) + z = x + ( y + z )$ (結合法則)
- (ii) すべての $R$ の元 $x$ , $y$ に対して $x + y = y + x$ (交換法則)
- (iii) ある $R$ の元 $0$ が存在して、すべての $R$ の元 $x$ に対し $0 + x = x + 0 = x$ が成り立つ。 $0$ を $R$ の零元(zero element)という。
- (iv) すべての $R$ の元 $x$ に対して、加法の逆元が存在する。すなわち $y + x = x + y = 0$ をみたす $R$ の元 $y$ が存在する。この $y$ を $-x$ と書く。
$R$ は乗法に関して結合法則が成り立つ。すなわちすべての $R$ の元 $x$ , $y$ , $z$ に対して $(xy)z = x(yz)$
$R$ は乗法に関して交換法則が成り立つ。すなわちすべての $R$ の元 $x$ , $y$ に対して $xy = yx$
$R$ は乗法の単位元(単に $R$ の単位元という) 1 をもつ。すなわち $R$ の元 $1$ が存在してすべての $R$ の元 $x$ に対して $1x = x1 = x$
分配法則が成り立つ。すなわちすべての $R$ の元 $x$ , $y$ , $z$ に対して $x(y + z) = xy + xz、 (x + y)z = xz + yz$

$x + (- y) を x - y$ と書きます。

【体の定義】

$0$ 以外の元がすべて乗法の逆元を持つ環を、体といいます。すなわち $F$ が環で、任意の $F$ の元 $x$ に対して $xy = yx = 1$ を満たす $F$ の元 $y$ が存在するとき、 $F$ は体であるといいます。

$p$ が素数のときに $\mathbb{Z}/p\mathbb{Z}$ は体になります。
[証明]
$p$ は素数なので、整数 $x$ に対して、 $mx + np = 1$ を満たす整数 $m$ , $n$ が存在します。 $mx≡1 \ (\mathrm{mod} \ p)$ となるので $m + \mathbb{Z}$ は $x + \mathbb{Z}$ の乗法の逆元となります。
[証明終わり]

$\mathbb{Z}/p\mathbb{Z}$ を $F_p$ と書きます。

群(演算は掛け算で書きます) $G$ の元 $x$ が存在して $G = \{1, x^{±1}, x^{±2}, … \}$ となるとき ( $x^n$ は $n$ 個の $x$ の積、 $x^{-1}$ は $x$ の逆元、 $x^{-n}$ は $n$ 個の $x$ の逆元の積です)、 $G$ を巡回群といいます。 $x$ を $G$ の生成元といいます。

$G$ の元 $x$ に対して $\{1, x^{±1}, x^{±2}, … \}$ を $\langle x \rangle$ と書きます。 $\langle x \rangle$ の元の個数が有限のとき、 $\langle x \rangle$ の元の個数を $x$ の位数といいます。

群 $G$ の部分集合 $H$ が、 $G$ の演算によって群になるとき、 $H$ は $G$ の部分群であるといいます。 $x$ を $G$ の元とすると $\langle x \rangle$ は $G$ の部分群となります。

$G$ を群、 $H$ を $G$ の部分群とします。 $G$ の元 $x$ に対して $xH$ を $xy$ ( $y$ は $H$ の元)という元の全体の集合とします。 $xH$ を左剰余類といいます。異なる左剰余類の共通部分は空となります。 $H$ の元の個数が有限のとき、 $xH$ の元の個数は $H$ の元の個数に等しくなります。さらに $G$ の元の個数が有限のとき、 $G$ は共通部分のない左剰余類の和集合になるので、 $G$ の元の個数は $H$ の元の個数の倍数になります。

$x$ , $y$ を可換群 $G$ の元とします。 $x$ の位数が $m$ 、 $y$ の位数が $n$ 、 $m$ と $n$ が互いに素( $1$ , $-1$ 以外の共通の約数を持たない)であるとき、 $xy$ の位数は $mn$ となります。
[証明]
$(xy)^k = 1$ とします。 $1 = (xy)^{km} = (x^{km})(y^{km}) = y^{km}$ より $km$ は $n$ の倍数となります。 $m$ と $n$ が互いに素なので $k$ は $n$ の倍数となります。 $1 = (xy)^{kn} = (x^{kn})(y^{kn}) = x^{kn}$ より $kn$ は $m$ の倍数となります。 $m$ と $n$ が互いに素なので $k$ は $m$ の倍数となります。よって $k$ は $mn$ の倍数となります。逆に $k$ を $mn$ 倍数とすると $(xy)^k = (x^k)(y^k) = 1$ となるので、 $xy$ の位数は $mn$ となります。
[証明終わり]

$F$ を体、 $f(X)$ を $F$ の元を係数とする $n$ 次以下の多項式( $F$ の元と $X$ から足し算、引き算、掛け算を繰り返してできた式。 $n$ 次以下とは $f(X) = a[0] + a[1]・X + a[2]・X^2 + … + a[n]・X^n$ ( $a[0]$ , $a[1]$ , $a[2]$ , …. $a[n]$ は $F$ の元)と書くことができるということをいいます)とすると、 $f(a) = 0$ を満たす $F$ の元 $a$ の個数は $n$ 以下となります( $f(a)$ は $f(X)$ の $X$ を $a$ で置き換えたもので、 $F$ の元となります)。
[証明]
$n$ に関する帰納法によって証明します。 $f(a) = 0$ とすると、 $f(X)$ を $(X - a)$ で割ると余りは $0$ となります。よって $f(X) = (X - a)g(X)$ を満たす $n-1$ 次以下の多項式 $g(X)$ が存在します。帰納法の仮定により $g(b) = 0$ を満たす $b$ は $n-1$ 個以下なので $f(a) = 0$ を満たす a は $n$ 個以下となります。
[証明終わり]

$F$ が有限体のとき $F^* = F - \{0\}$ は乗法に関して巡回群になります。
[証明]
$x$ を $F^*$ の位数が最大の元とし、 $x$ の位数を $m$ とします。 $\langle x \rangle ≠ G$ とすると $G - \langle x \rangle$ の元 $y$ が存在します。 $y$ の位数を $n$ とし、 $k$ を $m$ と $n$ の最大公約数とします。 $z = y^{(n/k)}$ とおくと $z^m = y^{(mn/k)} = (y^n)^{(m/k)} = 1$ となります。 $\langle x \rangle = \{x^e | e = 0, 1, 2, … , m-1\}$ の元 $x^e$ は $(x^e)^m = (x^m)^e = 1$ を満たすので、 $a^m = 1$ を満たす $F^*$ の元(最大 $m$ 個) $a$ は $\langle x \rangle$ の元となります。よって $z$ は $\langle x \rangle$ の元となります。 $n/k = 1$ ならば $y = z ∈ \langle x \rangle$ となるので $n/k > 1$ となります。 $w = x^k・y$ とおくと、 $w の位数 = x^k の位数 × y の位数 = (m/k)・n = mn/k > m$ となります。 $x$ の位数が最大であることに反するので $\langle x \rangle = G$ となり、 $G$ は巡回群となります。
[証明終わり]

$F_p^*$ は巡回群になります。

【フェルマーの小定理】

$p$ が $2$ ではない素数、 $a$ が $p$ と素な整数のとき、 $a$ の $p-1$ 乗は $p$ を法として $1$ と合同になります。
[証明]
$x$ を $F_p^*$ の生成元とすると、 $x^{p-1} = 1$ となります。 $a$ を含む剰余類はある $x^e$ に等しいので $a^{p-1} + p\mathbb{Z} = (x^e)^{p-1} = (x^{p-1})^e = 1$ となります。
[証明終わり]

【オイラーの規準】

$p$ が $2$ ではない素数、 $a$ が $p$ と素な整数のとき、 $a$ が法 $p$ に関する平方剰余のとき、 $a$ の $(p-1)/2$ 乗を $p$ で割ったときの余りは $1$ 、 $a$ が法 $p$ に関する平方剰余ではないとき、 $a$ の $(p-1)/2$ 乗を $p$ で割ったときの余りは $p-1$ になります。
[証明]
$a^{p-1}≡1 \ (\mathrm{mod} \ p)$ となるので $a^{ (p-1)/2}≡±1 \ (\mathrm{mod} \ p)$ となります。 $a≡x^2 \ (\mathrm{mod} \ p)$ とすると $a^{ (p-1)/2}≡x^{p-1}≡1 \ (\mathrm{mod} \ p)$ となります。逆に $a^{ (p-1)/2}≡1 \ (\mathrm{mod} \ p)$ とします。 $r$ を $F_p^*$ の生成元として、 $a + p\mathbb{Z} = r^e$ とします。 $(r^e)^{ (p-1)/2} = 1$ より $e(p-1)/2$ は $p-1$ の倍数となり、 $e$ は $2$ の倍数となるので、 $a$ は法 $p$ に関する平方剰余となります。
[証明終わり]