互いに素な整数の個数 | ドリル1（入門）
注意事項
n の異なる素因数を p_1, p_2, ..., p_k とすると、個数は次の公式で求めます。
\[
\[
\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)
\]
\]
問題
1以上 n 以下の整数のうち、n と公約数が1だけである整数の個数を求めなさい。
n=10n=12n=18n=25n=27
解答・解説
- 4個
\[
10=2\times5; \varphi(10)=10\times\frac12\times\frac45=4
\] - 4個
\[
12=2^2\times3; \varphi(12)=12\times\frac12\times\frac23=4
\] - 6個
\[
18=2\times3^2; \varphi(18)=18\times\frac12\times\frac23=6
\] - 20個
\[
25=5^2; \varphi(25)=25\times\frac45=20
\] - 18個
\[
27=3^3; \varphi(27)=27\times\frac23=18
\]