平成 30 年度「数理科学基礎」有限力学系
1
数論からの準備
1.1
付値
整数 x が，素数 p で何回割り切れるか，という回数を vp(x) と書き，「x の p 進付値（p-adic valuation of x）」という．例えば v2(8) = 3, v3(12) = 1, v5(10000) = 4, 等々となる．これらはそれぞれの x を素因数分解すると 8 = 23, 12 = 22· 3, 10000 = 104= 24· 54 となるからである．1.2
合同式
整数 n を一つ固定して考える．二つの整数 a, b について 「a と b が法 n で合同である」 とは 「a− b が n で割り切れる」 ことをいう．そして記号で a≡ b (mod n) と表す．例えば 11 ≡ 3 (mod 2), 25 ≡ 43 (mod 3), 101 ≡ 122 (mod 7),等々となる．これはそれぞれの「a− b」に当たるものが 11− 3 = 8 = 2 · 4, 25− 43 = −18 = 3 · (−6), 101− 122 = −21 = 7 · (−3), というようにそれぞれの法で割り切れているからである．
1.3
Z
n 合同式「a≡ b (mod n)」は，見方を変えると 「a を n で割った余りと，b を n で割った余りが等しい」 ということもできる．例えば前節の合同式「101≡ 122 (mod 7)」については 101を 7 で割った余りが 3， 122を 7 で割った余りも 3 なので成り立っているのである．この立場からすると，法 n で考えるときは nで割った余りのみに注目しているのであり，またどんな整数も n で割った 余りは 0 以上 n− 1 以下の整数だから，それらを取り出して Zn={0, 1, 2, · · · , n − 2, n − 1} という記号で表す． 今後重要となるのは，Zn の上で演算を行うことができる，という点であ る．特に足し算と掛け算がほぼ普通と同様にできる．先に定義と記号を書い ておくと Znでの足し算「+n」： a +nb =「普通の足し算 a + b を n で割った余り」 Znでの掛け算「×n」： a×nb =「普通の掛け算 a× b を n で割った余り」 というルールである．例えば 3 +54 = 2 (⇐ 3 + 4 = 7 を 5 で割った余りは 2) 7 +119 = 5 (⇐ 7 + 9 = 16 を 11 で割った余りは 5) 6×74 = 3 (⇐ 6 × 4 = 24 を 7 で割った余りは 3) 10×1110 = 1 (⇐ 10 × 10 = 100 を 11 で割った余りは 1)というようになる． 注意．今後法の n を決めて考えていくときは，Znの演算「+n，×n」のどち らも添字の「n」を省略して単に「+，×」と書くことが多い．
1.4
Z
nでのベキ乗
例えば Z5で 2 を何回も掛けていくと 2×52 = 4, 2×52×52 = 4×52 = 3, 2×52×52×52 = 3×52 = 1 というように 4 回掛けると 1 になる．これを普通のベキ乗の記号「xy」を使っ て書くともっとみやすくなり 21 = 2, 22 = 4, 23 = 3, 24 = 1 というように表される．前節の最後の注意のようにいくつを法として考えて いるのかが明白なときは添字は省略されるし，ベキ乗の記号もその法で計算 されていることは注意する必要がある． 他の素数に対してもベキ乗を計算した表が次の表である： a a1 a2 a3 a4 aの位数 1 1 1 1 1 1 2 2 4 3 1 4 3 3 4 2 1 4 4 4 1 4 1 2 表 1.1 Z5におけるベキ乗 a a1 a2 a3 a4 a5 a6 aの位数 1 1 1 1 1 1 1 1 2 2 4 1 2 4 1 3 3 3 2 6 4 5 1 6 4 4 2 1 4 2 1 3 5 5 4 6 2 3 1 6 6 6 1 6 1 6 1 2表 1.2 Z7におけるベキ乗 （⇐「a の位数」については後で説明される．） このように，Z5においては 0 以外のすべての数は 4（= 5− 1）乗すると 1 に なり，Z7においても 0 以外のすべての数が 6（= 7− 1）乗すると 1 になって いる．この現象は次のように一般化される： 定理 1.1 (Fermat の小定理) pが素数のとき，任意の n∈ Zpは (p− 1) 乗すると 1 になる．すなわち Zpの掛け算に関して np−1= 1 が成り立つ．
証明] （Golomb による証明．）Suppose we have beads in n different colors, and we wish to make necklaces using exactly p beads. First we put p beads on a string. Since each of the beads can be chosen in n ways, there are np
possible strings. For each of the n colors, there is one string entirely of that color. We throw these away, leaving np−n strings. We will join the two ends
of each of these strings to form necklaces. But we observe that if two strings differ only by a cyclic permutation of the beads, the resulting necklaces will be indistinguishable. Since there are p cyclic permutations of the p beads on a string, the number of distinguishable necklaces is (np− n)/p, which
must therefore be an integer. □
この証明を p = 5，n = 2 のときで例示すると次のようになる．5 個のビーズ で 2 色からなるネックレスを作ることになるが，その 2 色を A，B とすると，
両端を結ぶ前の紐の状態は 25= 32通りある：
AAAAA
AAAAB AAABA AABAA ABAAA BAAAA AAABB AABBA ABBAA BBAAA BAAAB AABAB ABABA BABAA ABAAB BAABA AABBB ABBBA BBBAA BBAAB BAABB ABABB BABBA ABBAB BBABA BABAB ABBBB BBBBA BBBAB BBABB BABBB BBBBB
ここでそれぞれの行の紐は両端を結ぶと区別できなくなってしまうものを並 べてある．したがって A 一色だけのものと B 一色だけのものを全体から除い た 25− 2 通りの紐が，5 個ずつのグループに分かれる．よって 25− 2 は 5 で 割り切れることになる，というのがこの場合の証明である．
1.5
位数
素数 p に対し，Zpの 0 以外の元 a の「位数」とは ak = 1となるような最 小の自然数 k のことをいう．そして記号で「ordp(a)」と表す．前節の表 1.1 と表 1.2 には，Z5と Z7の元の位数も載せてある．例えば Z7において「4」 の位数を求めたいときは，41, 42, 43,· · · というようにベキ乗を計算していっ て初めて 1 になるのは 43だから，4 の位数は 3 である．要するにそれぞれの 表の a の行を左から見ていって最初に 1 が現れるところの指数が位数である． 元の位数について重要なのが次の命題である： 命題 1.2 素数 p に対し，Zpの任意の元の位数は p− 1 の約数である． 証明] 背理法によって証明する．すなわちある元 a∈ Zpの位数が p− 1 の約数 でないと仮定して矛盾を導くのである．そこで a の位数を k とし，k が p− 1 の約数でない，と仮定する．したがって p− 1 を k で割ると余りは 0 にはな らないから，割り算の式 p− 1 = qk + r において，余り r は 0 < r < k をみたしている．そこでこの両辺を a の指数 にした等式 ap−1= aqk+r (1.1) を用いて考えていこう．この左辺は Fermat の小定理より 1 に等しい．また 右辺は指数法則を用いれば aqk+r = aqk· ar= (ak)q· ar= 1q· ar= ar となる．（⇐ 途中で a の位数が k であること，したがって ak = 1であること を用いている．）よって等式 (1.1) は ar= 1であることを主張している．しか しこれは a の位数が k であるのに，k より小さい r について ar= 1であることになり，位数の定義に反する．したがって k が p− 1 の約数でない，と仮 定したのが間違いであり，命題の主張が証明される． □ 系 1.3 a∈ Zpの位数が k であるとき，自然数 n について an= 1が成り立つな らば，k は n の約数である． 証明] 上の命題の証明の「p− 1」を「n」で置き換えれば全く同じ証明でよ い． □
2
平方写像のグラフ
2.1
グラフの定義
素数 p に対し，写像 f : Z∗p→ Z∗pを f (x) = x2で定義する．そして有向グ ラフ Gp= (Vp, Ep)を Vp = Z∗p, Ep = {(a, f(a)); a ∈ Z∗p} で定義し，「法 p の平方写像のグラフ」あるいは単に「平方グラフ」と呼ぶ． いくつかの小さい p に対して，平方グラフは次のようになる： G3： 1 2G5： 1 2 3 4 G7： 1 2 3 4 5 6
G11： 1 2 3 4 5 6 7 8 9 10 G13： 1 2 3 4 5 6 7 8 9 10 11 12
2.2
テールとサイクル
任意の a∈ Z∗pに対し，次のように数列{an} を定義する： a0 = a, a1 = f (a0), a2 = f (a1), · · · , ak+1 = f (ak) (k≥ 0)すなわち a から始めて次々に f を施して a1.a2.· · · を作っていくのである．例 えば p = 13 で a = 2∈ Z∗13のときは a0 = 2, a1 = f (a0) = f (2) = 22= 4, a2 = f (a1) = f (4) = 42= 3, a3 = f (a2) = f (3) = 32= 9, a4 = f (a3) = f (9) = 92= 3, a5 = f (a4) = f (3) = 32= 9 · · · というようになっており，一度それまでの値と同じ値が現れたら以後ずっとパ ターンが繰り返されることもわかる．この場合，繰り返し始める a2までは a0 から 2 回かかっており，その後 a2= a4= a6=· · · というように周期が 2 で 繰り返される．このように繰り返し始めるまでにかかる回数を「tail number」 と呼んで「t(a)」で表し，その後繰り返される周期を「cycle number」と呼 んで「c(a)」で表す．したがってこの例の a = 2∈ Z∗13の場合は t(2) = 2, c(2) = 2 となる．また別の例として 7∈ Z∗11の場合は t(7) = 1, c(7) = 4 となる．これは上の図を見ても一目瞭然であろう．
2.3
tale number
と cycle number の基本命題
本節の目標は次の命題を証明することである： 命題 2.1 任意の a∈ Z∗pに対し，その位数を 2 ベキの部分と奇数の部分に分けて ordp(a) = 2e· ℓ とおく．ただし e, ℓ は非負整数であり，さらに ℓ は奇数 とする．このとき t(a) = e, c(a) = ordℓ(2) が成り立つ．
証明] a を固定しておいて t(a) = t, c(a) = c とおくと，定義によって ft(a) = ft+c(a) (2.1) である．しかも t, c はこの等式が成り立つような最小の非負整数であること に注意しておく．式 (2.1) は f の定義によって a2t = a2t+c (2.2) が成り立つことを意味している．したがってこの両辺に a−2tを掛けると a2t+c· a−2t= a2t+c−2t = a2t(2c−1)= 1 (2.3) という等式が成り立つ．したがって系 1.3 より a の位数 ordp(a)は 2t(2c− 1) の約数であり，最初に ordp(a) = 2e· ℓ とおいたから 2e· ℓ|2t(2c− 1) が成り立つことになる．ここで ell は奇数だから，このことから 2e | 2t, (2.4) ℓ | (2c− 1) (2.5) という二つのことが成り立つことがわかる．ここで条件 (2.4) は e≤ t である ことを意味するが，実は本当に等号 e = t (2.6) が成り立つ．以下このことを背理法で証明しよう．すなわち e < t (2.7) と仮定して矛盾を導くのである．条件 (2.5) より 2eℓ|2e(2c− 1) であるから， a2e(2c−1)= 1である．したがって式 (2.3) の変形を逆にたどれば a2e+c·a−2e = 1 となり，等式 a2e+c = a2e
が得られる．これは fe+c(a) = fe(a)が成り立つこ
とを意味しており，一方で tail number t の定義によって t は fk+c(a) = fk(a) が成り立つような最小の k であったから，不等式 (2.7) は t の定義に反する． したがって等式 (2.6) が成り立つことがわかった． 次に条件 (2.5) によれば 2c≡ 1 (mod ℓ) が成り立つから c は ord ℓ(2)の倍数 でなければならないが，実は c = ordℓ(2)であることを背理法で証明しよう． 以下見やすいように ordℓ(2) = dとおくと，c は d の倍数であるが，証明したい のは等号 c = d が成り立つことである．そこで c > d と仮定して矛盾を導こう． ここで modℓ での 2 の位数が d だから 2d≡ 1 (mod ℓ) が成り立ち，したがって 2d−1 は ℓ の倍数である．ということは 2eℓ|2e(2d−1) が成り立ち，a2e(2d−1) = 1
が成り立つ．そこで先ほどと同様の変形を行うと，fe+d(a) = fe(a)が成り
立つことになる．しかし cycle number c は fe+m(a) = fe(a)が成り立つ m
の最小値だったから，c > d だとするとこれは矛盾となる．したがって等号 c = dが成り立つのである．これで命題の証明が完成した． □
3
巡回群の
2
倍写像
素数 p に対し Z∗pには原始根が存在すること，すなわち位数 p− 1 の元 r が存在することを利用すると，掛け算を演算とする群 Z∗pと，足し算を演算 とする群 Zp−1が同型になる．具体的には次の命題が成り立つ： 命題 3.1 写像 F : Zp−1→ Z∗pを F (a) = ra で定義すると，F は準同型写像であってしかも全単射となる． 証明] 準同型写像であるとは，任意の a, b∈ Zp−1に対して F (a + b) = F (a)× F (b) (3.1) が成り立つことをいう．この右辺を計算していくと F (a + b) = ra+b = ra× rb = F (a)× F (b) というように左辺と等しくなり，式 (3.1) が確かに成り立っていることがわか る．次に F が単射であることを示そう．それには単射の定義 F (a) = F (b)⇒ a = b が成り立つことを示せばよい．この仮定「F (a) = F (b)」は F の定義によって ra = rb (3.2) ということである．ここで a≤ b として式 (3.2) の両辺に (r−1)aを掛けると 左辺は ra× (r−1)a = (r× r−1)a = 1a = 1となり，右辺は rb× (r−1)a = ( b個 z }| { r× · · · × r) × ( a個 z }| { r−1× · · · × r−1) = rb−a となる．したがって rb−a= 1であるが，ここで a, b∈ Z p−1だから 0≤ b−a ≤ p− 2 であることに注意すると r の位数が p − 1 であることから b − a = 0 でな ければならず，a = b であることが結論される．したがって F は単射である． さらに F の定義域も値域も共に元の個数が p− 1 であるから，単射であるこ とから全射であることもわかり，F が全単射であることも証明された． □ この命題から，次の重要な事実が得られる： 命題 3.2 Z∗pにおける平方写像を q : Z∗p → Z∗pとし，Zp−1 における 2 倍写像を m : Zp−1→ Zp−1とすると，等式 F◦ m = q ◦ F (3.3) が成り立つ． 証明] 任意の a∈ Zp−1の，(3.3) の左辺の写像による値を計算していくと (F ◦ m)(a) = F (m(a)) = F (2a) = r2a = (ra)2 = q(ra) = q(F (a)) = (q◦ F )(a) というように (3.3) の右辺の写像による値と等しくなる．したがって命題が 証明される． □ この命題の内容は 「Z∗pの平方写像は，同型写像 F を介して Zp−1の 2 倍写像に変換される」
ということを意味している．したがって平方写像から作られるグラフを考察 することと，2 倍写像から作られるグラフを考察することとは同等である．そ こで以下では巡回群 Zmにおける 2 倍写像のグラフに注目していこう．
3.1
Z
2kの 2 倍写像
まず Zmの m が 2 のベキ乗の場合から見ていきたい．そのグラフは次のよ うになる： Z2： 0 1 Z4： 0 1 2 3Z8： 0 1 2 3 4 5 7 Z16： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Z32： 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 このようにすべてが「二分木（binary tree）」と呼ばれるグラフになってい る．その理由を解明するのが本節の目標であり，次の命題が基本となる： 命題 3.3 Z2kにおける方程式 2x = a（a∈ Z2k）の根に関し，以下が成り立つ： (1) aが奇数のとき根は存在しない． (2) aが偶数のとき a = 2b とおくと，根は x = b, b + 2k−1である． 証明] (1) Z2kにおいて 2x = a が成り立つ，ということは 2x≡ a (mod 2k) が成り立つことを意味する．これは 2x− a が 2kで割り切れる，ということ であり，a が奇数のときは 2x− a は奇数となるから，偶数 2k で割切れるこ とはあり得ない． (2)まず a = 0 のときは，方程式 2x = 0 は合同式 2x≡ 0 (mod 2k)が成り 立つことを意味する．これは 2x が 2kで割り切れる，ということであるから， x = 0か x = 2k−1のときしか成り立たない．次に方程式 2x = a (3.4) の根があったとしてそれを x0とおくと 2x0= a (3.5) が成り立っている．そこで式 (3.4) から式 (3.5) を引くと 2(x− x0) = 0 となるから，上で見たように x− x0= 0, 2k−1
であり，したがって x = x0, x0+ 2k−1が根である．しかも a = 2b とおくと x0= bと取ることができるから，命題の証明が完成する． □ この命題から，Z2kの 2 倍写像のグラフが上の例の図のようになる理由が解 明できた．
3.2
Z
mの元の位数分布
本節では次の命題を示すのが目標である： 命題 3.4 自然数 m とその約数 d に対し，群 Zmにおいて位数 d の元は φ(d) 個あ る．さらに等式 m =∑d|mφ(d)が成り立つ． 注意．この命題の「φ(d)」は「1 以上 d− 1 以下の整数のうち d と互いに素な ものの個数」を表す関数であり，「オイラー関数」と呼ばれる． いくつかの補題をつないで証明を実行する． 補題 3.5 mの約数 d に対して m = dd′とおくと {x ∈ Zm; dx = 0} = {x ∈ Zm; d′|x} (3.6) 証明] （右辺）⊂（左辺）：x が右辺の元であるとすると d′|x であり，x = d′x′ と表されるから，Zmにおいて dx = d(d′x′) = (dd′)x = mx = 0となる．し たがって x は左辺に属する． （左辺）⊂（右辺）：x が左辺の元であるとすると Zmにおいて dx = 0 が成 り立つから dx は m の倍数であり，dx = my（y∈ Z）と表される．したがっ て dx = dd′yであって d を約分すれば x = d′yとなる．したがって x は右辺 に属する． □補題 3.6 x∈ Zmに対して xの位数が m より小さい⇔ x が m の 1 より大きい約数で割り切れる 証明] 式 (3.6) の左辺の集合を Gd，右辺の集合を Md′とおく． （左）⇒（右）：x の位数を d とおき，m = dd′とおくと，仮定より x∈ Gd であり，したがって等式 (3.6) より x∈ Md′であるから x は d′で割り切れる． しかも d < m であるから d′= m/d > 1であり，（右）が成り立つ． （右）⇒（左）：x が m の 1 より大きい約数 d′で割り切れるとし，m = dd′ とおくと，x∈ Md′であるから，等式 (3.6) より x∈ Gdである．したがって xの位数は d 以下であり，m より小さい． □ 補題 3.6 の同値な命題のそれぞれの否定を取れば次の補題が得られる： 補題 3.7 x∈ Zmに対して xの位数が m⇔ x は m と互いに素 この補題から次の系が得られる： 系 3.8 Zmにおいて，位数が m の元の個数は φ(m) である． さらに補題 3.5 によれば Gd= Md′であったが，この右辺の Md′ について次 の補題が成り立つ： 補題 3.9 写像 f : Zd→ Md′(⊂ Zm))を f (a) = d′a で定義すると，f は群の同型写像である．
証明] 任意の a, b∈ Zdに対して f (a + b) = d′(a + b) = d′a + d′b = f (a) + f (b) であるから f は準同型写像である．さらに定義によって Md′ の元はすべて d′a（0≤ a < d）の形をしているから f は全射である．しかも Md′の元の個 数は m/d′ = dであり，Zdの元の個数も d であるから，f は単射にならざる を得ない．したがって f は同型写像である． □ 命題 3.4 の証明] Zmにおいて位数 d の元全体の集合を Odとすると，Zdの任 意の元の位数は m の約数であるから等式 Zm= ∪ d|m Od (3.7) が成り立つ．また，Odは Gdの部分集合であり，補題 3.5 によれば Gd= Md′ だから Odは Md′の部分集合となる．さらに補題 3.9 によって Md′は Zdと同 型であるから，Odは Zdにおいて位数 d をもつ元の集合と対応し，この後者の 元の個数は系 3.8 によれば φ(d) 個である．したがって Odの元の個数も φ(d) である．よって等式 (3.7) のそれぞれの元の個数を数えれば m =∑d|mφ(d) が成り立つ． □
3.3
Z
m（m：奇数）の 2 倍写像 今後 Zmにおける 2 倍写像を「D」で表すことにする．本節では m が奇数 の場合の Zmの 2 倍写像 D，そしてそのグラフ Gadd2 を考察するのが本節の 目標である．まず次の補題は重要である： 補題 3.10 mが奇数の場合の Zmの 2 倍写像 D は全単射である． 証明] m が奇数だから gcd(2, m) = 1 であり，したがってユークリッドの互除 法により 2x + my = 1 をみたす整数 x, y が存在する．この等式を mod m で考えれば 2x = 1 が Zm において成り立つことになり，これは x が Zmにおける 2 の逆元であること を意味する．したがって写像 E : Zm → Zmを E(a) = x· a で定義すれば D◦ E = E ◦ D = id となり，D が全単射であることが示された． □系 3.11
mが奇数の場合の Zmの 2 倍写像のグラフ Gadd2 は tail を持たない．言
い換えれば，任意の a∈ Zmに対して t(a) = 0 が成り立つ．
証明] a の tail number を t，cycle number を c とすると
Dt(a) = Dt+c(a)
が成り立っている．ここで t > 0 と仮定して矛盾を導こう．この等式から
D(Dt−1(a)) = D(Dt+c−1(a)) (3.8) という等式が導かれるが，ここで a′ = Dt−1(a), a′′ = Dt+c−1(a)とおくと，
a′は a の作る cycle には属していないが，a′′は a の作る cycle に属している． したがって a′ ̸= a′′である．しかし等式 (3.8) は D(a′) = D(a′′)であること を主張しているから，これは D が単射ではないことになり補題 3.10 に反す る．したがって系 3.11 が成り立つことが示された． □ 以下の図からもこの系が成り立つ様子が見て取れる． 次に前節の等式 (3.7) によれば Zm= ∪ d|mOdが成り立つのであった．この右 辺のそれぞれの Odが 2 倍写像 D で不変である，ということをまず示したい： 補題 3.12 mが奇数のとき，m の任意の約数 d に対して，Zmにおける位数 d の元 の集合 Odは 2 倍写像 D で不変である．すなわち D(Od)⊂ Od が成り立つ． 証明] 任意の a∈ Odに対して 2a ∈ Odが成り立つことを示せばよい．まず
d(2a) = 2(da) = 0だから 2a の位数 d′は d の約数である．一方 d′(2a) = 0
であることから，(2d′)a = 0が成り立つことになるが，a の位数は d である
から，2d′は d で割り切れる．しかし d は奇数 m の約数として奇数であるか
ら，d′が d で割り切れる．よって d′= dであることがわかり，2a∈ Odであ
したがって Zmを 2 倍写像 D に関して軌道分解するためには，それぞれの Odの軌道分解を考えればよい． 補題 3.13 mが奇数のとき，m の任意の約数 d に対して，ordd(2) = ℓとする．こ のとき集合 Odを 2 倍写像に関して軌道に分解すると，それぞれの軌道 は cycle であり，その元の個数はすべて ℓ に等しい． 証明] 位数 d の元は Gdに属し，補題 3.5 によれば Gd= Md′であった．さら に補題 3.9 によって Md′は Zdと同型であったから，Zdにおける位数 d の元 の集合において 2 倍写像を考察すればよい．しかも補題 3.7 によってこの集 合は Z×d ={a ∈ Zd; gcd(a, d) = 1} と一致するのであったことを思い出そう． そこで任意の a∈ Z×d をとり，その 2 倍写像に関する軌道 orb(a) を考えよう．
まず系 3.11 によれば t(a) = 0 が成り立つから，a の軌道は一つの cycle に なっている．したがってその cycle number を c とすると Dc(a) = a (3.9) が成り立ち，cycle number の定義により Dc′(a)̸= a (0 < c′< c) (3.10) でなければならない．ここで等式 (3.9) は合同式で表すと 2ca≡ a (mod d) すなわち (2c− 1)a ≡ 0 (mod d) となり，(2c− 1)a が d で割り切れることを意味する．しかし a は d と互いに 素であるから，これは 2c− 1 が d で割り切れることと同値である．したがっ て等式 (3.9) は，合同式 2c≡ 1 (mod d) (3.11) が成り立つことと同値である．同様に条件 (3.10) は 2c′ ̸≡ 1 (mod d) (0 < c′ < c) (3.12) という条件と同値である．すなわち ordd(2) = cである．これで証明が完成 した． □
Z3： 0 1 2 Z5： 0 1 2 3 4 Z7： 0 1 2 4 5 6 Z9：
0 1 2 3 4 6 7 8 Z11： 0 1 2 3 4 5 6 7 8 9 10 Z13： 0 1 2 3 4 5 6 7 8 10 11 12 Z15：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Z17： 0 1 3 4 6 7 8 9 10 11 12 13 14 15 16 Z19：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Z21： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Z23：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Z25： 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 Z27：
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 Z29： 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
3.4
中国剰余定理
表題の「中国剰余定理」とは次の定理を指す： 定理 3.14 2以上の互いに素な自然数 m1, m2が与えられたとき，任意の整数 a1, a2 に対して連立合同式 { x≡ a1 (mod m1) x≡ a2 (mod m2) は mod m1m2 で唯一の解をもつ．証明] m1と m2は互いに素だから，ユークリッドの互除法によって m1u1+ m2u2= 1 をみたす整数 u1, u2が存在する．この両辺を mod m1で考えると m2u2≡ 1 (mod m1) (3.13) となり，同様に両辺を mod m2で考えると m1u1≡ 1 (mod m2) (3.14) となることに注意しよう．そこで x = m2u2a1+ m1u1a2 (3.15) とおくと x = m2u2a1+ m1u1a2 ≡ m2u2a1 (mod m1) ≡ a1 (mod m1) (⇐ (3.13)) が成り立ち，同様に x = m2u2a1+ m1u1a2 ≡ m1u1a2 (mod m2) ≡ a2 (mod m2) (⇐ (3.14)) も成り立つ．したがって式 (3.15) で定義した x は定理の連立合同式を確かに みたしている．ここで写像 ch : Zm1m2 → Zm1× Zm2を ch(x) = (rm1(x), rm2(x)) で定義する．ただし rm(x)は「x を m で割った余り」を意味するものとする． すると前半で証明されたことは写像 ch が全射であることを意味している．と ころが ch の定義域，値域の元の個数は共に等しく m1m2であるから，ch は 単射でもある．したがって定理の x はただ一つ存在することもわかり，証明 が完成した． □ この定理は群論の言葉を用いると，次の形で定式化される：
定理 3.15 2以上の互いに素な自然数の組 m1, m2に対し，写像 ch : Zm1m2 → Zm1× Zm2を ch(x) = (rm1(x), rm2(x)) で定義する．ただし rm(x)は「x を m で割った余り」を意味するものと する．このとき写像 ch は群の同型写像である． 注意．定理 3.14 の証明の中の式 (3.15) が，定理 3.15 の写像 ch の逆写像を与 えていることになる．
3.5
Z
2m（m：奇数）の 2 倍写像
前節の中国剰余定理を応用して，Z2m（m：奇数）における 2 倍写像の振 る舞いを考察しよう． この定理によれば Z2m∼= Z2× Zmが成り立っており，この二つの群を同一 視する．ここで混乱を避けるために今後 Znにおける 2 倍写像を添え字「n」 を付けて Dnで表すことにする．したがって Z2× Zmの任意の元 (t, a) に対 し等式 D2m(t, a) = (D2(t), Dm(a)) (3.16) が成り立っていることに注意しよう．次の命題が本質的である： 命題 3.16 任意の (t, a)∈ Z2× Zmに対し，その 2 倍写像に関する逆像は次の式で 与えられる: D−12m({(t, a)}) = { {(1, Em(a)), (0, Em(a))} t ̸= 0 のとき ϕ t = 1のとき ただし「Em」は補題 3.10 の証明で用いた Dm: Zm→ Zmの逆写像で ある． 証明] Z2においては 0 も 1 も 2 倍すると 0 になるから，式 (3.16) の右辺の 「D2(t)」は実はつねに 0 に等しい．したがって t = 1 のときは D2m−1({(t, a)}) =ϕであるから，命題の等式の下半分が示された．上半分についても D2m−1({(0, a)}) = {(s, b) ∈ Z2m; D2(s) = 0, Dm(b) = a} = {(s, b) ∈ Z2m; s = 0, 1かつ 2b = a} = {(1, Em(a)), (0, Em(a))} というように計算でき，命題の証明が完成する． □ この命題から Z2mの 2 倍写像のグラフの形が完全に決定できる： 命題 3.17 mが奇数のとき，グラフ Gadd 2mは Gaddm の頂点それぞれに，そこに向かう 長さ 1 の tail を付け加えたグラフである． 証明] まず V′ = {(0, a); a ∈ Zm}, E′ = {((0, a), (0, Dm(a)); a∈ Zm} とおくと，これらの作るグラフ G′= (V′, E′)は Gaddm と同型な Gadd2m の部分 グラフである．さらに Vadd 2m \ V′={(1, a); a ∈ Zm} のそれぞれの元に 2 倍写 像を施すと D2m(1, a) = (0, 2a) となって，一回で V′の元になる．これで命題が証明された． □ 以下に 3≤ m ≤ 11 の範囲の奇数 m に対して，Gadd m と Gadd2m をペアにして図 示した．この命題の通りの構造を持っていることが一目瞭然であろう：
Gadd3 ： 0 1 2 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd6 ： (0,0) (1,1) (0,2) (1,0) (0,1) (1,2) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Gadd5 ： 0 1 2 3 4 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd10 ： (0,0) (1,1) (0,2) (1,3) (0,4) (1,0) (0,1) (1,2) ,3) (1,4) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Gadd7 ： 0 1 2 4 5 6 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd 14 ： (0,0) (1,1) (0,2) (1,3) (0 4) (1,5) (0,6) (1,0) 0,1) (1,2) 0,3) (1,4) (0 5) (1,6) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Gadd9 ： 0 1 2 3 4 6 7 8 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd 18 ： (0,0) (1,1) 0,2) (1,3) (0,4) (1,5) (0,6) (1,7) (0,8) (1,0) (0,1) (1,2) (0,3) (1,4) 0,5) (1,6) (0,7) (1,8) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Gadd11 ： 0 1 2 3 4 5 6 7 8 9 10 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd 22 ： (0,0) (1,1) (0,2) (1,3) (0,4) (1,5) (0,6) (1,7) (0,8) (1,9) (0,10) (1,0) (0,1) (1,2) (0,3) (1,4) (0,5) (1,6) (0,7) (1,8) (0,9) (1,10) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
3.6
Z
4m（m：奇数）の 2 倍写像
前節のに引き続き，本節では Z4m（m：奇数）における 2 倍写像の振る舞 いを考察しよう．中国剰余定理によれば Z4m∼= Z4× Zmが成り立っており，この二つの群 を同一視すると，Z4× Zmの任意の元 (t, a) に対し等式 D4m(t, a) = (D4(t), Dm(a)) (3.17) が成り立っていることに注意しよう．さらに前の命題 3.3 が大事な役割を果 たす．その内容を逆像の記号を使って書くと次のように翻訳される： 命題 3.18 Z2kにおける 2 倍写像 D2kの，1 点 a∈ Z2kからなる集合の逆像に関し D−12k({a}) = { ϕ aが奇数のとき {b, b + 2k−1} a が偶数で a = 2b のとき この命題から自然に次の命題が導かれる： 命題 3.19 任意の (t, a)∈ Z4× Zmに対し，その 2 倍写像に関する逆像は次の式で 与えられる: D−14m({(t, a)}) = {(2, Em(a)), (0, Em(a))} t = 0 のとき {(1, Em(a)), (3, Em(a))} t = 2 のとき ϕ t = 1, 3のとき ただし「Em」は補題 3.10 の証明で用いた Dm: Zm→ Zmの逆写像で ある． 証明] 次の補題が成り立つことが理解できれば，この命題は命題 3.18 と補題 3.10からすぐに導かれる．その補題とは次の一般的な法則である： 補題 3.20 写像 f1 : X1 → Y1と写像 f2 : X2 → Y2が与えられているとき，写像 F : X1× X2→ Y1× Y2を F (x1, x2) = (f (x1), f (x2)) ((x1, x2)∈ X1× X2)
で定義する．このとき任意の B1⊂ Y1, B2⊂ Y2に対して F−1(B1× B2) = f1−1(B1)× f2−1(B2) (3.18) が成り立つ． 補題 3.20 の証明] 次のように定義を書き直していけば (x1, x2)∈ F−1(B1× B2) ⇔ F (x1, x2)∈ B1× B2 ⇔ (f(x1), f (x2))∈ B1× B2 ⇔ f(x1)∈ B1かつ f (x2)∈ B2 ⇔ x1∈ f−1 1 (B1)かつ x2∈ f2−1(B2) ⇔ (x1, x2)∈ f1−1(B1)× f2−1(B2) となる．したがって (3.18) の左辺に属するという条件と，右辺に属するとい う条件が同値になり，等式 (3.18) が証明される． □ この補題から直接次の系が出る： 系 3.21 任意の (t, a)∈ Z4× Zmに対して D4m−1({(t, a)}) = D4−1({t}) × Dm−1({a}) (3.19) が成り立つ． そして Dmは補題 3.10 によれば全単射であってその逆写像が Emであった から Dm−1({a}) = {Em(a)} であり，D−14 ({t}) は命題 3.18 で与えられていたから，それらをこの系と合 わせれば命題 3.19 が得られる． □ この命題から Z4mの 2 倍写像のグラフの形を表現するために次の定義が役に 立つ：
定義 3.22 有向グラフ G とその一つの頂点 v に対し，グラフ Gadd 2k の v への「接着 （attaching）」とは，次のように頂点集合 V と辺集合 E を定義したグラ フである： V = V (G)∪ (V (Gadd2k )\ {0})
E = E(G)∪ (E(Gadd2k )\ {(2k−1, 0), (0, 0)}) ∪ {(2k−1, v)}
そしてこうしてできるグラフを「Gadd 2k ∨vG」と表す．さらに G のすべ ての頂点に Gadd 2k を接着したグラフを G add 2k × G と表し，「G add 2k と G の直 積」という． 命題 3.23 mが奇数のとき，グラフ Gadd 4m はグラフの直積 Gadd4 ×Gaddm と同型である． 証明] まず V′ = {(0, a); a ∈ Zm}, E′ = {((0, a), (0, Dm(a)); a∈ Zm} とおくと，これらの作るグラフ G′= (V′, E′)は Gadd m と同型な Gadd4m の部分 グラフである．さらに V′のそれぞれの元 (0, a) (a∈ Zm)に対し V4madd\ V′ の部分集合{(2, a); a ∈ Zm} のそれぞれの元に 2 倍写像を施すと D4m(2, a) = (0, 2a) となって，一回で V′の元になる．これで命題が証明された． □ 以下に 3≤ m ≤ 11 の範囲の奇数 m に対して，Gadd m と Gadd4m をペアにして図 示した．この命題の通りの構造を持っていることが一目瞭然であろう：
Gadd3 ： 0 1 2 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd 12 ： ( ,0) (1,1) (2,2) (3,0) (0,1) (1,2) (2,0) (3,1) (0,2) (1,0) (2,1) (3,2) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Gadd5 ： 0 1 2 3 4 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd20 ： ,0) (1,1) (2,2) (3,3) (0 (1,0) (2,1) (3,2) ,3) (1,4) (2,0) (3 1) (0,2) (1,3) (2 4) (3,0) (0,1) (1,2) (2,3) (3,4) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Gadd7 ： 0 1 2 4 5 6 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd28 ： (0,0) (1,1) (2,2) (3,3) (0,4) (1,5) (2,6) (3,0) (0,1) (1,2) (2,3) (3,4) (0,5) (1,6) (2,0) (3,1) (0,2) (1,3) (2,4) (3,5) (0,6) (1,0) (2,1) (3,2) (0,3) (1,4) (2,5) (3,6) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Gadd9 ： 0 1 2 3 4 6 7 8 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd36 ： (0,0) (1,1) (2,2) (3,3) (0,4) (1,5) (2,6) (3,7) (0,8) (1,0) (3,2) (0,3) (1,4) (2,5) (3,6) (0,7) (1,8) (2,0) (3,1) (0,2) (1,3) (2,4) (3,5) (0,6) (1,7) (2,8) (3,0) (0,1) (1,2) (2,3) (3,4) (0,5) (1,6) (2,7) (3,8) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
Gadd11 ： 0 1 2 3 4 5 6 7 8 9 10 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー Gadd44 ： (0,0) (1,1) (2,2) (3,3) (0,4) (1,5) (2,6) (3,7) (0,8) (1 9) (2,10) (3,0) (0,1) (1,2) (2,3) (3,4) (0,5) (1,6) (2,7) (3,8) (0,9) (1 10) (2,0) (3,1) (0,2) (1,3) (2,4) (3 5) (0,6) (1,7) 2,8) (3,9) (0,10) (1,0) (2,1) (3,2) (0,3) (1,4) (2,5) (3,6) (0,7) (1,8) (2,9) (3,10)
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
