最小整数解を代入以外の方法で知りたい

質問

(30X+24)^2-4*7169が整数の２乗となるときの０以上の最小の整数Xを求めたいのですが、
０から順に代入してみる、以外に何かいい方法はないでしょうか？

回答No.2

ask-it-aurora · ベストアンサー

整数の2乗とのことですが一般性を失わずにそれを自然数の2乗と仮定できます．そこで
(30x + 24)^2 - 4*7169 = n^2
となる整数 x と自然数 n の組を探しましょう．

変形して整理すれば
(30x + 24 + n)(30x + 24 - n) = 4*7169
です．右辺が偶数なので左辺も偶数でなくてはなりません．したがって n = 2m と書けます．さらに 7169 = 67*107 に注意すれば
(15x + 12 + m)(15x + 12 - m) = 67*107
となります．いま m は自然数と仮定しているので 15x + 12 + m ≧ 15x + 12 - m です．また x は整数なので
15x + 12 + m = 107
15x + 12 - m = 67
あるいは
15x + 12 + m = -67
15x + 12 - m = -107
あるいは
15x + 12 + m = 7169
15x + 12 - m = 1
あるいは
15x + 12 + m = -1
15x + 12 - m = -7169
が成り立ちます．実際に解いてみると，解はそれぞれ(x, m) = (5, 20), (x, m) = (-33/5, 20), (x, m) = (1191/5, 3584), (x, m) = (-1199/5, 3584) です．
したがって答えは x = 5, n = ±40 のときとわかります．

## この解答だと質問よりずっとキツイことを証明したことになります．最初に書いた方程式の整数解はこれに限ることまでがわかります．ちなみに問題文にある"最小の整数"はおかしいので写し間違いでは？

お礼

ありがとうございます
素因数分解をすればいいんですね

仮に、ですが
素因数分解しようと思っても桁数が大きかったり、今回みたいに大きな素数で見つけにくい場合、ほかに方法はないでしょうか？

回答No.3

ask-it-aurora

<回答No.2お礼

思いつきませんね．4*7169 = 4*67*107 という人工的な感じのチョイスからも露骨にこの解法を示しているように思えます（もし 7169 が 3つ以上の素数の積で表せたら，それは面倒なことになるので）．手計算でやる必要がなければ参考URLのようなところに放り込めば答えはすぐわかりますが．

もしこの問題が別の問題を解くために出てきたならば，定式化そのものを考えなおしたほうがよいかもしれません．

また素因数分解のアルゴリズムでよくある手ですが √7169 ~ 85 を超える数は因数として考える必要はそもそもありません．なぜなら一般に p を N の最も小さい素因数とすれば
N = p * (N/p) ≧ p^2
より√N ≧ p がわかるからです．これくらいならば少し時間をかければ紙と鉛筆でも見つかるでしょう．

あと場合分けでは全部書きましたが実際に方程式を解くときには行列で書きなおして逆行列を計算しておいたほうが無駄がないように思います:
(x, m) ((15, 15), (1, -1)) = (u, v) - (12, 12)
こうすればそれぞれの場合に応じて
(u, v)((15, 15), (1, -1))^{-1}
だけを再計算すれば済むので．

参考URL：

http://www.wolframalpha.com/input/?i=7169

お礼

ありがとうございました

補足

そんなサイトがあるんですね

回答No.1

ast0718

私が一分ぐらい考えて考え付いた方法を説明します。

(30X+24)^2-4*7169 = n^2 となればよいわけですね
n=2mとすると（そうするとさらに都合がよい）
これを変形して
(30X+24)^2 -4*m^2 =4*7169
4で割って
(15X+12)^2 -m*2 = 7169

(15X+12+m)(15X+12-m)=7169 となりました。

整数の問題ではこうした　　掛け算にするような変形をすると解けることが多いです。

右を素因数分解しようとおもったのですがこれ素数みたいですね。
と思ったのですがなんと素因数分解できる。

7169 =67*107 これはうまく計算しないと見つかりませんね。
いずれにせよ
(15X+12+m)(15X+12-m)=107*67
これで15X+12+m=107 , 15X+12-m =67 として
m=20,X=5 ですね
他のパターンはあるとすれば
15X+12+m=7169 で15X+12-m=1 の場合です。
m=3584 これだとXが整数になりませんね。

X=0から代入していったほうが早いですね。

お礼

ありがとうございます。
素因数分解しようとも思いませんでしたが、思ったよりも大きな素数の掛け算なんですね

確かに代入していった方が早そうですが・・・・・
仮に、ですが
素因数分解しようと思っても桁数が大きかったり、今回みたいに大きな素数で見つけにくい場合、ほかに方法はないでしょうか？