欧拉函数如何运算快!当 n=12时，它的值是多少？

由原根定义 (p-1)^φ(q)=1(modq)...φ(q)=2q,..所以(p-1)^p=-1(modq).由欧拉判别法可知为非二次剩余.φ
因为无平方因子.所以n的每个素因子的幂次都等于1.即(p1-1)(p2-1).(pi-1)|n-1.假设只有两个素因子.则(p-1)(q-1)|pq-1.(p-1)|pq-1.p-1|q-1..同理q-1|p-1...所以p=q矛盾.尝试所有余数发现-1是模24的非二次剩余.所以n的素因子幂次均为1.所以除数函数为(p1+1)...(pi+1)易知n有3k+2型的素因子和8k+7型或8k+3型和8k+5型.两种情况均能被24整除

对正整数n,欧拉函数φ(n)是少于或等于n的数中与n互质的数的数目
与10互质的数有1,3,7,9
共4个
所以φ(10)=4
通常计算如下：
10=2*5
φ(10)=10*(1-1/2)*(1-1/5)=4

据我所知是没什么关系的.
一些相关的结论：
Fermat-Euler定理：a^φ(p)=1(mod p),即a的阶是φ(p)=p-1的因子.
原根的存在性：至少存在一个a满足1

24的约数有1, 2, 3, 4, 6, 8, 12, 24, 其中后继为素数的有1, 2, 4, 6, 12.
因此n的可能质因数有2, 3, 5, 7, 13.
可设n = 2^a·3^b·5^c·7^d·13^e.
有24 = φ(n) = φ(2^a)·φ(3^b)·φ(5^c)·φ(7^d)·φ(13^e).
分别由φ(2^a), φ(3^b), φ(5^c), φ(7^d), φ(13^e)是24的约数, 可知a ≤ 4, b ≤ 2, c, d, e ≤ 1.
可能性情况约束为有限种.
1. 若e = 1, 有φ(2^a)·φ(3^b)·φ(5^c)·φ(7^d) = φ(n)/φ(13) = 2.
可知a ≤ 2, b ≤ 1, c = d = 0.
(1) 若b = 1, φ(2^a) = 1, 可得a = 0, 1, 分别得解n = 39, 78.
(2) 若b = 0, φ(2^a) = 2, 可得a = 2, 得解n = 52.
2. 若e = 0, d = 1, 有φ(2^a)·φ(3^b)·φ(5^c) = φ(n)/φ(7) = 4.
可知a ≤ 3, b ≤ 1, c ≤ 1.
(1) 若c = 1, φ(2^a)·φ(3^b) = 1, 得b = 0, a = 0, 1, 分别得解n = 35, 70.
(2) 若c = 0, b = 1, φ(2^a) = 2, 得a = 2, 得解n = 84.
(3) 若b = c = 0, φ(2^a) = 4, 得a = 3, 得解n = 56.
3. 若d = e = 0, c = 1, 有φ(2^a)·φ(3^b) = φ(n)/φ(5) = 6.
可知b = 2, 否则左端不能被3整除.
于是φ(2^a) = 1, 得a = 0, 1, 得解n = 45, 90.
4. 若c = d = e = 0, 有φ(2^a)·φ(3^b) = 24.
同样知b = 2, 于是φ(2^a) = 4, 得a = 3, 得解n = 72.
综上, 全部解为n = 35, 39, 45, 52, 56, 70, 72, 78, 84, 90, 共10个.
以上过程可以推广为一般方法(虽然效率难以保证).
枚举φ(n)的约数, 确定n的可能的素因子.
确定各素因子的指数范围, 然后在有限的范围内枚举指数的取值.
视情况不需要枚举所有可能的组合, 而是可由已经取定的指数进一步限制未取定的指数的范围.

当且仅当m=1或2时,φ(m)是奇数.
证明：
当m=1时,显然φ(m)=1是奇数；
设 m=p1^n1*p2^n2*.*pk^nk 是 m 的标准分解式,
其中 pi 为质数,ni 为正整数.
则φ(m)=[p1^n1-p1^(n1-1)]*[p2^n2-p2^(n2-1)]*.*[pk^nk-pk^(nk-1)] ,
如果 k>=2 ,则至少有一个 pi 为奇质数,而 pi^ni-pi^(ni-1)=pi^(ni-1)*(pi-1) 为偶数,则φ(m)为偶数.
所以,k=1 ,且 p1=2 ,m=2^n ,n>0
则 φ(m)=2^n-2^(n-1)=2^(n-1) 为奇数,所以 n=1 ,此时 m=2 .
故当且仅当m=1或2时,φ(m)是奇数.
更多内容,请参见我的博文：
常用数论术语、符号、性质参考约定

