締切済み 最大公約数 2007/05/11 15:53 素因数分解を使わない最大公約数の求め方で、二つはユークリッドの互除法を利用するというのはわかったのですが、３つはどのようにして求めればいいと思いますか？ みんなの回答 （2） 専門家の回答 みんなの回答 komimasaH ベストアンサー率16% (179/1067) 2007/05/12 11:48 回答No.2 ２つの数の最大公約数をまず求める。 その数と残りの数の最大公約数が３つの数の最大公約数。 ということでＮＯ．１さんの回答どおり。 通報する ありがとう 0 広告を見て他の回答を表示する（1） Tacosan ベストアンサー率23% (3656/15482) 2007/05/11 15:57 回答No.1 2回やればいいんじゃないかと思いますが. 通報する ありがとう 0 カテゴリ 学問・教育数学・算数 関連する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 として求めても同じではないのですか? 下の方法で何か困ることはあるのでしょうか？ 素因数分解で最小公倍数・最大公約数がわかるのは何故？ この年齢になって、ちょっと恥ずかしいのですが 素因数分解について質問があります。 なぜ素因数分解で「最小公倍数」や 「最大公約数」がわかるのでしょうか？ 最大公約数の場合、例えば８と１２だと ２）８ １２ ーーーーーー ２）４ ６ －－－－－－ ２ ３ ８＝２ｘ２ｘ２ １２＝２ｘ２ｘ３ となり、どちらの数にも縦軸の２ｘ２が共通だから ４が最大公約数になる、というのはわかるんですけど なんか、いまいち説明になってないような気もします。 ２、１２、１６で最小公倍数を求めた場合 ２）８ １２ １６ －－－－－－ーー ２）４ ６ ８ －－－－－－－－ ２）２ ３ ４ －－－－－－－－ １ ３ ２ ８＝２ｘ２ｘ２ １２＝２ｘ２ｘ３ １６＝２ｘ２ｘ２ｘ２ なぜ２ｘ２ｘ２ｘ１ｘ３ｘ２で答えを出すことが 出来るのかわかりません。 いろいろ考えてはみたんですが・・・（＾＾： 猿にも理解出来るよう、教えて頂けないでしょうか？ ユークリッドの互除法について ユークリッドの互除法を使って最大公約数、整数解を求められると聞いたのですが、イマイチ要領がつかめません。 もしよろしければ、どなたかユークリッドの互除法での最大公約数、整数解の求め方を教えてください。 高校数学 最大公約数，最小公倍数 問題． 3つの自然数４５，６３，ｎ の最大公約数が９，最小公倍数が３１５０であるとき，ｎを求めよ なんですが，いろいろ素因数分解とかやってみて考えてみたのですが解けません． どなたか，解説してほしいです． よろしくお願いします．． 最小公倍数と最大公約数でわからないことがあります 例えば24と20という数字があって この二つの共通の素因数2でわると それぞれ12と10 さらに共通の素因数2でわると それぞれ6と5 6と5は互いに素 この素因数を掛けて 2×2=4 最大公約数4 互いに素の6と5を掛けて6×5=30 この30を共通の素因数の2×2 をかけて120 この120が最小公倍数 となると参考書に書いてあるのですが なぜこのような計算をして最大公約数と最小公倍数を求めてることが出来るのでしょうか? センター試験のために数Aの勉強をしているのですが そこまで考えずに、この計算をすると、それが求められるのだと 丸暗記するしかないでしょうか? 出来れば理解をしたいと思っています。よろしくお願いします。 あまり数学が得意ではないので簡単な表現で説明していただけると助かります。 多項式の最大公約数について 多項式の最大公約数について 以下の解き方が数学的に問題がないのか教えていただきたいのです。 (試験で○をもらえるのでしょうか？) 例えば多項式 x^3-x^2-x-2 , x^4+x^3+3x^2+2x+2 , 2x^3+x^2+x-1 の最大公約数ですが、 x=2の時、x^3-x^2-x-2=0なので、比較的簡単に(x-2)(x^2+x+1)となります。 残りの式に因数として(x^2+x+1)が含まれることを仮定し、(x^2+x+1)で除すと、 x^4+x^3+3x^2+2x+2=(x^2+2)(x^2+x+1) 2x^3+x^2+x-1=(2x-1)(x^2+x+1) 要約すると、簡単な式を因数分解し、その因数を利用して 複雑な式の因数分解をしていく方法なのですが、ユークリッド などを使った解法の方が良いのでしょうか？ ご意見を御願いします。 素因数分解ができない？ １２３、２０５の最大公約数はいくつでしょう？ 素因数分解をして求めたいのですが、 １２３は３で割って４１ ３＊ ２０５は５で割って４１ ５＊ となるのでしょうか？ その後の素因数分解が続きません。 すいませんが、教えてください。 よろしくお願いします。 ３つの数の最大公約数？？（急いでます！） 出かける前にどうしても知りたいのです！ ３つの数の最大公約数は、 どれか２つの最大公約数を求めるだけで できますか？？ 例えば（８，２０，２８）の最大公約数は どの組み合わせでも ４と出ますよね。 どなたか回答宜しくお願いします！！ 最大公約数 最大公約数 952と748の最大公約数の求め方教えてください。 素因数分解について 中学三年で習う素因数分解についてです。 素因数分解をするときに、数字を最小の素数で割らなければいけない理由は何ですか? また、素因数分解を利用して最大公約数と最小公倍数を求めるための式(共通の素数をかけていくという式です)の意味が理解できません。。 何故あの式で最小公倍数と最大公約数が出るんでしょうか? テストが近いのでかなり焦っています。 どなたか詳しく説明してくださる方、回答よろしくお願いします。 最大公約数 教えてください！ 「７と０」の最大公約数と「７と－７」の最大公約数は、どちらも７になるのはなぜですか？ できたら、詳しい解説よろしくお願いします。 最大公約数 0と0の最大公約数は何ですか? また、0と10、１０と０の最大公約数は何ですか？ 理由もおねがいします。
