2024 大阪大学（理系）前期第 5 問｜オイラーの φ 関数

自然数 $1, 2, 3, \dots, n$ のうち、 $n$ と互いに素であるものの個数を $f (n)$ とする。

(1) 自然数 $a, b, c$ および相異なる素数 $p, q, r$ に対して、等式

$f (p^{a} q^{b} r^{c}) = p^{a - 1} q^{b - 1} r^{c - 1} (p - 1) (q - 1) (r - 1)$

が成り立つことを示せ。

(2) $f (n)$ が $n$ の約数となる 5 以上 100 以下の自然数 $n$ をすべて求めよ。

解説

この問題で登場する $f (n)$ は、数論ではオイラーのトーシェント関数（Euler’s totient function）と呼ばれ、 $φ (n)$ と表記される。「 $n$ 以下の正の整数のうち、 $n$ と互いに素なものの個数」を表す重要な関数だ。

(1) の証明

$n = p^{a} q^{b} r^{c}$ としたとき、 $1$ から $n$ までの整数のうち $n$ と互いに素でないものは、 $p, q, r$ のいずれかで割り切れる整数である。これを包除原理で数えていく。

$1$ から $n$ までの整数で、 $p$ の倍数は $\frac{n}{p}$ 個、 $q$ の倍数は $\frac{n}{q}$ 個、 $r$ の倍数は $\frac{n}{r}$ 個ある。

重複を考慮すると、 $pq$ の倍数は $\frac{n}{pq}$ 個、 $p r$ の倍数は $\frac{n}{p r}$ 個、 $q r$ の倍数は $\frac{n}{q r}$ 個、 $pq r$ の倍数は $\frac{n}{pq r}$ 個となる。

包除原理より、 $n$ と互いに素な整数の個数は次のようになる。

$f (n) = n - (\frac{n}{p} + \frac{n}{q} + \frac{n}{r}) + (\frac{n}{pq} + \frac{n}{p r} + \frac{n}{q r}) - \frac{n}{pq r}$

$n = p^{a} q^{b} r^{c}$ を代入して整理する。

$f (n) = p^{a} q^{b} r^{c} (1 - \frac{1}{p} - \frac{1}{q} - \frac{1}{r} + \frac{1}{pq} + \frac{1}{p r} + \frac{1}{q r} - \frac{1}{pq r})$

括弧内を通分すると、

$= p^{a} q^{b} r^{c} \cdot \frac{pq r - q r - p r - pq + r + p + q - 1}{pq r}$

$= p^{a - 1} q^{b - 1} r^{c - 1} (pq r - q r - p r - pq + p + q + r - 1)$

ここで、括弧内の式を因数分解する。

$pq r - q r - p r - pq + p + q + r - 1$

これは次のように変形できる。

$= q r (p - 1) - p (q + r - 1) + (q + r - 1)$

$= q r (p - 1) - (p - 1) (q + r - 1)$

$= (p - 1) (q r - q - r + 1)$

$= (p - 1) (q - 1) (r - 1)$

よって、

$f (p^{a} q^{b} r^{c}) = p^{a - 1} q^{b - 1} r^{c - 1} (p - 1) (q - 1) (r - 1)$

が示された。

(2) の解答

$f (n)$ が $n$ の約数となる条件、すなわち $\frac{n}{f ( n )}$ が正の整数となる条件を調べる。

(1) の結果を一般化すると、 $n$ の素因数分解を $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ としたとき、

$f (n) = n i = 1 \prod k (1 - \frac{1}{p _{i}})$

と表せる。したがって、

$\frac{n}{f ( n )} = i = 1 \prod k \frac{p _{i}}{p _{i} - 1}$

この値が整数になる条件を調べる。

まず、 $\frac{n}{f ( n )}$ が整数になるためには、分母の $p_{i} - 1$ の積が分子の $p_{i}$ の積を割り切る必要がある。奇素数 $p$ に対しては $p - 1$ が偶数なので、分母に偶数因子が現れる。この偶数を打ち消すには、分子に 2 が含まれていなければならない。よって $n$ は偶数、すなわち 2 を素因数に持つ必要がある。

素因数が 2 のみの場合

$n = 2^{a}$ のとき、 $\frac{n}{f ( n )} = \frac{2}{2 - 1} = 2$ となり整数。条件を満たす。

素因数が奇素数のみの場合

$n = q^{b}$ （ $q$ は奇素数）のとき、 $\frac{n}{f ( n )} = \frac{q}{q - 1}$ は整数にならない。 $q - 1 \geq 2$ より分母が 1 にならないためだ。

次に、 $n = 2^{a} \cdot q^{b}$ （ $q$ は奇素数）の場合を考える。

$\frac{n}{f ( n )} = \frac{2}{1} \cdot \frac{q}{q - 1} = \frac{2 q}{q - 1}$

