ユークリッドの互除法で最大公約数を求める

質問

＜問題＞
n^2+2n+1とn+3の最大公約数になりうる値をすべて求めよ

＜解答＞
整数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である。

例えば、
n+3=5 すなわちn=2のとき、g(5,4)=1
n+3=6　・・・ g(6,4)=2
n+3=8 ・・・　g(8,4)=4
となり、最大公約数として可能な数は1,2,4の３つの自然数である。

＜質問＞
「g(n+3,4)として考えうるのも1,2,4である。」
が必要条件であることはわかります。
その後、解答でなにがしたいのかよくわかりません。
なぜ例示しただけで「最大公約数として可能な数は1,2,4の３つの自然数である。」といえるのでしょうか？
よろしくお願いします。

＜思ったこと＞
必要十分条件なら「g(n+3,4)として考えうるのも1,2,4である」場合、「4の正の約数は1,2,4である」であることを示すことになると思います。

回答No.5

stomachman · ベストアンサー

「…になりうる値をすべて求めよ」という習慣的な言い方は、論理的に正確な表現に言い直せば、

★〔「…になりうる値」を全て含み、【「…になりうる値」ではない値】はひとつも含まない集合〕の要素を列挙せよ。

という問いなんです。さらに、「…になりうる値」というのは、

★ 「…になる例」が少なくともひとつ存在するような値

という意味なんです。
　このように読み替えるんだという事は、（言葉遣いの習慣の問題ですから）憶えて戴くしかありません。

　で、その答となる集合を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の必要十分条件である」と言っても同じ事ですね。

お礼

回答ありがとうございます。
パーフェクトな解説に感謝です。

もう少しでこの問題における必要条件、十分条件の理解をせずにおいておくところでした。

回答No.4

中村 拓男（@tknakamuri）

〉必要十分条件なら「g(n+3,4)として考えうるのも1,2,4である」場合、
〉「4の正の約数は1,2,4である」であることを示すことになると思います。

何故必要充分性を吟味するのか不明ですが、
これはp→qの形になっていないですね。2っとも恒真命題です。

素直に考えれば

2数がn+3と4で与えられるならば、最大公約数は 1, 2,4のいずれかである。

が真であることを示すのがこの問題です。

もちろんこの逆はなりたたないです。

お礼

解答ありがとうございます。
解説にちーさく必要条件がうんたら～と書いてあってそのせいで変に考えすぎていたようです。

回答No.3

中村 拓男（@tknakamuri）

4に対する最大公約数は1、2、4しかありません。
従って、この3個が存在することが示せたのであれば
もうやるべきことは残っていません。

回答No.2

noname2727

＞＞整数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であることを示しています

だからあとは存在を示せばよくて、その後存在を例示してるのではないでしょうか。

お礼

回答ありがとうございます。
「存在するとすれば、」ということですね。
わかりました。

回答No.1

Tacosan

問題は「最大公約数になりうる値をすべて求めよ」でしょ?

で, 実際に「最大公約数になる」ことを言ってるんだよね?

どこに疑問がある?

補足

細かいかもしれませんが、なりうる値を示すだけなら別に例示する必要がないと思いました。