いくつか命題を証明していきたい.
奇素数pを法とすると平方剰余の個数は(p-1)/2個となる
\(A := \{x^{2} \, mod \, p \mid x \in GF(p) \} \) としたときに, \( \#A = \frac{p-1}{2} \) となることを示したい.
まず\(GF(p) = \{1, 2, ..., p-1 \}\), \(\#GF(p) = p-1\)であり, \(\forall a \in A, a^{\frac{p-1}{2}} \equiv 1 \, mod \, p\)
\(x^{2} \equiv (p-x)^{2} \, mod \, p\) であるため,
\begin{eqnarray} 1^{2} &\equiv& (p-1)^{2} \, mod \, p \newline 2^{2} &\equiv& (p-2)^{2} \, mod \, p \newline . \newline . \newline ({\frac{p-1}{2}})^{2} &\equiv& ({\frac{p+1}{2}})^{2} \, mod \, p \newline \end{eqnarray}
したがって\( \#A = \frac{p-1}{2} \)である. \(GF(p)\)の半分の元は平方剰余, もう半分は平方非剰余であることを言っている.
p ≡ 2 mod 3 のとき, x3 = a mod pはただ一つのみ解を持つ
\(f_p(x) = x^{3}\) が全単射であることを示せばよく, \( f: GF(p) \rightarrow GF(p) \)であるため単射であるならば全射でもある. 単射であることを示そう.
- 単射 (one to one)
単射の定義より, \(f_p(x) = f_p(y) \) なら \(x = y\)である.
\begin{eqnarray} x^{3} &\equiv & y^{3} \, (mod \, p) \newline (xy^{-1})^{3} & \equiv & 1 \newline \end{eqnarray}
ここで一旦置いておく.
先に, \(z^{3} \equiv 1 \, mod \, p; z \in GF(p) \) なら\( z \equiv 1 \, mod \, p\) を示す.
\(z^{3} = 1\)であるから \( \#G(z) \mid 3 \). これは\((1, 3)\)のどちらかである.
またラグランジュの定理より, \(G(z)\)は\(GF(p)\)の部分群であるため \( \#G(z) \mid \#GF(p) \)でなければならない.
\(p \equiv 2 \, mod \, 3\)より \(p = 3k + 2\)
\(\#GF(p) = p - 1 = 3k + 1 \)
\( \#G(z) \mid \#GF(p) \) となる\(\#G(z)\)は1のみであるから \( z^{3} \equiv 1 \, mod \, p\) なら \( z \equiv 1 \, mod \, p\)
これを踏まえて上の式を考える.
\begin{eqnarray}
(xy^{-1})^{3} & \equiv & 1 \newline
xy^{-1} & \equiv & 1 \newline
x & \equiv & y \, mod \, p
\end{eqnarray}
\(x, y \in GF(p)\)なので \(x \equiv y\)から\(x = y\)が言える.
\(f_p(x) = f_p(y) \) なら \(x = y\)を示せたので, \(f_p(x) = x^{3}\)は単射である.
したがって\(f_p(x) = x^{3}\)は全単射であり, p ≡ 2 mod 3のとき, x3 = a mod pはただ一つのみ解を持つ.
以下参考:
If 𝑝≡2 mod 3, 𝑥3≡𝑎 mod 𝑝 has only one solution modulo 𝑝.
上の2つは, 楕円曲線\(E_p(0, b); p \equiv 2 \, mod \, 3\) の位数が\(p+1\)であることを示すために使われる.
\(K := \{x^{3} + b \mid x \in GF(p), b \neq 0 \} \) のとき, \(K = \{ 0 \} \cup GF(p) \backslash \{b\} \neq GF(p) \) であるが, これは\(x^{3} + b \equiv 0 \, mod \, p\) の解が存在することを示している. この場合でも位数は変わらない.