• ベストアンサー

ユークリッドの互除法

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

質問者が選んだベストアンサー

  • ベストアンサー
  • rnakamra
  • ベストアンサー率59% (761/1282)
回答No.4

m=sn+tを変形し t=m-sn ここでm=ax,n=ay ,a=gcd(m,n)とする。当然x,yは互いに素である。 t=ay-s*ax=a(y-sx) となります。 gcd(n,t)=gcd(ax,a(y-sx))=a*gcd(x,y-sx) となります。 gcd(x,y-sx)=1を示せばよいのですが、背理法をつかうとよいでしょう。つまり、gcd(x,y-sx)=b (b≠1)とするとx,yが互いに素であることに矛盾することが示せます。

その他の回答 (3)

  • chie65535
  • ベストアンサー率43% (8512/19350)
回答No.3

http://www.cwo.zaq.ne.jp/bfaby300/math/gojyo.html

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

a≧b かつ b≧a なら a=b.

  • hugen
  • ベストアンサー率23% (56/237)
回答No.1

n = △・gcd(n,t) m=□・n+t = ○・gcd(n,t) だから　、gcd(m,n)≧gcd(n,t)

nemuine8
質問者

お礼

不等式だと公約数であっても最大公約数とは限らないとおもうですけど

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

関連するQ&A

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

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

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

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

  • ユークリッド互除法

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

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

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

  • ユークリッドの互除法

    ユークリッドの互除法を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となってしまいます。どうしたら正確な答えが出るでしょうか？

  • ユークリッドの互除法

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

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

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

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

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

  • ユークリッド互除法

    ユークリッド互除法を使用して最大公約数を求めるプログラムを、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; } これを、もっと簡略化できるらしいのですが、これ以上できることはありますか？ どう考えてもわかりません

  • ユークリッドの互除法

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

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する