互いに素な整数の個数 | ドリル1（標準）
注意事項
正の整数 n と1以上 n 以下の整数について考えます。n の異なる素因数を p_1, p_2, ..., p_k とすると、n と公約数が1だけの整数の個数は、
\[
\[
\varphi(n)=n\times\left(1-\frac{1}{p_1}\right)\times\left(1-\frac{1}{p_2}\right)\times\cdots\times\left(1-\frac{1}{p_k}\right)
\]
\]
で求められます。
問題
次の n について、1以上 n 以下の整数のうち、n と公約数が1だけである整数の個数を求めなさい。
n=60n=84n=90n=126n=180n=210
解答・解説
公式では、素因数分解したときの 異なる素数 だけを使います。
- 16個
\[
60=2^2\times3\times5
\]
異なる素因数は2, 3, 5なので、
\[
\varphi(60)=60\times\frac12\times\frac23\times\frac45=16
\] - 24個
\[
84=2^2\times3\times7
\]
\[
\varphi(84)=84\times\frac12\times\frac23\times\frac67=24
\] - 24個
\[
90=2\times3^2\times5
\]
\[
\varphi(90)=90\times\frac12\times\frac23\times\frac45=24
\] - 36個
\[
126=2\times3^2\times7
\]
\[
\varphi(126)=126\times\frac12\times\frac23\times\frac67=36
\] - 48個
\[
180=2^2\times3^2\times5
\]
\[
\varphi(180)=180\times\frac12\times\frac23\times\frac45=48
\] - 48個
\[
210=2\times3\times5\times7
\]
\[
\varphi(210)=210\times\frac12\times\frac23\times\frac45\times\frac67=48
\]
2^2や3^2のような指数があっても、公式に入れるのは素因数の種類2, 3, ...を1回ずつです。