首先我们知道因数分解定理,设
n=Πpi^αi
Φ(n)=Π(pi^αi-pi^(αi-1))
如果n=2^α,α≥2
则Φ(n)=2^α-2^(α-1),=[2^(α-1)](2-1)
为偶数；
如果n>2,而且至少有一个奇素数p
则 p^α-p^(α-1) 为偶数（α≥1）
(因为 p^α与p^(α-1) 均为奇数)
故若N＞2,则Φ(N)必定是偶数.

就是这样
3^k≡1(mod 53)
则k|52
3^2,3^4不符
3^13≡243^2*27≡31^2*27≡30(mod 53)
3^26≡900≡52(mod 53)
3^52≡1（mod 53)
可知.

套用结论的话,就是用中国剩余定理:
同余方程组x ≡ a (mod n1),x ≡ b (mod n2)在mod n意义下存在唯一解x ≡ c (mod n).
这样建立了{0,1,...,n1-1}×{0,1,...,n2-1} → {0,1,...,n-1}的单射,
比较元素个数可知这也是双射.
由c ≡ a (mod n1),c ≡ b (mod n2),n = n1·n2.
可验证(a,n1) = 1且(b,n2) = 1的充要条件是(c,n) = 1.
因此上述映射刚好给出A×B → C的双射.
用Bezout定理可以给出构造的细节.
由(n1,n2) = 1,存在整数u,v,满足n1·u+n2·v = 1.
可验证c = n1·ub+n2·va即满足c ≡ a (mod n1),c ≡ b (mod n2),
且c mod n的余数不依赖u,v的选取.
此外(a,n1) = 1且(b,n2) = 1的充要条件是(c,n) = 1.
构造映射将(a,b)映为c mod n的余数,可验证其为A×B → C的双射.

设m=2^a*p1^a1*.*pk^ak ,其中pi为奇素数
则 φ(m)=φ(2^a)Πφ(pi^ai)
=[2^a-2^(a-1)]Π[pi^ai-pi^(ai-1)]
pi^ai与pi^(ai-1)均为奇数,得pk^ak-pk(ak-1)为偶数,
所以2^a-2^(a-1)为奇数,得a=1,
m=2

E(x)表示比x小的且与x互质的正整数的个数.
*若p是素数,E(p)=p-1.
*E(p^k)=p^k-p^(k-1)=(p-1)*P^(k-1)
证：令n=p^k,小于n的正整数数共有n-1即(p^k-1)个,其中与p不质的数共[p^(k-1)-1]个(分别为1*p,2*p,3*p...p(p^(k-1)-1)).
所以E(p^k)=(p^k-1)-(p^(k-1)-1)=p^k-p^(k-1).得证.
*若ab互质,则E(a*b)=E(a)*E(b),欧拉函数是积性函数.
*对任意数n都可以唯一分解成n=p1^a1*p2^a2*p3^a3*...*pn^an(pi为素数).
则E(n)=E(p1^a1)*E(p2^a2)*E(p3^a3)*...*E(pn^an)
=(p1-1)*p1^(a1-1)*(p2-1)*p2^(a2-1)*...*(pn-1)*pn^(an-1)
=(p1^a1*p2^a2*p3^a3*...*pn^an)*[(p1-1)*(p2-1)*(p3-1)*...*(pn-1)]/(p1*p2*p3*...*pn)
=n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
* E(p^k) =(p-1)*p^(k-1)=(p-1)*p^(k-2)*p
E(p^(k-1))=(p-1)*p^(k-2)
->当k>1时,E(p^k)=E(p*p^(k-1))=E(p^(k-1))*p.
(当k=1时,E(p)=p-1.)
由上式: 设P是素数,
若p是x的约数,则E(x*p)=E(x)*p.
若p不是x的约数,则E(x*p)=E(x)*E(p)=E(x)*(p-1).
*快速求欧拉函数方法：
首先来回顾一下线性筛选素数方法：

phi(1)=1
phi(2)=1
phi(3)=2
phi(4)=2
phi(5)=4
phi(6)=2
phi(7)=6
phi(8)=4
phi(9)=6
phi(10)=4
phi(11)=10
phi(12)=4
phi(13)=12
phi(14)=6
phi(15)=8
phi(16)=8
phi(17)=16
phi(18)=6
phi(19)=18
phi(20)=8
具体计算规则将n素因子分解为(p1^a1)(p2^a2)...(pk^ak)
则phi(n)=n(1-1/p1)(1-1/p2).(1-1/pk)
如n=18=2×3² 则phi(18)=18(1-1/2)(1-1/3)=18×1/2×2/3=9×2/3=6

1、分母是正整数n的既约真分数的个数是多少?为什么?
2、分母不大于n的既约真分数的个数是多少?为什么?
答：
[外一则]简化剩余系,亦称既约剩余系,缩剩余系,简称缩系.
以下记表示欧拉（缩系计量）函数的希腊字母Φ为ph.
1、分母为n的真分数,1