【数学A】例題4.1.9：互いに素な自然数の個数（One More）★★★

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.1.9：互いに素な自然数の個数（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$n$以下の自然数で，$n$と互いに素である自然数の個数を$f(n)$とするとき，次の値を求めよ．ただし，$p,q$は異なる素数とする．

(1) $f(72)$

(2) $f(pq)$

(3) $f(p^n)$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.1.9の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) $72=2^3\cdot 3^2$であるから，72と互いに素ではない自然数は，2または3の倍数である．

72以下の自然数について，

2の倍数は36個，3の倍数は24個，6の倍数は12個

したがって，72以下の自然数のうち2または3の倍数は，

\[
36+24-12=48(\text{個})
\]

よって，$f(72)=72-48=24$

(2) $p,q$はともに素数であるから，$pq$と互いに素ではない自然数は，$p$または$q$の倍数である．

$pq$以下の自然数について，

$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個

したがって，$pq$以下の自然数のうち$p$または$q$の倍数は，$p+q-1$個

よって，$f(pq)=pq-(p+q-1)=pq-p-q+1$

(3) $p^n$以下の自然数について，$p$の倍数は，$p^n=p\cdot p^{n-1}$より，$p^{n-1}$個

よって，$f(p^n)=p^n-p^{n-1}$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.1.9：互いに素な自然数の個数（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

$n$以下の自然数で，$n$と互いに素である自然数の個数を$f(n)$とするとき，次の値を求めよ．ただし，$p,q$は異なる素数，$m$は自然数とする．

(1) $f(75)$

(2) $f(p^2q)$

(3) $f(2^m)$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.1.9の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(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^2q$と互いに素ではない自然数は，$p$または$q$の倍数である．

$p^2q$以下の自然数について，

$p$の倍数は，$p^2q=pq\cdot p$より，$pq$個，

$q$の倍数は，$p^2q=p^2\cdot q$より，$p^2$個，

$pq$の倍数は，$p^2q=p\cdot pq$より，$p$個

したがって，$p^2q$以下の自然数のうち$p$または$q$の倍数は，$pq+p^2-p$個

よって，$f(p^2q)=p^2q-(pq+p^2-p)=p^2q-p^2-pq+p$

(3) $2^m$以下の自然数について，2の倍数は，$2^m=2\cdot 2^{m-1}$より，$2^{m-1}$個

よって，$f(2^m)=2^m-2^{m-1}$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.1.9の側注：互いに素な自然数の個数（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
2，3，6の倍数の個数をそれぞれ求める．$72=2\cdot 36,72=3\cdot 24,72=6\cdot 12$

% 側注2
\begin{align*}
&n(A\cup B)\\
=&n(A)+n(B)-n(A\cap B)
\end{align*}

% 側注3
$p\cdot q$より，$q$個，$q\cdot p$より，$p$個と考えてもよい．

% 側注4
$1\cdot p,2\cdot p,\ldots,p^{n-1}\cdot p$の$p^{n-1}$個

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A4.1.9の側注：互いに素な自然数の個数（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
\begin{align*}
&n(A\cup B)\\
=&n(A)+n(B)-n(A\cap B)
\end{align*}

% 側注2
$1\cdot p,2\cdot p,\ldots,(pq-1)\cdot p,pq\cdot p$の$pq$個

% 側注3
\begin{align*}
&n(A\cup B)\\
=&n(A)+n(B)-n(A\cap B)
\end{align*}

% 側注4
$1\cdot 2,2\cdot 2,\ldots,2^{m-1}\cdot 2$の$2^{m-1}$個

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A4.1.9の考え方・補足など：互いに素な自然数の個数（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 考え方
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

補集合を用いるとよい．$n$以下の自然数のうち，$n$と1以外の公約数をもつ自然数の個数を求め，全体の個数$n$から引く．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 余談
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

自然数$N$が$N=p^lq^mr^n\cdots(p,q,r,\ldots$は素数)と素因数分解されているとき，1から$N$までの自然数のうち，$N$と互いに素であるものの個数は次のようになることが知られている．

\[
\phi(N)=N(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})\cdots(\text{個})
\]

この関数$\phi(N)$をオイラー関数という．なお，オイラー関数は解答に用いるのではなく，検算で用いるとよい．例えば，(1)のような$N=72$のとき，$72=2^3\cdot 3^2$は，$\phi(72)=72(1-\frac{1}{2})(1-\frac{1}{3})=24$のように計算できる．