0

自作問題001 解説

19
0
$$\newcommand{finf}[1]{\mathbb{F}_{#1}} $$

問題概要

$$ \# \{ (a{,}b) \in \mathbb{F}_p^{2} | \exists (x{,}m{,}n) \in \mathbb{Z}^{3} , p = \dfrac{x^{2}-ax+b}{mx-n} \} $$

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

解説

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

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



例えば, $ p = 5 $ のとき, $ \# \{ (a{,}b) \in \finf{5}^{2} | \exists ( \alpha {,} \beta ) \in \finf{5}^{2} , \alpha + \beta \equiv a , \alpha \beta \equiv b \} $ は,

$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline + & 0 & 1 & 2 & 3 & 4 & & × & 0 & 1 & 2 & 3 & 4 & & (+{,}×) & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 0 & 1 & 2 & 3 & 4 & & 0 & 0 & 0 & 0 & 0 & 0 & & 0 & (0{,}0) & (1{,}0) & (2{,}0) & (3{,}0) & (4{,}0) \\ \hline 1 & 1 & 2 & 3 & 4 & 0 & & 1 & 0 & 1 & 2 & 3 & 4 & & 1 & (1{,}0) & (2{,}1) & (3{,}2) & (4{,}3) & (0{,}4) \\ \hline 2 & 2 & 3 & 4 & 0 & 1 & & 2 & 0 & 2 & 4 & 1 & 3 & & 2 & (2{,}0) & (3{,}2) & (4{,}4) & (0{,}1) & (1{,}3) \\ \hline 3 & 3 & 4 & 0 & 1 & 2 & & 3 & 0 & 3 & 1 & 4 & 2 & & 3 & (3{,}0) & (4{,}3) & (0{,}1) & (1{,}4) & (2{,}2) \\ \hline 4 & 4 & 0 & 1 & 2 & 3 & & 4 & 0 & 4 & 3 & 2 & 1 & & 4 & (4{,}0) & (0{,}4) & (1{,}3) & (2{,}2) & (3{,}1) \\ \hline \end{array} $$

なので, $ \# \{ (a{,}b) \in \finf{5}^{2} | \exists ( \alpha {,} \beta ) \in \finf{5}^{2} \ {,}\ \alpha + \beta \equiv a , \alpha \beta \equiv b \} $


$ (a{,}b) = \begin{eqnarray} \left\{ \begin{array}{llll} (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{array} \right. \end{eqnarray} $


の計$15$になる(重複があることに注意する)


$ \finf{p} $上で, 和と積について交換法則が成り立つので, $ \alpha+\beta\equiv\beta+\alpha\equiv a, \alpha\beta\equiv\beta\alpha\equiv b $
これより,
$ \# \{ (a{,}b)\in\finf{p}^{2}|\exists(\alpha{,}\beta)\in\finf{p}^{2}, \alpha+\beta\equiv a, \alpha\beta\equiv b \} = \# \{ (a{,}b)\in\finf{p}^{2}|\exists(\alpha{,}\beta)\in\finf{p}^{2},\alpha+\beta\equiv a,\alpha\beta\equiv b, \alpha\leq\beta \} $が成立する.

また, $ \alpha_1+\beta_1\equiv\alpha_2+\beta_2\equiv a, \alpha_1\beta_1\equiv\alpha_2\beta_2\equiv b, \alpha_1\neq\alpha_2 \vee \beta_1\neq\beta_2 , \alpha_1\leq\beta_1, \alpha_2\leq\beta_2 $ を満たす $ (\alpha_1{,}\beta_1{,}\alpha_2{,}\beta_2)\in\finf{p}^{4} $ が存在すると仮定する. (この仮定が真であれば, 重複が存在しないことになる.)

$2$次合同方程式 $ x^{2}-ax+b\equiv 0 $ を考えたとき, $ x^{2}-(\alpha_1+\beta_1)x+\alpha_1\beta_1\equiv x^{2}-(\alpha_2+\beta_2)x+\alpha_2\beta_2\equiv 0 $ が成り立つ.
また, $ \finf{p} $上の$ n $次合同方程式について, $k$重解を$k$個の解と捉えると, 解は$n$個存在する. (この事実は, 数学的帰納法より容易に証明できる.)
よって, $\begin{cases} \alpha_1=\alpha_2\wedge\beta_1=\beta_2 & (1) \\ \alpha_1=\beta_2\wedge\beta_1=\alpha_2 & (2) \end{cases}$$2$つのうち何れかを満たす.
$(2)$の場合,
$\beta_1=\alpha_2\leq\beta_2=\alpha_1$より$\beta_1\leq\alpha_1$が導かれるが, $\alpha_1\leq\beta_1$より$(\alpha_1=\beta_1=\alpha_2=\beta_2)$となる.
これは$\alpha_1\neq\alpha_2,\beta_1\neq\beta_2$に矛盾する.
$(1)$の場合,
これも$\alpha_1\neq\alpha_2\vee\beta_1\neq\beta_2$に矛盾する.
よって, $3\leq p$のとき, $ \#\{(a{,}b)\in\finf{p}^{2}|\exists(\alpha{,}\beta)\in\finf{p}^{2},\alpha+\beta\equiv a,\alpha\beta\equiv b \} = \# \{(a,b)\in\finf{p}^{2}|a\leq b \} = \dfrac{p(p+1)}{2} $

$p=2$の場合,

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline + & 0 & 1 & & × & 0 & 1 & & (+{,}×) & 0 & 1 \\ \hline 0 & 0 & 1 & & 0 & 0 & 0 & & 0 & (0{,}0) & (1{,}0) \\ \hline 1 & 1 & 0 & & 1 & 0 & 1 & & 1 & (1{,}0) & (0{,}1) \\ \hline \end{array}$
となる.
$(a{,}b) = (0{,}0), (1{,}0), (0{,}1)$より, $\#\{(a{,}b)\in\finf{3}^{2}|\exists(\alpha{,}\beta)\in\finf{3}^{2},\alpha+\beta\equiv a,\alpha\beta\equiv b \} = 3$
また, $p=2$のとき$\dfrac{p(p+1)}{2} = 3$である.

よって, 任意の素数$p$について $\#\{(a{,}b)\in\finf{p}^{2}|\exists(\alpha{,}\beta)\in\finf{p}^{2},\alpha+\beta\equiv a,\alpha\beta\equiv b \} = \dfrac{p(p+1)}{2}$ が示された.

この問題の答えは$\dfrac{p(p+1)}{2}$である.

投稿日:20201114

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

pina_
pina_
19
890
本垢 @Kak1_n0_tane

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中