欧拉函数迭代问题

wsc810

如果我们定义欧拉函数$\varphi(2)=2$

对每一个因子继续计算欧拉函数的值则有

$\varphi(3)=\varphi(2)=2$  

$\varphi(4)=\varphi(2)=2$

$\varphi(5)=\varphi(4)=2$

$\varphi(5^2)=\varphi(4*5)=\varphi(4)*\varphi(5)=\varphi(4)\varphi(4)=2^2$

$\varphi(7)=\varphi(6)=\varphi(2)*\varphi(3)=2*2=2^2$

$\varphi(8)=\varphi(4)=2$

$\varphi(9)=\varphi(3-1)*\varphi(3)=2^2$

$\varphi(10)=\varphi(5)*\varphi(2)=2^2$

$\varphi(11)=\varphi(10)=\varphi(5)*\varphi(2)=2*2=2^2$

$\varphi(12)=\varphi(4)*\varphi(3)=2^2$

$\varphi(13)=\varphi(12)=\varphi(4)*\varphi(3)=2*2=2^2$

$\varphi(14)=\varphi(2)*\varphi(7)=2*2^2=2^3$

$\varphi(15)=\varphi(3)*\varphi(5)=2*2=2^2$

$\varphi(16)=\varphi(2^3)=\varphi(2^2)=2$

$\varphi(17)=\varphi(16)=2$

$\varphi(18)=\varphi(2)*\varphi(9)=2*2^2=2^3$

$\varphi(20)=\varphi(4)*\varphi(5)=2*2=2^2$

$\varphi(21)=\varphi(3)*\varphi(7)=2*2^2=2^3$

$\varphi(n)$是积性函数且有如下性质

$\varphi(2^n)=2$

$\varphi(p)=\varphi(p - 1)$

$\varphi(m*n)=\varphi(m)*\varphi(n)$   $m,n$互质

$\varphi(p^m)=\varphi(p-1)\varphi(p^{m-1})$

不知怎样用mathematica编写一个这样的函数，计算任意$\varphi(n)$的值或者返回2的指数

一个有趣的事实是如果把奇合数$p1*p2$看作是素数，计算$\varphi(p_1*p_2-1)$算出的结果 同$\varphi(p_1)*\varphi(p_2)$的值是不同的

如上例中的$\varphi(21),\varphi(20)$

wsc810

$\varphi(19)=\varphi(18)=\varphi(2)\varphi(9)=2*2^2=2^3$

$\varphi(20)=\varphi(4)\varphi(5)=2*2=2^2$

$\varphi(21)=\varphi(3)\varphi(7)=2*2^2=2^3$

$\varphi(23)=\varphi(22)=\varphi(2)\varphi(11)=2*2^2=2^3$

$\varphi(24)=\varphi(3)\varphi(8)=2*2=2^2$

$\varphi(25)=\varphi(4)\varphi(5)=2*2=2^2$

$\varphi(26)=\varphi(2)\varphi(13)=2*2^2=2^3$

$\varphi(27)=\varphi(2)\varphi(3^2)=2*2^2=2^3$

$\varphi(29)=\varphi(28)=\varphi(4)\varphi(7)=2*2^2=2^3$

$\varphi(31)=\varphi(30)=\varphi(5)\varphi(6)=2*2^2=2^3$

$\varphi(32)=2$

$\varphi(33)=\varphi(3)\varphi(11)=2*2^2=2^3$

$\varphi(34)=\varphi(2)\varphi(17)=2*2=2^2$

$\varphi(35)=\varphi(5)\varphi(7)=2*2^2=2^3$

$\varphi(37)=\varphi(36)=\varphi(4)\varphi(9)=2*2^2=2^3$

$\varphi(38)=\varphi(2)\varphi(19)=2*2^3=2^4$

$\varphi(39)=\varphi(3)\varphi(13)=2*2^2=2^3$

$\varphi(41)=\varphi(40)=\varphi(5)\varphi(8)=2*2=2^2$

