合同式

2022.6.30

Math

$a - b$ が $n$ の倍数であるとき、 $a, b$ は $n$ を法として合同であるといい、以下の合同式で表す。

a \equiv b\ (\rm{mod}\ n)

これは $a$ を $n$ で割った余りと、 $b$ を $n$ で割った余りが等しいことと同値である。

性質

反射律: $a \equiv a\ (\rm{mod}\ n)$

対称律: $a \equiv b\ (\rm{mod}\ n)$ ならば、 $b \equiv a\ (\rm{mod}\ n)$

推移律: $a \equiv b\ (\rm{mod}\ n)$ かつ $b \equiv c\ (\rm{mod}\ n)$ ならば、 $a \equiv c\ (\rm{mod}\ n)$

$a \equiv b\ (\rm{mod}\ n)$ かつ $c \equiv d\ (\rm{mod}\ n)$ のとき、

$ka \equiv kb\ (\rm{mod}\ n)$ かつ $k$ と $n$ が互いに素のとき、 $a \equiv b\ (\rm{mod}\ n)$

$ka \equiv kb\ (\rm{mod}\ kn)$ かつ $k \ne 0$ のとき、 $a \equiv b\ (\rm{mod}\ n)$