欧拉函数与平方因子

青青子衿 · 2019-8-4 17:30

正整数M与其欧拉函数φ(M)互素，是不是M没有平方因子？
Select[Select[Range[1000000], GCD[#, EulerPhi[#]] == 1 &], Not@*SquareFreeQ]

hbghlyj · 2019-8-6 08:16

Last edited by hbghlyj 2023-5-15 12:21逆否命题：$N$有平方因子$⇒N$与$φ(N)$有>1公因子
$p∣φ(p^2)=p(p-1)$
$p^2∣N⇒φ(p^2)∣φ(N)⇒p∣φ(N)$

hbghlyj · 2023-5-15 19:20

Last edited by hbghlyj 2023-5-16 08:10

hbghlyj 发表于 2019-8-6 01:19
逆命题
$N$与$φ(N)$有>1公因子$⇒N$有平方因子

逆命题不成立。见下方

Account		Remember me	Forgot password?
Password			Register account

[数论] 欧拉函数与平方因子