S={ax+by | x yは自然数}
について、Sはある整数n以上のすべての整数を含むことを示し、そのようなnの最小値を求めよ
この問の解説の前半部分の論述の意味が取れません、
どのような方針でこの解説は作られたのでしょうか
![]() |
No.32458 - 2015/08/06(Thu) 10:49:11
| ☆ Re: お願いします / IT | | | (2)の証明を少し手順を変えて書いてみます。
n=c[1]+1b=c[2]+2b=c[3]+3b=...=c[a]+ab …(1)
とするとc[1],c[2],c[3],...,c[a]は１以上の整数。
c[1],c[2],c[3],...,c[a]の中にaの倍数があることを示せばよい。
(背理法による）
c[1],c[2],c[3],...,c[a]の中にaの倍数が一つもないと仮定する。
c[1],c[2],c[3],...,c[a]をaで割った余りをr[1],r[2],r[3],...,r[a]とすると
これらの中には互いに等しいものがある（鳩ノ巣原理）ので
r[i]=r[j]=r,(1≦i＜ｊ≦a)とする
すなわちc[i]=ak+r,c[j]=am+r,(k,mは整数)とおける
(1)より ak+r+ib=am+r+jb
移項して整理 a(k-m)=b(j-i)
a,bは互いに素なので、j-iはaの倍数
ところが1≦j-i≦a-1なので矛盾。
よってc[1],c[2],c[3],...,c[a]の中にはaの倍数がある。
# どのステップが分からないかを明記（引用）して質問してください。
# n=1a+c[1]=2a+c[2]=3a+c[3]=...=ba+c[b] …(1)' としても同様です。
|
No.32499 - 2015/08/08(Sat) 12:39:02 |
|
