締切済み

ユークリッドの互除法について

2006/01/13 08:21

　ユークリッドの互除法を使って最大公約数、整数解を求められると聞いたのですが、イマイチ要領がつかめません。　　もしよろしければ、どなたかユークリッドの互除法での最大公約数、整数解の求め方を教えてください。

noname#15346

数学・算数
回答数2
ありがとう数0

みんなの回答 （2）
専門家の回答

みんなの回答

yoikagari
ベストアンサー率50% (87/171)

2006/01/13 18:16 回答No.2

こちらをご参照ください。

参考URL：: http://www004.upp.so-net.ne.jp/s_honma/euclid/euclid.htm

kigoshi
ベストアンサー率46% (120/260)

2006/01/13 08:49 回答No.1

参考ＵＲＬをどうぞ

参考URL：: http://homepage3.nifty.com/sugaku/gojyohou.htm

関連するQ&A

ユークリッドの互除法

二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。これまでの書き込みを見ても理解ができませんでした。どなたか分かりやすくお教えください。
ユークリッド互除法の意義

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

２９４４１と３２９３４の最大公約数をユークリッド互除法で求めて答えが１とでました。さらに最小公倍数を求めろとあるのですが、ユークリッド法でどうやって最小公約数を求めるのですか？
ユークリッドの互除法について

13を9で割ると　1.444…の循環小数で表せますが，このわり算の筆算ができる理由をユークリッドの互除法で説明したいと考えています。ユークリッドの互除法について　いくつかの文献を読みましたが　どれも　最大公約数を求める方法として紹介されています。筆算ができる理由としてユークリッドの互除法をどのように使えばよいか　ご回答の程よろしくお願いします。
ユークリッドの互除法

ユークリッドの互除法の処方でつまづいています。どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(x,y)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか？よろしくお願いします。
ユークリッドの互除法がわからない

ユークリッドの互除法は、どうして割っていくと公約数が求められるのですか？公約数を求めるやり方はわかったのですが、どうしてそうなるのかわかりません。調べて説明や証明を読んでもチンプンカンプンでした。わかりやすく教えていただけたら嬉しいです。よろしくお願いします。
ユークリッドの互除法

早急に解答求めています、ご協力よろしくお願いします(>_<) 1.自分では簡単に素因数分解できない2つの整数(どちらとも9桁以上の整数)を決めてその最大公約数をeuclidの互除法で求めよ。 2.1で求めた数が最大公約数であることを示せ。できれば途中式も省かないで書いていただきたいです。よろしくお願い申し上げます。
ユークリッドの互除法

ユークリッドの互除法の証明の一部なのですが aをで割った商をbあまりをrとすると a=bq+r であるので　r=a-bq である。ここで、この右辺はa bの最大公約数でわり切れるのは、なぜか教えて下さい。あと　a bの最大公約数がrとb の公約数でもあるのはなぜですか？お願いします。
ユークリッドの互除法について

質問させて頂きます。　　（有理整数環Ｚにωを添付した整域Z[ω]をＲとする。Ｒ=Z[ω]={a+bω}において） ω=(-1+√3i)/2 とした場合、α=16+14ω、β=11+9ω　の最大公約元、最小公倍元の求め方をユークリッド互除法にて教えて下さい。よろしくお願いいたします。
ユークリッドの互除法について

こんにちは。高校数学A、ユークリッドの互除法についてです。問題集の整数aを正の整数bで割った余りをrとする。aとbの最大公約数はbとrの最大公約数と一致することを証明せよ。という問題の解説で aをbで割った商をqとすると a=bq+r aとbの最大公約数をg1、bとrの最大公約数をg2とし、 a=a'g1,b=b'g1：b=b”g2,r=r'とする。ただし、a',b',b”,r'は整数で、a'とb',b”とr'はそれぞれ互いに素である。このとき、 r=a－bq=a'g1－b'g1q=(a'－b'q)g1 a'－b'rは整数であるから、g1はrの約数、★すなわちbとrの公約数になる。 ★よってg1≦g2 以下略この★の部分がわかりません。 g1がrの約数になると bとrの公約数とも言える理由は何なのでしょうか？そしてなぜg1よりg2のほうが大きくなるのでしょうか？どなたかよろしければご教授お願い致します。
ユークリッドの互除法

ユークリッドの互除法がよくわかりません。 m>nとして(m=nならばm=gcd(m,n)) m=sn+t (n>t)とあらわせる。ここでgcd(m,n)=gcd(n,t)となるのがわかりません。　これがわかったらあとはあまり部分が０になるまでやればそのときに最大公約数が出るというのはわかるのですが、、、
数学のユークリッド互除法についてです。

数学のユークリッド互除法についてです。 [４２０１ｘ－３８５９ｙ=１の１組の非負整数解を求めよ]の解答と解法を教えて下さい。何度計算しても負の値になってしまいます。よろしくお願いします。
ユークリッドの互除法

