一次不定方程式の解き方

質問

一次不定方程式（aX+bY=dの（X,Y）を求めたいとします。）には、解き方が2種類あると聞きました。

1つは、適当な解(X,Y)=(X1,Y1)を求め、
X=X1-bt
Y=Y1+at
(tは整数)とする方法

もう1つは、
a,bのうち、小さい方の素数に着目し、変形していく方法なのですが、こちらの解き方で解けない問題があり困っています。

具体的には、7X+5Y=3という一次不定方程式がある際に、

7X+5Y=3
(5*1+2)X+5Y=3
5(X+Y)+2X=3

ここで、t=(X+Y)とする

5t+2X=3
X=(3-5t)*(1/2)

となってしまい、分数になってしまいます。

こちらの方法でこの問題を解くにはどのようにしたらよいのかアドバイスいただけないでしょうか。

回答No.2

Tacosan · ベストアンサー

基本は「係数を 1 にする」こと.
5t + 2X = 3
から
X=(3-5t)*(1/2)
にもっていかずに 5t + 2X = t + 2(2t + X) = 3 から u = 2t + X とおいてください.

回答No.3

mister_moonlight

＞X,Yの係数が大きくなった場合に解くことが困難になると思うので、具体値を公式的に導くことはできないのでしょうか？

特別解を求めるのはどんな方法でも同じと思います。
しかし、係数が大きくなると少々の変形が必要です。
例えば　18x-43y＝1という場合を考えます。

18x-43y＝18(x-2y)－7y＝1と変形して、x-2y＝t　(x、yが整数からtも整数)とおきます。
そうすると、18t－7y＝1を解く事になります。

これ以降は、先の解と同じことになります。

回答No.1

mister_moonlight

7x＋5y＝3　‥‥(1)よりxとyの特別解を各々α、βとする。
従って、7α＋5β＝3　‥‥(2).
(1)-(2)を作ると、7(x-α)＝5(β-y)になるが、5と7は互いに素であるから、mを整数として、x-α＝5m‥‥(3)、従ってβ-y＝7m‥‥(4).
そこで、αとβの具体値を求めると、(α、β)＝(4、-5)。
これを、(3)と(4)に代入すると、x＝5m＋4、y＝-7m-5。

補足

この方法ですと具体値を憶測で計算しなければなりませんよね？？
その場合、X,Yの係数が大きくなった場合に解くことが困難になると思うので、具体値を公式的に導くことはできないのでしょうか？？