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

pekempeyのブログ

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

ラグランジュの定理（群論）

群論 教育的 ★★★★

この記事では群論の重要定理であるラグランジュの定理の簡単な説明と、 群論を用いたCodeforces 334 (Div. 1) B. Moodular Arithmeticの解法について説明する。

この記事は

  • 群の定義
  • 部分群の定義
  • 群の位数の定義
  • 既約剰余類群

を知っている人を対象として書いた。

さて、ラグランジュの定理とは次の定理のことである。

有限群\(G\)の部分群\(H\)がある。このとき\(|H|\)は\(|G|\)の約数である。

この定理の証明方法と、応用方法を順に説明する。

ラグランジュの定理

ラグランジュの定理を導くのに必要な2つの定理を紹介する。

1つ目の定理は次のようなもの。

定理1：有限群\(G\)の部分集合\(A=\{g_1,g_2,\ldots,g_n\}\)の各元に\(g\in G\)を掛けた集合を \(gA=\{gg_1, gg_2,\ldots,gg_n\}\)と書く。このとき \[|gA|=|A|\] が成り立つ。
定理1は\(m\)と互いに素な整数\(a_1,a_2,\ldots,a_n\)がどれも異なるなら、 それぞれに\(a\)を掛けたもの、つまり\(aa_1,aa_2,\ldots,aa_n\)も\(\bmod m\)ですべて異なる、という初等整数論の定理に対応している。 ここで、\(gA=A\)とは言っていないことに注意したい。

2つ目の定理は次のようなもの。

定理2：有限群\(G\)の部分群\(H\)がある。このとき\(G\)は次のように表せる。 \[ G=g_1H \cup g_2H \cup \cdots \cup g_dH \] ここで、\(g_iH\)と\(g_jH\)はどれも互いに素である。

定理2は部分群を使って\(G\)をいくつかの集合の和に分解できるということを主張している。 ちなみに\(g_iH\)を左剰余類と呼ぶ。 この言葉を使えば\(G\)は左剰余類の和に分解できるとも表現できる。

定理1と定理2を組み合わせるとラグランジュの定理が導ける。

ラグランジュの定理：有限群\(G\)の部分群\(H\)がある。このとき\(G\)は次のように表せる。 \[ |G|=d|H| \]
証明 \[ \begin{align} |G| &=|g_1H \cup g_2H \cup \cdots \cup g_dH| \\ &=|g_1H| + |g_2H| + \cdots + |g_dH| \\ &=|H|+|H|+\cdots + |H| \\ &=d|H| \end{align} \]

これを言い換えたものが冒頭で紹介したラグランジュの定理だ。

ラグランジュの定理'：有限群\(G\)の部分群\(H\)がある。このとき\(|H|\)は\(|G|\)の約数である。

巡回群

これだけでは少し不便なので、もう一つ定理を紹介しよう。

有限群\(G\)の元\(g\)に対して、\(\langle g \rangle = \{1,g,g^2,g^3,\ldots\}\)は\(G\)の部分群になる。

ちなみに\(\langle g \rangle\)は \(g\)が生成する巡回群と呼ぶ。 この定理とラグランジュの定理を組み合わせれば、巡回群の位数は群の位数の約数になることがわかるだろう。

問題の解法

Codeforces 334 Div.1 Bでは\(1,k,\ldots,k^{s-1}\)で集合の要素を類別した。これは既約剰余類群\((\mathbb{Z}/p\mathbb{Z})^{\ast}\)を巡回群\(\langle k \rangle\)を用いて \[ (\mathbb{Z}/p\mathbb{Z})^{\ast}=a_1\langle k \rangle \cup a_2\langle k \rangle \cup \cdots \cup a_d\langle k \rangle \] と分解することに対応する。さて準備段階でしていた議論を思い出すと、それぞれの集合はすべて同じサイズだから、 \[ |(\mathbb{Z}/p\mathbb{Z})^{\ast}|=d|\langle k \rangle| \] が成り立つ。\(|(\mathbb{Z}/p\mathbb{Z})^{\ast}|=p-1\)、\(|\langle k \rangle|=\mathrm{ord}(k)\)なので、 \[ d=\frac{p-1}{\mathrm{ord}(k)} \] になり、グループ数\(d\)を無事求めることができた。後は\(\mathrm{ord}(k)\)を求めるだけ。

ラグランジュの定理を使うと\(\mathrm{ord}(k)\)は\(p-1\)の約数であることがわかる。 そのため、\(p-1\)の約数\(d_1,d_2,\ldots,d_s\)の中で \(k^{d_i}=1\)を満たす最小の\(d_i\)を求めれば、それが位数。 よって位数は\(O(\sqrt{n})\)で求まる。

その他の応用

ラグランジュの定理を使うと次のような定理が示せる。

\(G\)を有限群とする。任意の\(g\in G\)に対して次の等式が成り立つ。 \[g^{|G|}=1\]

最強感ハンパない。元の位数が\(|G|\)の約数であることを考えれば実は自明。

さて、既約剰余類群\((\mathbb{Z}/m\mathbb{Z})^{\ast}\)に対してこの定理を適用すると、なんとオイラーの定理が現れる。

オイラーの定理： \[a^{|(\mathbb{Z}/m\mathbb{Z})^{\ast}|}=a^{\phi(m)}=1\]

特に\(m\)が素数のときフェルマーの小定理になる。

フェルマーの小定理： \[a^{ m -1}=1 \]

すごい。

残念ながらカーマイケルの定理は示せない。この定理は群の位数に着目した定理であるのに対し、カーマイケルの定理は元の位数に着目した定理だからである。

まとめ

群を使うと構造がすぐに理解できて便利。