数学研发论坛

 找回密码
 欢迎注册
查看: 249|回复: 20

[原创] 欧拉函数迭代问题

[复制链接]
发表于 2020-9-25 22:28:39 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
本帖最后由 wsc810 于 2020-9-26 09:08 编辑

如果我们定义欧拉函数$\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)$

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-26 11:37:12 | 显示全部楼层
本帖最后由 wsc810 于 2020-9-26 21:57 编辑

$\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$

点评

11#已做了更新  发表于 2020-9-27 08:43
你是要重新定义φ(2^n)=2^n么?  发表于 2020-9-27 08:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-26 13:32:45 | 显示全部楼层
本帖最后由 wsc810 于 2020-9-26 13:56 编辑

试计算 $\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)$值,依此可以做一个

素性判定的算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-26 14:21:06 | 显示全部楼层
本帖最后由 wsc810 于 2020-9-26 21:43 编辑

$\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$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-26 17:04:43 | 显示全部楼层
本帖最后由 wsc810 于 2020-9-26 19:31 编辑

再计算一例

$\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 不是素数

点评

不是因为6不是素数,准确地说,是因为6是偶数。  发表于 2020-9-27 05:02
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-26 20:13:16 | 显示全部楼层
本帖最后由 wsc810 于 2020-9-26 22:13 编辑

计算一个三素因子的合数

$\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$

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-9-27 04:51:48 | 显示全部楼层
$\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}\]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-27 07:27:05 | 显示全部楼层
本帖最后由 wsc810 于 2020-9-27 08:33 编辑

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





毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-9-27 08:06:41 | 显示全部楼层
我认为这个函数的计算没有类似于欧几里德辗转相除法那样脱离因子分解的算法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-27 08:36:22 | 显示全部楼层
本帖最后由 wsc810 于 2020-9-27 09:09 编辑

定义 $\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$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-26 20:36 , Processed in 0.067314 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表