141124 初版 141124 更新
特に断らない限り，文字は整数を表す。
a と a' の n で割った余りが等しいとする。
(n を 法として a と a' は等しい(合同である)という
合同式では a ≡ a' (mod n) と記す)
このとき，
ax と a'x の n で割った余りは等しい。
(合同式では ax ≡ a'x (mod n) と記す)
証明
ax - a'x = (a-a') x
= nkx (仮定より a-a' は n で割り切れるから)
つまり ax - a'x は n で割り切れる。
逆は成り立たないことに注意すること。
例えば，
6 を法にしたとき，
2 × 9 と 4 × 9 は 等しい(合同である)が，
2 と 4 は 等しくはない(合同ではない)。
例1
4 を法とするとき，
7 の倍数 と 3 の倍数は一致する。
| x |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 7x |
7 |
14 |
21 |
28 |
35 |
42 |
49 |
56 |
63 |
70 |
| 7x (mod 4) |
3 |
2 |
1 |
0 |
3 |
2 |
1 |
0 |
3 |
2 |
| 3x |
3 |
6 |
9 |
12 |
15 |
18 |
21 |
24 |
27 |
30 |
| 3x (mod 4) |
3 |
2 |
1 |
0 |
3 |
2 |
1 |
0 |
3 |
2 |
例2
| x |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| 2x |
2 |
4 |
6 |
8 |
10 |
12 |
14 |
16 |
18 |
20 |
| 2x (mod 6) |
2 |
4 |
0 |
2 |
4 |
0 |
2 |
4 |
0 |
2 |
| 4x |
4 |
8 |
12 |
16 |
20 |
24 |
28 |
32 |
36 |
40 |
| 4x (mod 6) |
4 |
2 |
0 |
4 |
2 |
0 |
4 |
2 |
0 |
4 |