2元一次不定方程式の説明で意味がわかりません

自分の使っているテキストに

282x+113y=1　.......(1)
(ax+by=n)
これは右辺=1で0ではないから、すでに教えたように(1)をみたす(x.y)の値を一組見つければいい。
でもxとyの係数であるa,bの値が282と113とかなり大きな値なので、これを見つけるのが大変だ。
したがってこれがax+by=n型の方程式の応用問題ということになる。

この応用問題の特徴は
(1) 右辺のn=1であり
(2) 左辺のaとbは互いに素な整数である。

つまり　ax+by=1の形であれば、係数a,bが(1)のようにかなり大きな値であっても解くことが出来る。




と書かれているのですが、
なぜ「つまり　ax+by=1の形であれば、係数a,bが(1)のようにかなり大きな値であっても解くことが出来る」ということになるのかが読み取れません。

この中のどこに、この理由が書いてあるのでしょうか？
理解できる方がいましたらよろしくお願いします。

No.1 ベストアンサー 回答者： ask-it-aurora 回答日時： 2013/09/16 20:14

一般論として整数a, bに対してax + by = gcd(a, b)を満たす整数x, yが存在します．またこのようなx, yは拡張ユークリッド互除法によって手早く計算できることが知られています．この問題ではaとbが互いに素なのでgcd(a, b) = 1の場合に相当します．著者はこのことを念頭においているのでしょう．

参考URL：http://ja.wikipedia.org/wiki/ユークリッドの互除法#.E6.8B.A1.E5.BC.B5.E3.81.95.E3.82.8C.E3.81.9F.E4.BA.92.E9.99.A4.E6.B3.95

No.3 回答者： ask-it-aurora 回答日時： 2013/09/16 22:28

No.1です．どうも試行錯誤で頑張っている人がいるようなので，老婆心ながらもう少し補足しておきます．先の解答で示したWikipediaのページに書いてある方法(アルゴリズム)にしたがえば

282x + 113y = 1
を満たす整数は数行の計算ですぐ見つかります．実際，
282 = 2*113 + 56,
113 = 2*56 + 1
と割っていくと最後に最大公約数が余りに出てくるので上の式を逆に変形していけば
1 = 113 - 2*56
= 113 - 2*(282 - 2*113)
= 282*(-2) + 113*5
とわかります．もっともこの方法が既知でないならば(初等代数の基本的な命題なので知っておいて損はないと思いますが)試行錯誤によるしかないとは思います．

これを使って一般解を求めるには回答No.2で既に示されているようにすればよいでしょう．

No.2 回答者： spring135 回答日時： 2013/09/16 21:34

(1)を満たす整数解の組(x0,y0)が見つかったとすると

282x0+113y0=1 （2）

（1）-（2）より

282(x-x0)+113(y-y0)=0

282と113が互いに素なので

x-x0=113t　　　　(3)

y-y0=282t　　　　(4)

これにt=0,1,2...を代入すると解はいくつで見つかるというのがこの手の問題の定石です。


さて、(x0,y0)を見つけて話を具体化してくれという気持ちが強いと思います。

（1）はその手の問題として手こずる類のものです。試行錯誤で見つけました

x0=111, y0=277

見つけ方のコツはx0は113付近、y0は282付近、それでだめなら226,564付近というようにやります。


答え

x=111+113t

y=277+282t


n=1でaとbが互いに素という場合は(3)、(4)は問題ありませんがそうでない場合はaとbの公約数を考える必要があるということなのでしょう。まあ、あまり気にしないで、問題ごとに考えていったほうがいいでしょう。