互いに素な整数の個数 | ドリル1（応用）
注意事項
異なる素因数を 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)
\]
\]
また、m と互いに素な整数の並びは m 個ごとにくり返します。
問題
- 1以上360以下の整数のうち、360と公約数が1だけである整数は何個ですか。
- 1以上420以下の整数のうち、420と公約数が1だけである整数は何個ですか。
- 1以上420以下の整数のうち、210と公約数が1だけである整数は何個ですか。
- 1以上540以下の整数のうち、540と公約数が1だけである整数は何個ですか。
- 1以上600以下の整数のうち、600と公約数が1だけである整数は何個ですか。
解答・解説
- 96個
\[
360=2^3\times3^2\times5
\]
\[
\varphi(360)=360\times\frac12\times\frac23\times\frac45=96
\] - 96個
\[
420=2^2\times3\times5\times7
\]
\[
\varphi(420)=420\times\frac12\times\frac23\times\frac45\times\frac67=96
\] - 96個
210と互いに素な数は210個ごとに同じ並びになります。まず、
\[
\varphi(210)=210\times\frac12\times\frac23\times\frac45\times\frac67=48
\]
420は210の2周期分なので、48 × 2 = 96個です。 - 144個
\[
540=2^2\times3^3\times5
\varphi(540)=540\times\frac12\times\frac23\times\frac45=144
\] - 160個
\[
600=2^3\times3\times5^2
\varphi(600)=600\times\frac12\times\frac23\times\frac45=160
\]