自然数の集合

1 整数

1.1 整数の基本的性質

1. 記号と用語

• N={1,2,3,· · · } : 自然数の集合．

• Z={· · · ,−2,−1,0,1,2,· · · } : 整数の集合．

±,×,結合法則，分配法則 を付随させ整数環とよぶ．

• Q={p/q :p, q ∈Z}: 有理数の集合， R: 実数の集合， C: 複素数の集合，

÷も付随させて有理数体，実数体，複素数体とよぶ．

2. 定理 1.1 (除法定理):

∀n 非負整数，∀m 自然数 ⇒ ∃1q,∃1r ∈Z s.t. n=mq+r および 0≤r < m．

q を n を m で割った商，r を剰余という．

3. 除法定理の拡張 :

∀n∈Z,∀m(6= 0)∈Z ⇒ ∃1q,∃1r∈Z s.t. n =mq+r および0≤r <|m|． 4. 演習 :

(1) （d 進数展開）n を0以上整数，d を2以上の自然数とするとき n=c₀+c₁d+· · ·+c_kd^k (0≤c_i < d) の形に一意的に表せることができることを示せ．

(2) （d 進少数展開）d を2以上の整数，x を 0< x <1をみたす実数とするとき，

x= a1

d + a2

d² +· · ·+an

dⁿ +α_n  (0≤a_i < d, 0≤α_n< 1 dⁿ) の形に一意的に表されることを示せ．

5. 用語と記号

• m は n を割り切る ⇐⇒ m|n ⇐⇒ n は m で割り切れる このときm は n の約数，n は m の倍数という．

• n, mの公約数，公倍数．

最大公約数 (m, n)，最小公倍数=mn/(m.n)．

(n, m) = 1 のとき n と m は互いに素という．

6. 定理 1.2 :

n=mq+r (n, m, q, r∈Z− {0}) とする．

n と m の公約数は m と r の公約数である，また，逆もなりたつ．

とくに (n, m) = (m, r)．

7. 演習 : a₀ =a₁ = 1, a_n+2 =a_n+1+a_n で定まるフィボナッチ数列の隣り合う項は互 いに素，すなわち任意の n について (a_n, a_n+1) = 1 であることを示せ．

1.2 ユークリッドの互除法

1. ユークリッドの互除法 :

定理1.2 を応用した二つの整数の最大公約数を求めるアルゴリズム．

2. 例 :

(6188,4709) = (4709,1479) 6188 = 4709×1 + 1479

= (1479,272) 4709 = 1479×3 + 272

= (272,119) 1479 = 272×5 + 119

= (119,34) 272 = 119×2 + 34

= (34,17) 119 = 34×3 + 17 34 = 17×2 + 0

3. 演習 : 三つの自然数a, b, c の最大公約数を(a, b, c) で表す．ユークリッドの互除法 を発展させて，与えられた a, b, c から (a, b, c) を求めるアルゴリズムを作り，それ を用いて (273,468,182) を計算せよ．

4. 定理 1.3（一次不定方程式）: a, b∈Z− {0} とするとき，

ax+by=k が整数解をもつ ⇔ (a, b)|k 5. 例 : 153x+ 340y= 85 の一般解を求める．

153x+ 340y= 153x+ (153×2 + 34)y= 34y+ 153(x+ 2y) (z =x+ 2yとおく) 34y+ 153z = 34y+ (34×4 + 17)z = 17z+ 34(y+ 4z) (w=y+ 4zとおく)

17z+ 34w= 17z+ (17×2 + 0)w= 17(z+ 2w) となる．あとは

17(z+ 2w) = 85, w=y+ 4z, z =x+ 2y

を x, y について解けばよい．，最後の変数w を自由変数と思って z を消去すれば x= 45−20w, y= 9w−20

が求める一般解である．

6. 補題 1.4 :

a, b, c を自然数，(a, b) = 1 とする．ことのき a|bcならa|cである．

7. 証明 : 定理1.3 より ax+by = 1 は整数解をもつ．両辺を c 倍して acx+bcy =c を得るが，a|bc よりbc=ad となる dが存在するので左辺は a で括れる．したがっ て a|c．

