オイラー関数の計算

素因数分解から $φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})$ を使って $φ (n)$ を求められる。互いに素な $m, n$ について $φ (mn) = φ (m) φ (n)$ を使える

前提

互いに素な法への分解（数学A 整数の性質）
包除原理（数学A 場合の数と確率）

この技能までの道筋（25 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
互いに素な法への分解（数学A 整数の性質）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
包除原理（数学A 場合の数と確率）

説明

正の整数 $n$ に対し、 $1$ から $n$ までの整数のうち $n$ と互いに素なもの（最大公約数が $1$ のもの）の個数を $φ (n)$ と書き、オイラー関数と呼びます（ $φ (1) = 1$ ）。この技能を使うと、1 つずつ数えずに、素因数分解だけから $φ (n)$ を求められます。 $φ (n)$ は、合同式で $n$ を法とする「逆数をもつ余り」の個数や、暗号（RSA）の計算などに使われます。

なぜそうしてよいのか

$n$ と互いに素であることは、「 $n$ のどの素因数でも割り切れない」ことと同じです。たとえば $n$ の異なる素因数が $p, q, r$ の 3 つなら、 $1$ から $n$ までで $p$ の倍数の集合を $A$ 、 $q$ の倍数を $B$ 、 $r$ の倍数を $C$ とすると、 $φ (n)$ は「どれでもない」ものの個数 $n - n (A \cup B \cup C)$ です。 $p, q, r$ はどれも $n$ の約数なので、 $n (A) = \frac{n}{p}$ 、 $n (A \cap B) = \frac{n}{pq}$ （ $pq$ の倍数）、 $n (A \cap B \cap C) = \frac{n}{pq r}$ のように割り切れる形で数えられます。包除原理より $φ (n) = n - \frac{n}{p} - \frac{n}{q} - \frac{n}{r} + \frac{n}{pq} + \frac{n}{q r} + \frac{n}{r p} - \frac{n}{pq r} = n (1 - \frac{1}{p}) (1 - \frac{1}{q}) (1 - \frac{1}{r})$ となります（右辺を展開すると左辺に一致します）。素因数がいくつでも同じで、 $φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})$ （ $p$ は $n$ の異なる素因数すべてを動く。 $n = 1$ では積を $1$ とみなす）が成り立ちます。特に $n = p^{k}$ なら、 $p$ の倍数 $p^{k - 1}$ 個を除いて $φ (p^{k}) = p^{k} - p^{k - 1} = p^{k - 1} (p - 1)$ です。

もう 1 つの見方として、 $m, n$ が互いに素なとき $φ (mn) = φ (m) φ (n)$ が成り立ちます。 $mn$ を法とする余り $x$ は、組（ $m$ で割った余り, $n$ で割った余り）と 1 対 1 に対応します（互いに素な法への分解）。さらに「 $x$ が $mn$ と互いに素 $⟺$ $x$ が $m$ とも $n$ とも互いに素」であり、 $x$ と $m$ の最大公約数は $x$ を $m$ で割った余りだけで決まります。よって条件を満たす $x$ の個数は、 $m$ と互いに素な余り $φ (m)$ 通りと、 $n$ と互いに素な余り $φ (n)$ 通りの組の数、つまり積になります。素因数分解 $n = p_{1}^{k_{1}} \dots p_{r}^{k_{r}}$ の各因子は互いに素なので、 $φ (n) = φ (p_{1}^{k_{1}}) \dots φ (p_{r}^{k_{r}})$ となり、上の公式と同じ結果が得られます。

手順

$n$ を素因数分解する： $n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}$ （ $p_{i}$ は異なる素数）
異なる素因数 $p_{1}, \dots, p_{r}$ を書き出す（指数 $k_{i}$ は公式の掛け算の回数には関係しない）
$φ (n) = n (1 - \frac{1}{p _{1}}) \dots (1 - \frac{1}{p _{r}})$ を計算する。または各因子ごとに $φ (p_{i}^{k_{i}}) = p_{i}^{k_{i}} - p_{i}^{k_{i} - 1}$ を求めて掛け合わせる
2 つの数の積 $mn$ の値が必要なときは、 $m, n$ が互いに素であることを確かめてから $φ (mn) = φ (m) φ (n)$ を使う

例題

$φ (360)$ を求めよ。ただし $φ (n)$ は $1$ 以上 $n$ 以下の整数のうち $n$ と互いに素なものの個数とする。

例題の解答

手順 1： $360 = 2^{3} \cdot 3^{2} \cdot 5$ と素因数分解する。
手順 2：異なる素因数は $2, 3, 5$ の 3 つ。
手順 3：公式より $φ (360) = 360 (1 - \frac{1}{2}) (1 - \frac{1}{3}) (1 - \frac{1}{5}) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96.$
確認（手順 3 の別法・手順 4）： $8, 9, 5$ は互いに素なので $φ (360) = φ (8) φ (9) φ (5) = (8 - 4) (9 - 3) (5 - 1) = 4 \cdot 6 \cdot 4 = 96$ で一致する。

答え: $96$

よくある誤り

指数の回数だけ $(1 - \frac{1}{p})$ を掛けてしまう誤り。例： $φ (8) = 8 (1 - \frac{1}{2})^{3} = 1$ は誤り。正しくは異なる素因数ごとに 1 回だけ掛けて $φ (8) = 8 \cdot \frac{1}{2} = 4$ （ $1, 3, 5, 7$ ）
互いに素でない数に $φ (mn) = φ (m) φ (n)$ を使ってしまう誤り。例： $φ (4) = φ (2) φ (2) = 1$ は誤り。正しくは $φ (4) = 4 - 2 = 2$ （ $1, 3$ ）
$φ (p^{k}) = (p - 1)^{k}$ としてしまう誤り。例： $φ (9) = 2^{2} = 4$ は誤り。正しくは $3$ の倍数 $3$ 個を除いて $φ (9) = 9 - 3 = 6$
素数 $p$ について $φ (p) = p$ としてしまう誤り。 $p$ 自身は $p$ と互いに素でないので、正しくは $φ (p) = p - 1$ （例： $φ (7) = 6$ ）

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

フェルマーの小定理とオイラーの定理（大学数学整数論）
乗法的関数と約数にわたる和（大学数学整数論）