@minomusi09 さんの「使い方」を原文で引用します: > 趣味で作った逆関数を求めるプログラムです > 処理できないバグあり ----v @_0xfffrog- による補足&追加 v---- オリジナルのプログラムは別のスクリプトで置き換えてしまったのでほとんど残っていません。 Euler's product formula を利用したアルゴリズムで高速化しました。 オイラー函数 (aka totient function) は、"単調" でないので、逆函数は多値函数になります。 * 単射でないので、正しい意味での逆関数は存在しません。$\phi(k)=n$となる$k$を列挙する、ということです。 たとえば、 $ \phi(n) = 40 $の解 $n, n\in\mathbb{N}$ は {41, 55, 75, 82, 88, 100} の6つです。 この逆関数の値の個数を調べることは未解決問題です。 ----TOYOPUTI による補足&追加 v---- $ \phi(n) = 40 $の解 $n, n\in\mathbb{N}$ は {41, 55, 75, 82, 88, 100, 110, 132, 150} の9つです。 (\ /) (\( * - * )/) ( ) V Ｖ* このイラストかわいい
オイラーの関数の性質として、 φ(p^n) = (p-1)p^(n-1) (n>=1,pは素数) φ(mn) = φ(m)φ(n) (m,nは互いに素) が成り立ちます。 ここから、 「n=φ(k)ならば、nは(p1-1),(p2-1),...の全ての公倍数(p1,p2,...はkの異なる素因数)である。」 がいえて、その対偶である 「nの約数とならない(p1-1),(p2-1),...(p1,p2,...はkの異なる素因数)が存在するならば、n≠φ(k)」 もいえます。 このプログラムはこの性質を用いています。 ちなみに、このことからφ(k)=nとなるkは1以外の奇数nに対しては存在しないことが言えます。
