インテジャーズ

INTEGERS

数、特に整数に関する記事。

非トーシェント数

\varphi (n)をEulerのトーシェント関数とするとき、\varphi \colon \mathbb{N} \to \mathbb{N}について、\mathrm{Image}(\varphi)の元のことをトーシェント数\mathbb{N} \setminus \mathrm{Image}(\varphi)の元のことを非トーシェント数と言います。

\varphi (1)=\varphi (2)=1ですが、3以上の奇数は全て非トーシェント数です。偶数であるような最小の非トーシェント数は14です*1

実は非トーシェント数全体のなす集合\mathbb{N}\setminus \mathrm{Image}(\varphi)は自然密度1をもちます。すなわち、x > 0に対して、x以下のトーシェント数全体のなす集合をT(x)x以下の非トーシェント数全体のなす集合をNT(x)とすれば、

\displaystyle \lim_{n \to \infty} \frac{\#T(n)}{n} = 0, \ \ \ \lim_{n \to \infty} \frac{\#NT(n)}{n} = 1

が成り立ちます。自然数は大抵非トーシェント数なのです。しかしながら、トーシェント数は無数に存在し、逆数和が発散する程度には分布しています(実際、素数pに対して、\varphi (p) = p-1なのでp-1は全てトーシェント数であり、素数の逆数和が発散するという事実からトーシェント数の逆数和も発散することが分かる)。密度に関する事実は次の定理から従います:

定理 (Pillai) 次の漸近公式が成立する:
\displaystyle \#T(n) = O\left( \frac{n}{\log^{\frac{\log 2}{e}}n} \right).

時間が出来次第証明を書きます。

*1:ちなみに、14はひっくり返すと素数となるような最小の半素数です。