これが整数になるには $q - 1 ∣ 2 q$ が必要。 $g cd (q, q - 1) = 1$ より $q - 1 ∣ 2$ となる。 $q - 1 = 1$ または $q - 1 = 2$ なので、 $q = 2$ （不適、奇素数でない）または $q = 3$ 。よって $q = 3$ のみが条件を満たす。

最後に、奇素数を 2 つ以上含む場合を検討する。 $n = 2^{a} \cdot q^{b} \cdot r^{c}$ （ $q, r$ は相異なる奇素数）のとき、

$\frac{n}{f ( n )} = 2 \cdot \frac{q}{q - 1} \cdot \frac{r}{r - 1}$

$q, r$ が奇素数なので $q - 1, r - 1$ はともに偶数である。よって分母には少なくとも $2 \times 2 = 4$ の偶数因子が含まれる。一方、分子の偶数因子は 2 のみ。したがって分母を割り切れず、整数にならない。

具体例で確認すると、 $q = 3, r = 5$ のとき、

$2 \cdot \frac{3}{2} \cdot \frac{5}{4} = \frac{15}{4}$

となり整数にならない。奇素数が 3 つ以上の場合も同様で、分母の偶数因子がさらに増えるため条件を満たさない。

以上より、条件を満たす $n$ は $n = 2^{a} \cdot 3^{b}$ （ $a \geq 1$ , $b \geq 0$ ）の形に限られる。

$5 \leq n \leq 100$ の範囲でこの形の整数を列挙すると、

6 = 2 × 3

8 = 2³

12 = 2² × 3

16 = 2⁴

18 = 2 × 3²

24 = 2³ × 3

32 = 2⁵

36 = 2² × 3²

48 = 2⁴ × 3

54 = 2 × 3³

64 = 2⁶

72 = 2³ × 3²

96 = 2⁵ × 3

答え

$n = 6, 8, 12, 16, 18, 24, 32, 36, 48, 54, 64, 72, 96$

この問題の数学的背景

実は (2) で示した結果は、「5 以上 100 以下」という制限がなくても成り立つ。すなわち、 $φ (n) ∣ n$ となる正整数 $n$ は完全に分類されているのだ。

分類定理

$φ (n)$ が $n$ の約数となる正整数 $n$ は、 $n = 1$ または $n = 2^{a} \cdot 3^{b}$ （ $a \geq 1, b \geq 0$ ）の形に限る。

意味

この入試問題は有限範囲での探索を求めているが、背景には全ての正整数に対する完全な分類定理が存在する。

群論的な解釈

$φ (n)$ には群論的な意味がある。 $n$ を法とする整数の乗法群 $(Z / n Z)^{\times}$ を考えると、この群の位数（元の個数）がちょうど $φ (n)$ になる。

具体的に言えば、 $(Z / n Z)^{\times}$ は「 $n$ と互いに素な $1$ 以上 $n$ 未満の整数」を元とし、乗法を演算とする群だ。例えば $n = 12$ のとき、 $12$ と互いに素な数は $1, 5, 7, 11$ の 4 つなので、 $φ (12) = 4$ であり、 $(Z /12 Z)^{\times} = {1, 5, 7, 11}$ は位数 4 の群となる。

したがって、 $φ (n) ∣ n$ という条件は「乗法群の位数が $n$ を割り切る」という群論的な制約を意味する。これが $2^{a} \cdot 3^{b}$ という特殊な形でしか実現しないのは、素因数の組み合わせに対する強い制限を反映している。

Lehmer の問題：90 年以上未解決の難問

この問題に関連して、1932 年に D.H. Lehmer が提起した有名な未解決問題がある。

この入試問題の条件

$φ (n) ∣ n$ （φ(n) が n を割り切る）

Lehmer の問題

$φ (n) ∣ n - 1$ となる合成数 $n$ は存在するか？

素数 $p$ については $φ (p) = p - 1$ なので、当然 $φ (p) ∣ p - 1$ が成り立つ。Lehmer の問いは「合成数でこの性質を持つものはあるか？」というものだ。

もし存在するならば、そのような合成数 $n$ はLehmer 数と呼ばれる。現在までに Lehmer 数は一つも発見されておらず、存在しないと予想されているが、証明には至っていない。

分かっていること

Lehmer 数が存在するならば、それは奇数であり、平方因子を持たず、少なくとも 14 個の異なる素因数を持ち、 $1 0^{30}$ を超える巨大数でなければならない。

問題の難しさ

この問題は単純に見えて、90 年以上も数学者たちを悩ませ続けている。素数の性質と合成数の性質の境界に関わる深い問題なのだ。

入試問題 (2) の条件 $φ (n) ∣ n$ と Lehmer の条件 $φ (n) ∣ n - 1$ は、たった 1 の差しかないが、前者は完全に解決済み、後者は未解決という対照的な状況にある。この事実は、数論における問題の難易度がいかに予測困難かを示している。

2024 大阪大学（理系）前期 第 5 問｜オイラーの φ 関数