数学ナビゲーター掲示板

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

■47670 / 親記事)  オイラーのφ関数
  
□投稿者/ 小娘 一般人(1回)-(2016/05/30(Mon) 12:37:42)
    本を読んでいて疑問に思ったので教えて下さい

    自然数nに対し、n以下の自然数でnと互いに素であるものの個数をφ(n)とします
    kを与えられた自然数とします
    φ(n)=kをみたす自然数nの個数は有限である
    ってのは簡単に分かることでしょうか?
引用返信/返信 [メール受信/OFF] 削除キー/
■47671 / ResNo.1)  Re[1]: オイラーのφ関数
□投稿者/ らすかる 一般人(17回)-(2016/05/30(Mon) 19:26:06)
    ちょっと雑ですが
    nの素因数のうち2以外の個数はlog[3](n/2)個以下ですから、
    n以下でnと互いに素である数は少なくとも
    n×(1/2)×(2/3)^log[3](n/2)=(n/2)^log[3]2個以上あります。
    従ってφ(n)=kをみたす自然数nの個数は有限個です。

引用返信/返信 [メール受信/OFF] 削除キー/
■47672 / ResNo.2)  Re[1]: オイラーのφ関数
□投稿者/ IT 一般人(1回)-(2016/06/01(Wed) 19:50:59)
    (別解)
    φ(n)=k とする。
    nがk+1より大きい素因数pを持つとすると、φ(n)≧p-1>kとなるので、nの素因数はk+1以下。
    k+1以下の素数の個数をmとする。
    nを素因数分解してn=(p^a)(q^b)...(r^c) とする
    このときφ(n)=n(1-1/p)(1-1/q)...(1-1/r)=k
    よってn(1/2)^m≦k
    よってn≦k(2^m) したがってnは有限
引用返信/返信 [メール受信/OFF] 削除キー/
■47673 / ResNo.3)  Re[1]: オイラーのφ関数
□投稿者/ 小娘 一般人(2回)-(2016/06/01(Wed) 22:50:42)
    お二人とも有り難うございます
    よく分かりました
解決済み!
引用返信/返信 [メール受信/OFF] 削除キー/



スレッド内ページ移動 / << 0 >>

このスレッドに書きこむ

Mode/  Pass/

HOME HELP 新規作成 新着記事 ツリー表示 スレッド表示 トピック表示 発言ランク ファイル一覧 検索 過去ログ

- Child Tree -
Edit By 数学ナビゲーター