• 締切済み

条件を満たす最小の整数解

ax^+bx+c=y^2 (a,b,cは既知数、x,yは未知数) x、yがともに正の整数であるとき、 上記の式を満たす最小のxを求めるためには どのような方法があるでしょうか? 例として 81x^2+34634x-375=y^2 という式等です。 考えてはみたものの全く糸口が見つかりません。 ぜひ考え方等をご教授ください。 ちなみに例の式の場合でいうと、 x=23の時 y=916 を得ました。 これは1から代入していって見つかっただけです。

みんなの回答

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.4

 回答はできませんが…a,b,cも整数でしょう? こりゃディオファントス方程式の一種です。  おそらく、スマートな解法は、あったとしてもそう簡単には見つからないでしょう。いや、解く方法以前に、解があるかどうか(可解性)を判定する事すら容易でない。  解を見つけてしまえば「解がある」のは当たり前ですが、幾らやっても解が見つからないからというだけでは「解がない」とは言えないですね。有限時間以内に「こりゃ解がありません」と言い切るための判定方法が研究されています。  ご質問において、もしb=c=0に限定してしまえば、とても簡単な問題です。しかし、式がちょこっと違うだけで難しさが全然違ってきます。たとえば、a x^2 + by = c (a,b,c > 0) という方程式の場合、解があるかどうかを判定する方法があります。けれど、その判定アルゴリズムはNP完全(nondeterministic polynomial complete)のクラスに属する(つまり判定には2^(a+b+c)にほぼ比例する手間が掛かる)ことが証明されています。ということは少なくとも「a,b,cがどんな値であっても関係なく簡単に判定できるような判定法は存在しない」ということです。(ということは、もし「a,b,cがどんな値であっても関係なく簡単に解を計算する方法」があったら、それで判定ができてしまうことになる。だから当然、そんな旨い計算方法もない訳です。)  一般の2変数2次のディオファントス方程式について可解性を判定する方法があるのかどうか、知りません。(少なくとも10年ほど前にはまだ数論の分野で研究が続いていた。なお、4次では判定法がないことが証明済み。)そして、ご質問の方程式の場合にも、可解性の判定法があるかどうか知りません。が、運が良ければディオファントス方程式を扱った数論の専門書に載っているかもしれない。そういう非常に難しい問題だと思います。

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.3

両辺を 4a 倍して 4a^2x^2 + 4abx + 4ac = 4ay^2. 左辺は (2ax)^2 + 2b(2ax) + 4ac = (2ax + b)^2 + 4ac - b^2 と書けて 結局 (2ax + b)^2 - 4ay^2 = b^2 - 4ac. この右辺は定数だから, いわゆるディオファンタス方程式... かな?

  • ungirl
  • ベストアンサー率43% (30/69)
回答No.2

地道に代入されたのですか。 数学に対する姿勢としては非常によい心がけだと思います。 ひとつの方法として、とりあえずコンピュータに答えを出してもらってはどうでしょう。 エクセルでもできるのではないでしょうか。 その上で、じゃあどのような方法があるのだろうか、と考えてみるのも一つの方法ではないかと思います。

davidVV
質問者

お礼

ありがとうございます。 ただ、しらみつぶしなやり方ではなく 効率の良いやり方があるならば、 と思い現在悩み中です。 今のところ思いついたのは、 平方数の下一桁が限られる事から、 xの下一桁も少し絞れるな、といったところです。

回答No.1

問題の条件でa,b,c,がそれぞれ既知数であると与えられているのですが、これらは定数と考えてもよいのでしょうか。 yは正の整数であると仮定されているので、両辺の平方根をとっても等号はなりたちます。 そのときの左辺の内部のax^2+bx+cを平方完成することで、xの最小値に検討がつけられるのでは、と考えます。

davidVV
質問者

補足

すいません、定数と考えて下さい。 出来ましたら、もう少し詳しく教えていただけないでしょうか。

関連するQ&A

専門家に質問してみよう