問題
を自然数とするとき，でとの最大公約数が1となる自然数の個数をとする．
(1) を求めよ．
(2) ，を互いに異なる素数とする．このときを求めよ．
出典：名古屋大学 2003年度 前期日程 第2次学力試験 文系 第3問(a)
方針
は から までのうち と互いに素なものの個数である。(1)は なので、3の倍数と5の倍数を除いて数える。(2)は と互いに素でない数が、 の倍数または の倍数であることを使い、重複する だけを一度戻す。
解答
(1)
である。 から までの自然数のうち、15と互いに素でないものは、3の倍数または5の倍数である。
3の倍数は の5個、5の倍数は の3個である。このうち15は重複して数えているので、15と互いに素でないものは 個である。したがって である。実際、互いに素なものは である。
(2)
は互いに異なる素数である。 から までの自然数のうち、 と互いに素でないものは、 の倍数または の倍数である。 の倍数は の 個であり、 の倍数は の 個である。両方に含まれるものは だけである。したがって、 と互いに素でないものは 個である。
よって であり、 である。