整数論の問題

$n=\prod p_i^{e_i}$ と素因数分解すると、$$\phi (n)=\prod p_i^{e_i-1}(p_i-1)$$ である。

現れうる素因数の制限. $p\mid n$ なら $p-1\mid \phi (n)=12$ なので $p-1\in \{1,2,3,4,6,12\}$、すなわち $p\in \{2,3,4,5,7,13\}$ のうち素数である $p\in \{2,3,5,7,13\}$ に限られる。また $p^2\mid n$ なら $p\mid 12$ なので、2 乗以上で現れうるのは $2,3$ だけである。

なお $\phi (m)$ は $m\geqq 3$ のとき偶数なので、$\phi (m)$ が奇数になるのは $m=1,2$（値は $1$）のときだけである。

(i) $13\mid n$ のとき. $n=13m$（$\gcd (m,13)=1$）とおくと $\phi (n)=12\phi (m)$ より $\phi (m)=1$、よって $m=1,2$。$n=13,26$。

(ii) $13\nmid n$、$7\mid n$ のとき. $49\nmid n$ なので $n=7m$（$\gcd (m,7)=1$）、$\phi (m)=2$。$\phi (m)=2$ となる $m$ は $3,4,6$ である（実際、素因数は $2,3$ のみで、$m=2^a{3}^b$ を調べると $3,4,6$ に限る）。いずれも $7$ と互いに素なので $n=21,28,42$。

(iii) $7,13\nmid n$、$5\mid n$ のとき. $25\nmid n$ なので $n=5m$、$\phi (n)=4\phi (m)$ より $\phi (m)=3$。これは奇数で $1$ でないので不可能。

(iv) $n=2^a{3}^b$ のとき. $b\geqq 1$ なら $\phi (3^b)=2\cdot 3^{b-1}$。
- $b=0$：$\phi (2^a)=12$ だが $\phi (2^a)$ は $1$ か $2$ のべきなので不可能。
- $b=1$：$\phi (2^a)=6$ となり不可能。
- $b=2$：$\phi (9)=6$ より $\phi (2^a)=2$、よって $a=2$。$n=36$。
- $b\geqq 3$：$\phi (3^b)\geqq 18>12$ で不可能。

確認. $\phi (13)=12$, $\phi (26)=1\cdot 12=12$, $\phi (21)=2\cdot 6=12$, $\phi (28)=2\cdot 6=12$, $\phi (42)=1\cdot 2\cdot 6=12$, $\phi (36)=2\cdot 6=12$。

よって求める $n$ は $\{13,21,26,28,36,42\}$ である。

φ(n)=12 をみたす n を求める。n=∏p^a と素因数分解すると φ(n)=∏p^(a-1)(p-1) である。φ(n)=12 なので、各素因数 p について (p-1) は 12 の約数でなければならない。

12 の約数は 1,2,3,4,6,12 であり、p=素数となる p-1 の候補は p=2,3,5,7,13 (p-1=1,2,4,6,12)。p-1=3 の p=4 は素数でないので除く。したがって n の素因数は 2,3,5,7,13 のみ。

まず 13 を含む場合：φ(13)=12 なので残りの部分の φ は 1。残りは 1 か 2 で、n=13, 26。13^2 以上は 13 の因子が出るので不可。

7 を含む場合（13 を含まない）：φ(7)=6 で、残りの φ が 2 であればよい。7^2 は φ=42 で不可。残りは 2,3,5 の積で φ=2：1 のとき φ=1 でなので不可。残りの候補は φ=2 となる数 3,4,6。n=21, 28, 42。

7,13 を含まない場合：n=2^a 3^b 5^c。
c=0, b=0：2^a で φ=2^(a-1)=12 は不可。
c=1：φ(5)=4 で、残りで φ=3。2^a3^b の φ は 3 の因子を持つなら b=2 以上が必要 (φ(9)=6 で 3 の因子が出るが 3 だけを出す方法はなく)、φ=3 は 3 の約数の素数 p=4 が素数でなく不可（φ(m)=3 となる m は存在しない）。よって不可。
c=0：n=2^a 3^b, b≥1。φ=2^(a-1)·2·3^(b-1) (a≥1)、または b≥1 で a=0 のとき 2·3^(b-1)。
- a=0：2·3^(b-1)=12 → 3^(b-1)=6 不可。
- a≥1：2^a·3^(b-1)=12 → a=2, b=2。n=36。
また 7 を含まず 13 も含まない場合の n=36 のみ。さらに c≥2 では φ に 5 の因子が出るので不可。

以上より n=13, 26, 21, 28, 42, 36。

検算：φ(13)=12, φ(26)=12, φ(21)=2·6=12, φ(28)=2·6=12, φ(42)=1·2·6=12, φ(36)=12。いずれも一致。

答え：{13, 21, 26, 28, 36, 42}