不定方程式の最小値

質問

a、bは互いに素な自然数の定数

m、nは自然数

ax0＋by0=1

x=x0n－bm>0

y=y0n＋am>0

となる自然数x、yが必ず存在するためには、

x0n/b－(－y0n/a)>1←？？？

－y0n/a<m<x0n/bであれば十分だと書いてありました

？？？を付けたところが分かりません
見づらいですが回答をよろしくお願いします！
x0、y0は整数です

回答No.8

178-tall · ベストアンサー

>テキストの範囲で、「n≧ab+1 なら ax+by=n は (非零) 自然数解をもつ」と納得できましたか？
>その (非零) 自然数解は、n≦ab での (含零) 自然数解から選択・加算して、必ず得られる気配ですが、果たして？

　　↑
証明しきれてませんが、シナリオだけでも…。

とりあえず ax＋by = ab+1 のケース。

　(1) ax＋by = ab の(含零) 自然数解 {x, y} は、{b, 0} と {0, a} 。
　(2) ax＋by = ab+1 の解は、ax＋by = ab および ax＋by = 1 の解の和だろう。
　　ax＋by = 1 の解には、{x, y} の一方が (非零) 自然数 {-c, +d} あるいは {+e, -f} の形 (+ のほうは非零) で、
　　b-c>0 あるいは a-f >0 を満たすペアがある。
　　(これの証明はできてません。簡単な実例では OK なのですが…)

このシナリオは「帰納法」になりそうで、気は進みません。けど、ほかの手も思いつきません。
テキストの引用範囲には、このあたりのハナシがない。
…のですけど、引用範囲外にも記述はありませんか？

回答No.10

178-tall

>nがab＋1以上なら可能な理由は添付テキストの範囲で理解できました

…ならば、

>nがabの場合は
片方が0でもう片方がabになるようなx、yの組み合わせしかあり得ないので
n以上の整数が不定方程式で全て表せる数nの最小値は結局n=ab＋1となる。
ということになるのでしょうか

…そのとおり、でしょうネ。
当方は、「nがab＋1以上なら可能な理由」が判らず、模索してたのですが…。

お礼

仰る通りマルチメディアの外の記述に大切なところが載っていました、大変申し訳ないです
－y0n/a<m<x0n/bから
mが存在するためには
x0n/b－(－y0n/a)>1で無いといけない、
ということだったみたいです
大変申し訳ないです
次から質問する時は気をつけます
何回も返信していただきありがとうございました
nがab＋1以上なら可能な理由は
マルチメディアの下の部分にある通りn≦abだと
(5)番に代入して分母を払うと矛盾が生じてしまうからみたいです

回答No.9

178-tall

少々ネット検索して、参照 URL の pdf ファイル「整数論の基礎」をゲット。

THEOREM 5.2 ( 正の整数解 ) にいわく、「特に c > nab ならば， ax + by = c は少なくとも n 個の正整数解をもつ」。

簡単な実例でテストしてみると、解せないところがありました。
暇をみて、チェックしてみますかネ。

参考URL：

http://kymst.net/index.php?plugin=attach&refer=MathDocs&openfile=mjkNSZ01bt1.pdf

回答No.7

178-tall

添付テキストの範囲で、(3), (4) から (5) の左式は導けます。

けど、(5) の右式は導けませんでした。
　　代わりに x0n/b + y0n/a≧0 なら得られる
　　その左辺は、n=ab のときに 0 or 1
　　対応する ax+by=n (=ab) の(含零) 自然数解が {x, y} = {b, 0} ＆ {0, a}
　　… つまり解に「零を含めざるを得ない」ケース
という感じらしい。

テキストの範囲で、「n≧ab+1 なら ax+by=n は (非零) 自然数解をもつ」と納得できましたか？
その (非零) 自然数解は、n≦ab での (含零) 自然数解から選択・加算すると得られる気配ですが、果たして？

補足

毎度返信が遅くなってしまい本当に申し訳ないです。
nがab＋1以上なら可能な理由は添付テキストの範囲で理解できました
nがabの場合は
片方が0でもう片方がabになるようなx、yの組み合わせしかあり得ないので
n以上の整数が不定方程式で全て表せる数nの最小値は結局n=ab＋1となる。
ということになるのでしょうか

