- ベストアンサー
ユークリッドの互除法で最大公約数を求める
- ユークリッドの互除法を使って、n^2+2n+1とn+3の最大公約数になりうる値を求める方法について解説します。
- 最大公約数を求めるためには、ユークリッドの互除法を利用します。具体的には、n+3と4の最大公約数を求めることで、n^2+2n+1とn+3の最大公約数を求めることができます。
- ユークリッドの互除法では、2つの数の最大公約数が1であれば、それらの数は互いに素といえます。ですので、n+3と4の最大公約数を求めることで、n^2+2n+1とn+3の最大公約数が1,2,4のいずれかになることがわかります。
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
「…になりうる値をすべて求めよ」という習慣的な言い方は、論理的に正確な表現に言い直せば、 ★〔「…になりうる値」を全て含み、【「…になりうる値」ではない値】はひとつも含まない集合〕の要素を列挙せよ。 という問いなんです。さらに、「…になりうる値」というのは、 ★ 「…になる例」が少なくともひとつ存在するような値 という意味なんです。 このように読み替えるんだという事は、（言葉遣いの習慣の問題ですから）憶えて戴くしかありません。 で、その答となる集合をAとすると、 (1) ＜解答＞の3行目までで A ⊂ {1,2,4} であることが証明できた。 ここまでで、{1,2,4}は「…になりうる値」を全て含んでいるのは確かである。けれども【「…になりうる値」でない値】も混じっているかもしれない。なので(1)の結論を「x∈{1,2,4}はx∈Aの必要条件である」と表すこともできます。 (2)＜解答＞の続きの部分では、 {1,2,4}の各要素について、それが「…になりうる値」だということを、実際に「…になる例」の存在を示す事で証明した。これで、 {1,2,4} ⊂ A であることが証明できた。 この部分の証明だけを見ると、1,2,4の他にも「…になりうる値」があるかもしれない。なので、(2)の結論を「x∈{1,2,4}はx∈Aの十分条件である」と表すこともできます。 (3) 以上から、(1)かつ(2) すなわち、 A = {1,2,4} が証明できたというわけです。これを「x∈{1,2,4}はx∈Aの必要十分条件である」と言っても同じ事ですね。
その他の回答 (4)
- 中村 拓男（@tknakamuri）
- ベストアンサー率35% (674/1896)
〉必要十分条件なら「g(n+3,4)として考えうるのも1,2,4である」場合、 〉「4の正の約数は1,2,4である」であることを示すことになると思います。 何故必要充分性を吟味するのか不明ですが、 これはp→qの形になっていないですね。2っとも恒真命題です。 素直に考えれば 2数がn+3と4で与えられるならば、最大公約数は 1, 2,4のいずれかである。 が真であることを示すのがこの問題です。 もちろんこの逆はなりたたないです。
お礼
解答ありがとうございます。 解説にちーさく必要条件がうんたら～と書いてあってそのせいで変に考えすぎていたようです。
- 中村 拓男（@tknakamuri）
- ベストアンサー率35% (674/1896)
4に対する最大公約数は1、2、4しかありません。 従って、この3個が存在することが示せたのであれば もうやるべきことは残っていません。
- noname2727
- ベストアンサー率35% (40/112)
＞＞整数a,bに対してa,bの最大公約数をg(a,b)とあらわす。 ＞＞g(n^2+2n+1,n+3)=g(n+3,4) ＞＞4の正の約数は1,2,4であるから、g(n+3,4)として考えうるのも1,2,4である。 ここまでで1，2，4以外の最大公約数がないことを示しています。 つまり、g(n+3,4)として考えうるものが存在するとすれば1,2,4であることを示しています だからあとは存在を示せばよくて、その後存在を例示してるのではないでしょうか。
お礼
回答ありがとうございます。 「存在するとすれば、」ということですね。 わかりました。
- Tacosan
- ベストアンサー率23% (3656/15482)
問題は「最大公約数になりうる値をすべて求めよ」でしょ? で, 実際に「最大公約数になる」ことを言ってるんだよね? どこに疑問がある?
補足
細かいかもしれませんが、なりうる値を示すだけなら別に例示する必要がないと思いました。
お礼
回答ありがとうございます。 パーフェクトな解説に感謝です。 もう少しでこの問題における必要条件、十分条件の理解をせずにおいておくところでした。