ユークリッドの互除法をJavascriptで書こうとしてます。以下のように書いたのですが、うまく動きません。(45と60の最大公約数を求めるプログラム) <script> window.alert(gcd(45, 60)); function gcd(a, b){ var r=a%b; if(r==0){ return b; }else{ gcd(b, r); } } </script> undifinedとなってしまいます。どうしたら正確な答えが出るでしょうか？
ユークリッドの互除法について（高１数学）

いつも大変お世話になっております。ユークリッドの互除法についての質問です。計算のやり方は知っているので、答えは出せるのですが、なぜそのように計算すると計算結果が最大公約数になるのかがよくわかりません。私の持っている問題集には、以下のように解説があります。　「N＝M×ａ＋Lのとき、NとMの最大公約数は、MとLの最大公約数と等しい。　　　　理由は、　　N＝M×ａ＋Lなので、MとLの公約数は、Nの約数　・・・（１）　　L＝N－M×ａなので、NとMの公約数は、Lの約数　・・・（２）」とあります。　（１）、（２）のそれぞれは理解できるのですが、その先がよくわかっておりません。　　アドバイスいただけると助かります。　よろしくお願い致します。
高校数学A ユークリッドの互除法についてです。

こんにちは。高校数学A、ユークリッドの互除法についてです。問題集の整数aを正の整数bで割った余りをrとする。aとbの最大公約数はbとrの最大公約数と一致することを証明せよ。という問題の解説で aをbで割った商をqとすると a=bq+r aとbの最大公約数をg1、bとrの最大公約数をg2とし、 a=a'g1:b=b”g2,r=r'とする。ただし、a',b',b”,r'は整数で、a'とb',b”とr'はそれぞれ互いに素である。このとき、 r=a－br=a'g1－b'g1q=(a'－b'q)g1 a'－b'rは整数であるから、g1はrの約数、★すなわちbとrの公約数になる。以下略この★の部分がわかりません。 g1がrの約数になると bとrの公約数とも言える理由は何なのでしょうか？どなたかよろしければご教授お願い致します。
ユークリッド互除法

ユークリッド互除法を使用して最大公約数を求めるプログラムを、C言語で書いてみました。 #include <stdio.h> main() { int a, b, t; scanf("%d %d", &a, &b); if(a<b){ t=a; a=b; b=t; } while(b != 0){ t = a % b; a = b; b = t; } printf("GCD = %d\n", a); return 0; } これを、もっと簡略化できるらしいのですが、これ以上できることはありますか？どう考えてもわかりません
ユークリッド互除法について

ユークリッド互除法について詳しく勉強したいのですが、教えていただけないでしょうか？よろしくお願いします。
拡張ユークリッドの互除法

mod 7の世界において2x≡1を満たすxを拡張ユークリッドの互除法を用いて求める方法がわかりません。ユークリッドの互除法は理解しています。
ユークリッドの互除法についての問題です。

ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき　ax≡b (mod5) (2)aが4の倍数でないとき　ax≡b (mod4) 誰か教えてください。
【数学】ユークリッドの互除法のごじょほうってどうい

【数学】ユークリッドの互除法のごじょほうってどういう意味ですか？ユークリッドの互除法を考えたユークリッドってユークリッド幾何の人と同じ人物ですか？別人ですか？ユークリッドってどんな人だったのか教えてください。偉伝の伝説が聞きたいです。あとユークリッド幾何とユークリッドの総除法ってどんなことなのか教えてください。簡単に。

ユークリッドの互除法について

みんなの回答

関連するQ&A

ユークリッドの互除法

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

ユークリッド互除法

ユークリッドの互除法について

ユークリッドの互除法

ユークリッドの互除法がわからない

ユークリッドの互除法

ユークリッドの互除法

ユークリッドの互除法について

ユークリッドの互除法について

ユークリッドの互除法

数学のユークリッド互除法についてです。

ユークリッドの互除法

ユークリッドの互除法について（高１数学）

高校数学A ユークリッドの互除法についてです。

ユークリッド互除法

ユークリッド互除法について

拡張ユークリッドの互除法

ユークリッドの互除法についての問題です。

【数学】ユークリッドの互除法のごじょほうってどうい

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

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

ユークリッドの互除法について

みんなの回答

関連するQ&A

ユークリッドの互除法

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

ユークリッド互除法

ユークリッドの互除法について

ユークリッドの互除法

ユークリッドの互除法がわからない

ユークリッドの互除法

ユークリッドの互除法

ユークリッドの互除法について

ユークリッドの互除法について

ユークリッドの互除法

数学のユークリッド互除法についてです。

ユークリッドの互除法

ユークリッドの互除法について（高１数学）

高校数学A ユークリッドの互除法についてです。

ユークリッド互除法

ユークリッド互除法について

拡張ユークリッドの互除法

ユークリッドの互除法についての問題です。

【数学】ユークリッドの互除法のごじょほうってどうい

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

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

カテゴリ
一覧

専門家に質問してみよう
専門家登録