参考資料2

代数学入門参考資料 2
2015 年度後期
工学部・未来科学部 1 年
担当: 原隆 (未来科学部数学系列・助教)
§ 約数と倍数 (続)
■ユークリッドの互除法 (復習)
定理 (互除法の原理)
m, n, q, r を整数とし、m ̸= 0 とする。等式 n = m q + r が成り立つ
ならば
g.c.d.(n, m) = g.c.d.(m, r)
が成り立つ。
babababababababababababababababababab
注:
1. この方法に基づく最大公約数の求め方は、ユークリッドの『原論』
第 7 巻命題 1, 2, 3 に記されていることから「ユークリッドの互
除法」と呼ばれている。
2. この定理の証明自体はさほど難しくはないので講義で扱います。
ユークリッド
3. テキスト『数の不思議』の 6–19 ページでは、互除法を「タイル張りの問題」
「分数の
約分を用いた考え方」など、様々な角度から考察しているので良く読んでおくこと!!
とにかく「互除法の考え方」に慣れることが肝心。
§ 一次不定方程式
■一次不定方程式の解の構造
定義 (一次不定方程式) a, b, d を整数とする。未知数 x, y に関する一次方程式 ax + by = c
を (二元) 一次不定方程式 indeterminate equation of degree one と呼ぶ。
以降では、一次不定方程式の整数解について考察する。
注:
− このような単純な方程式でも、考える対象を整数解に制限すると、整数解が存在しなかっ
たり無数に存在したりと極端な振る舞いが観察され、実数解を求める問題とは全く異なった面
白さが味わえる。
− 整数係数の (不定) 方程式の整数解 (または有理数解) を求める問題は、
アレクサンドリアのディオファントスによる著書『算術 (アリスメー
ティカ)』において系統的に研究された。したがって、不定方程式の整
数解 (有理数解) を求める問題のことを現在ではディオファントス問題
Diophantine problems と呼んでいる。ディオファントス問題は現在で
も活発に研究が進められている整数論の一分野である。
アレクサンドリアの
ディオファントス
babababababababababababababababababab
命題 (一次不定方程式の解の構造)
一次不定方程式 ax + by = d
(x0 , y0 ) を持つならば、(∗) のすべての整数解は
(x, y) = (x0 + b′ k, y0 − a′ k)
· · · (∗) が整数解
(k は任意の整数)
で与えられる。但し a′ , b′ は a = g.c.d.(a, b) × a′ , b = g.c.d.(a, b) × b′ を満たす数。
注: − 上の命題から、特に一次不定方程式が解を 1 つ持てば無限個の整数解が存在することが分か
ります。
− 上の命題を丸暗記するのではなく、解の導き出し方 (証明の手順) も含めて覚えるように心が
けること!!
babababababababababababababababababab
命題 (一次不定方程式が整数解を持つための必要条件)
一次不定方程式 ax + by = d
· · · (∗) に対し、a と b の最大公約数 d0 が d の約数とな
ることは、(∗) が整数解を持つための必要条件である。
つまり『d0 が d の約数となっていなければ (∗) の整数解は存在しない (!)』ということです。次回
の講義では、『d0 が d の約数となること』が実は (∗) が整数解を持つための必要十分条件となっ
ていることを、ユークリッドの互除法を用いて証明します。
■演習問題問題 2-1. (不定方程式の解の構造)
以下の各一次不定方程式に対して、与えられた整数組 (x0 , y0 ) が特殊解となっていることを確認し
なさい。また、すべての整数解を求めなさい。
(1) 3x + 5y = 1
(x0 , y0 ) = (−3, 2)
(2)
4x − 3y = 2
(x0 , y0 ) = (2, 2)
(3) 7x − 11y = 5
(x0 , y0 ) = (7, 4)
(4)
6x + 3y = −12
(x0 , y0 ) = (−2, 0)
(x0 , y0 ) = (2, −2)
(6) 12x − 18y = 24
(5)
8x + 10y = −4
(x0 , y0 ) = (5, 2)
【演習問題解答】
問題 2-1.
(1) 3 · (−3) + 5 · 2 = −9 + 10 = 1 より (x0 , y0 ) = (−3, 2) は特殊解。
3x + 5y = 1 および 3 · (−3) + 5 · 2 = 1 の辺々を引き算して
3(x + 3) + 5(y − 2) = 0
∴
3(x + 3) = −5(y − 2)
3 と 5 は互いに素なので、x + 3 は 5 の倍数であり、y − 2 は 3 の倍数となる。したがって
x + 3 = 5k とおくと、
−5
(y − 2) = 3(x + 3) = 3 · 5
k
∴
y = 2 − 3k.
したがって 3x + 5y = 1 の整数解は (x, y) = (−3 + 5k, 2 − 3k) (k は任意の整数)。
(2) 4 · 2 − 3 · 2 = 8 − 6 = 2 より (x0 , y0 ) = (2, 2) は特殊解。
4x − 3y = 2 および 4 · 2 − 3 · 2 = 2 の辺々を引き算して
4(x − 2) − 3(y − 2) = 0
∴
4(x − 2) = 3(y − 2)
4 と 3 は互いに素なので、x − 2 は 3 の倍数であり、y − 2 は 4 の倍数となる。したがって
x − 2 = 3k とおくと、
3
(y − 2) = 4(x − 3) = 4 · 3
k
∴
y = 2 + 4k.
したがって 4x − 3y = 2 の整数解は (x, y) = (2 + 3k, 2 + 4k) (k は任意の整数)。
(3) 7 · 7 − 11 · 4 = 49 − 44 = 5 より (x0 , y0 ) = (7, 4) は特殊解。
7x − 11y = 5 および 7 · 7 − 11 · 4 = 5 の辺々を引き算して
7(x − 7) − 11(y − 4) = 0
∴
7(x − 7) = 11(y − 4)
7 と 11 は互いに素なので、x − 7 は 11 の倍数であり、y − 4 は 7 の倍数となる。したがって
x − 7 = 11k とおくと、
− 4) = 7(x − 7) = 7 · 11(y
1
1k
∴
y = 4 + 7k.
したがって 7x − 11y = 5 の整数解は (x, y) = (7 + 11k, 4 + 7k) (k は任意の整数)。
(4) 6 · (−2) + 3 · 0 = −12 より (x0 , y0 ) = (−2, 0) は特殊解。
6x + 3y = −12 および 6 · (−2) + 3 · 0 = −12 の辺々を引き算して
6(x + 2) + 3y = 0
∴
2
1
6(x
+
2)
=
−
3y
2 と 1 は互いに素なので、x + 2 は 1 の倍数であり、y は 2 の倍数となる。したがって
x + 2 = k とおくと、
−y = 2(x + 2) = 2k
∴
y = −2k.
したがって 6x + 3y = −12 の整数解は (x, y) = (−2 + k, −2k) (k は任意の整数)。
(5) 8 · 2 + 10 · (−2) = 16 − 20 = −4 より (x0 , y0 ) = (2, −2) は特殊解。
8x + 10y = −4 および 8 · 2 + 10 · (−2) = −4 の辺々を引き算して
8(x − 2) + 10(y + 2) = 0
∴
4
5
> + 2)
10(y
8(x − 2) = −
4 と 5 は互いに素なので、x − 2 は 5 の倍数であり、y + 2 は 4 の倍数となる。したがって
x − 2 = 5k とおくと、
−5
(y + 2) = 4(x − 2) = 4 · 5
k
∴
y = −2 − 4k.
したがって 8x + 10y = −4 の整数解は (x, y) = (2 + 5k, −2 − 4k) (k は任意の整数)。
(6) 12 · 5 − 18 · 2 = 60 − 36 = 24 より (x0 , y0 ) = (5, 2) は特殊解。
12x − 18y = 24 および 12 · 5 − 18 · 2 = 24 の辺々を引き算して
12(x − 5) − 18(y − 2) = 0
∴
2
3
> − 5) = > − 2)
12(x
18(y
2 と 3 は互いに素なので、x − 5 は 3 の倍数であり、y − 2 は 2 の倍数となる。したがって
x − 5 = 3k とおくと、
3(y − 2) = 2(x − 5) = 2 · 3k
∴
y = 2 + 2k.
したがって 12x − 18y = 24 の整数解は (x, y) = (5 + 3k, 2 + 2k) (k は任意の整数)。

Download Report