オイラーのφ関数

自然数nに対して1以上n以下の自然数で
nと互いに素なものの個数をφ(n)とする。
φ(n)→∞(n→∞)の証明を教えて下さい。

質問者からの補足コメント

• 

  No.2の書き方だと
  φ(n)≧2^(j-1)log₂m
  が成り立つとはいえm=1になる
  ことが無数にあるのが心配です。

  No.2の回答に寄せられた補足コメントです。 補足日時：2021/07/09 01:52

• 

  > 偶数 n = (2^j)m に対して { 2^(j-1) } log₂ m が有界より、
  > j も m も有界になって n は有界。
  
  まさにこれこそ 「 ダウト。」 ですね…。
  m=1のとき、jが有界と言えるでしょうか…？

  No.3の回答に寄せられた補足コメントです。 補足日時：2021/07/09 02:10

• 

  >φ(n)≦M となる n には n≦N となる N が存在する
  
  このNの存在は、不等式 M ≧ φ(n) ≧ 2^(j-1) log₂ m
  でj,mが有限個の値しかとらないことから言うのですよね？
  でもm=1すなわちlog₂m=0の場合が問題になりませんか？
  
  ダウト。

  No.4の回答に寄せられた補足コメントです。 補足日時：2021/07/09 02:33

• 

  風変わりな定義ではなく、ごく一般的な定義
  でお願いできないでしょうか？
  
  普通は「φ(n)→∞」とは
  　　∀S∃M ∀n(n>M ⇒ φ(n)>S)
  ということ、です。

  No.1の回答に寄せられた補足コメントです。 補足日時：2021/07/09 09:09

• 

  補足にてかなり分かりやすくありものがたりさんの回答の間違いを指摘しましたが…、なぜか反応がありませんでした…。補足は読まれないのでしょうか…？No.4も間違っている上に、背理法と対偶を混同されていて、あまり良い印象を持てませんでした…。
  
  とにかく、どこが間違いか御理解されたのか、「ダウト」を反省したのかどうかを聞かせてほしかったのですが…。

  No.6の回答に寄せられた補足コメントです。 補足日時：2021/07/16 21:11

No.6 回答者： ありものがたり 回答日時： 2021/07/09 21:24

＞ No.2の間違いと誤魔化してある部分をうまく修正していますね。

No.2 は、書くのが面倒くさいところを「解るでしょ？」の意味で省略したが、
間違いは入っていない。 省略した部分は、No.4 で補足した。
どこが間違いだと思うのかと、「ダウト」を反省したのかどうかを聞かせてほしい。

この回答へのお礼

補足に全て書いていますが…。

お礼日時：2021/07/09 21:26

No.5 ベストアンサー 回答者： mtrajcp 回答日時： 2021/07/09 09:11

任意のSに対して

N>e^(4S)
となる自然数Nが存在する

n>N
となる
任意の自然数nに対し
n=(2^j)m,jは非負整数,mは奇数
となるj,mがある

φ(n)=φ(2^j)φ(m)≧φ(2^j)≧2^(j-1)
φ(n)=φ(2^j)φ(m)≧φ(m)

オイラーの定理から
奇数mに対して
2^φ(m)=1 (mod m)
2^φ(m)=1+mk
となる整数kがある
φ(m)≧1だから
1+mk=2^φ(m)≧2
1+mk≧2
mk≧1
k≧1/m
↓kは整数だから
k≧1
mk≧m
1+mk≧m+1
↓2^φ(m)=1+mkだから
2^φ(m)≧m+1
↓両辺のlogをとると
φ(m)log2≧log(1+m)
φ(m)≧log(1+m)/log2

φ(n)≧φ(m)≧log(1+m)/log2
φ(n)≧φ(2^j)≧2^(j-1)

