名古屋大学 2003年度 前期日程 第2次学力試験 整数・場合の数文系数学 第3問(a)

(1) $15=3\cdot 5$ である。$1$ から $15$ までの自然数のうち、15と互いに素でないものは、3の倍数または5の倍数である。

3の倍数は $3,6,9,12,15$ の5個、5の倍数は $5,10,15$ の3個である。このうち15は重複して数えているので、15と互いに素でないものは $5+3-1=7$ 個である。したがって $f(15)=15-7=8$ である。実際、互いに素なものは $1,2,4,7,8,11,13,14$ である。

(2) $p,q$ は互いに異なる素数である。$1$ から $pq$ までの自然数のうち、$pq$ と互いに素でないものは、$p$ の倍数または $q$ の倍数である。 $p$ の倍数は $p,2p,\dots ,qp$ の $q$ 個であり、$q$ の倍数は $q,2q,\dots ,pq$ の $p$ 個である。両方に含まれるものは $pq$ だけである。したがって、$pq$ と互いに素でないものは $p+q-1$ 個である。

よって $$f(pq)=pq-(p+q-1)=pq-p-q+1$$ であり、$f(pq)=(p-1)(q-1)$ である。

素数 $p$ ごとに $p$ の倍数を避け、さらに素数 $q$ の倍数を避ける。中国剰余定理を使わず、$1,\dots ,pq$ を $p$ 個ずつのブロックに分けて数える。

(1)

$1,\dots ,15$ のうち、3でも5でも割り切れないものは$$1,2,4,7,8,11,13,14$$の8個である。よって $f(15)=8$ である。

(2)

$1,\dots ,pq$ を$$1,\dots ,p;p+1,\dots ,2p;\dots ;(q-1)p+1,\dots ,qp$$の $q$ 個のブロックに分ける。

各ブロックには $p$ の倍数が1個あるので、それを除くと $p-1$ 個が残る。また、$q$ の倍数は全体で $p$ 個あるが、そのうち $pq$ はすでに $p$ の倍数として除かれている。したがって追加で除くのは $p-1$ 個である。

よって$$f(pq)=q(p-1)-(p-1)=(p-1)(q-1)\mathrm{.}$$