問題
座標平面において，座標と座標がともに整数である点を格子点という．また，2つの格子点を結ぶ長さ1の線分から両端の点を除いたものを格子辺という．次の問に答えよ．
(1) 点を通る直線(は定数)はの範囲で何個の格子辺と交わるか．
(2) を2以上の整数とする．点を通る曲線(はにより定まる定数)は，の範囲で何個の格子辺と交わるか．
方針
格子辺は格子点を除いた単位の縦横線分なので、曲線が縦の格子線または横の格子線を格子点以外で通過した回数を数える。格子点を通ると、その点自体は格子辺に含まれないため、縦線・横線の両方の数え上げから除く。(1)は直線上の内部格子点数を から求める。(2)は内部の整数 で も整数になる点数 を、既約分母 の 乗が を割る条件で分類する。
解答
(1)
点 を通る直線 は原点も通るので である。したがって直線は である。 の範囲にある縦の格子線は の629本である。また の範囲にある横の格子線は の5399本である。
ただし、直線が格子点を通る場合、その点は格子辺から除かれているので、縦の格子辺との交点にも横の格子辺との交点にも数えない。直線上の内部格子点を数える。 であり、 と は互いに素であるから、原点と の間の格子点は の89個である。
よって縦の格子辺と交わる回数は 、横の格子辺と交わる回数は である。したがって求める個数は である。
(2)
曲線 が点 を通るので であり、 である。この曲線は で単調に増加するので、縦格子線と横格子線をそれぞれ1回ずつ横切る。ただし内部格子点を通る場合は、(1)と同じく縦・横の両方から除く。
内部の格子点数を とする。縦格子線は629本、横格子線は5399本なので、求める個数は である。
内部格子点を数える。 で整数 をとり、 と既約分数で表す。すると 、 は の約数である。曲線上の 座標は である。 と は互いに素なので、 が整数であるための条件は である。
素因数分解すると である。 のとき、 となる は の約数である。このとき可能な既約分数 は、 を既約化して得られるものすべてであり、個数は29個である。したがって で、交わる格子辺の個数は である。 のとき、 となる は の約数である。同様に、可能な既約分数は を既約化して得られる5個である。したがって で、交わる格子辺の個数は である。 のとき、 を満たす は存在しない。したがって内部格子点はなく、 である。よって交わる格子辺の個数は である。
以上より、答えは
である。