- ベストアンサー
ユークリッドの互除法
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
a,bの最大公約数をkとすると、 r=a-bq r=ka'-kb'q r=k(a'-b'q) なので、割り切れる。
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
どこまで考えましたか? 少なくとも前者についてはほぼ自明ですよ.
お礼
よく考えたら出きました。 ありがとうございます。
関連するQ&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'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のほうが大きくなるのでしょうか？ どなたかよろしければ ご教授お願い致します。
- 締切済み
- 数学・算数
- ユークリッドの互除法について
ユークリッドの互除法を使って最大公約数、整数解を求められると聞いたのですが、イマイチ要領がつかめません。 もしよろしければ、どなたかユークリッドの互除法での最大公約数、整数解の求め方を教えてください。
- 締切済み
- 数学・算数
- ユークリッド互除法の意義
２つの数の最大公約数の求め方の１つとしてユークリッド互除法を学習しました。 しかし、最大公約数の求め方は素因数分解でも求められます。 共通に割り切れるもので割っていけばよいので、わざわざユークリッド互除法を使わなくてもいいのでは？と思うのですが、ユークリッド互除法を使うことのよさってあるのですか？ 回答よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 高校数学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の公約数とも言える理由は何なのでしょうか？ どなたかよろしければ ご教授お願い致します。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法がわからない
ユークリッドの互除法は、どうして割っていくと公約数が求められるのですか？ 公約数を求めるやり方はわかったのですが、どうしてそうなるのかわかりません。 調べて説明や証明を読んでもチンプンカンプンでした。 わかりやすく教えていただけたら嬉しいです。 よろしくお願いします。
- 締切済み
- 数学・算数
- ユークリッドの互除法
二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法について
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となってしまいます。どうしたら正確な答えが出るでしょうか？
- ベストアンサー
- JavaScript
- 【 ユークリッドの互除法が成り立つ理由の証明につい
【 ユークリッドの互除法が成り立つ理由の証明について】 実教出版数学Aのp89に記載されている、以下の定理と証明で G＝G' となる理由について、私の解釈が数学的に正しいのか、その他アドバイス等、ご教示よろしくお願いします。 ただし、Thm．1を前提としています。 【Thm．1 割ったときのあまりと公約数】 自然数a，bについて，aをbで割った余りをrとするとき 1.aとbの公約数は、rの約数になっている。 2.bとrの公約数は、aの約数になっている。 【Thm2．割ったときのあまりと最大公約数】 自然数a,bについて、aをbで割ったときのあまりをrとするとき、aとbの最大公約数的Gと、bとrの最大公約数Gは等しい。 Pf．aとbの最大公約数Gもrの約数となるから、Gはbとrの公約数である。bとrの最大公約数はG'であるから G≦G'……(1) 同様に、bとrの最大公約数G'はaの約数であるから G'≦G……(2) (1)，(2)より G＝G'証明終 【解釈】 証明したいのはG＝G'である。 (1)はG＜G' または G＝G'という意味である。 また、(2)はG'＜G または G'＝Gという意味である。 (1)，(2)より G'＜G＜G' または G＝G'かつG'＜G＜G' または G'＝Gがいえる。 または、というのはどちらか一方が成り立てば良いという意味である。ここでもし、G＝G' またはG'＝Gが成り立てば命題が証明できたことになるが、どちらも成り立たないとすると、 G'＜G＜G' または G＜G'＜G…☆ が成り立たなければならない。 ところが、☆が成り立つときもG＝G'が成り立つので、結局 G＝G'である。 証明終 具体的な例で示すと、G'＝3のとき 3＜G＜3 つまりG＝3 G＝3より 3＜G'＜3 つまりG'＝3 したがって、 G＝G' であることがいえる。 数学が得意な方には言語化せずにもわかることかもしれませんが、記号の意味を正しく理解して使いたいと思い、掘り下げて考えてみました。 誤りの指摘や、今後の学習に関するアドバイスなどをいただければ幸いです。
- 締切済み
- 数学・算数
お礼
ありがとうございます。