座標が両方とも整数である点を格子点と呼ぶ。原点をOとし、格子点Pに対し、線分OP上にあるOとP以外の格子点の個数をn(P)と表す。条件 $1 \le a \le 30$ かつ $1 \le b \le 30$ かつ $n(P) = 4$ を満たす格子点P(a, b)の個数を求めよ。

1. 問題の内容

座標が両方とも整数である点を格子点と呼ぶ。原点をOとし、格子点Pに対し、線分OP上にあるOとP以外の格子点の個数をn(P)と表す。条件 $1 \le a \le 30$ かつ $1 \le b \le 30$ かつ $n(P) = 4$ を満たす格子点P(a, b)の個数を求めよ。

2. 解き方の手順

点P(a, b)に対して、線分OP上にある格子点の個数n(P)は、aとbの最大公約数GCD(a, b)から1を引いた値に等しい。つまり、$n(P) = GCD(a, b) - 1$ である。

よって、$n(P) = 4$ という条件は、$GCD(a, b) - 1 = 4$、つまり$GCD(a, b) = 5$と同値である。

$1 \le a \le 30$ かつ $1 \le b \le 30$ を満たす整数の組(a, b)で、$GCD(a, b) = 5$ となるものを数える。

a = 5x, b = 5y (x, yは整数) とおくと、GCD(x, y) = 1となる。

$1 \le a \le 30$ より $1 \le 5x \le 30$ なので、$1 \le x \le 6$

$1 \le b \le 30$ より $1 \le 5y \le 30$ なので、$1 \le y \le 6$

xとyの組み合わせを考える。ただし、GCD(x, y) = 1。

(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6)

(2, 1), (2, 3), (2, 5)

(3, 1), (3, 2), (3, 4), (3, 5)

(4, 1), (4, 3), (4, 5)

(5, 1), (5, 2), (5, 3), (5, 4), (5, 6)

(6, 1), (6, 5)

上記は、x < y の場合のみを考慮している。x > y の場合も考慮する必要がある。

x=yの場合は、(1, 1)のみ。

x < y の場合

(1, 2), (1, 3), (1, 4), (1, 5), (1, 6) : 5個

(2, 3), (2, 5) : 2個

(3, 4), (3, 5) : 2個

(4, 5) : 1個

(5, 6) : 1個

(6, 0)は不可なので除外

x > y の場合

y < x なので上記と同様に考えて

(2, 1), (3, 1), (4, 1), (5, 1), (6, 1) : 5個

(3, 2), (5, 2) : 2個

(4, 3), (5, 3) : 2個

(5, 4) : 1個

(6, 5) : 1個

合計18個

x = y の場合 (1, 1) : 1個

合計：5 + 2 + 2 + 1 + 1 + 5 + 2 + 2 + 1 + 1 + 1 = 23個

したがって、条件を満たす格子点P(a, b)の個数は23個。

3. 最終的な答え

23