a1,a2,・・・,an,bを整数とするとき、方程式
a1x1+a2x2+・・・+anxn=bが整数解を持つための必要十分条件は(a1,a2,・・・,an)ｌb
である理由が分かりません。よろしく御願いします。
|
No.14011 - 2011/06/18(Sat) 16:29:29
| ☆ Re: 高3 / シャロン | | | a[1],a[2],...,a[n]がすべて0、ではないとしてよい。
a[1]x[1]+a[2]x[2]+...+a[n]x[n]の形で表される整数全体からなる集合をＡとする。
Ａ≠{0}から、Ａの元である正の整数には最小値が存在する。(∵z∈Ａ→-z∈Ａ)
この正整数をdとすると、d=(a[1],a[2],...,a[n])[☆]であり、Ａ={zd|zは整数}である。[★]
★の証明
Ａの元の倍数はあきらかにＡの元であるので、{zd|zは整数}⊆Ａ。
また、z(≠0)∈Ａとすると、z=qd+r、0≦r＜dとなる整数q、rが存在し、仮定から、z∈Ａ。また、qd∈Ａ。
∴r=z-qd∈Ａ。
いま、0≦r＜dかつdがＡの正の最小元であるから、r=0。
したがって、Ａ⊆{zd|zは整数}
以上より、Ａ={zd|zは整数}
[★証明終わり]
☆の証明
任意のa[k]について、a[k]=a[k]･1+Σ_{i≠k、1≦i≦n}^{n}(a[i]･0)から、すべてのkについて、a[k]∈Ａであり、d|a[k]。よって、dはa[1],a[2],...,a[n]すべての公約数である。
また、d∈Ａより、d=a[1]x[1]+a[2]x[2]+...+a[n]x[n]と表せることから、a[1],a[2],...,a[n]すべての公約数はdの約数である。
以上よりd=(a[1],a[2],...,a[n])
[☆証明終わり]
ここで、a[1]x[1]+a[2]x[2]+...+a[n]x[n]=bが整数解を持つ条件はb∈Ａであり、Ａはdの(負まで含めた)倍数全体の集合であるから、(a[1],a[2],...,a[n])|bが解を持つ条件である。
QED
|
No.14013 - 2011/06/18(Sat) 18:35:39 |
| ☆ Re: 高3 / ウツボ | | | 元とは何ですか？ｚとは何ですか？またzdとは何ですか？最小限とは最小の元ということですか？Σ_{i≠k、1≦i≦n}^{n}(a[i]･0)はどういう意味ですか？
よろしく御願いします。
|
No.14022 - 2011/06/19(Sun) 04:13:40 |
| ☆ Re: 高3 / シャロン | | | 元...要素ともいいます。集合に含まれる個々のモノです。z∈Ａなら、zは集合Ａの元です。
z...任意の元です。ただここでは、Ａとの関係を論じていますから、整数とみなしてかまいません。特に「z∈Ａ→-z∈Ａ」とは、「ある元zがＡの元なら、-zもＡの元である」という命題ですから、Ａの要素であるものについて考えればいいです。(たとえばπなどはＡの要素でないので、zとして考える意味がありませんね)
zd...整数zをつかってzdの形に表される数、つまりdの(負の数まで含む)倍数を表します。
最小元...単に最小元でなく、「正の」最小元である点に注意を。負の数まで考えれば、Ａにはいくらでも小さい要素が存在します。
Σ_{i≠k、1≦i≦n}^{n}(a[i]･0)...技巧的に書きすぎました(反省)。1以上n以下かつkはでないi(「_{i≠k、1≦i≦n}」の部分)についての、a[i]･0の総和、という意味で書きました。(^{n}は不要でした。)
要は、a[k]=a[1]･0+a[2]･0+...+a[k]･1+...+a[n]･0と、各a[k]はa[1]x[1]+a[2]x[2]+...+a[n]x[n]の形で表される、という命題です。
|
No.14024 - 2011/06/19(Sun) 06:23:44 |
| ☆ 別解 / angel | | | こういう別解もあります。シャロンさんのとは別のアプローチで。
必要条件は自明なのでおいとくとして、十分条件「(a[1],…,a[n])|bならば、方程式a[1]x[1]+…+a[n]x[n]=bが整数解を持つ」の方をいきます。これをnに関する帰納法で説明します。
つまり、方程式の左辺の項数が増えても同様に成立しますよ、という方針でいくわけです。
n=1の時成立するのもやっぱり自明なので、n=kの時⇒n=k+1の時の推移について。
このとき、次の事実を利用します。
☆p,qが互いに素ならば、s,tの方程式 ps+qt=1 は整数解を持つ
※なぜかはまた後で触れます
後はちょっくら場合わけ。
(i) a[k+1]=0 の場合、帰納法の仮定より、明らかに方程式は解を持つ
(ii) a[k+1]≠0 の場合
g=(a[1],…,a[k],a[k+1]) と置くと、(a[1],…,a[k]), a[k+1] はともにgの倍数。
よって、あるp,qに対して、
(a[1],…,a[k])=gp, a[k+1]=gq
かつ、p,qは互いに素
※もし互いに素でないとすると、gが最大公約数であることに矛盾する
p,qが互いに素であるため、ps+qt=1 なる整数s,tが存在する
ここで、方程式を次のように変形する
a[1]x[1]+…+a[k]x[k]+a[k+1]x[k+1]=b
⇔ (a[1]x[1]+…+a[k]x[k]-bps)+(a[k+1]x[k+1]-bqt)=0
⇔ (a[1]x[1]+…+a[k]x[k]-gp・sb/g)+(gqx[k+1]-gq・tb/g)=0
(a[1],…,a[k])=gpかつb/gが整数のため、帰納法の仮定により方程式 a[1]x[1]+…+a[k]x[k]=gp・sb/gは整数解を持つ
よって、その解にx[k+1]=tb/gという条件を付け加えたものは、元の方程式の整数解になっており、n=k+1の時も解を持つことを示す
大体こんな感じで。
なお、
☆p,qが互いに素ならば、s,tの方程式 ps+qt=1 は整数解を持つ
については、このように変形して考えます。
★0≦t≦p-1 を満たすある t に関して、qtをpで割った余りが1に等しいものが存在する
なぜかというと、
もし余りが1に等しいものが存在しないとなると、0≦t≦p-1 の p通りに対して、qt の中で p で割った余りが等しいものが存在する。( pで割った余りも最大でp通りだから )
その等しくなるときの t を t1,t2 (t1＞t2) とおくと、qt1-qt2 は p の倍数、つまりあるmに対して、qt1-qt2=pm と表せる。
しかし、q(t1-t2)=pm となり、1≦t1-t2≦p-1 であるため、p,q が互いに素であることに矛盾
となるからですね。
後は、qt=pm+1 となる t,m があるわけなので、そのような t に対して s=-m とすれば ps+qt=1 となり、整数解の存在が示せたことになります。
|
No.14050 - 2011/06/21(Tue) 00:59:19 |
|
