整数集合の表現
こんにちは。M{R}です. 今回の記事では，整数についてのある興味深い性質について扱おうと思います. 具体値を用いたものは大学入試問題でも出題されていますが，一般的な場合についてみていくことにしましょう.
$a$,$b$は互いに素な自然数とし，$an+bm$($n,m\in\mathbb{Z}$)の形で表される数全体の集合を$\mathrm{M}$とする. このとき，$\mathrm{M}$は整数全体の集合を表す.
この事実を証明して行く上で，いくつかの補題を示すこととします.
$\mathrm{M}$の正の最小元が$d$のとき，$\mathrm{M}$は$d$の倍数全体の集合に一致.
以下では，$d$の倍数全体の集合を$\mathrm{K}$と置く.
題意を示すには，
任意の$d$の倍数は$\mathrm{M}$の要素であること
とそれに加えて，
$\mathrm{M}$の任意の要素は$d$の倍数であること
を示せば良い.
まず，前者について示す. $d$は$\mathrm{M}$の要素なので，
$d=an_{1}+bm_{1}$
と表せる. したがって，
$dk=kan_{1}+kbm_{1}=a(kn_{1})+b(km_{1})$
なので，$n_{2}=kn_{1},m_{2}=km_{1}$とおけば，$n_{2},m_{2}\in\mathbb{Z}$なので，任意の$d$の倍数である整数は$\mathrm{M}$の要素であることが示された.
次に，後者については背理法で示す. つまり，$d$の倍数でない$\mathrm{M}$の要素$x$が存在すると仮定する. このとき，整数$y,r$を用いて
$x=dy+r$ $(1 \leq r \leq d-1)$
と書くことが出来て，さらに$x$が$\mathrm{M}$の要素であることより，
$x=an_{3}+bm_{3}$
と表され，一方，$dy$が$d$の倍数であることより，上の議論から，
$dy=an_{4}+bm_{4}$
と表せる. したがって，
$r=a(n_{3}-n_{4})+b(m_{3}-m_{4})$
と表せて，$n_{3}-n_{4},m_{3}-m_{4}\in\mathbb{Z}$より，$r$は$\mathrm{M}$の要素となるが，$1 \leq r \leq d-1$より，これは，$d$が$\mathrm{M}$の正の最小元であることに反する. したがって，仮定は誤りで，$\mathrm{M}$の任意の要素は$d$の倍数である.
以上，前者と後者の議論より，補題１が示された. (証明終)
では，次に補題２を示しましょう. 補題２に関しては，比較的有名な事実でしょう.
$a,b$が互いに素なら，$\mathrm{M}$の正の最小元$d=1$
まず，$a$,$b$はそれぞれ以下のように表せる.
したがって，$a,b$は$\mathrm{M}$の要素であり，ここで，補題１で示した内容について，$\mathrm{M}$の任意の要素は$d$の倍数であるので，これらを合わせて考えると$a,b$は$d$で割り切れる. つまり，$d$は$a,b$の公約数となるが，$a,b$が互いに素であることより，$d=1$であることが分かる. (証明終)
最後に，次の補題３を示します.
$a,b$の最大公約数$g$は$d$に一致する
補題１の内容より，補題３を示すことは，$\mathrm{M}$は$g$の倍数全体の集合であることを示すことと同義である.
まず，$a,b$の最大公約数が$g$であることより，互いに素な自然数$a',b'$を用いて，$a=a'g，b=b'g$と表せる. したがって，
$an+bm=(a'g)n+(b'g)m=(a'n+b'm)g$ $\cdots$(A)
と表せる. 今，$a',b'$が互いに素な自然数であるとき，補題２と補題３より，$a'n+b'm$は$d=1$の倍数全体の集合となるので，つまり，これは整数全体の集合を表す. (A)より，このとき，$\mathrm{M}$は$g$の倍数全体の集合であることが示された. したがって，$g=d$であることが示された. (証明終)
以上より，$an+bm$($a,b\in\mathbb{N},n,m\in\mathbb{Z}$)の形の数全体の集合は，
$g(=gcd(a,b))$の倍数全体の集合
を表し(補題１)，$a,b$が互いに素な自然数のとき，$an+bm$($n,m\in\mathbb{Z}$)の形の数全体の集合は
と一致することが分かります. 実際の入試問題ではこのような問題がありました.
どのような負でない２つの整数$m$と$n$をもちいても
$x=3m+5n$
とは表すことができない正の整数$x$をすべて求めよ。
ちなみにこれを解くだけなら，ここまで大袈裟なことはしなくても良くて，$n=0,1,2$の時を見ればもう結果は明らかです。この問題の詳しい解答は世の中にありふれていますので，読者さん自身が良さそうなものを参考にしてもらえばと思います. それでは今回はここで. 最後まで読んで頂きありがとうございました. ぷぇっ～(⊂ ๑•﹏•๑｀∩)
この記事を高評価した人
この記事に送られたバッジ
投稿者
