# 競プロerのための群論 (整数論と群論) ###### tags: `記事` この記事は 「[競プロ Advent Calendar 2021](https://adventar.org/calendars/6713)」の 13 日目の記事です。 この記事は「[競プロerのための群論 (swapと順列と対称群)](https://koboshi-kyopro.hatenablog.com/entry/2020/08/21/211615)」の姉妹記事です。上述の記事が順列をテーマとしていたのに対し、ここでは整数論をテーマとします。しかし背後には群論が共通します。 フェルマーの小定理や原始根といった整数論の話題を、群論を通して見ることを目標とします。 ## ModInt 除算 競技プログラミングでは $10^9+7$ で割った余りや $998244353$ で割った余りを求める問題がよく出題されます。この 2 つの数はともに素数です。このようにある素数で割った余りを求める問題を解くとき、ModInt ライブラリが役立ちます。AtCoder Library にも実装されています。これがどのような仕組みで動いているかは把握しなくても使うことはできますが、その仕組みをここでは見ていきます。 例えば次の問題を考えてみましょう。 :::info **問題** $1+2+\cdots+n$ を素数 $p$ で割った余りを求めてください。($1\le n\le 10^{18}, 3\le p\le 10^9+7$) ::: 勿論愚直に足し合わせると間に合いません。そこで、等差数列の和を求める公式を使うと $$ 1+2+\cdots+n=\frac{n(n+1)}{2} $$ となります。しかし $n=10^{18}$ のとき、これを計算すると 64 bit 整数で表すことができません。そこで次のような方法が使えないか考えます。 :::danger 「計算してから余りをとる」のではなく「余りをとってから計算する」 ::: $n\times (n+1)$ を $p$ で割った余りは、$n$ を $p$ で割った余りと $n+1$ を $p$ で割った余りの積を $p$ で割った余りに等しいです。このようにすることで 64 bit 整数に収めて計算することができます。この方法で、足し算・引き算・かけ算はうまくいきます。 しかし割り算はうまくいきません。$n=10,p=7$ で試してみましょう。$n(n+1)=110$ を $7$ で割った余りは $5$ です。そのままの計算では右辺は $\frac{5}{2}$ になってしまいます。余りを考えつつ割り算を扱うにはどのようにすればよいでしょうか。 ## 割り算とは 商 $a\div b$ が $c$ であるというのは、$a=c\times b$ と同じことでした。よって、$6\div 3=x$ を求めるには、$6=x\times 3$ をみたす $x$ を求めればよいということになります。 これは「整数の世界」での話ですが、同じことを「余りの世界」で考えてみます。すなわち、与えられた $a,b$ に対し、$a\equiv c\times b \pmod{p}$ をみたす $c$ のことを、余りの世界における $a$ を $b$ で割った商だとするのです ($A\equiv B\pmod{p}$ とは、$A$ を $p$ で割った余りと $B$ を $p$ で割った余りが等しいことを意味する記号です)。先ほどの例 ($n=10,p=7$) では、$\frac52$ は $5\equiv 2c\pmod{7}$ をみたす $c$ です。計算すると $c=6$ が条件を満たすことがわかります。$1+2+\cdots+10=55$ を $7$ で割った余りは $6$ でしたから、無事に問題が解けたことになります。 ここで考えなければならないのは、商が必ず求められるかということです。勿論整数の世界でも割り切れない場合は商を求めることができません。また、$p$ が素数という仮定を外し $p=10$ とすると、$\frac{1}{2}$ は $1\equiv 2c\pmod{10}$ をみたす $c$ となるので存在しません。 しかし、$p$ が素数ならばほとんどの場合で商を求めることができます!次の命題が成り立ちます。 :::success **命題** $p$ が素数で $b$ が $p$ の倍数でないとき、$\frac{a}{b}$ が存在する。すなわち $a\equiv bx\pmod{p}$ をみたす $x$ が存在する。 ::: これを証明するための方法は主に 2 つあり、1 つはフェルマーの小定理を用いるもの、もう 1 つは拡張ユークリッドの互除法を用いるものです。AtCoder Library の ModInt では後者が採用されているようです。 ## ユークリッドの互除法 ユークリッドの互除法は、整数 $a,b$ の最大公約数 $d$ を求めるアルゴリズムです。また、このアルゴリズムを拡張して $ax+by=d$ をみたす整数 $x,y$ を求めることもでき、拡張ユークリッドの互除法と呼ばれています。ここではアルゴリズムの解説はしません。(参考文献をご覧ください) この拡張ユークリッドの互除法を用いると、上の命題は簡単に証明できます。$b$ は $p$ の倍数でないので、$b,p$ の最大公約数は 1 です。拡張ユークリッドの互除法より、$bx+py=1$ をみたす整数 $x,y$ が存在します。$\bmod{p}$ で考えることで、$bx\equiv 1\pmod{p}$ となります。両辺を $a$ 倍することで $b(ax)\equiv a\pmod{p}$ となり、この $ax$ が $\frac{a}{b}$ となることがわかりました。これで割る数 $b$ が $p$ の倍数でないときはいつでも余りの世界で割り算ができることがわかりました。 ## フェルマーの小定理 フェルマーの小定理は整数論における重要な定理で、次のような定理です。 :::success **フェルマーの小定理** $p$ を素数、$x$ を $p$ の倍数でない整数とする。このとき $x^{p-1}\equiv 1\pmod{p}$ が成り立つ。 ::: このフェルマーの小定理を使っても上の命題が示せます。実際 $b$ は $p$ の倍数でないので、$b^{p-1}\equiv 1\pmod{p}$ となります。両辺に $a$ をかけることで $ab^{p-1}\equiv a\pmod{p}$ となり、見た目を変えると $b\cdot ab^{p-2}\equiv a\pmod{p}$ となります。すなわち $ab^{p-2}\bmod{p}$ が $\frac{a}{b}$ となることがわかりました。 フェルマーの小定理は群論を用いて証明することができます。以下で解説します。 ## 群論登場 お待たせしました。群論に入っていきます。 まずは「余りの世界」と呼んでいたものを厳密に定義します。整数を $N$ で割った余りのなす集合を $\mathbb{Z}/N\mathbb{Z}$ と書きます。このとき和や積も余りをとったものとします。 任意の $a,b,c\in\mathbb{Z}/N\mathbb{Z}$ に対し次が成り立ちます。 - $a+b\in\mathbb{Z}/N\mathbb{Z}$ - $(a+b)+c=a+(b+c)$ - $a+0=0+a=a$ - $a+(-a)=(-a)+a=0$ また、$\mathbb{Z}/N\mathbb{Z}$ の元 $a$ のうち $\frac{1}{a}$ が存在するもの全体の集合を $(\mathbb{Z}/N\mathbb{Z})^{\times}$ と書きます。$N$ が素数 $p$ の場合は、$(\mathbb{Z}/p\mathbb{Z})^{\times}$ は $p$ で割った余りが 0 以外のものすべてからなることを上で示しました。よって $(\mathbb{Z}/p\mathbb{Z})^{\times}$ は $\mathbb{Z}/p\mathbb{Z}$ から 0 を取り除いたものとなり、位数 (要素の数) は $p-1$ です。$N$ が素数でないとき $(\mathbb{Z}/N\mathbb{Z})^{\times}$ の位数は $N-1$ より小さくなります。例えば $(\mathbb{Z}/10\mathbb{Z})^{\times}=\{1,3,7,9\}$ です。 任意の $a,b,c\in (\mathbb{Z}/N\mathbb{Z})^{\times}$ に対し次が成り立ちます。 - $a\cdot b\in (\mathbb{Z}/N\mathbb{Z})^{\times}$ - $(a\cdot b)\cdot c=a\cdot (b\cdot c)$ - $a\cdot 1=1\cdot a=a$ - $a\cdot \frac{1}{a}=\frac{1}{a}\cdot a=1$ 上の 2 つは似た構造を持っていることがわかります。また、姉妹記事を参照していただくと、対称群とも同じ構造をもっていることがわかると思います。このような構造をもつ集合をまとめて扱いたいです。そこで、このような構造をもつ集合を**群**と呼びます。正確に書くと次のようになります。 --- 群とは、集合 $G$ と演算 $\cdot: G\times G\to G$ の組であって、次の 3 つの条件を満たすものである。 - $a,b,c\in G$ に対し $(a\cdot b)\cdot c=a\cdot (b\cdot c)$ - ある $e\in G$ が存在して、任意の $g\in G$ に対し $g\cdot e=e\cdot g=g$ - 任意の $g\in G$ に対しある $g^{-1}\in G$ が存在して、$g\cdot g^{-1}=g^{-1}\cdot g=e$ $e$ のことを**単位元**、$g^{-1}$ のことを $g$ の**逆元**という。 --- 群論とは、群という共通の性質をもつ対象をまとめて扱う分野です。$\mathbb{Z}/N\mathbb{Z}$ は足し算について群をなし、$(\mathbb{Z}/N\mathbb{Z})^{\times}$ はかけ算について群をなします。このような一見異なるように見える 2 つも群論では統一的に扱うことができます。 ## ラグランジュの定理 $G$ を群とします。$G$ の部分集合 $H$ が $G$ の**部分群**であるとは、次を満たすことを言います。 - $h_1,h_2\in H$ に対し、$h_1\cdot h_2\in H$ - $h\in H$ に対し、$h^{-1}\in H$ 名前の示す通り部分群は群です。例えば、$\{0,2,4,6,8\}$ は $\mathbb{Z}/10\mathbb{Z}=\{0,1,2,3,4,5,6,7,8,9\}$ の部分群となります。部分群について、次の定理が成り立ちます。 :::success **ラグランジュの定理** $G$ が有限群、$H$ が部分群ならば、$H$ の位数は $G$ の位数の約数である。 ::: 興味がある方は証明を開いてみてください。 :::spoiler ラグランジュの定理の証明 $G$ 上の同値関係 $\sim$ を $g_1\sim g_2 \iff g_1^{-1}g_2\in H$ により定める。このとき $g\in G$ の同値類は $gH$ と表される。ある $g_1,\ldots,g_m\in G$ が存在して、$G=g_1H\cup g_2H\cup\cdots\cup g_mH$ と表され、かつ $g_iH\cap g_jH=\emptyset \ (i\ne j)$ となる。ここで $gH$ の位数はすべて $H$ の位数に等しいので、$G$ の 位数は $|G|=m|H|$ となる。よって $|H|$ は $|G|$ の約数である。 ::: ラグランジュの定理の応用例を 1 つ述べます。 :::success **定理** 素数位数の群は巡回群である。 ::: :::spoiler 証明 $p$ を素数とし、位数 $p$ の群 $G$ を考える。$p\ge 2$ なので、単位元でない元 $x\in G$ がとれる。このとき $H=\{x^0,x^1,x^2,\ldots\}$ という部分集合を考えると、これは $G$ の部分群であり、巡回群である。ラグランジュの定理より $H$ の位数は $G$ の位数の約数であるが、$p$ の約数は $1,p$ のみである。$x$ は単位元でないので $H$ の位数は 2 以上である。よって $H$ の位数は $p$ なので、$G=H$ である。 ::: ## フェルマーの小定理の証明 フェルマーの小定理もラグランジュの定理から導くことができます。 群 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ を考えます。$x$ を $p$ の倍数でないものとします。このとき $\{x^0, x^1, x^2, \ldots\}$ (を $p$ で割った余り) という集合を考えると、これは $(\mathbb{Z}/p\mathbb{Z})^{\times}$ の部分群になります。この部分群の位数を $e$ とすると、$x^e\equiv 1\pmod{p}$ をみたします。ここでラグランジュの定理を適用すると、$e$ は $(\mathbb{Z}/p\mathbb{Z})^{\times}$ の位数 $p-1$ の約数です。よって $x^{p-1}\equiv 1\pmod{p}$ となります。これでフェルマーの小定理が証明できました。 ## オイラーの定理 フェルマーの小定理では群 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ を考えましたが、一般に群 $(\mathbb{Z}/N\mathbb{Z})^{\times}$ を考えてみましょう。$\frac{1}{a}$ が存在するための条件を考えます。これは $ax\equiv 1\pmod{N}$ をみたす $x$ が存在するための条件と同値です。明らかに $a$ と $N$ が互いに素でないときは $x$ は存在しません。逆に、$a$ と $N$ が互いに素のときは $\frac{1}{a}$ が存在します。これは拡張ユークリッドの互除法より、$ax+Ny=\gcd(a,N)=1$ をみたす整数 $x,y$ が存在することがいえるからです。 よって、$(\mathbb{Z}/N\mathbb{Z})^{\times}$ の位数は $\phi(N)$ です。ここで$\phi(N)$ はオイラーの $\phi$ 関数で、1 以上 $N$ 以下の整数のうち $N$ と互いに素なものの個数を表します。 フェルマーの小定理の証明と同様にして、次のオイラーの定理を得ることができます。 :::success **オイラーの定理** $x$ が $N$ と互いに素であるとき、$x^{\phi(N)}\equiv 1\pmod{N}$ が成り立つ。 ::: $N$ が素数 $p$ のときフェルマーの小定理と一致します。 ## 原始根 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ という群は位数 $p-1$ ですが、より詳しい構造を見てみましょう。実は次のようになります。 :::success **命題** $(\mathbb{Z}/p\mathbb{Z})^{\times}$ は $\mathbb{Z}/(p-1)\mathbb{Z}$ と群として同型である。 ::: 同型の定義は省きますが、ざっくり説明すると「集合としては異なるかもしれないが、群としての構造は同じ」というものです。 この命題により、$\mathbb{Z}/(p-1)\mathbb{Z}$ の 1 に対応する $(\mathbb{Z}/p\mathbb{Z})^{\times}$ の元を $r$ とおくと、$(\mathbb{Z}/p\mathbb{Z})^{\times}$ の任意の元はある整数 $k$ を用いて $r^k$ の形で表すことができます。このような元 $r$ を**原始根**といいます。 上の定理の証明は原始根の存在を示すことで証明できます。(参考文献を参照してください) 原始根を使った問題を 1 つ考えてみましょう。 :::info **問題** $p$ を素数、$n,a$ を正の整数とします。$0\le x\le p-1$ かつ $x^n\equiv a\pmod{p}$ をみたす $x$ はいくつあるか求めてください。 ::: $a=0$ のときは $x=0$ のみです。以下 $a\ne 0$ とします。原始根を $g$ とすると、$x,a$ はともに 0 でないので $x=g^s, a=g^t$ と表せます。$x^n\equiv a\pmod{p}$ は $ns\equiv t\pmod{p-1}$ と同値になります。ここで一次合同式に関する次の結果を用います。 :::success **命題** $a,b$ を整数、$d=\gcd(a,N)$ とする。このとき $x\in\mathbb{Z}/N\mathbb{Z}$ に関する方程式 $ax\equiv b\pmod{N}$ の解の個数は - $b\equiv 0\pmod{d}$ のとき $d$ 個 - $b\not\equiv 0\pmod{d}$ のとき $0$ 個 ::: これより、$d=\gcd(n,p-1)$ とすると、解の個数は - $t\equiv 0\pmod{d}$ ならば $d$ 個 - $t\not\equiv 0\pmod{d}$ ならば $0$ 個 となることがわかりました。さらに $$ t\equiv 0\pmod{d} \iff \frac{p-1}{d}t\equiv 0\pmod{p-1} \iff 1\equiv g^{\frac{p-1}{d}t}\equiv a^{\frac{p-1}{d}}\pmod{p} $$ となります。以上をまとめると - $a=0$ のとき、解は $1$ 個 - $a^{\frac{p-1}{d}}\equiv 1 \pmod{p}$ のとき、解は $d$ 個 - それ以外のとき、解は $0$ 個 となります。 ## 中国剰余定理 中国剰余定理 (CRT) について述べます。 :::success **中国剰余定理** $m,n$ を互いに素な正の整数とする。このとき群 $\mathbb{Z}/mn\mathbb{Z}$ は群の直積 $\mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$ と同型である。 ::: 興味があれば証明を覗いてみてください。 :::spoiler 証明 群準同型 $\phi\colon \mathbb{Z}/mn\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$ を $z\mapsto (z\bmod{m}, z\bmod{n})$ により定める。これが全射であることを示す。$(x,y)\in \mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$ を任意にとる。$m,n$ は互いに素なので拡張ユークリッドの互除法により $ma+nb=1$ をみたす $a,b$ が存在する。$z=may+nbx$ とおくと、$z\equiv nbx=(1-ma)x\equiv x\pmod{m}$ となり、同様に $z\equiv y\pmod{n}$ となる。これより $\phi(z)=(x,y)$ となるので $\phi$ は全射。$\mathbb{Z}/mn\mathbb{Z}$ と $\mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$ は位数が等しいので、$\phi$ は同型である。 ::: この定理により、$m$ で割った余りが $x$、$n$ で割った余りが $y$ となるような数を $\bmod{mn}$ で求められることが保証されます。実際にこれを求めるアルゴリズムもあり、競技プログラミング界隈ではそちらも合わせて CRT と呼ばれることが多いです。 中国剰余定理は環論の定理に一般化できますが、ここでは深入りしないこととします。「競プロerのための環論」を書く日があれば書くかも……? ## ウィルソンの定理 最後に、ウィルソンの定理を紹介します。 :::success $p$ が素数ならば、$(p-1)!\equiv -1\pmod{p}$ が成り立つ。 ::: この記事で扱った知識をもとにしてウィルソンの定理を証明することで記事を締めくくりたいと思います。 $p=2$ のときは明らかなので、以下 $p$ を奇素数とします。 ### フェルマーの小定理を使った証明 フェルマーの小定理より $a=1,\ldots,p-1$ に対し、$a^{p-1}\equiv 1\pmod{p}$ となります。これより、多項式 $x^{p-1}-1$ を $\mathbb{Z}/p\mathbb{Z}$ において因数分解すると $$ x^{p-1}-1\equiv (x-1)(x-2)\cdots (x-(p-1)) \pmod{p} $$ となります。$x=0$ を代入すると、$-1\equiv (-1)(-2)\cdots(-(p-1))=(-1)^{p-1}(p-1)!=(p-1)!\pmod{p}$ となります。 ### 原始根を使った証明 $\mathbb{Z}/p\mathbb{Z}$ の原始根 (すなわち $(\mathbb{Z}/p\mathbb{Z})^{\times}\cong \mathbb{Z}/(p-1)\mathbb{Z}$ の生成元) を $g$ とします。このとき $\{1,2,\ldots,p-1\}=\{g^1,g^2,\ldots,g^{p-1}\}$ となるので、 $$ (p-1)!\equiv g^{1+2+\cdots+(p-1)}=g^{\frac{p(p-1)}{2}} \pmod{p} $$ となります。フェルマーの小定理より $g^{p(p-1)}\equiv 1$ なので、$g^{\frac{p(p-1)}{2}}\equiv \pm 1$ となります。ここで、$g^m\equiv 1$ となる $m$ は $p-1$ の倍数ですが、$\frac{p(p-1)}{2}$ は $p-1$ の倍数でないので $g^{\frac{p(p-1)}{2}}\equiv -1$ です。したがって $(p-1)!\equiv -1\pmod{p}$ が得られました。 ### (おまけ) シローの定理を使った証明 この記事では扱いませんでしたが、群論における非常に強力な定理であるシローの定理を用いてもウィルソンの定理を示すことができます。 $p$ 次対称群 $S_p$ の $p$ シロー部分群は位数 $p$ です。長さ $p$ の巡回置換の個数は $(p-1)!$ です。位数 $p$ の部分群に長さ $p$ の巡回置換が $p-1$ 個あることから、$p$ シロー部分群の個数は $\frac{(p-1)!}{p-1}=(p-2)!$ です。シローの定理より、これを $p$ で割った余りは 1 です。すなわち $(p-2)!\equiv 1\pmod{p}$ となります。これに $p-1$ をかければウィルソンの定理が得られます。 ## 演習問題 - [トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) E - Integer Sequence Fair](https://atcoder.jp/contests/abc228/tasks/abc228_e) - [キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193) E - Oversleeping](https://atcoder.jp/contests/abc193/tasks/abc193_e) - [AtCoder Beginner Contest 212 G - Power Pair](https://atcoder.jp/contests/abc212/tasks/abc212_g) - [yukicoder No.1578 A × B × C](https://yukicoder.me/problems/no/1578) - [yukicoder No.1287 えぬけー](https://yukicoder.me/problems/no/1287) ## 参考文献 - 雪江明彦, 代数学1 群論入門, 日本評論社, 2010 (群論の教科書の中でも代表的なものの 1 つです) - 山崎隆雄, 初等整数論, 共立出版, 2015 (原始根について参考にしました) - [「群」って何なの?「同一視」から始める群論](https://www.ajimatics.com/entry/2019/12/04/154951) (具体例から始めて群論とは何かを説明している記事です。初めての人にもオススメです) - [拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜](https://qiita.com/drken/items/b97ff231e43bce50199a) - [中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ](https://qiita.com/drken/items/ae02240cd1f8edfc86fd) - [原始根のアルゴリズム](https://37zigen.com/primitive-root/)