文献あり

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

278

はじめに

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

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

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

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

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

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

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

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

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

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

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

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

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

解法

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

$12$
$2\times 6$

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

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

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