m≧2^jの時
↓両辺にmをかけると
m^2≧(2^j)m
↓n=(2^j)mだから
m^2≧n
↓n>Nだから
m^2>N
↓N>e^(4S)だから
m^2>e^(4S)
↓両辺を1/2乗すると
m>e^(2S)
↓m<1+mだから
1+m>e^(2S)
↓両辺のlogをとると
log(1+m)>2S
↓2>log2だから
log(1+m)>Slog2
↓両辺をlog2で割ると
log(1+m)/log2>S

φ(n)≧log(1+m)/log2>S

2^j>mの時
↓両辺に(2^j)をかけると
2^(2j)>(2^j)m
↓(2^j)m=nだから
2^(2j)>n
↓n>Nだから
2^(2j)>N
↓N>e^(4S)だから
2^(2j)>e^(4S)
↓両辺を1/2乗すると
2^j>e^(2S)
↓e^(2S)>2Sだから
2^j>2S
↓両辺を2で割ると
2^(j-1)>S

φ(n)≧2^(j-1)>S

任意のSに対して
N>e^(4S)となる自然数Nが存在する
n>Nとなる任意の自然数nに対し
φ(n)>S
となるから
∴
lim_{n→∞}φ(n)=∞

この回答へのお礼

No.2の間違いと誤魔化してある部分をうまく修正していますね。

悪くないです。

お礼日時：2021/07/09 10:08

No.4 回答者： ありものがたり 回答日時： 2021/07/08 22:54

＞ 有界ではないということだけでは→∞を言えないのが難しいところです。

ダウト。
任意の M に対して、φ(n)≦M となる n には n≦N となる N が存在するから、
その N について n>N ⇒ φ(n) > M が成り立つ。
これは、εδ論法での limφ(n) = +∞ の定義そのもの。

この回答へのお礼

あ、失礼。
背理法と冒頭に書いてあったので背理法なのだとして読んでしまいました…。

お礼日時：2021/07/08 23:18

No.3 回答者： ありものがたり 回答日時： 2021/07/08 21:41

背理法で行く？

φ(n) が有界なら、
奇数 n に対して log₂ n が有界より n は有界。
偶数 n = (2^j)m に対して { 2^(j-1) } log₂ m が有界より、
j も m も有界になって n は有界。

対偶をとれば、 n→∞ のとき φ(n)→∞.

この回答へのお礼

有界ではないということだけでは→∞を言えないのが難しいところです。

お礼日時：2021/07/08 22:28

No.2 回答者： ありものがたり 回答日時： 2021/07/08 19:56

オイラーの定理より、

奇数 n について 2^φ(n) ≡ 1 (mod n).
2^φ(n) = nk+1 となる整数 k が存在することになるが、
φ(n) ≧ 1 より k ≧ １ は自明である。
2^φ(n) > nk の対数をとって、
φ(n) > log₂ n + log₂ k ≧ log₂ n.

n = (2^j)m, j は非負整数, m は奇数 のとき、
φ(n) = φ(2^j)φ(m) = { 2^(j-1) } φ(m) ≧ { 2^(j-1) } log₂ m.

n → ∞ のとき、 2^j → ∞ または m → ∞ となる。

この回答へのお礼

n→∞のとき2^j→∞またはm→∞までは理解できました。
ありがとうございます。

任意のM>0に対してあるNが存在してn>Nならばφ(n)>Mであることは、
2^j→∞またはm→∞であることからどのように言えばいいのでしょうか？

お礼日時：2021/07/08 21:32

No.1 回答者： stomachman 回答日時： 2021/07/08 08:08

「φ(n)→∞」とは

　　∀S∀M ∃n(n>M ∧ φ(n)＞S)
ということ。素数は無限個あるので、勝手な自然数S, Mについて、p＞Mかつp＞S+2を満たす素数pがいくらでも存在する。そしてφ(p)=p-2（∵ 1以上p以下の自然数のうち素数pと互いに素なのは、pと1以外の全部）なのでφ(p)＞S。

この回答へのお礼

間違っています。

お礼日時：2021/07/08 08:32