小学生向けの結論
合同な長方形をたてと横に何枚かずつ並べて、長方形を作ります。
下の図は、長方形をたてに2枚、横に3枚並べた長方形です。これに対角線を引きます。
| 2 | ||
| 1 | 2 | 3 |
このとき、対角線が通る長方形の枚数は、\[(たての枚数)+(横の枚数)-(たてと横の最大公約数)\]になります。ただし、対角線が頂点のみを通る長方形は、数えていません。
結論
合同な正方形を横に$a$枚、縦に$b$枚並べて長方形を作る。説明のため、正方形としておきます。$a\geqq b$とする。$a$と$b$の最大公約数を$g$とする。
下図は、$a=3$、$b=2$のときの例。正方形だと思ってください。
| 2行1列 | 2行2列 | 2行3列 |
| 1行1列 | 1行2列 | 1行3列 |
正方形のうち、この対角線が内部を通るものの枚数を$N(a,b)$とする。(つまり、対角線が頂点のみを通る正方形は、数えない。) \[N(a,b)=a+b-g\]
縦・横の枚数が互いに素であるとき
$a$と$b$は互いに素(最大公約数が$1$)とする。
1
$N(a,1)=a$である。
2
$b\geqq 2$とする。
前置き
正方形を並べた大きい長方形を、$xy$平面上で、原点、$(a,0)$、$(0,b)$を頂点とする長方形とみなす。対角線は、線分$\begin{cases} y=\dfrac{b}{a}x \\ 0\leqq x\leqq a \end{cases}$である。
正方形の縦の並びを「列」と呼ぶ。最も左の列を「第1列」、最も右の列は「第$a$列」と呼ぶ。
また、対角線が内部を通る正方形のうち、第$k$列のものの個数を$N_{a b}(k)$とする。$N_{a b}(k)\geqq 1$である。また、$\displaystyle N(a,b)= \sum_{k=1}^a N_{a b}(k)$である。
直線$y=\dfrac{b}{a}x$の傾き$\dfrac{b}{a}$は、1より小さい。よって、$1\leqq N_{a b}(k)\leqq 2$、つまり$N_{a b}(k)=1,2$である。
$\ell$を$b$未満の正の整数とする。
直線$y=\dfrac{b}{a}x$と直線$y=\ell$の交点の$x$座標は、$\dfrac{a}{b}\ell$である。交点は$b-1$個ある。
場合分け
$x=1,2,\cdots, a-1$のとき、任意の$\ell$に対し、\[x\neq\dfrac{a}{b}\ell\]である。
$N_{ab}(k)=1$のとき、$k-1\lt x \lt k$で直線$y=\dfrac{b}{a}x$と直線$y=\ell$は交わらない。
よって、任意の$\ell$に対し、$N_{ab}(k)=2$となる$k$が存在し、$k-1\lt x \lt k$で直線$y=\dfrac{b}{a}x$と直線$y=\ell$が交わる。つまり、$k-1\lt\dfrac{a}{b}\ell\lt k$となる。
\[k-1\lt \dfrac{a}{b}\ell\lt k\]ならば、\[k \lt \dfrac{a}{b}\ell+1 \lt \dfrac{a}{b}\ell+\dfrac{a}{b}=\dfrac{a}{b}(\ell+1)\]である。したがって、各$\ell$に対して、\[k-1\lt \dfrac{a}{b}\ell\lt k\]となる$k$の値は1つだけである。
また、$N_{ab}(k)=2$となる任意の$k$に対し、ある$\ell$が存在し、$k-1\lt x \lt k$で$y=\dfrac{b}{a}x$と$y=\ell$が交わる。
よって、$N_{ab}(k)=2$となるとき、\[k-1\lt \dfrac{a}{b}\ell\lt k\]となる$k$と$\ell$は1対1に対応する。
$N_{ab}(k)=2$となる$k$は$b-1$個あり、$N_{ab}(k)=1$となる$k$は$a-b+1$個ある。
よって、$N(a,b)=a+b-1$である。
まとめ
結局、$a$と$b$が互いに素のとき、全ての$b$に対して、$N(a,b)=a+b-1$。
互いに素でないときも
正の整数$m$に対し、正方形を横に$ma$個、縦に$mb$個並べて長方形を作る。この長方形を、$xy$平面上で原点、$(ma,0)$、$(0,mb)$を頂点とする長方形とみなす。対角線は、線分$\begin{cases} y=\dfrac{b}{a}x \\ 0\leqq x\leqq ma \end{cases}$である。
この長方形の対角線のうち$0\leqq x\leqq a$の部分は、正方形を横に$a$個、縦に$b$個並べた長方形の対角線になっている。
よって、任意の正の整数$m$に対し、$N(ma,mb)=m N(a,b)$となる。
$a$と$b$の最大公約数を$g$とし、$a=ga^{\prime}$、$b=gb^{\prime}$とする。$a^{\prime}$と$b^{\prime}$は互いに素。
任意の$a$、$b$に対し、$N(a,b)=N(ga^{\prime},gb^{\prime})=gN(a^{\prime},b^{\prime})=g(a^{\prime}+b^{\prime}-1)=a+b-g$である。