$\varphi(43)=\varphi(42)=\varphi(2)\varphi(21)=2*2^3=2^4$

$\varphi(44)=\varphi(4)\varphi(11)=2*2^2=2^3$

$\varphi(45)=\varphi(5)\varphi(9)=2*2^2=2^3$

$\varphi(47)=\varphi(46)=\varphi(2)\varphi(23)=2*2^3=2^4$

$\varphi(48)=\varphi(3)\varphi(16)=2*2=2^2$

$\varphi(49)=\varphi(6)\varphi(7)=2^2*2^2=2^4$

$\varphi(50)=\varphi(2)\varphi(25)=2*2^2=2^3$

$\varphi(51)=\varphi(3)\varphi(17)=2*2=2^2$

$\varphi(53)=\varphi(52)=\varphi(4)\varphi(13)=2*2^2=2^3$

$\varphi(54)=\varphi(2)\varphi(27)=2*2^3=2^4$

$\varphi(55)=\varphi(5)\varphi(11)=2*2^2=2^3$

$\varphi(56)=\varphi(7)\varphi(8)=2^2*2=2^3$

$\varphi(57)=\varphi(3)\varphi(19)=2*2^3=2^4$

$\varphi(59)=\varphi(58)=\varphi(2)\varphi(29)=2*2^3=2^4$

$\varphi(61)=\varphi(60)=\varphi(4)\varphi(15)=2*2^2=2^3$

$\varphi(62)=\varphi(2)\varphi(31)=2*2^3=2^4$

$\varphi(63)=\varphi(7)\varphi(9)=2^2*2^2=2^4$

$\varphi(64)=2$

$\varphi(65)=\varphi(5)\varphi(13)=2*2^2=2^3$

补充内容 (2020-9-27 07:36):
哪位管理员可以重新编辑一下本贴所有涉及2^n的$\varphi(m)$的值，定义 $\varphi(5)=\varphi(4)=2^2$

wsc810

试计算 $\varphi(2047)=\varphi(23)\varphi(89)=\varphi(22)*\varphi(88)=\varphi(22)\varphi(8)\varphi(11)=2^3*2*2^2=2^6$

$\varphi(2046)=\varphi(2)\varphi(1023)=\varphi(2)\varphi(3)\varphi(11)\varphi(31)=2*2*2^2*2^3=2^7$

假设2047是素数,那么$\varphi(2047)=\varphi(2046)$,现在计算结果不相等，说明2047是合数，如果有不通过因子分解的其他计算方法,得到$\varphi(2047)$值，依此可以做一个

素性判定的算法

wsc810

$\varphi(p^m)=\varphi(p-1)\varphi(p^{m-1})$

$\varphi(\varphi(p^{m-1}))=\varphi(p-1)\varphi(p^{m-2})$

$\varphi(p^m)=\varphi^m(p-1)$

例  计算$\varphi(7^3)=\varphi(6)\varphi(7^2)=\varphi(6)\varphi(6)\varphi(7)=\varphi(6)^3=(2^2)^3=2^6$

若 m 是奇数 $\varphi(m^n)=\varphi(m)^n$

       $\varphi(45^2)=\varphi(5^2*3^4)=\varphi(5^2)\varphi(3^4)=2^2*2^4=2^6$

       $\varphi(45^2)=\varphi(45)^2=(2^3)^2=2^6$

wsc810

再计算一例

$\varphi(4181)=\varphi(37)\varphi(113)=\varphi(36)\varphi(112)=\varphi(36)\varphi(16)\varphi(7)=2^3*2*2^2=2^6$

$\varphi(4180)=\varphi(4)\varphi(5)\varphi(11)\varphi(19)=2*2*2^2*2^3=2^7$

根据公式  若 m 是素数，有 $\varphi(m)=\varphi(m-1)$ ，我们可以得到它的逆否命题  $\varphi(m)\ne\varphi(m-1)$ 则 m 是合数 ，上述实例也说明结果的正确性

