一橋大学前期2021第１問/「包除の原理」

「1050以下の素数が250個以下」
ならば，「1000 以下の素数は 250 個以下」がいえる．
1050以下の自然数で，2,3,5,7のどれとも互いに素なものの個数を数えることとし，［包除の原理］を用いて次のような「代わり」の問題を考え、証明しました．

Nを自然数，$p,q(p<q)$を素数とする．
自然数$Npq(=M)$以下の$p,q$のどちらとも互いに素な自然数の個数を求める．
$p$の倍数は，
$p,2p,\cdots ,(Nq)p$の$Nq=\frac{M}{p}$個，
同様にして，$q$の倍数は，$Np=\frac{M}{q}$個，
$pq$の倍数は，$N=\frac{M}{pq}$個，
したがって，どちらとも互いに素なものは，
$$Npq-(Nq+Np-N)$$
$$=N(p-1)(q-1)=M(1-\frac{1}{p})(1-\frac{1}{q})．$$
Nを自然数，$p,q,r(p<q<r)$を素数とする．
自然数$Npqr(=M)$以下の$p,q,r$のどれとも互いに素な自然数の個数を求めると，
$$N(p-1)(q-1)(r-1)$$
$$=M(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})．$$
同様にして，
Nを自然数，$p,q,r(p<q<r<s)$を素数とする．
自然数$Npqrs(=M)$以下の$p,q,r,s$のどれとも互いに素な自然数の個数を求めると，
$$N(p-1)(q-1)(r-1)(s-1)$$
$$=M(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})(1-\frac{1}{s})．$$
$1050=2\cdot 3\cdot 5^2\cdot 7$以下の，2,3,5,7のどれとも互いに素なものの個数は，
$$1050(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})(1-\frac{1}{7})$$
$$=5(2-1)(3-1)(5-1)(7-1)=240．$$
したがって，「代わり」の事柄は証明されました．
この240個の中に，2,3,5,7を除く，1000以下の素数はすべて属しているので，問題の素数は250個以下となり，「最初」の問題は解決しました．□□