◆茨城県 こんにちは さんからの解答。
以下、x座標,y座標ともに整数である点の事を格子点と呼ぶ。
【補題１】
nを負でない整数、a,bを互いに素である自然数とする。
n=a*s+b*t,かつ0≦t≦a-1となる整数s,tが存在する。
【証明】
n,n-b,n-2*b,・・・・,n-(a-1)*bのa個の数を考える。
これらの中にbで割り切れるものが必ず存在するはず。
もしそうでなければ、n,n-b,n-2*b,・・・・,n-(a-1)*bをaで割った余りは
1,・・・,a-1のa-1通り。
よって、n,n-b,n-2*b,・・・・,n-(a-1)*bの中にaで割った余りが同じ2数が必ず存在する。
これらをn-u*b、n-v*bとする。
（ただし0≦u＜v≦a-1）
よって、(n-u*b)-(n-v*b)=b*(v-u)がaで割り切れる。
aとbが互いに素よりv-uがaで割り切れる事になるが、
これは0＜v-u＜aに反する。
n,n-b,n-2*b,・・・・,n-(a-1)*bの中にaで割り切れるものが必ず存在する
これをn-t*bとする。
tは0≦t≦a-1なる整数であることがわかる。
n-b*t=a*sとなる、整数tが存在する。
よって、n=a*s+b*tかつ0≦t≦a-1となる整数s,tが存在する。
【補題２】
a,b,nは補題１と同じものとする。
a*x+b*y=nとなる整数x,yは補題１のs,tを用いて
x=s-b*k,y=t+a*k(kは任意の整数をとる)と書ける。
【証明】
a*x+b*y=n・・・(1)
補題１より以下のような整数s,tが存在する。
a*s+b*t=n・・・(2)
(1)-(2)より
a(s-x)=b*(y-t)
aとbは互いに素より、y-tはaで割り切れる。
整数kを用いて、y-t=a*kとかける
a*b*k=a*(s-x)ゆえに
x=s-b*k
よって、
x=s-b*k,y=t+a*k (kは任意の整数)と書ける。
逆に、x=s-b*k,y=t+a*k (tは任意の整数)のとき
a*x+b*y=a*(s-b*k)+b*(t+a*k)=a*s+b*t=n
となって、x,yが元のa*x+b*y=nを満たしていることが示された。
証明終
このときのx,yを、xk=s-b*k、yk=t+a*kと書く
さて、a,bをa＜bなる自然数、nを0以上の整数とする。
nをa*bで割り商をq、余りをrとおく。
n=(a*b)*q+r、0≦r≦a*b-1
r＞a*b-a-bのとき
| s= | n-b*t a | =b*q+ | r-b*t a | ＞b*q+ | a*b-a-b-a*b+b b | =b*q-1 |
| s=b*q+ | r-b*t a | ＜b*q+ | a*b a | =b*q+b |
| よって、求める個数はq+1=[ | n a*b | ]+1個となる。 |
| このとき求める個数は[ | n a*b | ]+1個である。 |
| このとき求める個数は[ | n a*b | ]個である。 |
| A(n)=[ | n a*b | ]+1 |
| A(n)=[ | n a*b | ]となる。 |
◆出題者のコメント。
こんにちはさん、ありがとうございます。
私が用意していた解答と同じです。
ただ、私よりも解き方が丁寧でした。