第 1 章 初等整数論 1.1 1.1.1 互除法と不定一次方程式 ユークリッドの互除法 ユークリッドの互除法 : a、b ∈ N に対し、 (ステップ 1) a の b による割り算の余りを r1 とする。 (ステップ 2) b の r1 による割り算の余りを r2 とする。 (ステップ 3) r1 の r2 による割り算の余りを r3 とする。 .. . (ステップ k ) rk−2 の rk−1 による割り算の余りを rk とする。 .. . というような操作を繰り返す。このとき、 (1) ある有限の 自然数 K で、余り rK は必ず 0 になる。 (2) rK = 0 とすると、 rK−1 = gcd (a, b)。すなわち、rK−1 が、a と b の最大公約数である。 ab (3) が最小公倍数である。 gcd (a, b) がいえる。 例 : 858 と 3927 の最大公約数を求めてみよう。 3927 = 858 × 4 + 495 858 = 495 × 1 + 363 495 = 363 × 1 + 132 363 = 132 × 2 + 99 132 = 99 × 33 99 = 33 × 3 + 0 となるから、最大公約数は 33 となる。実際、それぞれを素因数分解してみると、 3927 = 3 × 7 × 11 × 17, 858 = 2 × 3 × 11 × 13 であり、gcd (3297, 858) = 33。また、lcm (3927, 858) = 3297 × 858/33 = 102102 であることもわかる。(例終) 問題 1.1. 次の自然数 a、b の最大公約数と最小公倍数を求めよ。 (1) a = 598, b = 858, (2) a = 5296, b = 7613, 2 (3) a = 572, b = 323 1.1.2 不定1次方程式 不定一次方程式の解法 : 不定一次方程式 ax + by = c (1.1) の解は、次のようになる、 (a) c が d = gcd (a, b) で割り切れない場合は解は存在しない。 (b) c が d で割り切れる場合、 az + bw = d (1.2) の解のひとつをユークリッドの互除法を用いて求める。それらを z = z0 、w = w0 とし、a′ = a/d、b′ = b/d、c′ = c/d とすると、(1.1) の解の全体は、 x = c′ z0 + b′ k, y = c′ w0 − a′ k (k : 整数) で表わせる。 例: 一次不定方程式 341x − 242y = 22 (1.3) の解全体を求める。 341 = 242 × 1 + 99 242 = 99 × 2 + 44 99 = 44 × 2 + 11 44 = 11 × 4 + 0 だから、gcd (341, −242) = gcd (341, 242) = 11 なので、この一次不定方程式は解を持つ。このとき、上の計算 より、 11 = 99 − 44 × 2 = 99 − (242 − 99 × 2) × 2 = 99 × 5 − 242 × 2 = (341 − 242) × 5 − 242 × 2 = 341 × 5 − 242 × 7 なので、341z − 242w = 11 の解のひとつは z = 5、w = 7。よって、 x= 22 −242 ×5+ k = 10 − 22k, 11 11 y= 22 341 ×7− k = 14 − 31k, 11 11 (k : 整数) が、(1.3) の解の全体。(例終) 例: 一次不定方程式 34x − 187y = 13 を解く。ユークリッドの互除法を用いると、 34 = 187 × 0 + 34 187 = 34 × 5 + 17 34 = 17 × 2 + 0 3 (1.4) よって、gcd (34, −187) = gcd (34, 187) = 17。このとき、13 は 17 で割り切れないから、(1.4) の解は存在しない。 (例終) 問題 1.2. 次の不定1次方程式の解の全体を求めよ。解が存在しないときは、「存在しない」と答えること。 (1) 57x − 209y = 171, (2) 113x − 12y = 4, (3) 63x − 153y = 14, 問題 1.3. 1枚 52 円の葉書と1枚 82 円の切手を何枚かずつ購入したら、合計が 1890 円となった。葉書と切手 を何枚ずつ買ったか。(ヒント:不定一次方程式の解のうち、両方とも正になるものを選ぶ) 1.2 合同式 自然数 n と整数 a、b に対し、差 a − b が n の倍数であるとき、a と b は、n を法として互いに合同であるといい、 a ≡ b (mod n) と書く。すなわち、 def. a ≡ b (mod n) 1.2.1 ⇐⇒ a − b ∈ nZ 合同式の性質 (i) 自然数 n と、整数 a、a′ 、b、b′ に対して、a ≡ a′ (mod n)、b ≡ b′ (mod n) ならば、 a + b ≡ a′ + b′ (mod n), a − b ≡ a′ − b′ (mod n), ab ≡ a′ b′ (mod n). (ii) 自然数 n と、整数 a、a′ に対して、a ≡ a′ (mod n) ならば、任意の自然数 m に対して、 am ≡ a′ m (mod n) 問題 1.4. (1) (i) 1 の位が a0 、10 の位が a1 、100 の位が a2 、· · · 、10n の位が an (0 ≤ ak ≤ 9) である自然数 a = a0 + a1 × 10 + a2 × 103 + · · · + an × 10n に対し、「a が 9 の倍数 ⇔ a0 + a1 + · · · + an が 9 の倍数」であることを示せ。 (ヒント:k ∈ N に対し、10k − 1 = (10 − 1)(10k−1 + 10k−2 + · · · + 1) = 9(10k−1 + 10k−2 + · · · + 1) より、これ は 9 の倍数になる) (ii) 777777、198531、222222222、90876 のうち、9 の倍数を選べ。 (2) 11 の倍数の見つけ方を考えよ。 問題 1.5. (1) 100100 を 9 で割った余りはいくつか。 (2) 501000 を 7 で割った余りはいくつか。 4 1.2.2 1次合同式 一次合同式の解法 : ax ≡ b (mod n) (1.5) は次のように解く。 (1) ユークリッドの互除法で、d = gcd (a, n) を求める。 (2) b が d で割り切れない場合は、解は存在しない。 (3) b が d で割り切れる場合は、b′ = b/d、n′ = n/d とおく。そして、 (i) 一次合同式 aw ≡ d (mod n) (1.6) を満たす w0 をユークリッドの互除法から逆算して求める。 (ii) 解の全体は、 x = b′ w0 + n′ k (k : 整数) で与えられる。 (iii) n を法としての解の個数は d。 例: 一次合同式 85x ≡ 34 (mod 204) (1.7) を解く。ユークリッドの互除法を用いると、 85 = 204 × 0 + 85 204 = 85 × 2 + 34 85 = 34 × 2 + 17 34 = 17 × 2 + 0 なので、gcd (85, 204) = 17。34 は 17 で割り切れるので、この1次合同式は解をもつ。ここで、一次合同式 85w ≡ 17 (mod 204) (1.8) を解く。ユークリッドの互除法の計算を逆算すると、 17 = 85 − 2 × 34 = 85 − 2 × (204 − 2 × 85) = 85 × 5 − 204 × 2 だから、 85 × 5 ≡ 17 (mod 204) である。すなわち、w = 5 は (1.8) のひとつの解。となる。よって、(1.7) の解の全体は、 x= 34 204 ×5+ k = 10 + 12k 17 17 となり、204 を法として 解の個数は 17 個ある。(例終) 例 : 一次合同式 12x ≡ 5 (mod 6) 5 (k : 整数) について、(12, 6) = 6 で、5 は 6 の倍数ではないので、解は存在しない。(例終) 問題 1.6. 次の一次合同式を解け。 (1) 39x ≡ 27 (mod 63) (2) 123x ≡ 7 (mod 42) (3) 22x ≡ 9 (mod 13) 問題 1.7. 研究室にいた学生1人に対し 7 個ずつお土産のお菓子を配ったら、24 個入りの箱に 5 個余った。配属 になっている学生は 15 人だが、そのうちの何人が部屋にいたことになるか。 1.3 1.3.1 合同式 (2) 連立1次合同式 連立一次合同式の解法 : 連立一次合同式 x ≡ a1 x ≡ a2 x ≡ ak (mod n1 ) (mod n2 ) .. . (mod nk ) は次のように解くことができる。 (1) N = n1 · · · nk とおき、各 i について Ni = N/ni とおく。 (2) 各 i について、一次合同式 Ni ui ≡ 1 (mod ni ) を満たす ui をひとつ求める。 (3) (1.9) の解は x0 = k ∑ N i u i ai i=1 で与えられ、N を法として x = x0 ただひとつである。 例 : 連立一次合同式 x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7) を解く。上の解法における N にあたる数は 3 · 5 · 7 = 105、N1 にあたる数は 105/3 = 35、N2 にあたる数は 105/5 = 21、N3 にあたる数は 105/7 = 15 であるから、3つの合同式 35u1 ≡ 1 (mod 3) 21u2 ≡ 1 (mod 5) 15u3 ≡ 1 (mod 7) を考えればよい。各々の合同式の解のひとつとして、 u1 = 2, u2 = 1 6 u3 = 1 (1.9) が取れるから、考えている連立一次合同式の解は 35 · 2 · 2 + 21 · 1 · 3 + 15 · 1 · 2 = 140 + 63 + 30 = 233 ≡ 23 (mod 105) となるので、解は x ≡ 23 (mod 105) のただひとつになる。(例終) 問題 1.8. 次の連立一次合同式を解け。 (1) 1.3.2 x≡1 x≡4 x≡5 (mod 2) (mod 7) (mod 9) (2) x ≡ 3 (mod 4) x ≡ 2 (mod 5) x ≡ 6 (mod 11) 剰余類 def. 問題 1.9. p を素数とし、a ∈ Z に対し、C(a) := {x ∈ Z | x ≡ a (mod p)} と定める。a,b ∈ Z に対し、 def. C(a)C(b) := C(ab) とする。このとき、次の問いに答えよ。 (1) C(a)2 = C(1) となる 1 ≤ a ≤ p − 1 は、a = 1 または a = p − 1 のいずれかであることを示せ。 (2) (p − 1)! ≡ −1 (mod p) を示せ。 (ヒント:(1) より、C(2)、· · · 、C(p − 2) は、それぞれ、互いにかけたら C(1) になる相異なる要素をひとつずつもつ。例えば、p = 7 のとき、C(2)C(4) = C(1)、C(3)C(5) = C(1) である。こ れを用いて、C(1)C(2) · · · C(p − 1) を考える。) 1.4 オイラーの関数 n ∈ N とする。{ 1, 2, · · · , n } のうち、n と互いに素になる数の個数を φ(n) で表す。この φ を オイラーの関数とい う。n の素因数分解を n= k ∏ pai i i=1 とすると、 φ(n) = n ) k ( ∏ 1 1− pi i=1 となる(オイラーの公式)。 問題 1.10. p を素数、e ∈ N とするとき、φ(pe ) はいくつか。 問題 1.11. (1) 60 = 22 · 3 · 5 である。 1 から 60 までの数のうち、 (i) 2 の倍数の個数はいくつか。 (ii) 「2 の倍数かまたは 3 の倍数である」数の個数はいくつか。 (iii) φ(60) はいくつか。 (2) (1) の考え方を用いて、オイラーの公式の証明を考えよ。 問題 1.12. 次の n ∈ N に対し、オイラーの公式を用いて φ(n) を求めよ。 (1) n = 120, (2) n = 39, 7 (3) n = 162 1.5 オイラーの定理 (オイラーの定理)自然数 n、整数 a に対して、 gcd(a, n) = 1 =⇒ aφ(n) ≡ 1 (mod n) がいえる。ただし、φ(n) はオイラーの関数 問題 1.13. n ∈ N、m = φ(n)、とし、n と互いに素な 0 以上 n 未満の全ての自然数の集合を {x1 , x2 , · · · , xm } とする。また、a を n と互いに素な数とする。 (1) 任意の i ∈ {1, 2, · · · , m} に対し、axi ≡ xj (mod n) となる j ∈ {1, · · · , m} が存在することを示せ。 (2) aφ(n) ≡ 1 (mod n) を示せ。 問題 1,14. n = 8 のとき、a = 1、3、5、7、9、11 で、aφ(8) ≡ 1 (mod 8) が成り立つことを確認せよ。 問題 1.15. 19300 を 93 で割った余りを求めよ。 問題 1.16. 3x ≡ 5 (mod 11) を満たす x を、オイラーの定理を用いて求めよ。 8
© Copyright 2024