Euler関数の下からの素朴な評価と極限値 (1)

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

正の整数 $n$ に対して, $1$ から $n$ までの整数のうち $n$ と互いに素なものの個数を $\varphi(n)$ で表す. こうして定まる関数 $\varphi(n)$ を Euler 関数という.

[補題] $n$ を正の整数とする. このとき, $2^{\varphi(n)} - 1 = n$ であるための必要十分条件は, $n=1$ または $3$ となることである.

[証明] $s=\varphi(n)$ とおき, $2^{s} - 1 = n$ と仮定する. $1$ から $n$ までの整数のうち $n$ と互いに素なものの個数は $s$ である. ところが, $0\leq i\leq s-1$ なるすべての整数 $i$ に対して, $1\leq 2^{i}\leq n$ かつ $\gcd(2^{i}, n)=1$ である. $s\geq 2$ のとき, $1\leq 2^{s}-2\leq n$ かつ $\gcd(2^{s}-2, n)=1$ であるから, $0\leq j\leq s-1$ なる整数 $j$ が存在して, $2^{s}-2=2^{j}$ となる. 左辺は $4$ の倍数でない偶数だから, $j=1$. よって, $s=2$, $n=3$ となる. $s=1$ のときは, $n=1$ である.

逆に, $n=1$ または $3$ ならば $2^{\varphi(n)} - 1 = n$ が成り立つことは直接確かめられる. (証明終)

[定理] $n\geq 7$ なる任意の整数 $n$ に対して, 不等式 $$ \log_{2}n < \varphi(n) $$ が成り立つ.

[証明] 最初に, $n$ が正の奇数である場合 ($n\geq 7$ でなくてもよい) を証明する. Euler の定理より, $$ 2^{\varphi(n)}\equiv 1\pmod{n}. $$ すなわち, ある整数 $k$ が存在して, $$ 2^{\varphi(n)} - 1 = nk. $$ よって, $$ 2^{\varphi(n)} > nk. $$ 対数をとると, $$ \varphi(n) = \log_{2}2^{\varphi(n)} > \log_{2}(nk) = \log_{2}n + \log_{2}k. $$ 一方, $\gcd(1, n)=1$ より $\varphi(n)\geq 1$ であるから, $$ k = \frac{2^{\varphi(n)} - 1}{n} \geq \frac{2 - 1}{n} = \frac{1}{n} > 0. $$ よって, $k\geq 1$. 対数をとると, $\log_{2}k\geq 0$. したがって, $\varphi(n) > \log_{2}n$.

$n$ が $5$ 以上の奇数ならば $\varphi(n) > \log_{2}(2n)$ ($=\log_{2}n + 1$) である. 実際, $k=1$ ならば, $2^{\varphi(n)} - 1 = n$ であるから, 上の補題より, $n=1$ または $3$. ゆえに, $n$ が $5$ 以上の奇数ならば $k\geq 2$ である (より正確には, $nk$ が奇数なので $k\geq 3$ がいえる). したがって, $\varphi(n) > \log_{2}(2n)$.

次に, $n$ が正の偶数である場合を証明する. $n=2^{i}m$ ($i\geq 1$ は整数, $m\geq 1$ は奇数) とおくと, $$ \varphi(n) = \varphi(2^{i}m) = \varphi(2^{i})\varphi(m) = 2^{i-1}\varphi(m). $$

$m=1$ のとき. $\varphi(1)=1$ より, $\varphi(n) = 2^{i-1}$. 一方, $n=2^{i}$ であり, $n\geq 7$ という仮定より $i\geq 3$ であるから, $2^{i-1}>i = \log_{2}n$. ゆえに, $\varphi(n) > \log_{2}n$.

$m\geq 3$ かつ $i=1$ のとき. $\varphi(n)=\varphi(m)$ である. 一方, $n=2m$ であり, $n\geq 7$ という仮定より, $m\geq 5$. このとき, 上で述べたことから, $$ \varphi(m) > \log_{2}(2m) = \log_{2}n. $$ ゆえに, $\varphi(n) > \log_{2}n$.

$m\geq 3$ かつ $i\geq 2$ のとき. $2^{i-1}\geq i$ より, $$ 2^{i-1}\varphi(m) \geq i\varphi(m). $$ $\gcd(1, m)=\gcd(2, m)=1$ より $\varphi(m)\geq 2$ であるから, $$ i\varphi(m) = (i-1)\varphi(m) + \varphi(m) \geq 2(i-1)+\varphi(m). $$ $i\geq 2$ ならば $2(i-1)\geq i$ であるから, $$ 2(i-1)+\varphi(m) \geq i + \varphi(m). $$ $n$ が奇数の場合の結果を用いると, $$ i + \varphi(m) > \log_{2}2^{i} + \log_{2}m = \log_{2}(2^{i}m) = \log_{2}n. $$ ゆえに, $\varphi(n)>\log_{2}n$. (証明終)

[系] $\displaystyle \lim_{n\to\infty}\varphi(n)=\infty$.

[証明] 上の定理と $\log_{2}n\to\infty$ ($n\to\infty$) よりわかる. (証明終)

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示