一元不定方程式
著者:梅谷 武
語句:一元不定方程式
一元不定方程式について述べる。
作成:2006-05-21
更新:2013-06-17
第2章において整係数の二元一次不定方程式の解法について考えましたが、有理数体ℚ上の代数方程式において整数解を求めるときに、この方程式を不定方程式といいます。一般には二元以上の不定方程式を解くことは難しい問題ですが、一元不定方程式は有限回の代入計算を実行することで解くことができます。
整係数の一元
n次不定方程式
| anXn + ⋯ + a2X2 + a1X + a0 = 0, n ≧ 1, a0 ≠ 0
|
の整数解
αは
a0の約数である。
証明
αを整数解とする。
anαn + ⋯ + a2α2 + a1α + a0 = 0より、
| a0 = － α ( anαn－1 + ⋯ + a2α + a1 )
|
となり、
α|a0であることがわかる。■
次に有理係数の一元
n次代数方程式
| anXn + ⋯ + a2X2 + a1X + a0 = 0, n ≧ 1, a0 ≠ 0
|
の有理解を求めることについて考えます。まず係数の分母の最小公倍数をかけることによって整係数の代数方程式とすることができます。ですから、最初から整係数と考えても一般性を失うことはありません。両辺に
ann－1をかけます。
| (an X)n + an－1(an X)n－1 + ⋯ + a1 ann－2 (an X) + a0 ann－1 = 0
|
ここで
Y=an Xとおけば、整係数の単方程式とすることができます。
| Yn + bn－1Yn－1 + ⋯ + b1Y + b0 = 0, n ≧ 1, b0 ≠ 0
|
整係数の単方程式の有理解については次の補題が成り立ちます。
整係数の一元
n次不定方程式
| Yn + bn－1Yn－1 + ⋯ + b1Y + b0 = 0, n ≧ 1, b0 ≠ 0
|
の有理解
βは
b0を割る整数である。
証明
を有理解とする。ここで
s,tは互いに素な整数であるとする。
| ( | | )n + bn－1( | | )n－1 + ⋯ + b1( | | ) + b0 = 0
|
の両辺に
tnをかけると
sn + bn－1 sn－1t + ⋯ + b1 stn－1 + b0 tn = 0となり、これを移行して
| sn = － t ( bn－1 sn－1 + ⋯ + b1 stn－2 + b0 tn－1 )
|
とする。この式から
t = ± 1であることがわかる。したがって
βは整数であり、
前の命題から
β | b0であることがわかる。■
ここまで述べたことを整理して、整係数一元代数方程式の有理解を求める算法を与える次の命題が得られます。
整係数の一元
n次不定方程式
| anXn + ⋯ + a2X2 + a1X + a0 = 0, n ≧ 1, a0 ≠ 0
|
の有理解
βは
a0 ann－1の約数
mによって
と
表される。
上の算法による計算例を示します。
整係数一元不定方程式
4X3 － 19X2 + 19X + 6 = 0を解け。
from Poly1 import *
f = Poly1( [6,19,-19,4] )
print "f(X) = ", f, "= 0"
m = [ 1, -1, 2, -2, 3, -3, 6, -6 ]
for i in m:
if f.Horner( i ) == 0:
print "f(%d) = 0" % i
f(X) = 4X^3 - 19X^2 + 19X + 6 = 0
f(2) = 0
f(3) = 0
require 'mathn'
require './poly1'
f = Poly1([6, 19, -19, 4])
print "f(X) = ", f, "= 0", "\n"
m = [1, -1, 2, -2, 3, -3, 6, -6]
for i in m
if f.Horner(i) == 0
printf "f(%d) = 0\n", i
end
end
f(X) = 4X^3 - 19X^2 + 19X + 6= 0
f(2) = 0
f(3) = 0
整係数一元代数方程式
9X2 + 3X － 2 = 0の有理解を求めよ。
from Poly1 import *
f = Poly1( [-2,3,9] )
print "f(X) = ", f, "= 0"
m = [ 1, -1, 2, -2, 3, -3, 6, -6, \
9, -9, 18, -18 ]
for i in m:
if f.Horner( Fraction(i,9) ) == 0:
print "f(%s) = 0" % Fraction(i,9)
f(X) = 9X^2 + 3X - 2 = 0
f(1/3) = 0
f(-2/3) = 0
require 'mathn'
require './poly1'
f = Poly1([-2, 3, 9])
print "f(X) = ", f, "= 0", "\n"
m = [1, -1, 2, -2, 3, -3, 6, -6, 9, -9, 18, -18]
for i in m
if f.Horner(i/9) == 0
printf "f(%s) = 0\n", i/9
end
end
f(X) = 9X^2 + 3X - 2= 0
f(1/3) = 0
f(-2/3) = 0