オイラー関数の値(互いに素な数の個数)

方針

解答

⓪ 発想 — どう考え始めるか。 $360$ と互いに素とは、$360$ の素因数 $2,3,5$ のどれでも割り切れないことだ。

だから数えるべきは「$2$ でも $3$ でも $5$ でも割り切れない数」。裏返して、$2$ または $3$ または $5$ で割り切れる数を包除原理で数え、全体 $360$ から引けばよい。

この計算を整理すると、素因数 $p$ ごとに「割り切れない割合 $1-\frac{1}{p}$」を掛ける形にまとまる。$\phi (n)=n\prod _{p\mid n}\left(1-\frac{1}{p}\right)$ という積の公式だ。

① 素因数分解。 $360=2^3\cdot 3^2\cdot 5$。相異なる素因数は $2,3,5$。

② 公式にあてはめる。 $$\phi (360)=360\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=360\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{4}{5}.$$ ③ 計算する。 順に $360\cdot \frac{1}{2}=180$、$180\cdot \frac{2}{3}=120$、$120\cdot \frac{4}{5}=96$。よって $$\phi (360)=96.$$ (包除でも:$360-(180+120+72)+(60+36+24)-12=96$。)

まとめ 互いに素 $=$ 素因数 $2,3,5$ で割り切れない。包除原理を整理した公式 $\phi (n)=n\prod (1-\frac{1}{p})$ で $360\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{4}{5}=96$。整数(オイラー関数)と数え上げの融合。

発展 — 一歩先へ。 $\phi$ には、$m,n$ が互いに素なら $\phi (mn)=\phi (m)\phi (n)$ という乗法性があり、$\phi (360)=\phi (8)\phi (9)\phi (5)=4\cdot 6\cdot 4=96$ とも計算できる。さらに約数全体で足すと ${\sum }_{d\mid n}\phi (d)=n$ という美しい等式が成り立つ(分数 $\frac{1}{n},\dots ,\frac{n}{n}$ を約分して分母で仕分けると見える)。

別解

別解 — $30$ ごとの繰り返しで数える(苦手な人向け)。 $360$ と互いに素かどうかは、$2,3,5$ で割り切れるかだけで決まる。そしてこの割り切れ方は $30=2\cdot 3\cdot 5$ ごとに同じパターンを繰り返す。

まず $1\sim 30$ で、$2,3,5$ のどれでも割り切れない数を書き出す。

$$1,7,11,13,17,19,23,29\text{の }8\text{ 個}.$$

$360=30\times 12$ だから、このパターンが $12$ 回繰り返される。$8\times 12=96$。

包除原理の式を経由しなくても、周期性と手の数え上げだけで同じ $96$ に届く。素因数が小さいときは、この“$1$ 周期だけ数える”方法が確実で速い。