けんちょんの数学・情報・教育探検記

数学・情報・心理・教育など色々なことを書いていきます！

OMC 164 D 問題 (黄色, 400 点)

数学高校数学問題紹介 OMC OMC400点問題 OMC黄色問題整数問題 N(整数) 2次方程式数学A 数学A:整数素数互いに素中国剰余定理合同方程式方程式平方剰余 mod(素数)は体をなすこと

これまた面白かった！

平方剰余に関する複雑な議論などするのかなと思ったけど、そんな必要はなかった。

問題へのリンク

問題

素数 $P = 2^{107} - 1$ について、次の条件を満たす $1$ 以上 $P$ 以下の整数の組 $(a, b, c)$ の個数を $107 \times 109$ で割ったあまりを求めてください。

(条件) $ax^{2} + bx + c \equiv 0 \pmod P$ を満たす整数 $x$ が無限個存在し、それらが等差数列をなす

　

考えたこと

さあ、2 次の合同方程式 $ax^{2} + bx + c \equiv 0 \pmod P$ を頑張って解いていきましょう！

まず、最初に思ったことはこんな感じでした (これ以降、 $\pmod P$ を省略します)。

1 次の合同方程式 $bx + c \equiv 0$ なら簡単に解けるぞ。しかも $b \not \equiv 0$ であるならば、解は $x \equiv -b^{-1}c$ となって、等差数列になっているね！
問題として出題されている以上は、きっと $a \not \equiv 0$ であっても、解が等差数列をなすことがあるのだろう......！

これを踏まえて考察を深めていきます。その前に、一旦 $a \equiv 0$ の場合を片付けておきましょう。

のとき
- $c \equiv 0$ のとき：任意の整数 $x$ で解をもつ ( $1$ 通り)
- $c \not \equiv 0$ のとき：解なし
のとき
- 任意の $c$ に対して $x \equiv - b^{-1}c$ となる ( $P(P-1)$ 通り)

つまり、 $a \equiv 0$ の場合については、 $P(P-1) + 1$ 通りです。

　

2 次方程式を解く！

ここから先は、2 次方程式 $ax^{2} + bx + c \equiv 0$ を実際に解くつもりで考察を深めていきましょう。 $a \not \equiv 0$ なので、両辺に $a^{-1}$ をかけて、

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

となります。ここで、 $a^{-1}$ はなんだろう......となった方は、逆元という概念についてぜひ調べてみてください。平たく言えば、素数を法としたあまりの世界では、普通の有理数と同じように「足し算」「引き算」「掛け算」「割り算」ができるということです。

そして、さらに上の式を平方完成しましょう。普通の 2 次方程式の解の公式を導くのと同様の手続きです。

$(x + (2a)^{-1}b)^2 \equiv (2a)^{-2} (b^{2} - 4ac)$

となります。

ここで、平方剰余に関する知見があれば、次のことが直ちにみて取れます！

Case 1： $b^{2} - 4ac \equiv 0$ のとき、解は $x \equiv -(2a)^{-1}b$ と書ける
Case 2： $b^{2} - 4ac \not \equiv 0$ で $(2a)^{-2} (b^{2} - 4ac)$ が $P$ を法として平方剰余であるとき、1 つの平方剰余を $\sqrt{(2a)^{-2} (b^{2} - 4ac)}$ と表すこととすると、解は $x \equiv -(2a)^{-1}b \pm \sqrt{(2a)^{-2} (b^{2} - 4ac)}$ と書ける
Case 3： $b^{2} - 4ac \not \equiv 0$ で $(2a)^{-2} (b^{2} - 4ac)$ が $P$ を法として平方剰余でないとき、解なし

本当に 2 次方程式の解の公式のような結果になりましたね！

$b^{2} - 4ac \equiv 0$ である場合は、解の個数は $P$ を法として 1 個となります。

$b^{2} - 4ac \not \equiv 0$ である場合は、解なしであるか、解の個数が $P$ を法として 2 個であることになります。

　

解が等差数列をなすためには......！

