合同式の性質ごうどうしきのせいしつ

合同ごうどう式しきの性質せいしつは、$a\equiv b$, $c\equiv d\left(modn\right)$ のとき次つぎが成なり立たつ、というものです。これにより大おおきな数かずの剰余じょうよや何なん乗じょうかした数かずの余あまりが簡単かんたんに計算けいさんできます。

演算えんざん	性質せいしつ
加法かほう	$a+c\equiv b+d$
減法げんぽう	$a-c\equiv b-d$
乗法じょうほう	$ac\equiv bd$
累乗るいじょう	$a^k\equiv b^k$

たとえば $7^{100}$ を $5$ で割わった余あまりは、$7\equiv 2$ より $7^{100}\equiv 2^{100}\left(mod5\right)$ とでき、$2^4\equiv 1$ を使つかえば計算けいさんできます。

注意ちゅうい 加減かげん乗じょう・累乗るいじょうはそのままできるが、割わり算ざん（約分やくぶん）は自由じゆうにできない。両辺りょうへんを割われるのは割われる数かずが法$n$ と互いに素たがいにそのときだけ。