{x | b^x = a (mod m)} の構造

概要

$a, b, m$ が与えられて $\lbrace x \mid b^x \equiv a \pmod m \rbrace$ の構造を観察します。

結論

$S := \lbrace x \mid b^x \equiv a \pmod m \rbrace$ について、次のうちいずれかが成り立ちます。

$S = \emptyset$
$\exists\ 0 \le c \lt \log_2(m),\ S = \lbrace c \rbrace$
$\exists\ n \mid \lambda(m),\ \exists\ t,\ S = \lbrace x \mid x \equiv t \pmod n \rbrace$
$\exists\ 0 \le c \lt \log_2(m),\ \exists\ n \mid \lambda(m),\ \exists\ t,\ S = \lbrace x \mid x \gt c \land x \equiv t \pmod n \rbrace$

証明

$m = \prod_{i=1}^{k} p_i ^ {e_i}$ とすると、中国剰余定理から $\mathbb{Z} / m\mathbb{Z} \simeq \prod_{i=1}^{k} \mathbb{Z} / p_i ^ {e_i} \mathbb{Z}$ 。 $i$ を 1 つ固定して考えると、

$p \mid b, a \neq 0 \pmod {p^e}$ のとき、 $x$ は存在しないか、一意に定まる。
$p \mid b, a = 0 \pmod {p^e}$ のとき、 $x \gt c$ の形の条件が付く。
$p \nmid b$ のとき、 $x$ は存在しないか、 $x = t \pmod {n}$ の形の条件が付く (ただし $n \mid \lambda(p^e)$ )。