ここで重要な考察をします。まず大前提として、一般に整数係数の $x$ の多項式を $f(x)$ としたとき、合同方程式 $f(x) \equiv 0 \pmod P$ の解は

$x \equiv \alpha, \beta, \gamma, \dots$

の形で書かれます。なぜなら、 $f(\alpha) \equiv 0 \pmod{P}$ が成り立つならば、 $f(\alpha + P) \equiv 0 \pmod{P}$ が成り立つからです。

ここで、 $P$ は素数であることから、解が等差数列になるパターンは限られることに注目します。

簡単のため、 $P = 7$ としてみましょう。このとき、合同方程式の解が等差数列をなすようなパターンは

解が $x \equiv \alpha$ となるパターン ( $\alpha = 0, 1, 2, 3, 4, 5, 6$ )
解が「すべての整数」となるパターン

の 2 つしかありません！

たとえば、 $x \equiv 2, 5 \pmod 7$ の様子を図示すると下図のようになります。

決して等差数列とはならないことが見て取れるでしょう。

一応きちんと示しておきましょう。合同方程式 $ax^{2} + bx + c \equiv 0$ の解が等差数列になるとき、その周期を $T$ とします。このとき、 $T$ は $P$ の約数になります。 $P$ は素数なので、 $T = 1, P$ のいずれかとなります。

　

個数を求める

ここまで来れば、いよいよこの問題を解くことができます！

$ax^{2} + bx + c \equiv 0$ の解が無限個存在し、等差数列をなすための必要十分条件は、以下のいずれかが成り立つことです。

$a \equiv b \equiv c \equiv 0$ である ( $1$ 通り)
$a \equiv 0$ かつ $b \not \equiv 0$ である ( $P(P-1)$ 通り)
$a \not \equiv 0$ かつ $b^{2} - 4ac \equiv 0$ である

最後の 3 番目の場合について、個数を求めましょう。

$a \not \equiv 0$ である $a$ を 1 つ固定すると、任意の $b$ に対して、 $c$ の値は $c \equiv (4a)^{-1}b^{2}$ と 1 つに決まります。よって、 $P(P-1)$ 通りです。

まとめると、求める個数は $2P(P-1) + 1$ 個となります。

　

詰め

最後に、 $P = 2^{107}-1$ として、 $2P(P-1) + 1 \pmod{107 \times 109}$ を求めます。

$2P(P-1) + 1$ を $107, 109$ で割った余りをそれぞれ求めて、中国剰余定理を適用して求めることにしましょう。

$107$ で割ったあまり

Fermat の小定理より、 $2^{106} \equiv 1 \pmod{107}$ なので、 $P \equiv 2 - 1 \equiv 1 \pmod{107}$ です。よって、

$2P(P-1) + 1 \equiv 2 \times 1 \times (1 - 1) + 1 \equiv 1 \pmod{107}$

$109$ で割ったあまり

Fermat の小定理より、 $2^{108} \equiv 1 \pmod{109}$ なので、 $P \equiv 2^{-1} - 1 \equiv 54 \pmod{109}$ です。よって、

$2P(P-1) + 1 \equiv 2 \times 54 \times (54 - 1) + 1 \equiv 57 \pmod{109}$

です。

中国剰余定理

求める値は、 $109$ で割ったあまりが $57$ であることから、求める値は $109t + 57$ と表せます。 $t$ の値を求めましょう。

$\begin{align} 109t + 57 &\equiv 1 \pmod{107} \\ 2t &\equiv -56 \pmod{107} \\ t &\equiv -28 \pmod{107} \\ t &\equiv 79 \pmod{107} \end{align}$

となります。

よって、求める値は $109 \times 79 + 57 = 8668$ です！！

　

感想

楽しい問題でした！！

特に、「 $ax^{2} + bx + c \equiv 0 \pmod P$ を満たす整数 $x$ が無限個存在し、それらが等差数列をなす」という条件に対して、必要十分条件を求める部分は、数学的考察を進める実感が得られて楽しいですね。

意外と、今までの人生で、 $\pmod{P}$ における 2 次方程式を解いたことはありませんでした！！