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

質問

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

回答No.3

zk43 · ベストアンサー

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

お礼

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

回答No.2

yasei

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

回答No.1

Tacosan

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