合同式
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 。
