ディオファントス方程式 (Diophantine Equation)
ディオファントス方程式とは、次のように定義されます。
|
ディオファントス方程式 (Diophantine Equation) |
|
x1、x2、x3、…、xn に関する整数係数の方程式
f ( x1、x2、x3、…、xn ) = 0 …(*) の整数解の組 ( x1、x2、x3、…、xn ) を存在するか否かにかかわらず求めようとするとき、(*)をディオファントス方程式とよびます。 |
ここで、f が一次式の場合は次のことがいえます。
a1x1 + a2x2 + a3x3 + … + anxn - k = 0
（a1、a2、a3、 … 、an は整数でその最大公約数を d とする。）
が整数解を持つための必要十分条件は、d｜k となります。ここで、d｜k とは k が d で割り切れることを示します。
ここでは、２変数の場合を取り上げていきましょう。
つまり、
ax + by = k
（a、b は整数でその最大公約数を d とする。）
を考えていきます。
|
ax + by = k （a、b は整数でその最大公約数を d とする。） が 整数解(x、y) を持つ。 …(1) ⇔ d｜k …(2) |
（証明）
まずは(1)⇒(2)から。
a = d a'
b = d b'
とすると、
ax + by = k
⇔ da' x + db' y = k
⇔ d(a' x + b' y ) = k
左辺は、d の倍数なので、k も d の倍数である必要がある。
∴ d｜k
次に、(2)⇒(1)を示します。
a = d a'
b = d b'
k = d k'
とすると、
ax + by = k
⇔ da' x + db' y = dk'
⇔ a' x + b' y = k'
ここでa'、b'は互いに素となります。
A = { a'x + b'y ｜x、yは整数 }
として、Aの要素で、最小の自然数を s とおきます。
s = a'x0 + b'y0
ここで、a'、b' を s で割った商、余りをそれぞれ、qa、ra、qb、rb とおくと、
a' = sqa + ra ( 0≦ ra ＜ s )
b' = sqb + rb ( 0≦ rb ＜ s )
となり、
ra = a' - sqa
= a' - (a'x0 + b'y0)qa
= a'( 1 - x0qa ) + b'(-y0qa)
このことより、
ra ∈ Aであることがわかります。
しかし、( 0≦ ra ＜ s )と、s がAの要素で最小の自然数であることから、
ra = 0
となります。
同様に、
rb = 0
よって
a' = sqa
b' = sqb
となり、s はa'、b'の公約数になるが、a'、b'は互いに素なので、s = 1。従って、
a'x0 + b'y0 = 1
を満たす、整数解( x0、y0 )が存在することになります。
ここで、この両辺に k' をかけて、
a'k'x0 + b'k'y0 = k'
これは、
a'x + b'y = k'
が整数解、(x、y) を持つことを示す。
以上より、d｜k なら、
ax + by = k
も整数解(x、y) を持つことが示された。
（証明終）
証明はできました。実際、
ax + by = k
の形の整数解を求めてみましょう。
|
例） 11x + 7y = 1 の整数の一般解を求めよ。 |
解）まずどのように解くかの方針を立てましょう。ユークリッドの互除法を用いる手もありますが、ここではまず整数解のひとつをひねり出しましょう。
すると、( 2、-3 )という解が思いつきます。
ここで
11x + 7y = 1
から
11・2 + 7・(-3) = 1
を辺々引きましょう。
11( x - 2) + 7(y + 3) = 0
１１と７は互いに素なので、(x - 2)は７の倍数になるはずですね。そこで、
x - 2 = 7m (m は整数)
とおくと、
x = 2 + 7m、y = -3-11m
となります。よって、
11x + 7y = 1
の整数の一般解は、
(x、y) = ( 2 + 7m、-3-11m ) (mは整数) //
