読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

素数冪 mod における階乗の周期性

整数論

概要

素数 mod における階乗の周期性は Wilson の定理としてよく知られている。

Wilson の定理:$p$ が素数であるとき、かつそのときに限り $(p-1)! \equiv p-1\;(\mathrm{mod}\; p)$

$p!\equiv0$ は当然であるため、この記事では階乗は既約のものを扱う。すなわち $p$ の倍数以外の $n$ 以下の正整数の積 $(n!)_p$ について取り扱う。 Wilson の定理から$(n!)_p$ の周期性が証明できる。

$$ ((n\;\mathrm{mod}\;2p)!)_p \equiv (n!)_p $$

実は $p^q$ においても周期性が存在し、

$$ ((n\;\mathrm{mod}\;2p^q)!)_{p} \equiv (n!)_{p} $$

となる。この記事ではこの等式の証明と、この周期性を用いたテクニックを説明する。

定理の証明

$(\mathbb{Z}/p^q\mathbb{Z})^{\times}$ は群になるから、任意の元に逆元が存在する。$(2p^q!)_p$ の中には同じ要素が 2 つずつ存在するので、逆元とペア組して積をとることにより 1 にできる。よって $(2p^q)_p\equiv 1$である。

実際には Wilson の定理のときと同様にもっと強いことがいえる。$(\mathbb{Z}/p^q\mathbb{Z})^{\times}$ の構造を把握してればすぐに示せる。

原始根の存在定理

素数 mod では原始根というものが存在する。$ \mathrm{mod}\; p $ における原始根 $g$ というのは $\{1,2,3,\ldots,p-1\}=\{1,g,g^2,\ldots,g^{p-2}\}$ が成り立つ数のことである。 $g$ を累乗していくだけで $ \mathrm{mod}\; p $ をすべて列挙できる数、とも言える。群論的に言えば生成元である。

原始根の存在が言えると、Wilson の定理を示すことができる。

$(n-1)!$ というのは$1,2,3,\ldots,p-1$ のすべての積をとったものである。 これは $1,g,g^2,\ldots,g^{p-2}$ のすべての積をとったものと等しい。

$g$と$g^{p-2}$、$g^2$と$g^{p-3}$、$g^3$ と $g^{p-4}$ のように 2 つ組を作って積を求めると、すべて $g^{p-1}$ となる。これはフェルマーの小定理より$ \mathrm{mod}\; p $では$ 1 $となる。 したがってペアにすることができない中央の数が残り、$(n-1)! \equiv g^{(p-1)/2} $ となる。

$g^{p-1}\equiv 1$ であることから $g^{(p-1)/2}$ は $1$ か $-1$ のどちらかである必要がある。ここで $1$ とすると $g$ が原始根であることに矛盾してしまうので $-1$ が正しい。したがって Wilson の定理は示された。

原始根の存在は構築的に証明できる。アルゴリズムは次のような感じ(細かい所は省略)。

  1. まず適当な元 $x$ を持ってくる
  2. $x$ の冪で得られない数 $y$ を持ってくる
    2.1. $x$ と $y$ の位数が互いに素なら $x\gets xy$ とする。($\mathrm{ord}(xy)=\mathrm{ord}(x)\mathrm{ord}(y)$ となる)
    2.2. $x$ と $y$ の位数が互いに素でないなら$\mathrm{lcm}(\mathrm{ord}(x),\mathrm{ord}(y) )$ となる元を作る方法があるのでそれを使って $x$ を更新。
  3. $x$ の位数が $p-1$ になったら終了。そうでなければ 2 に戻る。

mod pq における原始根

$p\ge 3$のときは原始根が存在する。これは $(\mathbb{Z}/p^q\mathbb{Z})^{\times}$ での $p+1$ の位数が $p^{q-1}$ であることと、mod p での原始根の存在を使えば証明できる。

補題として $(p+1)^{p^{q-1}}\equiv 1+p^q \;(\mathrm{mod}\;p^{q+1})$ を使う。これは数学的帰納法で容易に証明できるので省略する。$\mathrm{mod}\;p^q$ で $p+1$ の位数が $p^{q-1}$ であることを数学的帰納法によって示す。

$(p+1)^d \equiv 1 \;(\mathrm{mod}\; p^{q+1})$ を満たす $d$ は$(p+1)^d \equiv 1 \;(\mathrm{mod}\; p^q)$ も当然満たす。つまり $d$ は $p^{q-1}$ の倍数である。そこで $d=sp^{q-1}$ とおく。 $$ (p+1)^{sp^{q-1}}\equiv(p^q+1)^{s}=1+sp^q+\cdots\equiv1+sp^q\equiv 1 \;(\mathrm{mod}\; p^{q+1})$$ となる。これを満たす最小の $s$ は $p$ である。したがって数学的帰納法により示された。

$g$ の mod pq での位数を $d$ としたとき、$d$ は$ p-1$ の倍数であるから、$d=k(p-1)$ となる。$g^k$ は位数 $p-1$ になる。$g^k(p+1)$ を累乗していくと、$g^k$ と $p+1$ の位数が互いに素なので $(p-1)p^{q-1}$ 個すべての値を生成する。

$p=2$ のときは少し振る舞いが変わっていて、$q\le 2 $ なら原始根が存在するが、$q>2$ では原始根が存在しない。$q\le 2$ のときは総当りですぐ見つかる。 $q>2$ のときは $5$ の位数が $2^{q-2}$ になることがわかり、位数 $2^{q-1}$ の元が存在しないことも示せる。また、任意の元が $5^i (-1)^j$ の形で一意に表現できることも分かる。