另外 不能这样计算  $\color{red}{\varphi(36)=\varphi(6^2)=\varphi(6)^2=(2^2)^2=2^4}$

因为 6 不是素数

wsc810

计算一个三素因子的合数

$\varphi(1001)=\varphi(7*11*13)=\varphi(7)\varphi(11)\varphi(13)=2^2*2^2*2^2=2^6$

$\varphi(1000)=\varphi(2^3*5^3)=\varphi(2^3)\varphi(5^3)=2*2^3=2^4$

再计算一例 用最小的卡迈克尔数 561

$\varphi(561)=\varphi(3*11*17)=\varphi(3)\varphi(11)\varphi(17)=2*2^2*2=2^4$

$\varphi(560)=\varphi(2^4*5*7)=\varphi(2^4)\varphi(5)\varphi(7)=2*2*2^2=2^4$

此例说明 若 m 是素数  $\varphi(m)=\varphi(m-1)$  它的逆命题不成立 即  如果 $\varphi(m)=\varphi(m-1)$ 不一定推出 m 是素数，有可能 m 是合数

m=561  计算 $\varphi(m^2)=\varphi(m)\varphi(m)=(2^4)^2=2^8$

         $\varphi(m^2-1)=\varphi(561^2-1)=\varphi(314720)=\varphi(2^5*5*7*281)=\varphi(2^5)\varphi(5)\varphi(7)\varphi(281)=2*2*2^2\varphi(280)$

                                   =$2^4\varphi(2^3*5*7)=2^4*2*2*2^2=2^8$

         $\varphi(m^3)=\varphi(m)^3=(2^4)^3=2^12$

         $\varphi(m^3-1)=\varphi(561^3-1)=\varphi(176558480)=\varphi(2^4*5*7*103*3061)=2*2*2^2\varphi(102)\varphi(3060)=2^4\varphi(2*51)\varphi(2^2*3^2*5*17)$

                                   $=2^4*2*2^2\varphi(2^2)\varphi(3^2)\varphi(5)\varphi(17)=2^7*2*2^2*2*2=2^12$
  

卡迈克尔数 1105

$\varphi(1105)=\varphi(5*13*17)=\varphi(5)\varphi(13)\varphi(17)=2*2^2*2=2^4$

$\varphi(1104)=\varphi(2^4*3*23)=\varphi(2^4)\varphi(3)\varphi(23)=2*2*2^3=2^5$

hujunhua

$\varphi(n)$是部分积性函数，定义如下：
\[\begin{split}
\varphi(2^n)&=2\\
\varphi(p)&=\varphi(p - 1)\\
\varphi(m\*n)&=\varphi(m)\*\varphi(n), 2\nmid\gcd(m,n).
\end{split}\]
然后可以定义$\psi(n)=\log_2\varphi(n)$, 性质如下：
\[\begin{split}
\psi(2^n)&=1\\
\psi(p)&=\psi(p - 1)\\
\psi(m\*n)&=\psi(m)+\psi(n), 2\nmid\gcd(m,n).
\end{split}\]

wsc810

如果定义 $\varphi(2^n)=2^n$ ,那么 $\varphi(m)$就是一完全积性函数，这样定义使得原函数更加简洁，明了。

hujunhua

我认为这个函数的计算没有类似于欧几里德辗转相除法那样脱离因子分解的算法。

wsc810

定义 $\varphi(4)=\varphi(2*2)=\varphi(2)\varphi(2)=2*2=2^2$

以下对 $\varphi(m)$ 做重新计算

$\varphi(3)=\varphi(2)=2$

$\varphi(5)=\varphi(4)=2^2$

$\varphi(6)=\varphi(2)\varphi(3)=2^2$

$\varphi(7)=\varphi(6)=\varphi(2)*\varphi(3)=2*2=2^2$

$\varphi(8)=2^3$

$\varphi(9)=\varphi(3)*\varphi(3)=2^2$

$\varphi(11)=\varphi(10)=\varphi(2)*\varphi(5)=2*2^2=2^3$