8. 演習 :

(1) 62x+ 103y= 5 を解け．

(2) a₁, a₂,· · · , a_n を0でない整数とする．一次不定方程式 a₁x₁+a₂x₂+· · ·+a_nxⁿ=k

が整数解をもつための必要十分条件は(a₁, a₂,· · · , a_n)|k であることを証明せ よ．ただし a₁, a₂,· · · , a_n) は a₁, a₂,· · · , a_n の最大公約数．

1.3 素因数分解

1. 定義 : 素数とは，約数が1 と自分自身しかない 2 以上の自然数のこと．

合成数とは，素数ではない 2以上の自然数のこと．

2. 補題 1.5 :

p を素数とするとき，p|mnならば p|m または p|n である．

3. 証明 : p6 |m とすると，(p, m) = 1 で，補題 1.4 より分かる．

4. 定理 1.6 (素因数分解の一意性) :

2 以上の自然数は素数の積として順序を除いて一意的に表せる．

5. 一意的な表示 : n=p^e₁¹p^e₂²· · ·p^e_k^k

ただし2≤p₁ < p₂ <· · ·< p_k は素数，e₁, e₂,· · · , e_k ≥1 6. 演習 : n が上のように素因数分解されているとする．

(1) n の異なる約数の個数は(e₁+ 1)(e₂+ 1)· · ·(e_k+ 1) であることを示せ．

(2) n の異なる約数の全体の和は p^e₁¹⁺¹−1

p₁−1 · p^e₂²⁺¹−1

p₂−1 · · · · · p^e_k^k+1−1 p_k−1 となることを示せ．

7. 定理 1.7:

素数は無限個ある．

1.4 合同式

1. 定義 :

• a と b は m を法として合同 ⇐⇒ m|(a−b) 合同という関係は同値関係．

• m を法として合同な a, bを a≡b mod m で表し，合同式とよぶ．

2. 定理 1.8（合同式の和と積）:

a≡a⁰ mod m, b≡b⁰ modm のとき (1) a±b≡a⁰±b⁰ mod m

(2) ab≡a⁰b⁰ mod m

3. 証明 : いずれもルーティン！

4. 演習 :

(1) （公約数による商）自然数 d が a, b, m の公約数であるとき，a ≡b mod m となる必要十分条件は a/d≡b/d mod m/d であることを示せ．

(2) （法の簡略化）a≡b mod mn ならば a≡b mod m かつ a≡b modn となることを示せ．また，(m, n) = 1 なら逆が成り立つことを示せ．

(3) 整数a, b, c が a²+b² =c² をみたすとき，abc≡0 mod 60 を示せ．

5. 定理 1.9 :

(1) pを素数とすると，ab≡0 mod p =⇒ a≡0 mod p または b ≡0 mod p (2) （合同式の割り算）(c, m) = 1 のとき，ac≡bc mod m =⇒ a≡b mod m 6. 証明 : (1) は補題1.5 の言い換え．

(2) は bc を左辺に移し，a−b と cの素因数分解を考えればよい．

7. 定理 1.10 :

ax≡b mod m は (a, m)|b のとき解をもつ．

とくに (a, m) = 1 のときは常に解がある．

8. 証明 : ax≡b modm の解を求めるという問題は，ax−b =my をみたす整数x, y を求める，すなわち不定方程式ax−my =b の整数解を求めるという問題と同じな ので，定理 1.3 よりただちに分かる．

9. 例 : 42x≡24 mod 51を解く．

まず(42,24,51) = 3 より，全項で商をとると 14x≡8 mod 17 そこで両辺から 17x≡17 mod 17 を引くと

3x≡9 mod 17 さらに (3,17) = 1 だから，両辺を3で割って

x≡3 mod 17 10. 演習 : 次の合同式を解け．

(1) 7x≡2 mod 11 (2) 63x≡98 mod 161

11. 定理 1.11 (中国の剰余定理) :

m₁,· · · , m_k ∈N で, ∀i6=j について (m_i, m_j) = 1 とする．

