$n$ は自然数とする。1 から $n$ までの自然数で、$n$ と互いに素であるものの個数を $f(n)$ とするとき、$f(85)$ を求め、また $f(pq) = 120$ となる 2 つの素数 $p$, $q$ ($p < q$) の組の個数とそのうち最も大きい $q$ を求めよ。

1. 問題の内容

$n$ は自然数とする。1 から $n$ までの自然数で、$n$ と互いに素であるものの個数を $f(n)$ とするとき、$f(85)$ を求め、また $f(pq) = 120$ となる 2 つの素数 $p$, $q$ ($p < q$) の組の個数とそのうち最も大きい $q$ を求めよ。

2. 解き方の手順

(1) $f(85)$ を求める。

$85 = 5 \times 17$ であるから、$f(85)$ は 1 から 85 までの自然数で、5 と 17 のどちらでも割り切れないものの個数である。

1 から 85 までの自然数の中で、5 で割り切れるものは $85/5 = 17$ 個、17 で割り切れるものは $85/17 = 5$ 個ある。また、5 と 17 の両方で割り切れるもの (すなわち 85 で割り切れるもの) は 1 個である。したがって、5 または 17 で割り切れるものの個数は $17 + 5 - 1 = 21$ 個である。

よって、5 と 17 のどちらでも割り切れないものの個数は $85 - 21 = 64$ 個である。

したがって、$f(85) = 64$ である。

(2) $f(pq) = 120$ となる素数 $p$, $q$ ($p < q$) の組を求める。

$f(pq)$ は $1$ から $pq$ までの自然数の中で、$p$ と $q$ のどちらでも割り切れないものの個数である。$1$ から $pq$ までの自然数の中で、$p$ で割り切れるものは $q$ 個、$q$ で割り切れるものは $p$ 個、$p$ と $q$ の両方で割り切れるものは 1 個である。したがって、$p$ または $q$ で割り切れるものの個数は $p + q - 1$ 個である。

よって、$p$ と $q$ のどちらでも割り切れないものの個数は $pq - (p + q - 1)$ 個であるから、

$f(pq) = pq - p - q + 1 = (p-1)(q-1)$ となる。

$f(pq) = 120$ なので、 $(p-1)(q-1) = 120$ である。

$p-1 < q-1$ であり、$p-1$ と $q-1$ は自然数であるから、$120$ を 2 つの自然数の積に分解する。

$120 = 1 \times 120 = 2 \times 60 = 3 \times 40 = 4 \times 30 = 5 \times 24 = 6 \times 20 = 8 \times 15 = 10 \times 12$

$p$ と $q$ は素数であるから、$p-1$ と $q-1$ に 1 を足したものが素数になる必要がある。

$p-1 = 1$ のとき $p = 2$, $q-1 = 120$ より $q = 121 = 11^2$ (素数ではない)

$p-1 = 2$ のとき $p = 3$, $q-1 = 60$ より $q = 61$ (素数)

$p-1 = 3$ のとき $p = 4$ (素数ではない)

$p-1 = 4$ のとき $p = 5$, $q-1 = 30$ より $q = 31$ (素数)

$p-1 = 5$ のとき $p = 6$ (素数ではない)

$p-1 = 6$ のとき $p = 7$, $q-1 = 20$ より $q = 21$ (素数ではない)

$p-1 = 8$ のとき $p = 9$ (素数ではない)

$p-1 = 10$ のとき $p = 11$, $q-1 = 12$ より $q = 13$ (素数)

したがって、$f(pq) = 120$ となる素数 $p$, $q$ ($p < q$) の組は $(3, 61)$, $(5, 31)$, $(11, 13)$ の 3 組である。

これらのうち、最も大きい $q$ は 61 である。

3. 最終的な答え

$f(85) = 64$

$f(pq) = 120$ となる 2 つの素数 $p$, $q$ ($p < q$) の組は全部で 3 組あり、そのうち最も大きい $q$ は 61 である。