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

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

Nを自然数，$p , q(p \lt 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 \lt q \lt 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 \lt q \lt r\lt 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個以下となり，「最初」の問題は解決しました．□□