G - Simple Math Problem 2

考察

$a, b$ を互いに素とします。整数 $x, y$ が $x^3 \equiv x \pmod a, y^3 \equiv y\pmod b$ を満たすとき、中国剰余定理より $n\equiv x\pmod a, n \equiv y\pmod b$ を満たす $n$ が mod $ab$ で一意に存在します。

この $n$ に対して、 $n^3 \equiv x^3 \equiv x \pmod a, n^3 \equiv y^3 \equiv y \pmod b$ が成り立つため、 $n^3-n \equiv 0 \pmod a, n^3 - n \equiv 0 \pmod b$ が従います。同じく中国剰余定理より、 $n^3 - n \equiv 0 \pmod{ab}$ すなわち $n^3 \equiv n \pmod{ab}$ が成り立ちます。

逆に $0$ 以上 $ab$ 未満の $n^3 \equiv n \pmod {ab}$ を満たす整数 $n$ を指定したとき、$n$ から $n \equiv x \pmod a, n \equiv y \pmod b$ を満たす $(x, y)$ が存在し、これは $x^3 \equiv x \pmod a, y^3 \equiv y \pmod b$ を満たします。

今までの議論により、次のような解法が正当です。

1. $M$ を素因数分解して $M = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ とおく。
2. 各 $i=1,2,\cdots, k$ に対して、mod $p_i^{a_i}$ での $x^3 \equiv x$ の解をすべて求める。
3. Garner のアルゴリズムを用いて、解をすべて復元する。

ここの計算量は、解の個数を $K$ 個として、 $O(K \log M)$ 時間かかります。しかし、問題点として、まだ 2. の部分のステップに時間をかけすぎてしまうことがあります。そこで、素数べき $p^a$ に対してその解の特徴を考察します。

$p \ge 3$ のとき

$p \ge 3$ とします。 $x^3 - x = (x-1)x(x+1) \equiv 0 \pmod{p^a}$ の解は $0, 1, p^a - 1$ があります。しかし、実はそれだけであることが示されます。

もし他に解 $x$ があるとしたら、 $(x-1)x(x+1)$ は $p^a$ の倍数になります。よって、 $x-1, x, x+1$ のどれか $1$ つは $p^k$ の倍数になります。ここで、 $x \ne 0, 1, p^a-1$ なので、 $1 \le k \le a-1$ です。

しかし、 $p \ge 3$ であるので、 $(x-1)x(x+1)$ であって $p$ の倍数であるものは $1$ つしかなく、 $(x-1)x(x+1)$ はよって $p^a$ の倍数になりません。

よって、解は $0, 1, p^a-1$ の $3$ つだけです。

$p = 2$ のとき

$a = 1$ のとき、明らかに解は $x = 0, 1$ の $2$ つです。

$a = 2$ のとき、明らかに解は $x = 0, 1, 3$ の $3$ つです。

$a \ge 3$ のとき、解は $x = 0, 1, 2^{a-1}-1, 2^{a-1}+1, 2^a - 1$ の $5$ つです。 $v(t)$ を、 $t$ を $2$ で割ることができる回数とします。いま、解であるための必要十分条件は $v((x-1)x(x+1)) \ge a$ であることです。

$x \ne 0, 1, 2^a - 1$ として、先ほどの議論をなぞると、 $x-1, x+1$ がともに $2$ の倍数である必要があります。ここで、たとえば $f(x-1) = k \ge 2$ とすると、必ず $f(x+1) = 1$ となります。もし $f(x+1) \ge 2$ とすると、連続する $3$ つの整数の中に $4$ の倍数が $2$ 個現れてしまい矛盾します。

$k \le a-1$ であったので、 $f(x-1) = a-1$ すなわち $x = 2^{a-1} + 1$ が必要です。そしてこれは解になります。同様にして、 $f(x+1)=a-1$ の場合、 $x = 2^{a-1}- 1$ が導かれます。これで $p=2, a\ge 3$ のとき解は $x = 0, 1, 2^{a-1}-1, 2^{a-1}+1, 2^a-1$ の $5$ つであることが示されました。

まとめ

• $p \ge 3$ のとき、mod $p^a$ での解は $x = 0, 1, p^a - 1$ である
• $p = 2, a = 1$ のとき、mod $p^a$ での解は $x = 0, 1$ である
• $p = 2, a = 2$ のとき、mod $p^a$ での解は $x = 0, 1, 3$ である
• $p = 2, a \ge 3$ のとき、mod $p^a$ での解は $x = 0, 1, 2^{a-1}-1, 2^{a-1}+1, 2^a - 1$ の $5$ つである

これで mod $p^a$ での $x^3 \equiv x$ の解が $O(1)$ で求まり、この問題に答えることができます。

実装について

解の復元をする際、集合の直積の要素をすべて列挙する必要がありますが、これは再帰で求めることができます。また、Python を使用する場合は itertools.product が便利です。