剰余類の演算

剰余環について

AtCoderの問題で剰余環についてふと思ったので、復習しておきます。

用語

同値類

集合 U で同値関係 \sim が定まっているとき、x,y,zU を変域とする変数とする。
U の空でない部分集合 C

  1. x,y \in C \to x \sim y
  2.  [ x \in C \land x \sim z ] \to z \in C

の2つの条件を満たす時、 C を同値関係 \sim に関する同値類という。

m を法とする剰余類

\mathbb{Z} 上の m を法とする合同関係 \equiv_m に関する整数 k の同値類 [k]_m

m を法とする剰余系

\mathbb{Z}m を法とする合同関係 \equiv_m に関する代表系

m を法とする剰余集合

商集合 \mathbb{Z} / \equiv_m = \mathbb{Z}_m

例1) \mathbb{Z} における m を法とする剰余集合 \mathbb{Z}_m

\mathbb{Z}_m = \{ [0]_m,[1]_m, \cdots ,[m-1]_m \}

剰余類の演算

剰余集合 \mathbb{Z}_m には和 + と積 \cdot の演算が定義される。

A,Bm を法とする剰余類とし、 A,B の代表元を a,b とする。  A=[a]_m,B=[b]_m と表すと、
 A+B=[a]_m+[b]_m = [a+b]_m
A \cdot B=[a]_m \cdot [b]_m = [a \cdot b]_m

が矛盾なく定義される。

例2)7 を法とする剰余環 \mathbb{Z}_7 における演算
[1]_7+[6]_7=[7]_7=[0]_7
[3]_7・[5]_7=[15]_7=[1]_7

例3) 5 を法とする剰余環について [a]_5 = [1]_5 とするとき、  [a+2a^{2}+3a^{3}+ \cdots + 100a^{100} ]_5 の値
 \forall n \in \mathbb{N}, [a^{n}]_5 \equiv [1]_5 なので  [na^{n}]_5 \equiv [n]_5
よって、  [a+2a^{2}+3a^{3}+ \cdots + 100a^{100} ]_5 \equiv [1+2+ \cdots +99+100 ]_5
\equiv [(1+2+3+4+0)+ \cdots +(1+2+3+4+0)]_5 \equiv [(1+2+3+4+0)*20]_5 \equiv [0]_5

階乗の余りの計算

以下のAtCoderの問題を解く際に、ある整数 N の階乗 N!m で割った余りを計算する必要がありました。
https://beta.atcoder.jp/contests/abc065/tasks/arc076_a

そのまま N!m で割った余りを計算すると、 N100000 と大きい場合に 100000! の計算結果が膨大になり時間がかかります。JavaであればBigIntegerを使用して結果を求めることは可能です。 ここで剰余類の演算を応用すると
[N!]_m = [1 \cdot 2 \cdots (N-1) \cdot N]_m = [1 \cdot 2 \cdots (i-1) \cdot i]_m \cdots [N-1]_m \cdot [N]_m
 = [(i-1)! \cdot i ]_m \cdots [N-1]_m \cdot [N]_m
で求められます。
つまり (i-1)!i を掛けたときに除数 m を超えたとしても、  [(i-1)! \cdot i ]_m によって m 未満となり、計算途中の結果が膨大になることが防げ、時間内に結果が得られます。

参考

  • 嘉田勝著,「論理と集合から始める数学の基礎」,日本評論社,2008
  • 加藤文元、中井保行著,「天に向かって続く数」,日本評論社,2016