a₁,· · · , a_k ∈Zに対し，連立合同式

x≡a_i modm_i i= 1,2,· · · , k は解をもち，解は m₁m₂· · ·m_k を法として合同．

12. 証明 : M =m1m2· · ·mk, Mj =M/mj とおき，Mjy≡aj mod mj の解 dj を使っ て x =M₁d₁+M₂d₂ +· · ·+M_kd_k とおけば，これは連立合同式の解であることが 分かる．

一方，他の解との差は M を法として合同であることも，直接合同式の計算で確か められる．

13. 例 : 1以上 500 以下の整数で，3で割ると1余り，7で割ると5余り，11で割ると2 余るようなものをすべて列挙する．

求める整数をx として条件を書き下すと，

x≡1 mod 3, x≡5 mod 7, x≡2 mod 11

となる．中国の剰余定理の証明にしたがいう未知数 y₁, y₂, y₃ に関する合同式は (11×7)y₁ ≡1 mod 3, (11×3)y₂ ≡5 mod 7, (7×3)y₃ ≡2 mod 11 が得られ，それぞれの解は

y₁ ≡2 mod 3, y₂ ≡1 mod 7, y₃ ≡9 mod 11 となる．そこで

x= 77×2 + 33×1 + 21×9 = 376 mod 231 が一般解となる．うち1以上500以下の数は145と376の二つ．

14. 定理 1.12 (フェルマーの小定理) : p を素数とすると, ∀a∈Z に対し

a^p ≡a modp がなりたつ．

15. 証明 : a≡0 mod p のときは容易．

a6≡0 mod p のとき，a,2a,· · · ,(p−1)a は pを法として互いに異る．それらをす べてかけ合わせれば，1·2· · ·(p−1)≡1·2· · ·(p−1)a^p−1．

16. 素数判定への応用 : フェルマーの小定理の対偶，すなわち，

a^q−1 6≡1 modq ⇒ qは素数ではない

は，万能ではないが，ある数が合成数であることの効率の良い判定に使える．

例 : n = 899, a = 2 とすると2⁸⁹⁸ = 2^21+27+28+29 ≡ 4·721·219·312 ≡ 845 6≡ 1 mod 899．実際899 = 29·31より，899 は素数ではない．

演習 : 判定できない例を構成せよ．

1.5 乗法群（群論への導入）

1. Z, Q, R, C の加法が持つ性質．

• 結合法則：(a+b) +c=a+ (b+c)．

• 0の役割：a+ 0 =a = 0 +a．

• 逆元の存在：a+ (−a) = 0 = (−a) +a．

2. A=Z,Q, R, C に対し A− {0} の乗法が持つ性質．

• 結合法則：(ab)c=a(bc)．

• 1の役割：a1 = a= 1a．

• 逆元の存在：aa⁻¹ = 1 =a⁻¹a，ただし Z− {0} の場合を除く．

3. 自然数 n≥1 を指定し，集合 Zに n を法とする合同という関係の同値類の集合を Z/nZで表す．Z/nZ={[0], [1], · · ·,[n−1]}だが，混乱が生じない場合は同値類の 記号を省略してZ/nZ={0, 1, · · · , n−1} と表す場合もある．

4. Z 上の加法は Z/nZ 上の「加法」を誘導する．

説明：

• 加法とよぶ演算の定義とwell-definedness．

• 三つの性質の確認．

5. Z 上の乗法は Z/nZ 上の「乗法」を誘導する．

説明：

• 乗法とよぶ演算の定義とwell-definedness．

• 二つの性質の確認．

• Z/nZ− {0} の元が逆元を持つための条件？ 

6. (Z/nZ)^×={[a]∈Z/nZ; (a, n) = 1} をZ/nZ の乗法群とよぶ．

説明：

• 乗法で閉じていることの確認．

• 逆元の存在を確認．

7. 例：n = 5,12 のとき積の表を作る．

8. p を素数とすると，(Z/pZ)^×=Z/pZ− {0}．

9. (Z/pZ)^× ={a^k; k = 0, 1, · · · , p−1} をみたす a∈(Z/pZ)^× が存在する．