- ベストアンサー
離散数学の証明
離散数学の証明 次の問題の証明方法が分かりません。助けてください。 任意の整数m,nに対して次の(1)(2)を証明せよ。 (1)m,n≠0のとき、dがm,nの正の公約数であるならば、gcd（m/d,n/d）＝gcd（m,n）/d (2)m,n≠0のとき、gcd（m/gcd(m,n),n/gcd(m,n)）＝１ ちなみにxが非負整数でm,nの最大公約数であるとき、gcd（m,n）=xと表されます。 よろしくお願いします。
- exymezxy09
- お礼率94% (194/205)
- 数学・算数
- 回答数2
- ありがとう数10
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
ふつう、（２）は自明のことというか、＝１だからこそ最大公約数という気がするんだけど・・・ということで、（２）の方が基本的なので、（２）から。 gcd（m,n）=xとするとき、ｍ＝ａｘ、ｎ＝ｂｘと置ける。 gcd（m/gcd(m,n),n/gcd(m,n)）＝gcd（ａ，ｂ）で、これが１ではないとすると、 ａ，ｂが１ではない公約数を持つことになる（これをｐ（ｐ＞１）とする）。 すると、ａ＝ｅｐ，ｂ＝ｆｐと置け、ｍ＝ｅｐｘ、ｎ＝ｆｐｘとなって、ｐｘもｍ，ｎの公約数。 ところが、ｐ＞１なのでｐｘはｘよりも大きい。これはｘがｍ、ｎの「最大」公約数であることと矛盾する。 よってgcd（m/gcd(m,n),n/gcd(m,n)）＝１ （１）は簡単でしょ。
その他の回答 (1)
- B-juggler
- ベストアンサー率30% (488/1596)
こっちが先でしたか。もう一つありましたね。 これも同じ。 素因数分解の形で ｍ，ｎ を丁寧に表すと、 何も考える必要なんてないよ。難しく考えてはいけない。 数学は、「物事を理論的に、順序だてて考える」という、ものですから 最初から難しく考える、というのは不合理だよ。 どこまで簡単に分かるか、それを書いてみるだけでも ずいぶんと違うからね。 この（２）は、互いに素 ということになるけど、 公約数は存在しないということだね。もう一問のほうで出てきているけれど、 互いに素って言うのはちょっと注意しながら扱わないといけないから、 「素因数分解」の形で出すこと！ が先。 がんばってね。
お礼
ご指摘ありがとうございます。 頑張って考えます。
関連するQ&A
- 離散数学の証明問題
離散数学の証明問題 合同でないことを≡×と表します。 Pを素数とし、a≡×0(mod p)とする。また、aの位数をdとする。 このとき、次のことを示せ。 (1)整数nに対して、a^n≡1(mod p)であるならば、かつそのときに限り、d|n (2)dはp-1の約数である。 (3)整数i,jに対してa^i≡a^j (mod p)であるならば、かつそのときに限り、i≡j(mod p) (1)はFermatの小定理を使うと思うのですが、いまいち解法が浮かびません。 (2)はFermatの小定理から自明に思えますが、厳密に証明しないといけないみたいです。 (3)は証明方法がまったく分かりません。 分かる方、証明お願いします。
- ベストアンサー
- 数学・算数
- gcdとlcmについての証明
最大公約数gcdと最小公倍数lcmについての質問です。 正の整数n1,n2,......,nlについて gcd(n1,n2,n3,....,nl)=gcd(gcd(gcd(n1,n2),n3),...,nl) を示せ。 という問題なのですが、これはどのように証明すればよいのでしょうか？nが3つまでのは証明できたのですが、l個での証明の仕方が分かりません。 lcmについてもgcdの証明と同様にすれば示せるのでしょうか？
- ベストアンサー
- 数学・算数
- わかりません・・・。
二つの自然数を引数として与えられて，それらの最大公約数を返す関数 int gcd(int m, int n) { /* … */ }を作成し，それを利用して入力された二つの正整数の最大公約数を求めるプログラムを作り方を教えてください。 ユークリッドの互除法を使い、関数を使う事が条件なのですが全然わかりません。 #include<stdio.h> int gcd(int m, int n) if(m>n) {m%n} if(m%n==0) printf("最大公約数は%d",n); ←このあたりがわかりません else if (n%(m%n)) printf("最大公約数は%d",n%(m%n)); int main( void ) { int na, nb; puts(""二つの整数を入力してください。)； printf("整数1：")； scanf("%d",na); printf("整数2：")； scanf("%d",nb); printf("最大公約数は%dです。\n",gcd(int m, int n)); return0; }
- ベストアンサー
- C・C++・C#
- 最大公約数と最小公倍数の関係
ある二つの正の整数の最大公約数と最小公倍数をかけたものは、元の二つの数字をかけたものと等しいっていうことは言えますか？ つまり、最大公約数をgcd、最小公倍数をlcmとあらわすことにして、 正の整数ｍとｎについて、 gcd（m , n）・lcm（m , n）＝m・n は成り立つかどうかを教えてください。 できればその理由（証明）も添えてください。 協力お願いします！！
- 締切済み
- 数学・算数
- 数学 問題
数学でいくつか質問があります。 １．任意の整数ｍ、ｎに対して、以下のうちどれが真であるか (A)mのn+1乗≧mのn乗 (B)(m+1)のｎ乗≧mのn乗 (C)nx≧n(x+1) (D)nx≦n(x+1) (E)none 整数なので、負も含めるので、力技ではダメなのでしょうか。 ２．２個のサイコロを３回投げた時、２個の目が同じであることが少なくとも１っ回である確率 ３．3の3乗の3乗を５で割った余り これも力技の方が早いのでしょうか。 ４．n>2である時、次のうちどれが最大か (A)nのn乗 (B)nの2n乗 (C)nの４n乗 (D)（4n）のn乗 (E)（2ｎ)のn乗 私の答えは(D)なのですが。 よろしくお願い致します。
- ベストアンサー
- 数学・算数
お礼
すごくヒントになり、助かりました！ どうもありがとうございました。