合同式の使い方と性質、具体例、例題について
1. 合同式とは
\[ a \equiv b \pmod{n} \]
ここで、
- \(a\) と \(b\) は整数
- \(n\) は法（modulus）と呼ばれる正の整数
この式は、\(a\) と \(b\) が \(n\) で割ったときに同じ余りを持つことを意味します。すなわち、整数$k$に対して、次の式が成り立ちます。
\[ a-b= nk \]
1.1. 合同式の具体例
例えば、法 \(5\) において \(17\) と \(7\) が合同であることを考えます。これを合同式で表すと、
\[ 17 \equiv 7 \equiv 2\pmod{5} \]
となります。これは、17 と 7 を 5 で割ったとき、どちらも余りが 2 になることを意味します。
- \(17 \div 5 = 3\) 余り \(2\)
- \(7 \div 5 = 1\) 余り \(2\)
したがって、合同式は成立します。
2. 合同式の性質
合同式には以下のような性質があります。
- 同値性: 合同式は通常の等式と同じように扱うことができ、以下の性質が成り立ちます。
- \( a \equiv a \pmod{n} \) （反射律）
- \( a \equiv b \pmod{n} \) ならば \( b \equiv a \pmod{n} \) （対称律）
- \( a \equiv b \pmod{n} \) かつ \( b \equiv c \pmod{n} \) ならば \( a \equiv c \pmod{n} \) （推移律）
- 加法: \( a \equiv b \pmod{n} \) かつ \( c \equiv d \pmod{n} \) のとき、\( a + c \equiv b + d \pmod{n} \) 。
- 減法: \( a \equiv b \pmod{n} \) かつ \( c \equiv d \pmod{n} \) のとき、\( a – c \equiv b – d \pmod{n} \) 。
- 乗法: \( a \equiv b \pmod{n} \) かつ \( c \equiv d \pmod{n} \) のとき、\( ac \equiv bd \pmod{n} \) 。
2.1. 加法の性質の証明
まず、\( a \equiv b \pmod{n} \) というのは、ある整数 \( k_1 \) が存在して \[ a = b + k_1 n \] と表せることを意味します。同様に、\( c \equiv d \pmod{n} \) であれば、ある整数 \( k_2 \) が存在して \[ c = d + k_2 n \] と表せます。
これらを加えると、
\[ a + c = (b + k_1 n) + (d + k_2 n) = b + d + (k_1 + k_2) n \]
となります。したがって、\( a + c \equiv b + d \pmod{n} \) となります。
2.2. 減法の性質の証明
\( a \equiv b \pmod{n} \) より \( a = b + k_1 n \)、また \( c \equiv d \pmod{n} \) より \( c = d + k_2 n \) と表せます。
これらを引き算すると、
\[ a – c = (b + k_1 n) – (d + k_2 n) = b – d + (k_1 – k_2) n \]
となります。したがって、\( a – c \equiv b – d \pmod{n} \) となります。
2.3. 乗法の性質の証明
\( a \equiv b \pmod{n} \) より \( a = b + k_1 n \)、また \( c \equiv d \pmod{n} \) より \( c = d + k_2 n \) と表せます。
これらを掛けると、
\[ ac = (b + k_1 n)(d + k_2 n) = bd + b k_2 n + d k_1 n + k_1 k_2 n^2 \]
ここで、\( n \) で割り切れる項 \( b k_2 n + d k_1 n + k_1 k_2 n^2 \) が含まれているので、\( ac \equiv bd \pmod{n} \) となります。
2.4. 除法について
合同式では一般的に除法は成り立ちません。しかし、次の場合は除法が成り立ちます。
$$b\equiv c \pmod p$$
除法の性質を示します。まず、条件を整理します。与えられた式は次の通りです。
\[ ab \equiv ac \pmod{p} \]
すなわち、
\[ ab – ac = a(b – c) \equiv 0 \pmod{p} \]
したがって、次の式が成り立ちます。
\[ a(b – c) \equiv 0 \pmod{p} \]
つまり、$a$または$b-c$のどちらかは少なくともpの倍数である。そして、\( a \) と \( p \) が互いに素であることから、\( b – c \equiv 0 \pmod{p} \) が成り立つ。したがって、aを割ったような次の形が導かれます。
\[ b \equiv c \pmod{p} \]
この性質は一次不定方程式を解くときに利用することができます。
3. 練習問題
3.1. 問題 1
$$ 29 \equiv -3 \pmod{8}$$
$29=8\times 3 +5$であるから、
$$\begin{align*}29 &\equiv 8\times 3 +5 \pmod{8} \\ &\equiv5 \pmod{8} \\ &\equiv 5-8 \pmod{8} \\ &\equiv -3 \pmod{8} \end{align*}$$
3.2. 問題 2
\( x \equiv 3 \pmod{7} \) であるとき、$2x+4$を7で割った余りを求めなさい。
まず、与えられた条件 \( x \equiv 3 \pmod{7} \) なので、
$$\begin{align*}2x+4 &\equiv 2\cdot 3 +4 \pmod{7} \\ &\equiv 10 \pmod{7} \\ &\equiv 3 \pmod{7} \end{align*}$$
