合同式
1.合同式
\( a,b \) を \( m \) で割った時の余りが等しい時、\( a \) は \( m \) を法として、\( b \) と合同という。
この時、
\( a \equiv b \quad \pmod{m} \)
と書く。
実際に\( 3 \)を法として具体的に考える。
■ 余り \( 0 \) (割り切れる)
\(30を3\)で割ると、余りが\(0\)になるので
\( 30 \equiv 0 \quad \pmod{3} \)
同じように、18も
\( 18 \equiv 0 \quad \pmod{3} \)
なので、
\( 30 \equiv 18 \equiv 0 \quad \pmod{3} \)
■ 余り \( 1 \)
\( 28 \equiv 19 \equiv 1 \quad \pmod{3} \)
■ 余り \( 2 \)
\( 20 \equiv 5 \equiv 2 \quad \pmod{3} \)
■ 余り \( 3 \)
余りは3は3で割り切れる。
つまり、
\( 3 \equiv 0 \quad \pmod{3} \)
となる。
合同式の性質をまとめると下記のようになる。
① \( a \equiv b \quad \pmod{m} \) について
- 整数倍 (整数 \( c \))
\( ca \equiv cb \quad \pmod{m} \)
- 和・差
\( a+b \equiv 2a \equiv 2b \quad \pmod{m} \)
\( a-b \equiv 0 \)
- \( b \equiv c \quad \pmod{m} \)
\( a \equiv c \quad \pmod{m} \)
② \( a \equiv b,\quad c \equiv d \quad \pmod{m} \) について
- 和
\( a+c \equiv b+d \equiv a+d \equiv b+c \quad \pmod{m} \)
- 差
\( a-c \equiv b-d \equiv a-d \equiv b-c \quad \pmod{m} \)
- 積
\( ac \equiv bd \quad \pmod{m} \)
- 累乗
\( a^k \equiv b^k \quad \pmod{m} \quad (k \in \mathbb{N}) \)
③ \( ca \equiv cb \quad \pmod{m} \) について
- \( cとm \) の最大公約数を\( G \) の時
\( a \equiv b \quad \pmod{\frac{m}{G}} \)
- \( cとm \) が互いに素 (\( G=1 \)) の時
\( a \equiv b \quad \pmod{m} \)
例). \( 4a \equiv 4b \quad \pmod{6} \) の時
\( a \equiv b \quad \pmod{3} \) (4と6の最大公約数は2)
2.累乗の余り (定数 c)
(1). \( 17 を 3\) で割った余りを求めよ。
(2). \( 17^2 を 3 \) で割った余りを求めよ。
(3). \( 17^3 を 3 \) で割った余りを求めよ。
(4). \( 17^5 を 3 \) で割った余りを求めよ。
(5). \( 17^{100} を 3 \) で割った余りを求めよ。
例1). \( 17 \equiv 2 \quad \pmod{3} \)
例2). \( 17^2 \equiv 2^2 \equiv 4 \equiv 1 \quad \pmod{3} \)
例3). \( 17^3 = 17 \cdot 17^2 \equiv 2 \cdot 1 \equiv 2 \quad \pmod{3} \)
例4). \( 17^5 = (17^2)^2 \cdot 17 \equiv 1^2 \cdot 2 \equiv 2 \quad \pmod{3} \)
例5). \( 17^{100} = (17^2)^{50} \equiv 1^{50} \equiv 1 \quad \pmod{3} \)
(1). \( 8^{10} + 4^{10} を 3\) で割った余りを求めよ。
(2). \( 4^{10} – 2^{10} を 3 \) で割った余りを求めよ。
例1). \( 8^{10} + 4^{10} = 2^{30} + 4^{10} = 4^{15} + 4^{10} \)
\( 4 \equiv 1 \quad \pmod{3} \)
なので、
\begin{eqnarray}
4^{15} + 4^{10} & \equiv & 1^{15} + 1^{10} \quad \pmod{3} \\
& \equiv & 2
\end{eqnarray}
例2). \( 4^{10} – 2^{10} = (4^5 – 2^5)(4^5 + 2^5) = (4^5 – 2^5)(4^5 + 2^5) \)
・ \( 4 \equiv 1 \)
・ \( 2^5 = 4^2 \cdot 2 \equiv 2 \quad \pmod{3} \)
よって、
\( 4^5 + 2^5 \equiv 1 + 2 \equiv 3 \equiv 0 \pmod{3} \)
となるので、
与式を3で割ると余りは0
～ 補足説明 ～
つまり、
\( 4^5 + 2^5 \) は3の倍数なので、その積である
\( (4^5 – 2^5)(4^5 + 2^5) \) も3の倍数という事である。
そりゃ3の倍数は3で割り切れますよね。
3.累乗の余り (自然数 n)
\(n \) は自然数とする。
(1). \( n を 4 \) で割った余りを求めよ。
(2). \( n^2 を 4 \) で割った余りを求めよ。
(3). \( n^3 を 4 \) で割った余りを求めよ。
(4). \( n^4 – n^2 を 4 \) で割った余りを求めよ。
(5). \( n^{50} を 4 \) で割った余りを求めよ。
例1). \( 0,1,2,3 \) の4つ。
例2). \( 4 \) を法として、余りの表を作成すると、
| \( n \) | \( 0 \) | \( 1 \) | \( 2 \) | \( 3 \) |
| \( n^2 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) |
よって、\( n^2 を 4 \) で割った余りは \( 0と1\)。
例3). \( 4 \) を法として、余りの表を作成すると、
| \( n \) | \( 0 \) | \( 1 \) | \( 2 \) | \( 3 \) |
| \( n^2 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) |
| \( n \cdot n^2 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 3 \) |
よって、\( n^3 を 4 \) で割った余りは \( 0と1と3\)。
例4解法1). \( n^4 – n^2 = n^2 (n^2-1) \)
4を法として、余りの表を作成すると
| \( n \) | \( 0 \) | \( 1 \) | \( 2 \) | \( 3 \) |
| \( n^2 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) |
| \( n^2-1 \) | \( 3 \) | \( 0 \) | \( 3 \) | \( 0 \) |
| \( n^2(n^2-1) \) | \( 0 \) | \( 0 \) | \( 0 \) | \( 0 \) |
よって、\( n^4 – n^2 を 4 \) で割った余りは \( 0 \)。
例4解法2). \( n^4 – n^2 \)
4を法として、余りの表を作成すると
| \( n \) | \( 0 \) | \( 1 \) | \( 2 \) | \( 3 \) |
| \( n^2 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) |
| \( n^2 \cdot n^2 = n^4 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) |
| \( n^4 – n^2 \) | \( 0 \) | \( 0 \) | \( 0 \) | \( 0 \) |
よって、\( n^4 – n^2 を 4 \) で割った余りは \( 0 \)。
例4解法3). \( n^4 – n^2 = n^2 (n^2-1) = (n-1)n \cdot n(n+1) \)
連続する2整数はどちらかが、2の倍数となる。
① \( n-1 \) が2の倍数である場合
\( n+1 \) も2の倍数となるので、
\( n^4 – n^2 \) は4の倍数となる。
② \( n \) が 2の倍数である場合
\( n^2 \) は4の倍数であるので、
\( n^4 – n^2 \) は4の倍数となる。
よって、①②より\( n^4 – n^2 )を4で割った余りは0となる。
(5). \( n^{50} = (n^2)^{25} \)
4を法として、余りの表を作成すると
| \( n \) | \( 0 \) | \( 1 \) | \( 2 \) | \( 3 \) |
| \( n^2 \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) |
| \( (n^2)^{25} \) | \( 0 \) | \( 1 \) | \( 0 \) | \( 1 \) |
よって、\( n^{50} \) を4で割ると余りは \( 0か1 \)。