回答No.6

178-tall

>不定方程式がn以上の全ての整数を表せる時のnの最小値を求める…
　　↓
> ANo.5

　　↑

… は錯誤でした。訂正。

ax＋by=n にて、n=ab のケースが「零を含めざるを得ない n の max」に相当してますネ。

これと、n≧ab +1 なら (非零) 自然数解が存在することが、添付テキストの趣旨…だったらしい。

回答No.5

178-tall

> ANo.4 の補足。

たとえば、
　(零を含めた) 自然数解なら、n=2 以上の全ての整数を表せる。
　その中で、零を含めざるを得ない n の　max を求める？
…これも、めんどいか。

回答No.4

178-tall

>不定方程式の最小値ではなく　不定方程式がn以上の全ての整数を表せる時のnの最小値を求める問題でした…

たとえば　2x+3y=n　の場合だと、

　n = 1, 2, 3, 4　:　(非零) 自然数解なし
　n : 5　:　…あり
　n = 6　:　…なし
　n = 7 :　…あり

途中に穴があり、一刀両断とはいかぬ模様。
添付テキストじゃ、どのように処理してますか？

補足

返答遅れて申し訳ございません
テキストの流れは
ax0＋by0=1となる整数をx0、y0とし
a(x0n)＋b(y0n)=n…(1)
a(－bm)＋b(am)=0…(2)

(1)＋(2)より
a(x0n－bm)＋b(y0n＋am)=n

x=x0n－bm>0…(3)
y=y0n＋am>0…(4)
となる自然数x、yが必ず存在するためには
－y0n/a<m<x0n/b、

x0n/b－(－y0n/a)>1
であれば良いと書いてあり
そこからの証明の流れは分かりますが、
最後のx0n/b－(－y0n/a)>1 であれば良いという流れが分かりません

回答No.3

178-tall

補足。

>添付テキストの「n の最小値は ab+1 です」も眉唾モノ。
>n=5 が最小値 (ab-1) と思われます。
　　↑
これは、a=2, b=3 の場合、でした。

補足

大変申し訳ありませんでした
大切なことを書き忘れていました
不定方程式の最小値ではなく
不定方程式がn以上の全ての整数を表せる時のnの最小値を求める問題でした
そのことについて、初めに？？？を付けた所が分からなかったので、時間があるときでいいので回答して頂けると幸いです

回答No.2

178-tall

(一部・訂正)

a. b ともに正値のケース (= 自然数) では、
　x0n/b > m
　y0n/a > -m → m > y0n/a
つまり、
　x0n/b > m > -y0n/a　　…(4)
なる条件を得る。これが (5) の左式。

(5) の右式だが、添付テキストでは説明不足。
　　↓
>x0n/b－(－y0n/a)>1←？？？
　　↓
添付テキストの「n の最小値は ab+1 です」も眉唾モノ。
n=5 が最小値 (ab-1) と思われます。

回答No.1

178-tall

これは、
　ax＋by=n　　　…(1)
にて (非零) 自然数解の有無を調べているらしい。

n=1 の一整解を {x0, y0} とすれば、(1) の一般整解は、
　x=x0n - bm　　　…(2)
　y=y0n + am　　　…(3)
と書ける。
(2), (3) の左辺がともに (非零) 正値なら、
　x0n > bm
　y0n > -am
が成立つ。

a. b ともに正値のケースでは、
　x0n/b > m
　y0n/a > -m → m > y0n/a
つまり、
　x0n/b > m > y0n/a　　…(4)
なる条件を得る。

>x0n/b－(－y0n/a)>1←？？？
　　↑
これは出所不詳。
[反例]　　2x＋3y=5　:　(4) が成立。実際、x=1, y=1 が (非零) 自然数解。けど、x0n/b－(－y0n/a) = 0.833… 。

補足

すみません私の書いた前提条件に不備があったのだと思います
マルチメディアを追加したので時間がある時に回答して頂けると嬉しいです