第1章初等整数論

第 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
不定１次方程式
不定一次方程式の解法 : 不定一次方程式
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)
57x − 209y = 171,
(2)
113x − 12y = 4,
(3)
63x − 153y = 14,
問題 1.3. １枚 52 円の葉書と１枚 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
１次合同式
一次合同式の解法 :
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 で割り切れるので、この１次合同式は解をもつ。ここで、一次合同式
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. 研究室にいた学生１人に対し 7 個ずつお土産のお菓子を配ったら、24 個入りの箱に 5 個余った。配属
になっている学生は 15 人だが、そのうちの何人が部屋にいたことになるか。
1.3
1.3.1
合同式 (2)
連立１次合同式
連立一次合同式の解法 : 連立一次合同式

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 であるから、３つの合同式
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

Download Report