OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

最大公約数、定理の証明

  • 困ってます
  • 質問No.108693
  • 閲覧数524
  • ありがとう数5
  • 気になる数0
  • 回答数2
  • コメント数0

a,bを a=b=0 でない2つの整数とするとき

a*r + b*s =(a,b)
      のような整数 r,s が存在する
---------------------------------------
という定理があって、この定理を使って
次の定理を証明せよ、という問題なのですが…

d=(a,b)
整数 n は、 n|d のとき、その時に限り
a と b の公約数である
… n|d は dはnで割り切れるという意味


どういうふうに導くのかわかりません。
d=(a,b)= a*r + b*s = t*n  (tは整数)
とおく、ここまで何となくやってみたのですが…
「公約数」であることを示す方法、目標が見えません。

教えてください。
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

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

  • 回答No.2
レベル8

ベストアンサー率 65% (17/26)

n|d ⇒ 公約数 を示すのは簡単ですよ.∃r,s a*r + b*s = dは使わなくてもできますね.

dはaの約数なので,

a = p * d = p * q * n

などと表せ,nがaの約数であることがわかります.bについても同様ですね.

公約数 ⇒ n|d を示すのは,a*r + b*s = dを使うとできるようです.
お礼コメント
noname#5824

この回答をもらって、しばらく悩んでいました。
両方向から、攻めればいいんですね。

公約数→n|d にかなり悩まされましたけど、
解けてみればなんてことない…でも、すっきりして面白いですね。

とても参考になりました、ありがとうございました。
投稿日時 - 2001-07-24 22:30:38
-PR-
-PR-

その他の回答 (全1件)

  • 回答No.1
レベル10

ベストアンサー率 33% (34/103)

(a,b)の定義がないので定理と言われても何を主張した定理なのか分かりませんが、文脈から察するにa=2, b=3に対して12が     12 = 2*3 + 3*2 のようにa*r + b*sの形に表せるような整数r, sが存在するとき、     12 = (2,3) と表すと言う事でしょうか? それにしても左辺は一つの数を表していますが右辺は数の性質を表していて、これを等号で結んでしまって良い ...続きを読む
(a,b)の定義がないので定理と言われても何を主張した定理なのか分かりませんが、文脈から察するにa=2, b=3に対して12が
    12 = 2*3 + 3*2
のようにa*r + b*sの形に表せるような整数r, sが存在するとき、
    12 = (2,3)
と表すと言う事でしょうか?
それにしても左辺は一つの数を表していますが右辺は数の性質を表していて、これを等号で結んでしまって良いのでしょうか?

しかし(a,b)の定義に関しては求められている証明にはあまり関係ないので置いておきましょう。
    n|(a*r + b*s) ⇔ n|a かつ n|b
を証明すれば良いんですよね?しかし証明は出来ません。なぜなら反例があるからです。
a=2, b=3, r=2, s=1, n=7 とおくと
    n|(a*r + b*s) ⇔ 7|7 ⇔ true
ですが
    n|a ⇔ 7|2 ⇔ false
    n|b ⇔ 7|3 ⇔ false
です。

何か問題を読み違えていらっしゃいませんか?
補足コメント
noname#5824

すみません、何の前置きもなく書いてしまいました。

(a,b) というのは、aとbの最大公約数です。
ものによっては gcd(a,b)とも書いてあります。
投稿日時 - 2001-07-24 19:57:28

このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