最大公約数に関する問題です。

最大公約数に関する問題です。
『２つの整数6186と4709の最大公約数(6189,4709)を求めよ。また、この最大公約数に対して、(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』という問題です。最大公約数は1と求められたのですが、後半の『(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』は、X,Y の組み合わせが無数にあると思うのですが、どうしたら良いのでしょうか？宜しくお願い致します。

No.3 ベストアンサー 回答者： zk43 回答日時： 2010/04/01 00:38

最大公約数はどのように求めたのでしょうか？

素因数分解したのでしょうか？
ユークリッドの互除法により求めれば、その計算過程から
X,Yも同時に求められます。
計算は長くなりますが、仕組みは単純です。
ちなみに、X=-2219,Y=2915となりました。
また、一般には、X=-2219+4709n,Y=2915-6186n（nは整数）
の形のものがすべて解であり、したがって、解は無数に
あります。
一般に、aX+bY=dの形の方程式は、不定方程式と呼ばれ、
解は無数にあります。（ただし、a,bの最大公約数がdを
割り切る場合のみ。）
とにかく、ユークリッドの互除法を調べてみてください。

この回答へのお礼

ありがとうございました。このような解法があるとは思いませんでした。

お礼日時：2010/04/01 01:43

No.2 回答者： yasei 回答日時： 2010/03/31 23:43

１つ見つければあとは6189と4709を使って表せます。

No.1 回答者： Tacosan 回答日時： 2010/03/31 23:32

ん～, 1つ見つけるか「全て」見つけるか... 問題に何も書いてないなら「全て」求めるのがいいかな.