合同式と剰余類

合同式とは、整数の差がある数で割り切れるときに成り立つ数式です。これは数論や暗号理論で重要な概念です。

合同式の基本

合同式は次のように表されます:

\(a \equiv b \pmod{n}\)

ここで、\(a\) と \(b\) は整数で、\(n\) は法と呼ばれる正の整数です。意味は「\(a\) と \(b\) の差が \(n\) で割り切れる」です。

具体例

例1: \(17 \equiv 5 \pmod{12}\)

• \(17 - 5 = 12\)
• 12 は 12 で割り切れるので、成立します。

例2: \(23 \equiv 2 \pmod{7}\)

• \(23 - 2 = 21\)
• 21 は 7 で割り切れるので、成立します。

剰余類

剰余類は全ての整数を法 \(n\) ごとに分類した集合です。

具体例

例: \(n = 3\) の場合の剰余類

• \([0] = \{...\ -6, -3, 0, 3, 6, ...\}\)
• \([1] = \{...\ -5, -2, 1, 4, 7, ...\}\)
• \([2] = \{...\ -4, -1, 2, 5, 8, ...\}\)

つまり、任意の整数は、3つの剰余類 \([0], [1], [2]\) のどれかに属します。

演算規則

合同式にも通常の演算と同様の規則が適用されます。そのため、加減乗除の操作を行うことができます。

具体例

例: \(a \equiv 3 \pmod{5}\) と \(b \equiv 4 \pmod{5}\) のとき

• \(a + b \equiv 3 + 4 \equiv 7 \equiv 2 \pmod{5}\)
• \(a - b \equiv 3 - 4 \equiv -1 \equiv 4 \pmod{5}\)
• \(a \times b \equiv 3 \times 4 \equiv 12 \equiv 2 \pmod{5}\)

練習問題

次の問題を解いて、合同式の理解を深めましょう：

1. \(29 \equiv ? \pmod{8}\)
2. \(56 \equiv ? \pmod{7}\)
3. \([-15] \pmod{4}\) を求めなさい。