数学の質問スレ　part20

a≡c(mod b) (0<c<b) とする。
このとき、ax≡cx(mod b)である。
cと1がmod bで合同のとき、(1)の成立は自明。
そこで、cと1がmod bで合同で無い時を考える。
　cとbが互いに素だから、ck≡d (mod b) (0<d<b)となる自然数k,dの組が存在する。
　　ここで、数列d_l,k_lを以下の(ア)(イ)を満たす様に定める。
　　　(ア)
　　　d_1=d,k_1=k
　　　(イ)
　　　d_lと1がmod bで合同で無いとき、
　　　(d_l)(k_l)≡d_(l+1) (mod b) ただし0<d_(l+1)<d_l
　　　を満たすよう、k_(l+1),d_(l+1)を定める。
　　このとき、d_nとbは互いに素で、また、全ての自然数lについてd_l>d_(l+1)だから、
　　d_n≡1 (mod b)となるnが存在しないと仮定すると、
　　全ての自然数nに対して、d_(n+1)が存在するので、
　　dより小さく、bと互いに素である自然数が無限に存在することになり矛盾する。
　従って、d_n≡1(mod b)となるnが存在する。
このnについて、
n=1のとき、x=k_1
n>1のとき、x=Σ(l=1,n-1)k_l
とすれば(1)は成立する。

>>foursite　たぶんあってると思うよ！！！

集合 S={ax+by|x,yは整数} を考える。
Sの中には正の整数が存在し、その最小値をm(0)とする。
当然、ax(0)+by(0)=m(0) を満たす整数x(0),y(0)が存在する。

今 ax+by=m とおいてmをm(0)で割った余りをrとする（0≦r＜m(0)）。
当然、m=qm(0)+r を満たす整数qが存在する。

ax+by=qm(0)+r=q(ax(0)+by(0))+r だから
a(x-qx(0))+b(y-qy(0))=r。つまり r∈S である。
0≦r＜m(0) とm(0)はSに含まれる正の整数の最小値であることからr=0。
よってm=qm(0)。

ところでa∈S、b∈Sより、a,bは共にm(0)で割り切れる。
つまりm(0)はa,bの正の公約数であるが、aとbが互いに素であることからm(0)=1。

終わり！！！

あら、もう解答出てたのね。。
一応参考にしてくださいな！！！

>>425 ｸﾞｯｼﾞｮﾌﾞ

既出だが一応。
a,bを整数の定数、x,yを整数として、
P(x,y)=xa+yb全体の集合をMとする。
任意のp,q,x,yについて、P(x,y)+P(p,q)∈M,P(x,y)-P(p,q)∈Mだから
x=p,y=qとして0∈M,x=-p,y=-qとして-P(x,y)∈M
したがって、あるn=P(α、β)が存在してM={nz|z∈Z}・・・(1)

また、Mの元で正であるものの集合は空でないから、連続公理によりその最小元Nがとれる。
すべてのNの倍数はMに属する。任意のx∈Mをとって、
x=yN+r(0≦r<N)とおく。r=x-yN∈Mだから、Nの定義よりr=0　x=yn
したがって、(1)におけるP(α、β)はただひとつに決まる。
∴ある整数d>0がただひとつ決まり、Mとdの倍数全体の集合が一致する。

ここで、a=P(1,0)∈M,b=P(0,1)∈Mだから、aとbが互いに素であるとき、d=1