アルゴリズム論特論（塩田）第5回 (1) 合同式
合同式
Def.1 ( 合同式 )
- 自然数 $n$ をひとつ固定し、これを「法 ( modulus )」と呼ぶ。
- $a-b$ が $n$ で割り切れるとき、
$a \equiv b \pmod n$
と表し、「 $a$ 合同 $b$ モッド $n$ 」と読む。
また、「 $a$ は $n$ を法として $b$ と合同である」と言う。
Rem.2 次は同じことの言い換えである：
- (1) $a \equiv b \pmod n$
- (2) $a-b$ が $n$ で割り切れる
- (3) $a-b$ は $n$ の
である ... を埋めよ
- (4) $n$ は $a-b$ の
である ... を埋めよ
- (5) ( $a$ を $n$ で割った余り ) $=$ ( $b$ を $n$ で割った余り )
ただし (5) は理論上の話で、プログラミング言語の仕様によってはバグることがあるので注意してください。
Rem.3 $a\,\%\,n$ の符号は
- C 言語では $a$ の符号に同じ
- Python では $n$ の符号に同じ
例えば
$\newcommand\T{\Rule{0pt}{1em}{.3em}}
\begin{array}{|c|c|c|c|c|}
\hline & 2\ \%\ 5 & (-3)\ \%\ 5 & 2\ \%\ (-5)\ & (-3)\ \% (-5) \\\hline
\mbox{C} & 2 & -3 & 2 & -3 \\\hline
\mbox{Python} & 2 & 2 & -3 & -3 \\\hline
\end{array}$
すなわち、$a=2$, $b=-3$, $n=5$ のとき、理論上は $a\equiv b \pmod n$ ですが、
(a % n) == (b % n)
は Python では正しく True と判定されるのに対し、C 言語では False と判定されてバグの原因となります。