帐号 自动登录 找回密码 密码 欢迎注册
 搜索

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

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

x

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

楼主| 发表于 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

楼主| 发表于 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 不是素数

### 点评

楼主| 发表于 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$

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

 您需要登录后才可以回帖 登录 | 欢迎注册 本版积分规则 回帖后跳转到最后一页

GMT+8, 2020-10-19 23:53 , Processed in 0.062836 second(s), 18 queries .