整数剰余類環 - イシカワの外部記憶

整数剰余類環

$ nを法とする剰余類の全体は、加法と乗法に関して可換環を成す。

$ \Z/n\Z,\Z_nなどと表される。また、その集合も表す。

$ nが素数であるかそうでないか

$ nが素数であるならば、$ pを法とする剰余体とも呼ばれる。乗法に対して逆元が存在する。

$ nが素数でないならば、体にならない。$ nの任意の約数が零因子となる。例えば、$ 2\times 4 \equiv 0 \pmod 8。

既約剰余類と規約剰余類群

$ nとの最大公約数が$ 1である互いに素なある整数$ aに対して、

剰余類$ a+n\Zを既約剰余類という。

既約剰余類の全体を、既約剰余類群という。$ (\Z/n\Z)^{\times}と表す。

例

$ \mathbb{Z}/3\mathbb{Z} = \{0, 1, 2\}

演算

剰余類$ [a],[b] を用いて

$ [a]+[a]:=[a+b]

$ [a]\times[b]:=[a\times b]

関連する競技プログラミングの問題

フィボナッチ数列。周期が3になる。

$ F_2 = F_1 \oplus F_0

$ F_0 = F_2 \oplus F_1

$ F_1 = F_0 \oplus F_2