素数冪 mod における階乗の周期性

$p \ge 3$ のとき、$1,g,g^2,\ldots,g^{n-1}$ の積を Wilson の定理のときと同様にペア組していくと $g^{(p-1)p^{q-2}/2}$が残る。よって $(p^q!)_p\equiv -1$ である。

$p=2,q\ge 3$ のとき、$g^0g^1g^2\cdots g^{p^{q-2}-1}$ と $(-g^0)(-g^1)(-g^2)\cdots (-g^{p^{q-2}-1})$の積を取ればいい。両方 -1 になるので $(p^q!)_p\equiv 1$ になる。このことを使うともっと省メモリで計算可能。

これらをまとめると次のようになる。

$$ \begin{align} (p^q!)_p \equiv \begin{cases} -1 & (p\ge 3 \lor (p=2 \land q \le 2) ) \\ 1 & (p=2 \land q\ge 3) \end{cases} (\mathrm{mod}\;p^q) \end{align} $$

原始根の存在定理を何故書いたのかというと、$(\mathbb{Z}/p^q\mathbb{Z})^{\times}$が巡回群になることを言いたかったから。-1 になることは、位数が偶数の巡回群になることから簡単にわかる(位数 2 の元がかならず残る)。巡回群であれば $x^2=1$ となる元が単位元ともうひとつしか存在しないことを使うと、この $x$ 以外は逆元とペアにできるから $x$ しか残らない、という見方もできる。

Wilson の定理の群論的一般化

結局、群で考えると楽なので、書きます。可換性は必要です。

まず、有限可換群$G$ の元の最大位数を $ m $ としたとき、任意の元の位数は $ m $ の約数であることを示す。

位数が極大となる 2 つの元 $x$, $y$ を持ってくる。ただし位数は異なるものとする。 $x$ の位数を $d$、$y$ の位数を $e$ とする。たとえば$d=2^3\cdot 3^4 \cdot 5^2 \cdot 7$、$e=2^2 \cdot 3^3 \cdot 5^2 \cdot 7^2$ としよう。各素因数の指数を比較した結果を使って $d=st,\;e=uv$ と分解する。この例では、$s=5^2 \cdot 7,\;t=2^3 \cdot 3^4,\;u=2^2 \cdot 3^3,\; v=5^2\cdot 7^2$ となる。指数を比較して小さかったら $s$ に、大きかったら $t$ に入れている。このとき $tv$ は $d$,$e$ の最小公倍数になる。
$x^s$ の位数を $f$ としよう。このとき $sf$ は $d=st$ の倍数である。つまり $f$ は $t$ の倍数なので、その中で最小のものは $f=t$。同様にして $y^u$ の位数を $g$ とすると、$g=v$ となる。ここで $f,g$ は互いに素であるから、$a^sb^u$ の位数は $fg$ となる。両者は極大であるから $\mathrm{lcm}(f,g)>d,e$ である。このように構成できることを考えると成り立つことが分かる。

位数 $n$ の 群$G$ における位数最大の元を $g$ とし、その位数を $ m $ とする。このとき $g$ が生成する巡回群 $C$ の積を考える。$ m $ が奇数のときは 1 になり、$ m $ が偶数のときは $g^{m/2}$ が残る(ここでは hと書くことにする)。

群$G$ は $G=a_1C+a_2C+a_3C+\cdots+a_{n/m}C$ と分解できる。$a_i C$ のすべての積を考えてみよう。これは $a_i^{m} \mathrm{prod}(C)$ になる。$G$ の最大位数が $ m $ であるから、$a_i^{m}=1$ である。よって、$\mathrm{prod}(a_iC)=\mathrm{prod}(C)$である。

以上より $\mathrm{prod}(G)=\mathrm{prod}(C)^{n/m}=h^{n(m+1)/m}$となる。きれいな数式に書き直したけど、つまり、「最大サイクルのパリティ」と「サイクルの個数のパリティ」で決まる。

周期性を用いたテクニック

このことを使うと $n$ が巨大であっても $n!=Xp^e$ の分解が高速にできる(ただし mod は小さめである必要がある)。

たとえば 13!=X×3e と分解するのであれば、X は次のようにして求められる。

f:id:pekempey:20161025183749p:plain

つまり $X=(13!)_3(4!)_3(1!)_3$ である。一般に$n!$ から $p$ 成分を除いた値は、

$$ F(n)= \left(\left\lfloor \frac{n}{p^0} \right\rfloor!\right)_p \left(\left\lfloor \frac{n}{p^1} \right\rfloor!\right)_p \left(\left\lfloor \frac{n}{p^2} \right\rfloor!\right)_p \cdots $$

で計算できる。$n!$ を素因数分解したとき $p$ がいくつあるかも簡単に求められるので、$n!=X p^e$ という分解の形を得るのは容易である。

これができると mod pq における二項係数の値が計算できる。$e(x)$ と書いたら $x$ が $p$ で何回割ることができるかを表すものとする。このとき二項係数の値は

$$ \begin{align} \binom{n}{r} &=\frac{n!}{r!(n-r)!} \\ &=\frac{F(n)}{F(r)F(n-r)} p^{e(n)-e(r)-e(n-r)} \end{align} $$

となる。ここで $(n!)_p$ は $p$ の倍数でないから $p^q$ での逆元を持つことが重要。mod が小さいという仮定があれば、すべての $(n!)_p$ を前計算しておくことにより $O(\log n)$ で計算ができる。

変更履歴

2016/10/16 12:29:一般化の Wilson の定理をきちんと書いたついでに文章構成も変更。