$\varphi(13)=\varphi(12)=\varphi(4)*\varphi(3)=2^2*2=2^3$

$\varphi(14)=\varphi(2)*\varphi(7)=2*2^2=2^3$

$\varphi(15)=\varphi(3)*\varphi(5)=2*2^2=2^3$

$\varphi(17)=\varphi(16)=2^4$

$\varphi(19)=\varphi(18)=\varphi(2)*\varphi(9)=2*2^2=2^3$

$\varphi(20)=\varphi(4)*\varphi(5)=2^2*2^2=2^4$

$\varphi(21)=\varphi(3)*\varphi(7)=2*2^2=2^3$

$\varphi(23)=\varphi(22)=\varphi(2)\varphi(11)=2*2^3=2^4$

$\varphi(24)=\varphi(8)\varphi(3)=2^3*2=2^4$

$\varphi(25)=\varphi(4)\varphi(5)=2^2*2^2=2^4$

$\varphi(26)=\varphi(2)\varphi(13)=2*2^3=2^4$

$\varphi(27)=\varphi(3)\varphi(9)=2*2^2=2^3$

$\varphi(29)=\varphi(28)=\varphi(4)\varphi(7)=2^2*2^2=2^4$

$\varphi(31)=\varphi(30)=\varphi(5)\varphi(6)=2^2*2^2=2^4$

$\varphi(32)=2^5$

$\varphi(33)=\varphi(3)\varphi(11)=2*2^3=2^4$

$\varphi(34)=\varphi(2)\varphi(17)=2*2^4=2^5$

$\varphi(35)=\varphi(5)\varphi(7)=2^2*2^2=2^4$

$\varphi(37)=\varphi(36)=\varphi(4)\varphi(9)=2^2*2^2=2^4$

$\varphi(38)=\varphi(2)\varphi(19)=2*2^3=2^4$

$\varphi(39)=\varphi(3)\varphi(13)=2*2^3=2^4$

$\varphi(41)=\varphi(40)=\varphi(8)\varphi(5)=2^3*2^2=2^5$

$\varphi(43)=\varphi(42)=\varphi(2)\varphi(21)=2*2^3=2^4$

$\varphi(44)=\varphi(4)\varphi(11)=2^2*2^3=2^5$

$\varphi(45)=\varphi(5)\varphi(9)=2^2*2^2=2^4$

$\varphi(47)=\varphi(46)=\varphi(2)\varphi(23)=2*2^4=2^5$

$\varphi(48)=\varphi(16)\varphi(3)=2^4*2=2^5$

$\varphi(49)=\varphi(7)\varphi(7)=2^2*2^2=2^4$

$\varphi(50)=\varphi(2)\varphi(25)=2*2^4=2^5$

$\varphi(51)=\varphi(3)\varphi(17)=2*2^4=2^5$

$\varphi(53)=\varphi(52)=\varphi(4)\varphi(13)=2^2*2^3=2^5$

$\varphi(54)=\varphi(2)\varphi(27)=2*2^3=2^4$

$\varphi(55)=\varphi(5)\varphi(11)=2^2*2^3=2^5$

$\varphi(56)=\varphi(8)\varphi(7)=2^3*2^2=2^5$

$\varphi(57)=\varphi(3)\varphi(19)=2*2^3=2^4$

$\varphi(59)=\varphi(58)=\varphi(2)\varphi(29)=2*2^4=2^5$

$\varphi(61)=\varphi(60)=\varphi(4)\varphi(15)=2^2*2^3=2^5$

$\varphi(62)=\varphi(2)\varphi(31)=2*2^4=2^5$

$\varphi(63)=\varphi(7)\varphi(9)=2^2*2^2=2^4$

$\varphi(64)=2^6$

$\varphi(65)=\varphi(5)\varphi(13)=2*2^3=2^4$

补充内容 (2020-9-28 00:14):
更正  $\varphi(65)=\varphi(5)\varphi(13)=2^2*2^3=2^5$