% 例題A4.1.9：互いに素な自然数の個数 （One More）★★★
$n$以下の自然数で,$n$と互いに素である自然数の個数を$f(n)$とするとき,次の値を求めよ.ただし,$p,q$は異なる素数とする. (1)$f(72)$(2)$f(p q)$(3)$f\left(p^n\right)$
% 解答（例題A4.1.9）
(1)$72=2^3 \cdot 3^2$であるから,72と互いに素ではない自然数は,2または3の倍数である. 72以下の自然数について, \begin{center} 2の倍数は36個,3の倍数は24個,6の倍数は12個 \end{center} したがって,72以下の自然数のうち2または3の倍数は,$$36+24-12=48(\text{個})$$よって,$f(72)=72-48=24$(2)$p,q$はともに素数であるから,$p q$と互いに素ではない自然数は,$p$または$q$の倍数である.$p q$以下の自然数について, \begin{center}$p$の倍数は,$1 \cdot p,2 \cdot p,\ldots,(q-1)p,pq$の$q$個,$q$の倍数は,$1 \cdot q,2 \cdot q,\ldots,(p-1)q,pq$の$p$個,$p$の倍数かつ$q$の倍数は,$pq$の1個 \end{center} したがって,$p q$以下の自然数のうち$p$または$q$の倍数は,$p+q-1$個 よって,$f(p q)=p q-(p+q-1)=p q-p-q+1$(3)$p^n$以下の自然数について,$p$の倍数は,$p^n=p \cdot p^{n-1}$より,$p^{n-1}$個 よって,$f\left(p^n\right)=p^n-p^{n-1}$
% 問題A4.1.9
$n$以下の自然数で,$n$と互いに素である自然数の個数を$f(n)$とするとき,次の値を求めよ.ただし,$p,q,r$は異なる素数とする. (1)$f(75)$(2)$f(p^2 q)$(3)$f\left(2^m\right)$
% 解答A4.1.9
(1)$75=3 \cdot 5^2$であるから,75と互いに素ではない自然数は,3または5の倍数である. 75以下の自然数について, 3の倍数は25個,5の倍数は15個,15の倍数は5個 したがって,75以下の自然数のうち3または5の倍数は,$25+15-5=35(\text{個})$よって,$f(75)=75-35=40$(2)$p,q$はともに素数であるから,$p^2 q$と互いに素ではない自然数は,$p$または$q$の倍数である.$p^2 q$以下の自然数について, \begin{center}$p$の倍数は,$p^2q=pq \cdot p$より,$pq$個,$q$の倍数は,$p^2q=p^2 \cdot q$より,$p^2$個,$p q$の倍数は,$p^2q=p \cdot pq$より,$p$個 \end{center} したがって,$p^2 q$以下の自然数のうち$p$または$q$の倍数は,$pq+p^2-p$個 よって,$f(p^2 q)=p^2 q-(pq+p^2-p)=p^2 q-p^2-pq+p$(3)$2^m$以下の自然数について,2の倍数は,$2^m=2 \cdot 2^{m-1}$より,$2^{m-1}$個 よって,$f\left(2^m\right)=2^m-2^{m-1}$
