剰余環について

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

用語

同値類

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

$x,y \in C \to x \sim y$
$[ 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,B$ を $m$ を法とする剰余類とし、 $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$ で割った余りを計算すると、 $N$ が $100000$ と大きい場合に $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