剰余演算

Last-modified: Sat, 22 Jun 2019 00:11:40 JST (468d)
Top > 剰余演算

スマホ版が見づらい場合はPC版をお試しください

別名:モジュロ演算 (modulo operation)、mod計算
\( m \)\( n \)で割った余りを\( r \)とするとき、
\( m \equiv r \mod n \)
と表記する。

剰余演算の法則

\( a \equiv a \mod n \)
\( (a \mod n) \equiv a \mod n \\ n^k \mod n \equiv 0 \)
分配法則
\( (a+b) \mod n \equiv (a \mod n)+(b \mod n) \mod n \)
\( (ab) \mod n \equiv (a \mod n)(b \mod n) \mod n \)
逆数(逆元)
\( (xy) \equiv 1 \mod n \)を満たす\( y \)\( x \)の逆数と呼び、\( x^{-1} \)と表記する。
逆数を求めるアルゴリズム:拡張ユークリッド互除法