## 概要

$a,b$ を $m$ で割った余りが等しいとき、 **「$a,b$ は $m$ を法として合同」**といい、$a\equiv b{\pmod{m}}$ とかく。これを**合同式**ともいう。

合同式というより $\mathrm{mod}$ と呼んだ方が、数学できる感は出せる気がする。

$$a\equiv b{\pmod{m}}$$ 
$$c\equiv d{\pmod{m}}$$

のとき，次の性質が成り立つ。

- $a+c\equiv b+d{\pmod{m}}$（足し算）

- $a-c\equiv b-d{\pmod{m}}$（引き算）

- $ac\equiv bd{\pmod{m}}$（掛け算）

- $a^n\equiv b^n{\pmod{m}}$（累乗）（$n$ は自然数）

## 例

- $10\equiv 5{\pmod{5}}$

- $11\equiv 3{\pmod{4}}$

- $4\equiv 0{\pmod{2}}$

- $14\equiv -1{\pmod{3}}$

- $13^{1000}$ を $6$ で割った余りは、

$$
\begin{align}
13&\equiv 1{\pmod{6}}\\\\
13^{1000}&\equiv 1^{1000}{\pmod{6}}
\end{align}
$$

で、$1^{1000}=1$ なので $1$ と求まる。

### 補足

- 大学入試において**必ず必要な知識では無いが、知っておくと整数問題をスマートに解ける**ことがある
- 上の性質の証明は、例えば[ヨビノリさんのこちらの $\mathrm{mod}$ の動画](https://okedou.app/videos/6COGmURbrAw)を参照
- 基本的には**割り算はできない**ので注意
- 上の性質で式同士を計算するときは、$\mathrm{mod}$ **がそろっている**ことを忘れずに確認
- 例のとおり、 **累乗の余りを調べる**ときに有効なことも多い

mod

概要

例

補足

タグ