文献あり

MATH POWER 2022ガチ数学クイズのトーシェント関数の問題解説 #MathPower

314

はじめに

はじめまして。Zassyです。
先日行われましたイベントMATH POWER 2022( https://live.nicovideo.jp/watch/lv338206772 )で、ガチ数学クイズというコーナーの問題作成協力をいたしました。
この記事ではその中で多答クイズという形で出題された問題

MATH POWER 2022 ガチ数学クイズマス多答第2問

$φ (n) = 12$ を満たす自然数 $n$ は全部で6個ある。すべて求めよ。
ただし、 $φ$ はオイラーのトーシェント関数である。

について解説していきます。

オイラーのトーシェント関数とは？

オイラーのトーシェント関数 $φ$ は次のように定義されます。（ちなみに、この定義は解答者にも公開されました。）

オイラーのトーシェント関数

自然数 $n$ 以下の自然数のうち、 $n$ と互いに素であるものの個数を $φ (n)$ とする。

この関数には次のような性質が成り立つことが知られています。

$p$ を素数、 $α$ を自然数とする。このとき、 $φ (p^{α}) = (p - 1) p^{α - 1} .$ 特に、 $φ (p) = p - 1.$

自然数 $m, n$ は互いに素であるとする。このとき、 $φ (m n) = φ (m) φ (n) .$

$φ (n)$ は、 $n = 1, 2$ のときに $φ (n) = 1$ となる例外を除いて、偶数の値を取る。

$n$ を奇数とする。このとき、 $φ (n) = φ (2 n) .$

解法

$φ (n) = 12$ を満たす自然数 $n$ が、 $n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{k}^{α_{k}} (p_{1} < p_{2} < \dots < p_{k})$ の形に素因数分解されるとします。このとき、定理2より
$φ (n) = φ (p_{1}^{α_{1}}) φ (p_{2}^{α_{2}}) \dots φ (p_{k}^{α_{k}})$
が成り立ちます。ここで定理3より、 $p_{1}^{α_{1}} = 2$ の例外を除いて $φ (p_{1}^{α_{1}}), φ (p_{2}^{α_{2}}), \dots, φ (p_{k}^{α_{k}})$ はいずれも偶数であるはずです。この例外については $p_{1}^{α_{1}} = 2$ ならば定理4より $n = p_{2}^{α_{2}} p_{3}^{α_{3}} \dots p_{k}^{α_{k}}$ も条件をみたすはずなので、 $p_{1}^{α_{1}} \neq 2$ を仮定して求めてしまい、奇数の解が出てきたら最後にその2倍も解に加えるという方針で処理ができます。そうすると、今、 $φ (p_{1}^{α_{1}}), φ (p_{2}^{α_{2}}), \dots, φ (p_{k}^{α_{k}})$ はすべて偶数かつ $12$ の約数であるはずなので、 $12$ を偶数の積で表す方法をすべて列挙しましょう。すると、順序の違いを除いて

$12$
$2 \times 6$

の2つが得られます。次に $m = 2, 6, 12$ に対し、 $φ (q) = m$ を満たす素数べき $q$ を列挙すると

$m$	$q$
$2$	$3, 4$
$6$	$7, 9$
$12$	$13$

となります。ここから $12$ （分解していない積）に対応する解として $n = 13$ が得られました。 $2 \times 6$ に対応する解としては、互いに素な素数べきの組 $(q_{1}, q_{2})$ が $φ (q_{1}) = 2, φ (q_{2}) = 6$ を満たすように取ると $(q_{1}, q_{2}) = (3, 7), (4, 7), (4, 9)$ が得られます。したがって、解として $n = q_{1} q_{2} = 21, 28, 36$ も得られます。最後に、奇数解として $n = 13, 21$ が手に入ったので、これらを2倍して
$n = 26, 42$ も解になります。以上ですべての解が発見されました。