| ■47672 / inTopicNo.3) |
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は有限
|
|