数の循環

数の循環
2015 年 6 月 4 日 (木）
. 合同式の意味と基本性質
本章では、”数の循環”を定式化する
”合同式”を学ぶよ！
∼復習∼
！合同式
a,b を整数とし、m を負でない整数とする。a − b が m の倍数のとき a と b は
m を法としての合同であるといい、記号で ≡ と表す。このように ”≡ ”で結
ばれた式を合同式という。
例 4.1）94 − 55 を合同式で書くと？？
94 − 55
94 ≡ 55
(mod 13)
=
39
=
13 × 3
または
94 ≡ 55 (mod 3)
！例 4.2
a と b が m を法として合同であるためには、a を m で割った余りと b を m で
割った余りが等しくなることは必要十分である。
説明
a と b は次のように表せる。
0 ≤ s, t < m
a = mp + s、b = mq + t
このとき
a − b = m(p − q) + (s − t)
−m<s−t<m
が成り立つ。したがって a − b が m で割り切れる（つまり、合同である）た
めには、s − t が m で割り切れることが必要十分である。ところが、
−m < s − t < m
s−t=0→s=t
以上より
合同 ⇐⇒ 余りが等しい
1
例 4.1 を振り返ると・
・
・
94 = 13 × 7 + 3
94
55 = 13 × 4 + 3
≡
55 (mod 13)
または
94 = 3 × 33 + 1
94
55 = 3 × 18 + 1
≡
55 (mod 3)
・m を法とする合同式は一種の等式である！
一種の等式というからには、
等式の基本性質も満たしている
ハズだよね？？
！定理 4
m を法とする合同式に関して次のことが成り立つ。
(1)a ≡ a (mod m)
(2)a ≡ b (mod m) ならば b ≡ a (mod m)
(3)a ≡ b (mod m), b ≡ c (mod m) ならば a ≡ c (mod m)
(4)a ≡ b (mod m), c ≡ d (mod m) ならば、
(i)a + c ≡ b + d (mod m)・
・
・和
(ii)a − c ≡ b − d (mod m)・
・
・差
(iii) ac ≡ bd
が成り立つ。
(mod m)・
・
・積
この定理の (1) を反射律、(2) を対称律、(3) を推移律と呼ぶ。
証明 (1)、(2) は明らか。
(3) を証明する。
a ≡ b (mod m), b ≡ c (mod m) とする。
a − b = mk, b − c = ml(k, l ∈ Z) と表せる。
このとき a − c = a − b + b − c = mk + ml = m(k + l) と変形できる。
以上より示せた。
2
(4) を証明する。
a≡b
(mod m)
,
c≡d
a − b = mk
,
c − d = ml(k, l ∈ Z)
(i)(a + c) − (b + d)
=
a−b+c−d
(mod m)
= mk + ml = m(k + l)
(ii)(a − c) − (b − d)
a − b − (c − d)
=
= mk − ml = m(k − l)
(iii) a = b + mk
,
c = d + ml
ac =
(b + mk)(d + ml)
= bd + mbl + mdk + m2 kl
ac − bd = m(bl + dk + mkl)
m(bl + dk + mkl) は
、 m で割り切れるから
ac − bd = mk1
ac ≡ bd
(mod m)
加法、減法、および乗法に関して、合同式は、
等式と全く同じように取り扱うことができる！
！
へぇ∼
(例 4.4) 10n ≡ 1 (mod 9) が成り立つ。
(例 4.5)19410712 を、例 4.4 を使って、9 で割った余りを求めよう！
19410712
=
1 × 107 + 9 × 106 + 4 × 105 + 1 × 104
+0 × 103 + 7 × 102 + 1 × 101 + 2
≡
1+9+4+1+0+7+1+2
=
25
=
2 × 10 + 5
≡
2 + 5 (mod 9)
=
7
(mod 9)
！整数 9 で割った余りは、その数の各位の数字の和を 9 で割った余りに等しい。
つまり、各位の数字の和が 9 で割り切れば、その数は 9 で割り切れることになる！
3
(mod 9) 以外でも同じような計算
できないものかねぇ・
・
・。
10 ≡ 1 (mod x)
10 ≡ −1 (mod x)
x ≡ 3 のとき、10 ≡ 1 (mod 3) となるので、
例 4.4 と同様に 10n ≡ 1 (mod 3) が成り立つ！
！整数を 9, 3 で割った余りは、その数の各位の数字の和を 9, 3 で割った余りに等しい。
x ≡ 11 のとき、10 ≡ −1 (mod 11) となるので、
例 4.4 と同様に 10n ≡ (−1)n (mod 11) が成り立つ！
！整数を 11 で割った余りは、その数の数字を
(1 の位をプラスとして) 交互に符号を変えたものを 11 で割った余りに等しい。
. 合同式の簡約・合同式の両辺を同じ数で割ることを簡約と
いう。
法 m に関する 2 つの合同式は辺を、
足したり、引いたり、掛けたりできたけど、
簡約することはできるのかな？？
=⇒ 必ずしも成立しない！
では、c がどのような条件を満たすとき、
ac ≡ bc
(mod m)
の両辺から c を簡約できるのか？そのためには準備が必要である。
！定理 5
既約分数
(1) 任意の分数 dc (d > 0) に対して ab = dc
となる既約分数 ab (b > 0) が存在する。
(2) ab (b > 0) を既約分数とする。 ab = dc (d ＞ 0) ならば
c = ak, d = bk(k は整数) と表せる。
つまり c は a で割り切れる、d は b で割り切れるということ。
⋆(3) 整数 a, b(b > 0) に対して、 ab が既約分数であるためには、
a と b が互いに素であることが必要十分である。
4
！定理 6
(1)bc が a で割り切れ、a と b が互いに素であれば、
c が a で割り切れる。
(bc = ak(k ∈ Z)、a と b が互いに素 =⇒ c = ak(k ∈ Z))
(2)ac ≡ bc (mod m) で、c と m が互いに素であれば、
a ≡ b (mod m) が成り立つ。
証明 (定理 6)
(1)bc が a で割り切れるので、
ad = bc
すなわち、
a
c
=
b
d
となる d(∈ Z) が存在する。
a が b は互いに素であるから、
定理 5(3) より ab は既約分数である。
したがって、定理 5(2) より、c は a で割り切れる。
(2)ac ≡ bc (mod m) であるから、(a − b)c は m で割り切れる。
c と m は互いに素なので、定理 6(1) より a − b が m 割り切れる。
すなわち a ≡ b (mod m) が成り立つ。
重要！
！
等式の簡約では、
ac = bc, c ̸= 0 ならば a = b
だけど、
合同式の簡約では
ac ≡ bc (mod m) で
c と m が互いに素ならば
a ≡ b (mod m)
なんだね！
！
・ボールパスゲーム・
A0 ∼A7 の 8 人が、反時計回りに、等間隔で同一円周上に並んで
ボールパスゲームをする。A0 から始めて、反時計回りに (k − 1)
人飛ばしのパス”K”を続けていくとき、8 人全員にボールは回る
であろうか？（略図参照）
なげるよー
あ、ちょうちょだ
5
パス２
A1
A0
パス１
A7
A6
A2
略図
A5
A3
A4
パス１・
・
・A0 , A1 , A2 , A3 , A4 , A5 , A6 , A7 , A0 ・
・
・全員に回る。
パス２・
・
・A0 , A2 , A4 , A6 , A0 ・
・
・全員に回らない。
パス３・
・
・A0 , A3 , A6 , A1 , A4 , A7 , A2 , A5 , A0 ・
・
・全員に回る。
パス４・
・
・A0 , A4 , A0 ・
・
・全員に回らない。
パス５・
・
・A0 , A5 , A2 , A7 , A4 , A1 , A6 , A3 , A0 ・
・
・全員に回る。
パス６・
・
・A0 , A6 , A4 , A2 , A0 ・
・
・全員に回らない。
パス７・
・
・A0 , A7 , A6 , A5 , A4 , A3 , A2 , A1 , A0 ・
・
・全員に回る。
パス８・
・
・A0 , A0 ・
・
・全員に回らない。
！定理 7
n 人が等間隔で同一円周上に並び、反時計回りに
(k − 1) 人飛ばしのパス”K”でボールをまわしていく。
互いに素であれば、ボールは n 人全員に
1 回ずつ渡った後、最初にパスを出した人に戻る。
今日のキーワードだね！
！
お疲れ様！
！
6

Download Report