• 締切済み

最大公約数

素因数分解を使わない最大公約数の求め方で、二つはユークリッドの互除法を利用するというのはわかったのですが、３つはどのようにして求めればいいと思いますか？

みんなの回答

  • komimasaH
  • ベストアンサー率16% (179/1067)
回答No.2

２つの数の最大公約数をまず求める。 その数と残りの数の最大公約数が３つの数の最大公約数。 ということでＮＯ．１さんの回答どおり。

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

2回やればいいんじゃないかと思いますが.

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 最大公約数について

    ユークリッドの互除法について勉強していて 途中で疑問に思ったことがあるのですが 例えば 288と108という数について 288と108の最大公倍数は36 288÷108=2余り72 ここから 108と72を取り出して　この二つの数の最大公倍数も36 108÷72=1余り36 ここから72と36を取り出して、　この二つの数の最大公倍数も36 となりますが、なぜ割る数と余りの最大公倍数が、初めの数の最大公約数とずっと同じであり続けるのでしょうか? ユークリッドの互除法自体はある程度理解できています。 ユークリッドの互除法は、この数の動きを利用して最大公約数を求めていくようですが、なぜこのようなことになるのかが知りたいです。 難しい内容では理解できないので、できれば中学生レベルでも理解できるように説明してもらえればありがたいです。

  • ユークリッド互除法の意義

    ２つの数の最大公約数の求め方の１つとしてユークリッド互除法を学習しました。 しかし、最大公約数の求め方は素因数分解でも求められます。 共通に割り切れるもので割っていけばよいので、わざわざユークリッド互除法を使わなくてもいいのでは？と思うのですが、ユークリッド互除法を使うことのよさってあるのですか？ 回答よろしくお願いいたします。

  • 2^91-1と2^65-1の最大公約数

    2^91-1と2^65-1の最大公約数を求めるにはどうすればいいのですか？ これほど大きな値だと共通の素数で割ることもユークリッドの互除法も使えそうにありません。 ちなみにコンピュータに解いてもらったら GCD(2^91-1,2^65-1)=8191 でした。

  • 最大公約数の問題

    公約数と公倍数、という単元の問題なのですが 問2-3が「次の最大公約数を求めよ」というもので （39,18,8） などの問題が出されており、それに続く問題として 問2-4 自然数 a,b,c　に対して ((a,b),c)=(a,(b,c)) が成り立つことを示せ。 というものがあります。 最大公約数を使って解く問題だとは予想できるのですが、どのようにすれば証明できるのかが分かりません。 その前の問題では、ユークリッドの互除法を用いて最大公約数を求めていました。 どなたか分かる方がいらっしゃいましたら、ご教授願います。

  • 最大公約数を求める

    一般に、a,bが2^nくらいの整数であれば、最大公約数を求めるには、割り算も含めてn^3に比例した計算量が必要であるといわれている。しかし、これを素因数分解して求めると、素因数分解するのに、その数の平方根までの割り算が必要になるので、（√２）^nに比例した計算量が必要になる。 という説明があったのですが、”素因数分解するのに、その数の平方根までの割り算が必要になる”というのがよく分かりません。何故平方根まで割り算しないとならないのでしょうか？？？？

  • 最大公約数から最小公倍数

    ユークリッドの互除法についてなんですが、あるサイトでの公式？というか、 例》ａとｂの最大公約数を求めろ。 式がr(余り)＝a-(a÷b)b それはわかったんです。 ですが、最大公約数から最小公倍数を出すという作業がわかりません。それと、手でやっているのでコンピューターは使っていません。 わかりやすく教えてください！

  • 最大公約数

    最大公約数をだしたいとき、整数なら因数分解すればいいのは分かるんですが例えばax+b,cx+dの最大公約数を求めるようなときはどうすればよいのですか？

  • 最大公約数の出し方

    大人ですが、最大公約数の出し方につまってしまいました。 １２ ７２ １０８ ３数の最大公約数を求めるため因数分解 ２　|１２　７２　１０８ ２　|６　　３６　　５４ ３　|３　　１８　　２７ ３　|１　　　６　　　９ 　　 １　　　２　　　３ 最大公約数＝２ｘ２ｘ３ｘ３＝３６　　げっ。 正解は１２のはずなのに...。 本来は最後の３のところがいらないと思うのですが、なんて説明して いいかわかりません。こどもに。 わかるかた教えてください。なっとく次第締め切ります。

  • 素因数分解で最大公約数、最小公倍数を求める方法

    例えば 　24と18を使って素因数分解すると 2 |24　18 3 |12　 9 　　　4　3 となって共通の素因数をかけて6が最大公約数 共通の素因数と、共通の素因数を抜いた数を掛けて　72が最小公倍数 というふうに求めますが これは素数である必要はあるのですか? 別に 6|　24　18 　　　4　　3 として求めても同じではないのですか? 下の方法で何か困ることはあるのでしょうか？

  • 素因数分解で最小公倍数・最大公約数がわかるのは何故？

    この年齢になって、ちょっと恥ずかしいのですが 素因数分解について質問があります。 なぜ素因数分解で「最小公倍数」や 「最大公約数」がわかるのでしょうか？ 最大公約数の場合、例えば８と１２だと 　２）８　１２ 　　ーーーーーー 　２）４　　６ 　　－－－－－－ 　　　２　　３ 　８＝２ｘ２ｘ２ １２＝２ｘ２ｘ３ となり、どちらの数にも縦軸の２ｘ２が共通だから ４が最大公約数になる、というのはわかるんですけど なんか、いまいち説明になってないような気もします。 ２、１２、１６で最小公倍数を求めた場合 　２）８　１２　１６ 　　－－－－－－ーー 　２）４　　６　　８　 　　－－－－－－－－　 　２）２　　３　　４ 　　－－－－－－－－　 　　　１　　３　　２ 　８＝２ｘ２ｘ２ １２＝２ｘ２ｘ３ １６＝２ｘ２ｘ２ｘ２ なぜ２ｘ２ｘ２ｘ１ｘ３ｘ２で答えを出すことが 出来るのかわかりません。 いろいろ考えてはみたんですが・・・（＾＾： 猿にも理解出来るよう、教えて頂けないでしょうか？

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する