互いに素な整数の個数 | ドリル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=20n=24n=45n=50n=63
解答・解説
- 8個
\[
20=2^2\times5; \varphi(20)=20\times\frac12\times\frac45=8
\] - 8個
\[
24=2^3\times3; \varphi(24)=24\times\frac12\times\frac23=8
\] - 24個
\[
45=3^2\times5; \varphi(45)=45\times\frac23\times\frac45=24
\] - 20個
\[
50=2\times5^2; \varphi(50)=50\times\frac12\times\frac45=20
\] - 36個
\[
63=3^2\times7; \varphi(63)=63\times\frac23\times\frac67=36
\]