AIと戦って、あなたの人生のリスク診断 >>

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

A 回答 (3件)

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


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

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

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

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

    • good
    • 0

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

    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング