数研出版 メジアン 集合の問題

個別指導塾講師をしている者です。
生徒からの質問で、恥ずかしながらわからない問題があって困っています。どなたか解答お願いいたします。

問題
９で割り切れる整数全体の集合をＡ、
１５で割り切れる整数全体の集合をＢとする。
Ｃ＝{x+y｜x∈Ａ,y∈Ｂ}とするとき、
Ｃは３で割り切れる整数全体の集合（Ｄとする）と一致することを示せ。


Ｃ⊂ＤかつＤ⊂Ｃを示せばよい。

Ｃ⊂Ｄについては、
z∈Ｃとすると、
ｚ＝ｘ＋ｙ＝９ｌ＋１５ｍ＝３（３ｌ＋５ｍ）
よって、Ｃ⊂Ｄ

ここまではわかりました。

このあとのＤ⊂Ｃの証明がわかりません。
どなたか解答をお教えください。

No.1 回答者： ItachiMasamune 回答日時： 2010/04/03 23:41

3の倍数を整数nを使って3nと表します。

任意の整数nについて
3n = 9l + 15mをみたす整数の組(l,m)があることを示せばいい。
式を簡単にして、n=3l+5m　…※
数学的帰納法を使います。

n=0のとき(l,m)=(0,0)
n=1のとき(l,m)=(-3,2)
n=2のとき(l,m)=(-1,1)
n=k(k=0,1,2,…)のとき※を満たす(l,m)が存在すると仮定し、その解を(l,m)=(p,q)とすると
k=3p+5q
ここでk+3=3(p+1)+5qとなるため、n=k+3のときは(p+1,q)は※を満たす。

以上より、nが非負整数のとき、任意のnについて※を満たす整数の組(l,m)が存在することが示された。
nが負の整数のときはl,mの符号を逆にすればいい。

こんな感じで示せます

この回答へのお礼

なるほど！帰納法を使えばいいのですね。
思いつきませんでした。
助かりました。明日生徒に説明してきます！
ありがとうございました。

お礼日時：2010/04/04 00:09

No.2 ベストアンサー 回答者： kabaokaba 回答日時： 2010/04/03 23:41

9*2+15*(-1) = 3

であることから，
3の倍数を 3n と表せば
3n = 9*2*n + 15*(-1)*n
= 2*(9n) +(-1) *(15n)
よって
3の倍数は9の倍数と15の倍数の和

====================
これはユークリッドの互除法
「互いに素な整数m,nにたいして
整数a,bで am+bn=1 となるものが存在する」
がベースになっているだけです．

この回答へのお礼

おぉそっか！
これなら、帰納法を使わずとも
3n=9*(2n)+15*(-n)
ということだけで
Ｄ⊂Ｃが言えそうですね。

ありがとうございました！

お礼日時：2010/04/04 00:20