自作問題001 解説

問題概要

$# {(a, b) \in F_{p}^{2} | \exists (x, m, n) \in Z^{3}, p = \frac{x^{2} - a x + b}{m x - n}}$

この問題が載っている記事はこちらから

解説

以下, 特に断りのない場合, $a \equiv b$ は $a \equiv b (\mod p)$ を表すものとする.
まず、 $p = \frac{x^{2} - a x + b}{m x - n}$ を変形すると,
$x^{2} - (m p + a) + n p + b = 0$ となる. $x, m, n$ は変数なので, $x^{2} - a x + b \equiv 0$ を満たす $(a, b) \in F_{p}^{2}$ の個数と一致する.
解と係数の関係より
$α + β \equiv a (\mod p), α β \equiv b (\mod p)$
を満たす $(α, β) \in F_{p}^{2}$ が存在するような $(a, b) \in F_{p}^{2}$ の個数が答えと一致する.

つまり,
$# {(a, b) \in F_{p}^{2} | \exists (α, β) \in F_{p}^{2}, α + β \equiv a, α β \equiv b}$ を求めれば良い.

例えば,

p = 5

のとき,

# {(a, b) \in F_{5}^{2} | \exists (α, β) \in F_{5}^{2}, α + β \equiv a, α β \equiv b}

は,

\begin{array}{cccccccccccccccccccc} + & 0 & 1 & 2 & 3 & 4 & \times & 0 & 1 & 2 & 3 & 4 & (+, \times) & 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 1 & 2 & 3 & 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & (0, 0) & (1, 0) & (2, 0) & (3, 0) & (4, 0) \\ 1 & 1 & 2 & 3 & 4 & 0 & 1 & 0 & 1 & 2 & 3 & 4 & 1 & (1, 0) & (2, 1) & (3, 2) & (4, 3) & (0, 4) \\ 2 & 2 & 3 & 4 & 0 & 1 & 2 & 0 & 2 & 4 & 1 & 3 & 2 & (2, 0) & (3, 2) & (4, 4) & (0, 1) & (1, 3) \\ 3 & 3 & 4 & 0 & 1 & 2 & 3 & 0 & 3 & 1 & 4 & 2 & 3 & (3, 0) & (4, 3) & (0, 1) & (1, 4) & (2, 2) \\ 4 & 4 & 0 & 1 & 2 & 3 & 4 & 0 & 4 & 3 & 2 & 1 & 4 & (4, 0) & (0, 4) & (1, 3) & (2, 2) & (3, 1) \end{array}

なので,

# {(a, b) \in F_{5}^{2} | \exists (α, β) \in F_{5}^{2}, α + β \equiv a, α β \equiv b}

は

(a, b) = \begin{array}{r} {\begin{cases} (0, 0), (0, 1), (0, 4) \\ (1, 0), (1, 3), (1, 4) \\ (2, 0), (2, 1), (2, 2) \\ (3, 0), (3, 1), (3, 2) \\ (4, 0), (4, 3), (4, 4) \end{cases} \end{array}

の計

15

になる(重複があることに注意する)

F_{p}

上で, 和と積について交換法則が成り立つので,

α + β \equiv β + α \equiv a, α β \equiv β α \equiv b

これより,

# {(a, b) \in F_{p}^{2} | \exists (α, β) \in F_{p}^{2}, α + β \equiv a, α β \equiv b} = # {(a, b) \in F_{p}^{2} | \exists (α, β) \in F_{p}^{2}, α + β \equiv a, α β \equiv b, α \leq β}

が成立する.

また,

α_{1} + β_{1} \equiv α_{2} + β_{2} \equiv a, α_{1} β_{1} \equiv α_{2} β_{2} \equiv b, α_{1} \neq α_{2} \lor β_{1} \neq β_{2}, α_{1} \leq β_{1}, α_{2} \leq β_{2}

を満たす

(α_{1}, β_{1}, α_{2}, β_{2}) \in F_{p}^{4}

が存在すると仮定する. (この仮定が真であれば, 重複が存在しないことになる.)

2

次合同方程式

x^{2} - a x + b \equiv 0

を考えたとき,

x^{2} - (α_{1} + β_{1}) x + α_{1} β_{1} \equiv x^{2} - (α_{2} + β_{2}) x + α_{2} β_{2} \equiv 0

が成り立つ.
また,

F_{p}

上の

n

次合同方程式について,

k

重解を

k

個の解と捉えると, 解は

n

個存在する. (この事実は, 数学的帰納法より容易に証明できる.)
よって,

{\begin{cases} α_{1} = α_{2} \land β_{1} = β_{2} & (1) \\ α_{1} = β_{2} \land β_{1} = α_{2} & (2) \end{cases}

の

2

つのうち何れかを満たす.

(2)

の場合,

β_{1} = α_{2} \leq β_{2} = α_{1}

より

β_{1} \leq α_{1}

が導かれるが,

α_{1} \leq β_{1}

より

(α_{1} = β_{1} = α_{2} = β_{2})

となる.
これは

α_{1} \neq α_{2}, β_{1} \neq β_{2}

に矛盾する.

(1)

の場合,
これも

α_{1} \neq α_{2} \lor β_{1} \neq β_{2}

に矛盾する.
よって,

3 \leq p

のとき,

# {(a, b) \in F_{p}^{2} | \exists (α, β) \in F_{p}^{2}, α + β \equiv a, α β \equiv b} = # {(a, b) \in F_{p}^{2} | a \leq b} = \frac{p (p + 1)}{2}

$p = 2$ の場合,

$\begin{array}{ccccccccccc} + & 0 & 1 & \times & 0 & 1 & (+, \times) & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & (0, 0) & (1, 0) \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & (1, 0) & (0, 1) \end{array}$
となる.
$(a, b) = (0, 0), (1, 0), (0, 1)$ より, $# {(a, b) \in F_{3}^{2} | \exists (α, β) \in F_{3}^{2}, α + β \equiv a, α β \equiv b} = 3$
また, $p = 2$ のとき $\frac{p (p + 1)}{2} = 3$ である.