自然数 $n$ に対して、$n$ 以下の自然数のうち $n$ と互いに素であるものの個数を $\phi(n)$、正の約数の個数を $d(n)$ とする。 (1) $\phi(n)$ と $d(n)$ が等しくなる $n$ を全て求めよ。 (2) $\phi(n)$ と $d(n)$ が共に平方数となる $n$ が無限に存在することを示せ。

1. 問題の内容

自然数 $n$ に対して、$n$ 以下の自然数のうち $n$ と互いに素であるものの個数を $\phi(n)$、正の約数の個数を $d(n)$ とする。

(1) $\phi(n)$ と $d(n)$ が等しくなる $n$ を全て求めよ。

(2) $\phi(n)$ と $d(n)$ が共に平方数となる $n$ が無限に存在することを示せ。

2. 解き方の手順

(1) $\phi(n) = d(n)$ となる $n$ を求める。

$n = 1$ のとき、$\phi(1) = 1$、$d(1) = 1$ なので、$\phi(1) = d(1)$ が成り立つ。

$n = 2$ のとき、$\phi(2) = 1$、$d(2) = 2$ なので、$\phi(2) \ne d(2)$。

$n = 3$ のとき、$\phi(3) = 2$、$d(3) = 2$ なので、$\phi(3) = d(3)$ が成り立つ。

$n = 4$ のとき、$\phi(4) = 2$、$d(4) = 3$ なので、$\phi(4) \ne d(4)$。

$n = 5$ のとき、$\phi(5) = 4$、$d(5) = 2$ なので、$\phi(5) \ne d(5)$。

$n = 6$ のとき、$\phi(6) = 2$、$d(6) = 4$ なので、$\phi(6) \ne d(6)$。

$n = 8$ のとき、$\phi(8) = 4$、$d(8) = 4$ なので、$\phi(8) = d(8)$ が成り立つ。

$n=p$ （素数）のとき、$\phi(p) = p-1$, $d(p) = 2$ であるから $p-1 = 2$ より $p=3$。

$n=p^2$ （$p$ は素数）のとき、$\phi(p^2) = p^2 - p$, $d(p^2) = 3$ であるから、$p^2 - p = 3$ を満たす素数は存在しない。

$n=pq$ （$p, q$ は異なる素数）のとき、$\phi(pq) = (p-1)(q-1)$, $d(pq) = 4$ であるから、$(p-1)(q-1) = 4$ を満たす素数の組 $(p, q)$ を探す。

$p-1 = 1$ ならば $p=2$, $q-1 = 4$ ならば $q=5$ であり、このとき $n=10$, $\phi(10) = 4$, $d(10) = 4$ となる。

$p-1 = 2$ ならば $p=3$, $q-1 = 2$ ならば $q=3$ であり、$p, q$ は異なる素数であることに反する。

$n=12$ のとき、$\phi(12) = 4$, $d(12) = 6$ なので、$\phi(12) \ne d(12)$。

$n=1, 3, 8, 10$

(2) $\phi(n)$ と $d(n)$ が共に平方数となる $n$ が無限に存在することを示す。

$n = 2^{2k}$ (kは自然数)とすると、

$d(n) = 2k + 1$

$\phi(n) = 2^{2k} - 2^{2k-1} = 2^{2k-1}$

$2k+1$ が平方数になるような $k$ を考える.

$2k+1 = m^2$ （mは奇数）とすると、

$2k = m^2-1 = (m-1)(m+1)$

$k = (m-1)(m+1)/2$

$k$ は自然数であるから, $m$ は奇数であればよい.

$k = 4, 12, 24, 40, ...$

$n = 2^8, 2^{24}, 2^{48}, 2^{80}, ...$

$d(n) = 9, 25, 49, 81, ...$

$\phi(n) = 2^7, 2^{23}, 2^{47}, 2^{79}, ...$

$\phi(n) = n\prod_{p|n}(1 - \frac{1}{p})$

$n = 2^k 3^l$のとき, $k, l$が偶数であればよい。

$n = 2^{2k}3^{2l}$

$\phi(n) = 2^{2k-1} 3^{2l-1} * 2 = 2^{2k}3^{2l-1}$

$d(n) = (2k+1)(2l+1)$

$n = 3^k$ のとき,

$d(n) = k+1$

$\phi(n) = 3^k - 3^{k-1} = 2*3^{k-1}$

$n=2^k$とする. $\phi(n) = 2^{k-1}$であり、これが平方数になるには、$k-1$が偶数である必要があるので、$k$は奇数。

$d(n)=k+1$ が平方数になるには、$k+1 = m^2$とおくと、$k=m^2-1$

$m$は偶数とする. $k$は奇数だから不適。

3. 最終的な答え

(1) $n = 1, 3, 8, 10$

(2) $\phi(n)$ と $d(n)$ が共に平方数となる $n$ が無限に存在する。