整数に関する同値関係 |
k をある定まった整数とする。このとき、 a ， b ∈Zに対して、aとｂがｋを法として合同であるとは、
a − b が k の倍数である。
⇔ ある整数ｍがあって a - b ＝ m k となる。
⇔ a と b の割ったときの余りが同じ。
このとき、a ≡ b (mod k) と書く。
例： k = 3 の場合に、7 ≡ 16 (mod 3), 8 ≡ - 4 (mod 3).
Ｓ(0)：3で割り切れる集合、Ｓ(1)：3で割って1余る集合、Ｓ(2)：3で割って2余る集合とおくと、それぞれの中では、同値なものの集まりであることが分かる。
Ｓ(0)： ・ ・ ・ -3, 0, 3, ・ ・ ・
Ｓ(1)： ・ ・ ・ -2, 1, 4, ・ ・ ・
Ｓ(2)： ・ ・ ・ -1, 2, 5, ・ ・ ・
定理． a ≡ b (mod k ), a '≡ b ' (mod k ) のとき、次が成り立つ。
（１） a + a ' ≡ b + b ' (mod k )
（２） a - a ' ≡ b - b ' (mod k )
（３） a a ' ≡ b b ' (mod k )
∵) a - b = m k , a ' - b ' = n k とおくと、
( a ± a ') - ( b ± b ') = ( a - b ) ± ( a ' - b ') = ( m ± n ) k
a a ' - b b ' = a ( a ' - b ') + ( a - b ) b ' = ( a n + b 'm ) k
系． a ≡ b (mod k )の時次が成り立つ。
（１）
（２） a c ≡ b c (mod k )
例． 10 ≡ 1 (mod 3) ⇒ 
,
10 ≡ 1 (mod 9) ⇒ 
,
10 ≡ 3 (mod 7) ⇒ 
,
応用問題1． 54321を9で割ったときの余りを求めよ。
次に答えを入れてリターンせよ：
応用問題2． 5123123を7で割った余りを求めよ。
次に答えを入れてリターンせよ：
カレンダーの曜日：
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 | 31 |
このカレンダーから、月曜日は７で割って１余る日だということがわかる。
これを使って次の問題を考える。
（１９００＋Ｘ）年 Ｍ 月 Ｎ 日 は何曜日か？
上のカレンダーは、実は1900年1月のものである。従って、１月の曜日を調べるには、
Ｎ ≡ x (mod 7)
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
でよいことになる。２月以降はどうすればよいか？１月は、31日あるので 31 ≡ 3 (mod 7) から、3つ曜日がずれる。普通の年だと2月は28日なので 28 ≡ 0 (mod 7) より、２月と３月の日にちに対する曜日のずれはない。３月は31日あるのでさらに３つずれて、１月からみると３＋３＝６日ずれることになる。これを繰り返すと、
Ｍ’+Ｎ ≡ x (mod 7)
| M | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| M’ | 0 | 3 | 3 | 6 | 1 | 4 | 6 | 2 | 5 | 0 | 3 | 5 |
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 普通 | 日 | 月 | 火 | 水 | 木 | 金 | 土 |
これで、1900年のＭ月Ｎ日がなん曜日かはわかる。それでは、1901年以降はどうすればよいだろうか？１年は、普通365日なので 365 ≡ 1 (mod 7) から、1年で1つ曜日がずれる。従って、1900＋Ｘ年では、Ｘ曜日がずれることになる。従って、
Ｘ +Ｍ’+Ｎ ≡ x (mod 7)
を考えればよい。閏年がなければこれでおしまいだが、閏年は４年に１回、４で割れる年（夏季のオリンピックの年）に来る。そのとき、２月の最後にもう１日加わるので、閏年の２月以降はもう一日加えないといけない。すなわち、
Ｘ +［Ｘ／4］+Ｍ’+Ｎ ≡ x (mod 7)
| M | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| M’ | 0 | 3 | 3 | 6 | 1 | 4 | 6 | 2 | 5 | 0 | 3 | 5 |
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 普通 | 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 閏年の1、2月 | 土 | 日 | 月 | 火 | 水 | 木 | 金 |
但、ここで［］は小数以下切捨ての記号である。（ガウス記号と言う。）
｛例：［6.3］= 6, [63/4] = [15+3/4] = 15｝