互いに素な整数の個数 | ドリル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)
\]
\]
この公式は、素因数の指数の大きさではなく、異なる素因数の種類に注目して使います。
問題
n=2^a\times3^b\times5^c（a,b,cは正の整数）のとき、\(\varphi(n)\) をnを使って表しなさい。- 1以上840以下の整数のうち、840と公約数が1だけである整数は何個ですか。
- 1以上1680以下の整数のうち、840と公約数が1だけである整数は何個ですか。
n=2^4\times3^2\times5\times7のとき、\(\varphi(n)\) を求めなさい。n=2\times3\times5\times7\times11のとき、\(\varphi(n)\) を求めなさい。
解答・解説
- \(\varphi(n)=\frac{4}{15}n\)
異なる素因数は2、3、5なので、
\[
\varphi(n)=n\times\frac12\times\frac23\times\frac45=\frac{4}{15}n
\]
指数a,b,cの値には左右されません。 - 192個
\[
840=2^3\times3\times5\times7
\]
\[
\varphi(840)=840\times\frac12\times\frac23\times\frac45\times\frac67=192
\] - 384個
1680は840の2倍です。840と互いに素な並びが2周期分あるので、
\[
192\times2=384
\] - 1152個
まず、
\[
n=2^4\times3^2\times5\times7=5040
\]
異なる素因数は2、3、5、7なので、
\[
\varphi(5040)=5040\times\frac12\times\frac23\times\frac45\times\frac67=1152
\] - 480個
\[
n=2\times3\times5\times7\times11=2310
\]
\[
\varphi(2310)=2310\times\frac12\times\frac23\times\frac45\times\frac67\times\frac{10}{11}=480
\]