オイラーの φ関数の漸近挙動 前編 - Ex5.4

Shoup『A Computational Introduction to Number Theory and Algebra』を読んでいきます．

A Computational Introduction to Number Theory and Algebra

書影を得るためにAmazonのリンクを貼っていますが，この本は著者のＨＰからＰＤＦが無料でＤＬできます．単に安いだけでなくとてもおもしろい本なので，興味のある方はぜひどうぞ．

今回やるのは演習問題5.4です．

\[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} %%% カリグラフィー %%% \newcommand{\calf}{\mathcal{F} } \newcommand{\calg}{\mathcal{G} } %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \newcommand{\im}{\operatorname{im} } \]

問題文

原文はこちら．

For each positive integer $k$, let $P_k$ denote the product of the first $k$ primes. Show that $φ(P_k) = \Theta(P_k / \log \log P_k)$ (here, $φ$ is Euler's phi function).

Exercise 5.4

訳すとしたらこうです．

各整数 $k$ に対して，最初の $k$ 個の素数の積を $P_k$ とする．このとき $φ(P_k) = \Theta(P_k / \log \log P_k)$ であることを示せ．ただし $φ$ はオイラーの φ関数である．

回答

小さいほうから $k$ 番目の素数を $p_k$ と表すことにします．

そうすると $P_k$ は

$$ P_k = \prod_{1 \leq i \leq k} p_i $$

と表すことができます．このとき，同時に

$$ φ(P_k) = P_k \prod_{1 \leq i \leq k} \left( 1 - \frac{1}{p_i} \right) $$

が成り立ちます．

ここまではいいですね．

次にどうするかですが，Mertensの定理を使いたいです．

Mertensの定理

$$ \prod_{p \leq x} (1- 1/p) = \Theta(1/ \log x) $$

そこで，$φ(P_k)$ の上記の式をMertensの定理を使って書き換えると,

$$ φ(P_k) = \Theta(P_k / \log p_k) $$

であることがわかります．

後は，$p_k$ の大きさを $P_k$ を使って評価すればよいです．

どうやるかですが，チェビシェフのシータ関数に対する漸近評価を使えば

$$ \log P_k = \sum_{2 \leq p \leq p_k} \log p = \Theta(p_k) $$

が得られます．したがって $p_k = \Theta(\log P_k)$ なので，

$$ φ(P_k) = \Theta(P_k / \log \log P_k) $$

が成り立ちます．

おしまい．

感想

Mertensの定理の応用としてすぐ示せました．

今回は $n = P_k$ に対する評価だけですが，次の問題でこれを一般化します．