ぺんぎんさんのおうち

トリトリトリ

タイトルは後で考える

いくつか命題を証明していきたい.

素数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) \)であるため単射であるならば全射でもある. 単射であることを示そう.

単射の定義より, \(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\) の解が存在することを示している. この場合でも位数は変わらない.