- ベストアンサー
最大公約数の求め方
「２つの整数1271と1517の最大公約数を求めなさい」 という問題があります。 答えは「41」なのですが、 素数を順番に試していくしか方法しかないのでしょうか？
- naka-nishi
- お礼率100% (8/8)
- 数学・算数
- 回答数3
- ありがとう数4
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (2)
- hashioogi
- ベストアンサー率25% (102/404)
互除法は調べましたか ?
お礼
「互除法」というものは知りませんでした。 ありがとうございました。
- osaka-girl
- ベストアンサー率19% (91/456)
えー最大公約数だから、素因数分解すればいいのですよね。 素因数分解のことを素数を順番に試すというのであれば、 その通りだと思います。
お礼
早速の回答ありがとうございました。
関連するQ&A
- 最大公約数に関する問題です。
最大公約数に関する問題です。 『２つの整数6186と4709の最大公約数(6189,4709)を求めよ。また、この最大公約数に対して、(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』という問題です。最大公約数は1と求められたのですが、後半の『(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』は、X,Y の組み合わせが無数にあると思うのですが、どうしたら良いのでしょうか？宜しくお願い致します。
- ベストアンサー
- 数学・算数
- 最大公約数を見つけたい
C++初心者です。Visual studio 2005を用いてvisual C++の計算フォームアプリケーションを作りたいのです。 ２ヶ所のテキストボックスに整数を入力させ、「実行」ボタンを押すとその２つの整数の最大公約数を出力させたいのですが、どうも上手くいきません。 できるだけ簡素なコードで最大公約数を見つけるにはどうすればいいでしょうか？ どうかよろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- 最大公約数について
「a,b,c,rが正の整数で、a=rb+cであるとき、a,bの最大公約数とb,cの最大公約数は一致することを証明せよ。」 という問題の解答の出だしが、 「aとbの最大公約数をm、bとcの最大公約数をnとおくと a=mA, b=mB（AとBは互いに素な整数） b=nB',c=nC（B'とCは互いに素な整数） と書ける」 となっているのですが、なぜこう書けるのかわかりません。 「a=mA, b=mB」「b=nB',c=nC」とかけるのはわかりますが、なぜAとB,B'とCが互いに素と言えるのかわかりません。 思いつく反例を上げると、a,b,cは異なる数とは問題文に書かれていないので、もしaとbが同じ数だとしたらA=Bとなり互いに素ではありませんよね？
- ベストアンサー
- 数学・算数
- 最大公約数と最小公倍数の問題
「ある整数Ａと24の最大公約数は8で、最小公倍数は168である。Ａの値を求めよ。」 こちらの問題の答えは「56」ということですが、どのようにこの答えを導き出すか悩んでいます。 「24、8、168」と8に関係する数が並んでいるので8の倍数から探していくのではないかと思いますが、短時間で効果的に答えを導き出す方法はあるのでしょうか。
- ベストアンサー
- 数学・算数
- 最大公約数について教えてください！
二つの整数m、n(m＞n)の最大公約数をｇとすると、mをnで割ったあまりとnとの最大公約数もｇであることを証明せよ ただしm、nが互いに素であるとき、nとm－nも互いに素であることを使ってもよい 解説お願いします！
- 締切済み
- 数学・算数
- 最大公約数について！
二つの整数m、n(m＞n)の最大公約数をｇとすると、mをnで割ったあまりとnとの最大公約数もｇであることを証明せよ ただしm、nが互いに素であるとき、nとm－nも互いに素であることを使ってもよい はじめから解説をお願いします！
- ベストアンサー
- 数学・算数
お礼
参考URLまでいただき、ありがとうございました。