欧拉函数的计算

质数的定义可得,\(\phi(p)=p-1\)

\(\phi(p^k)=p^k-p^{k-1}\)

与p有公因数的数\(1*p^{p-1},2*p^{p-1},3*p^{p-1}......(p-2)*p^{p-1},(p-1)*p^{p-1},p*p^{p-1}\),共有p个这样的数

\(\phi(n*m)=\phi(n)*\phi(m)\),这是一个积性函数

关于积性函数，\(f(pq)=f(p)f(q),p⊥q\),若不要求\(p⊥q\),则称完全积性函数

现在有2个集合

\(A=\{ a\in[0,mn),gcd(a,mn)=1 \}\),\(B=\{ (b,c),b\in[0,m),c\in[0,n),gcd(b,m)=1,gcd(c,n)=1 \}\)

1.A，B的模数

由定义可得，\(\mid A\mid=\phi(mn)\),在B中，b有\(\phi(m)\)种取值，c有\(\phi(n)\)种取值，\((b,c)\)有\(\phi(m)*\phi(n)\)种取值

证明两个集合互为双射，就可以说明\(\phi(n*m)=\phi(n)*\phi(m)\)

2.有2个陈述需要被证明:

1.不同的a对应一组不同的(b,c),即存在\(f:A\rarr B\),且A到B为单射

2.不同的(b,c)对应一组不同的a,即存在\(f:B\rarr A\),且B到A为单射

证明1:

取a1,a2使\(a1\equiv a2 (modn),a1\equiv a2 (modm)\),即a1,a2在B中有相同的象

\(\therefore m\mid(a1-a2),n\mid(a1-a2)\)

\(\because gcd(m,n)=1\)

\(\therefore mn\mid(a1-a2)\)

\(\because a1,a2\in[0,mn)\)

\(\therefore a1=a2\)

即A中不存在两个不同的的元，使他们到B的象相同

证明2:

此处的证明就是中国剩余定理的一种情况，Chinese remainder theorem(CRT)，能引出许多性质来，这里只讨论限于二元同余方程组的解

\(x\equiv b(modm)\)

\(x\equiv c(modn)\)

式1可得\(x=b+my\)

将x带入式2

\(my\equiv c-b(modn)\)

可解出y,y有解，且必有1解\((gcd(m,n)=1)\),\(y\in[0,n)\)

回代入x，此时\(x\in[0,mn)\),且x为两个同余方程的解

这一事实说明了集合B中每一组(b,c)都能在A中找到唯一象

上述2个事实说明A，B互为满射，模数相等，即\(\phi(n*m)=\phi(n)*\phi(m)\)