集合の相等の証明？の仕方を教えてください。

整数全体の集合をZとするとき、次の問いに答えよ。
集合Xを
　X=｛5m＋7n｜m,n∈Z｝
とするとき、X=Zであることを示せ。

という問題です。

解答
[１]ｋ∈X　ならば　ｋ=5m＋7n（m,n∈Z）と表される。
　　5m＋7n∈Z　であるから　ｋ∈Z
　　よって、ｋ∈X　ならば　ｋ∈Z　であるから　X⊂Z

ここまでは作ったのですが、

[２]ｚ∈Zとする。
　　ｚ＝○ｚ－○ｚ

などとして、そこから　Z⊂X　を証明するための計算を作れません。
どのような方法が可能でしょうか？

よろしくお願いします。

　　

No.3 ベストアンサー 回答者： rabbit_cat 回答日時： 2009/07/14 00:04

証明自体はよいと思います。

ユークリッドの互除法は
z＝15ｚ－14ｚ＝5・(3z)＋7・(-2z)
という、一見、かなりトリッキーな式変形を行っているところ、
で使います。
まあ、
X=｛5m＋7n｜m,n∈Z｝
なら、まあ目分量でもなんとかなるでしょうが、
たとえば、
X=｛1234567m＋7654321n｜m,n∈Z｝
として、全く同じ問題がでたら、どうでしょう。

以下、一応、トリッキーな部分の概略
まず、1234567と7654321の最大公約数をユークリッドの互除法で求めます。

246919 = 7654321 - 6×1234567　…(1)
246891 = 1234567 - 4×246919　…(2)
28 = 246919 - 246891　…(3)
15 = 246891 - 8817×28　…(4)
13 = 28 - 15　…(5)
2 = 15 - 13　…(6)
1 = 13 - 6×2　…(7)

で、
(1)の左辺を(2)の右辺に代入
(2)の左辺を(3)の右辺に代入
…
(6)の左辺を(7)の右辺に代入
ってやっていって、整理すると
573192×7654321 - 3553793×1234567 = 1
ってことがわかります。
後は、同じです。

この回答へのお礼

どうもありがとうございます。

４桁の数（例えば、2952と1368）だと

2942=1368×2+216
1368=216×6+72
216=72×3+0

なので

72=1368-216×6
　=1368-(2952-1368×2)×6
　=1368×13+2952×(-6)

と計算できるのですが、
1234567と7654321のような７桁の数になると
計算が複雑で行き詰ってしまいました。。。
エクセレントな計算方法を教えていただけるとうれしいです♪

お礼日時：2009/07/15 21:32

No.2 回答者： rabbit_cat 回答日時： 2009/07/12 00:55

一応、証明の流れを書いておくと、

m=3，n=-2とすると、
5m+7n = 1 です。（実際には、こういうm,nの組を見つけるのに、ユークリッド互助法を使います）
というわけで、
ｚ∈Z に対して、
m=3z，n=-2z とすれば
z = 5m+7n

この回答へのお礼

回答ありがとうございます。
昨夜、赤チャートの方法に基づいて解いてみたのですが
rabbit_catさんのおっしゃるようにできていますか？

お礼日時：2009/07/13 00:35

No.1 回答者： kabaokaba 回答日時： 2009/07/11 22:45

X⊂Zであることは証明するまでもないでしょう

逆の包含関係は
互いに素な整数の有名な性質そのものです．
ユークッリドの互除法そのものです．

この回答へのお礼

回答、ありがとうございます。
赤チャートのやり方に習って
なんとかやってみました。

解答
[１]ｋ∈X　ならば　ｋ=5m＋7n（m,n∈Z）と表される。
　　5m＋7n∈Z　であるから　ｋ∈Z
　　よって、ｋ∈X　ならば　ｋ∈Z　であるから　X⊂Z
[２]ｚ∈Zとする。
のつづき

　z＝15ｚ－14ｚ＝5・(3z)＋7・(-2z)　であり、
　3z∈Z,-2z∈Z　であるから　z∈X
　よって、　z∈Z　ならば　z∈X　であるから　Z⊂X
[１]、[２]から　X=Z

ここにユークリッドの互除法がたぶん使われているということなんですね。
もう少し勉強してみます！


　

お礼日時：2009/07/12 23:58