ユークリッドの互除法と不定方程式（平成16年） - nifty

ユークリッドの互除法と不定方程式（平成１６年）
ユークリッドの互除法は, 現在, 我が国の初等・中等教育からほとんど疎外されている.
代数学なかでも数論における「ユークリッドの互除法」の果たす役割を改めて考えな
おし, 初等教育の段階から指導する必要を感じている.
「整数が素因数分解出来れば, ユークリッドの互除法はいらない」これがいまの教育
現場の考え方のように思えてしかたがない.
そこで, ユークリッドの互除法が, 古くから
どのように重んじられてきたかを記してみたい.
1. ユークリッドの互除法
補助定理１
(a, b) : a と b の最大公約数とする
a をbで割った商をk、余りを c とすると,
(a, b) = (b, c)
（証明） a, b の公約数を k とおくと
a = ka',
b = kb' ただし (a', b') = 1
a = kb + c だから, c = a－kb = k(a'－kb')
∴ a, b の公約数は b, c の公約数である.
同様にして, b, c の公約数は a, b の公約数である.
a, b の公約数の集合 = b, c の公約数の集合
∴ (a, b) = (b, c)
定理（ユークリッドの互除法）
a をbで割った余りをcとし, b を c で割った余りをd とし, 以下続けると
(a, b) = (b, c) = (c, d) = …… = (l, 0)
l が a, b の最大公倍数である.
-1-
ただし、a > b > c > d > … > l
補助定理２
(a, b) = (b, a)
…………………………①
(a, b) = (a－b, b)
…………………………②
（証明） ①は自明
②について
a, b の公約数を k とする.
a = ka',
b = kb'
(a', b' : 整数)
∴ a－b = k(a'－b')
よって a －b と b の公約数は k となる.
逆に, a－b と b の公約数を d とすると
a－b = db', b = db"
(b', b" : 整数)
a = b + db' = d(b" + b')
よって, a と b の公約数の全体は a－b と b の公約数の全体は等しい.
∴ (a, b) = (a－b, b)
古代中国ノ算書「九章算術」は, 後漢の初頭（一世紀）頃, 従来からあった中国の数学
を集大成して出来上がったものである.
方田の章六題に次のようにユークリッドの互助
法を用いて, 分母分子の最大公約数を求めている.
「また、九十一分の四十九がある。問うに、これを約すといくらか」「答えて曰く、
別に分母分子の数を置き（副置）、小さい数を大きい数からこもごも減じて、
（更相減損）
等数を求める。等数で分母分子を約す」
（副置分母子之数、以少減多、更相減損、求其等也、以等数約之）
49
49
7
7
7
7
7
7
91
42
42
35
28
21
14
7
ユークリッド原論第７巻２題には, 「互いに素でない２数が与えられたとき, それらの
最大公約数を見いだすこと」がある. ２数と単位数が線分として扱われている. ２線分の
差で小の線分を引き, その差が単位線分を残すまで続ける. その差が元の２数の約数のと
き, この差を最大公約数とする.
-2-
（注）ユークリッドの互除法は, 英語で Euclid's algorithm といい, ギリシャ語では
Antanairesis といい, 反復減法という意味をもつと云われる.
2. 不定方程式
次の不定方程式を考えてみたい.
1) Diophantos の方程式
ax + by = c ただし, (a, b) = c
2) Pell の方程式
x2－Ny2 = m
3) Pythagoras 数
x2 + y2 = z2
z
y
ただし, x, y, z は正の整数
x
Diophantos の方程式
(a, b) = c
のとき ax + by = c
を満足する整数 x, y が存在する.
（証明） a = a1, b = a2 とおき, ユークリッドの互除法により
a1 = k1a2 + a3
(0 < a3 < a2) ……………(1)
a2 = k2a3 + a4
(0 < a4 < a3) …………… (2)
a3 = k3a4 + a5
(0 < a5 < a4)
…………… (3)
…………
an-1 = kn-1an + an+1 (0 < an+1 < an )
…………(4)
an = kn an+1
………………………… (5)
(1),(2) より a4 = - ak2 + b(1 + k1k2) ……………(6)
(3),(6) より
a5 = a(1 + k2k3)－b(k1 + k3 + k1k2k3)
以下, 同じようにして
an+1 = ax + by
ただし, x, y : 整数
an+1 は a, b の最大公約数 (a, b) = c である.
アールヤバティーヤの解法
Diophantos 方程式の解法を記した最古の書は, 古代インドの天文学書「アールヤバテ
ィーヤ」だと言われている. その解法は, 次のようになものであったとされている.
-3-
(A )
ax + c = by
(1)
b を a で割り, 商を q 余りを r とすると
ただし, (a, b) = c
b = aq + r
(2)
x = qy + z
(B )
az + c = ry
∴
(r < a)
ax + c = (qa + r) y
とおく.
以下, 未知数の係数をユークリッドの互除法を用いて, 次々と小さくしていくと最後に
は次の方程式に達する.
( C)
1・v + c = sw または 1・v － c = sw
( C)から逆算することで x, y が w の整式で表される. 現代の我々の解法と同じであ
る.
Pell の方程式
x2 －2y2 = 1
この方程式の解
2 の近似分数は,
ている.
17
B.C.400 年頃古代インドやギリシャで求められ
577
古代インドの Bandhayana は , 12 , 408 を得ている.
プロクロス（４１０～４８５）によると , ピタゴラス学派は次の作図を行っている
F
と記している. (図 1)
辺 AB を次のように延長して,
d2
E
BC = AB,
CD = EB とする.
AD2 + CD2 = (AB + BD)2 + (BD－AB)2
d1
= 2AB2 + 2BD2
A
s1
B
C s2
(図 1 )
CD2 = EB2 = 2AB2 だから
D
AD2 = 2BD2 = FD2
∴ BD = AB + EB,
FD = AD = 2AB + EB
AB = s1, BD = s2, EB = d1, FD = d2 とおくと s2 = s1 + d1, d2 = 2s1 + d1
∴
sn+1 = sn + dn,
s1 = 1, d1 = 1
dn+1 = 2sn + dn
とすると
-4-
s1 = 1
d1 = 1 ,
s2 = 2
d2 = 3 ,
s3 = 5
d3 = 7 ,
s4 = 12
……
d4 = 17 ,
∴
d4
17 d 8
577
=
,
=
s4
12 s8
408
3 ユークリッドの互除法との関係
古代中国の九章算術では, 数の間の変換「更相減損」を行って, 最大公約数を求めた.
その変換は, 次のようにと ST または TS 表される.
S
x > y のとき
(x, y) → (x－y, y)
T
x < y のとき
(x, y) → (x, y－x)
のとき
ST:
TS:
S
(x, y) → (x－y, y)
T
(x, y) → (x, y－x)
T
→ (x－y, 2y－x)
S
→ (2x－y, y－x)
一方, ピタゴラス学派による変換は, 正方形の辺（数） s
と対角辺（数） d
の間の変
換は , BA 次のようにと表される.
B
A
BA: (s , d) → (s, s + d) → (2s + d, s + d)
２つの１次変換 BA, ST は, 次のように表されるから
BA:
d' = 2s + d
s' = s + d
… … … … … (1)
ST:
x' = x － y
y' = - x + 2y
… … … … (2)
(1)は(2)の逆変換であることが分る.
（注）ピタゴラス学派は, ユークリッド原論 II.10 を用いてこの作図を証明したといわれ
ている.
4 アルキメデスの解法
アルキメデス（B.C.3 世紀）は,
3 の近似分数として
その求め方は, 次の近似式によるものと推測されている.
-5-
265 1351
を得た.
,
153
780
b
a ±
2a ± 1
3 の計算
5
( a) 3 <
3 <
a2 ± b
<
< a ±
b
2a
(複号同順）…………(＊)
7
4
3 = 22－1 と変形して ,
3 の近似値を 2 として
1
1
不等式（＊）を用いると 2 －
<
22－1 < 2 －
2×2－1
2×2
5
7
< 3 <
∴
3
4
1 <
3<
4 で
( b)
19
<
11
3 <
5
<
3
26
15
7
5 <
より, 分母を払い
4
27 の近似値を 5 として ,
27 = 52 +
2
用いると
5 +
<
52 + 2 < 5
2×5 + 1
57
26
19
< 3 3<
<
3 <
∴
11
5
11
( c)
3 <
265
<
153
19
<
11
3 <
3 <
1351
780
26
15
より, 分母を払って
27 <
21
4
2 と変形して, 不等式（＊）を
2
+
2×5
26
15
285
<
11
675 < 26
675 =
26 2 － 1 と変形し, 不等式（＊）
675 の近似値が 26 として ,
1
1
を用いると 26 －
< 262 －1 < 26 －
2×26－1
2×26
1325
1351
265
1351
< 15 3 <
<
3 <
∴
51
52
153
780
（注）近似を左右交互に行っている.
（注）我々は, 連分数で次のように計算する.
3= 1 +
1
…
1 + 2 + 1 + 2 +
1
1
1
-6-
5 ブラフマグプタ（７世紀）の解法
pell の方程式
(x2
∵
x2
－Ny2
－Ny2)(z 2－Nt2)
(x2
(m≠0) について, 次の恒等式が成り立つ.
= m
= (xz ± Nyt)2－N(xt± yz)2
－Ny2)(z2－Nt2)
(Brahmaguptaの恒等式)
= x2z2 + N2y2t2－N(x2t2 + y2z2)
= (xz ± Nyt)2－N(xt± yz)2
（注） p2
－Nq2
= m,
r2－Ns = n
(x, y) = x2－Ny2
⇒ (pr ± Nqs)2－N(ps ± qr)2 = mn
と置くと
(p, q)(r, s) = (pr + Nqs, ps + qr)
(pn, qn) を、次のように置くと
(p0, q0) = (r, s),
(pk, qk) = (p, q)(pk-1, qk-1)
(p1, q1) = (1, 1)
(p2, q2) = (2p1 + 3q1, p1 + 2q1) = (5, 3)
(p3, q3) = (2p2 + 3q2, p2 + 2q2) = (19, 11)
(p4, q4) = (2p3 + 3q3, p3 + 2q3) = (71, 41)
(p5, q5) = (2p4 + 3q4, p4 + 2q4) = (256, 153)
………………
(pn, qn) は x2－3y2 = -2 の解だから 2652－3 × 1532 = - 2
(p1, q1) = (2, 1)
(p2, q2) = (2p1 + 3q1, p1 + 2q1) = (7, 4)
(p3, q3) = (2p2 + 3q2, p2 + 2q2) = (36, 15)
(p4, q4) = (2p3 + 3q3, p3 + 2q3) = (362, 209)
(p5, q5) = (2p4 + 3q4, p4 + 2q4) = (1351, 780)
………………
(pn, qn) は x2－3y2 = 1 の解だから 13512－3 × 7802 = 1
-7-
x2－Ny2 = m と置くと
x
1
m
－ N=
y
y x + y N
x
m に対して x, y が大ならば,
が
y
2652－3× 1532 = -2,
13512－3× 7802 = 1
265
<
153
3 <
6 Pythagoras 数の解法
N の近似値となるから
から
3 の近似値
265 1351
,
が考えられる.
153
780
1351
780
x2 + y2 = z2
ただし, x, y, z は正の整数
(x, y, z) = d ≠ 1 のとき, 上式は両辺を d2 で割ればよいので,
(x, y, z) = 1
と仮定する.
x, y, z のうち２つが１ではない公約数をもつと, 残りは１ではない公約数をもつ. よっ
て, のうちいずれの２つは互いに素となる.
x, y, z
つぎの４通りが考えられる.
(i) x: 奇数, y: 奇数, z: 偶数
(ii) x: 奇数, y: 奇数, z: 奇数
(iii) x: 奇数, y: 偶数, z: 奇数
(iv) x: 偶数, y: 奇数, z: 奇数
( iii) ,( iv) は x, y を交換したものだから, 同じものと考えられるので, (i),(ii),(iii)の３
通りについて考える.
( i) ,( ii)について
x ≡ 1 (mod.2),
y ≡ 1 (mod.2)
x2 ≡ 1 (mod.4), y2 ≡ 1 (mod.4)
∴ x2 + y2 ≡ 2 (mod.4)
z2 ≡ 2 (mod.4) ではないから, (i).(ii)は成り立たない.
( iii)について , y2 = (z + x)(z－x) …………(1)
y: 偶数だから
y2 ≡ 0 (mod.4)
x: 奇数, z: 奇数だから
z + x, z－x : 偶数
z + x = 2m, z－x = 2n
(m,n: 正整数
x = m－n,
(m,n: 互いに素) ………………………(3)
z = m + n
-8-
m > n) とおく ……(2)
(x, z) = 1 だから (m, n) = 1
∵
(m, n) = d ≠ 1 とすると n = dm
x = m(1－d), z = m(1 + d)
a2 + b2
(x, z) = m ≠ 1
2ab
( 1) ,( 2) より y2 = 4mn ……………(4)
m, n は完全平方数だから m = a2, n = b2 ……(5)
a2－b2
m > n より y2 = 4a2b2
∴ y = 2ab …………………(6)
( 3) ,( 5)より
x = a2 － b2,
x = a2 － b2,
z = a2 + b2
(a > b)
y = 2ab, z = a2 + b2
(a > b)
(Brahmagupta)
（注）次のものはよく知られた例である.
1)
a = 2, b = 1 のとき
x = 3, y = 4, z = 5
2)
a = 4, b = 1 のとき
x = 15, y = 8, z = 17
3)
a = 3, b = 2 のとき
x = 5, y = 12, z = 13
4)
a = 4, b = 3 のとき
x = 7, y = 24, z = 25
引用文献
［1］ B. L. van der Waelden: Geometry and Algebra in Ancient Civilizations
Springer-Verlag 1983
［2］ Thomas L. Heath: The Thirteen Books of Euclid's Element Vol.2 Dover 1956
［3］ Thomas L. Heath: A History of Greek Mathematics Vol. 1 Dover 1981
［4］ Leonard E. Dickson: History of the Theory of Numbers Vol. II Chelsea 1971
［ 5］
数
門
１９９９
北村
［ 6］
初等整数論講義
２０００
高木
貞治
［ 7］
アルキメデスを読む
１９９９
上垣
渉
論
入
泰一
著
槙
書店
著
岩波
書店
著
日本評論社
［8］ V. S. Varadarajan: ALGEBRA in ancient and MODERN TIMES, American
Mathematical Society, 1998
-9-

Download Report