(7/5) 略解, 補足等今日の授業では合同式を学習しました. b − a が m で

基礎数学 (7/5) 略解, 補足等
今日の授業では合同式を学習しました. b − a が m で割り切れるとき,
a ≡ b (mod m)
と表しました. また, (a ÷ m の余り)=(b ÷ m の余り) が成り立つとき, また, そのと
きに限り a ≡ b (mod m) が成り立つことを学習しました.
また, 足し算 a + c, 引き算 a − c, 掛け算 a × c を法 m で計算するとき, a, c をそ
れぞれ法 m で合同な数に置き換えていい, ということを学習しました. また, a ≡ b
(mod m) のとき, an ≡ bn (mod m) が成り立つことを学びました.
以上を駆使すると, 大きな数を適当な数で割った余りや, an 型の数を適当な数で
割った余りが計算できます. それが今日のプリントの問題です.
問題 11.1 の解答. a ≡ b (mod m) が成り立つかを, b − a が m で割り切れるかに戻っ
て確認する問題でした.
•
•
•
•
•
17 − 5 = 12 は 4 で割り切れるので, (1) は正しい.
5 − 17 = −12 も 4 で割り切れるので, (2) も正しい.
32 − 21 = 11 は 6 で割り切れないので, (3) は誤り.
234 − 123 = 111 は 3 で割り切れる (111 = 3 × 37) ので, (4) は正しい.
11 − 11 = 0 は 763 で割り切れる (0 = 763 × 0) ので, (5) も正しい.
というわけで, 合同式の中で正しいのは (1), (2), (4), (5) となります.
問題 11.2 の解答. まず, 定理 11.3 の証明を残した部分である
(a ÷ m の余り) = (b ÷ m の余り) =⇒ a ≡ b (mod m)
を証明してみましょう. 割り算の原理より,

a = mq + r かつ 0 ≤ r < m
1
1
1
b = mq2 + r2 かつ 0 ≤ r2 < m
を満たす整数 q1 , q2 , r1 , r2 が存在します. 今, 仮定から a ÷ m の余りと b ÷ m の余りは
等しいので, r1 = r2 が成り立ちます. よって,
b − a = (mq2 + r2 ) − (mq1 + r1 ) = m(q2 − q1 )
となり, b − a は m で割り切れること, つまり, a ≡ b (mod m) が成り立つことが分
かりました.
次に定理 11.4 の (1) を示してみましょう. 合同式の定義に戻ってみると, a − a = 0
が m で割り切れることを示したいのです. 0 = m × 0 だから 0 は m × (整数) の形で書
け, 0 が m で割り切れることが分かります. よって, a ≡ a (mod m) が成り立ちます.
定理 11.4 の (2) は省略します. 言うべきことは, 「b − a が m で割り切れるならば,
a − b も m で割り切れる」で, 「割り切れる」の定義に戻ればすぐに証明できます.
1
問題 11.3 の解答. 23 ≡ 7 (mod 8), 29 ≡ 5 (mod 8) に注意します. すると,
23 + 29 ≡ 7 + 5 = 12 ≡ 4
(mod 8)
だから, 23 + 29 を 8 で割った余りは 4 となります. 同様にして,
23 × 29 ≡ 7 × 5 = 35 ≡ 3
(mod 8)
だから, 23 × 29 を 8 で割った余りは 3 となります.
問題 11.3 の別解. 23 ≡ −1 (mod 8) に注目すると, より簡単に計算できます. 23 ≡
−1 (mod 8), 29 ≡ 5 (mod 8) だから,
23 + 29 ≡ −1 + 5 = 4 (mod 8)
だから, 23 + 29 を 8 で割った余りは 4 となります. 同様に,
23 × 29 ≡ −1 × 5 = −5 ≡ 3
(mod 8)
だから, 23 × 29 を 8 で割った余りは 3 となります.
問題 11.4 の解答.
12345 = 1 × 104 + 2 × 103 + 3 × 102 + 4 × 10 + 5
(1)
に注意します. 今, 10 ≡ 1 (mod 9) だから, 102 ≡ 12 = 1 (mod 9). 同様に, 103 ≡ 1
(mod 9), 104 ≡ 1 (mod 9) が成り立ちます. これらを式 (1) に適用して,
12345 ≡ 1 × 1 + 2 × 1 + 3 × 1 + 4 × 1 + 5 = 15 ≡ 6
(mod 9).
よって, 12345 を 9 で割った余りは 6 となります.
問題 11.5 の解答. 310 の下二桁と, 310 を 100 で割った余りは等しいことに注意しま
す. 310 を 100 で割った余りを計算します. 310 = 35×2 = (35 )2 に注意し, まず 35 を法
100 で計算します:
35 = 243 ≡ 43 (mod 100)
よって,
310 = (35 )2 = 43 × 43 = 1849 ≡ 49 (mod 100).
つまり, 310 を 100 で割ったときの余りは 49 となることが分かります. つまり, 310 の
下二桁は 49 となります.
2
問題 11.6 の解答. 定理 11.5 の (1) のみ, 証明を与えておきます. 仮定 a ≡ b (mod m)
から, b − a は m で割り切れます. よって, b − a = mk を満たす整数 k が存在しま
す. 同様に, c ≡ d (mod m) が成り立つので, d − c は m で割り切れます. つまり,
d − c = ml を満たす整数 l が存在します. よって,
(b + d) − (a + c) = (b − a) + (d − c) = mk + ml = m(k + l).
つまり, (b + d) − (a + c) は m で割り切れます. よって, a + c ≡ b + d (mod m) が成
り立ちます.
3

Download Report