欧拉函数性质及推导

互质

  • gcd(a,b) = 1 则a,b互质,
  • gcd(a,b,c) = 1 则两两互质
    gcd(a,b) = gcd(a,c) = gcd(b,c) = 1

    欧拉函数

    定义:[1,N)中与N互质数的个数被称为欧拉函数,记作 $\upsilon(N)$
    由算数基本定理知：$N = p_1^{c_1} * p_2^{c_2}*p_3^{c_3}……p_i^{c_i}$

  1. 先推倒i=2 c1=1 c2=1的情况，
    质因子为p,q,1~N中除去p的倍数, p,2p,3p,....,[n/p]*p, 那么1~N中有N/p个p的倍数， 同理q也有N/q个q的倍数，那么 $\upsilon(N)=N-N/q-N/p$,

    此时我们忽略了p,q同时被除去的倍数（应该是根据容斥定理）,例如2*3 3*2被计算2次，那么加上N/(p*q)个被减去2次的数的个数 就是所求的欧拉函数，(p*q)是p,q的最小公倍数，p,q的倍数一定是p*q的倍数,所以除以p*q

    所以 $\upsilon(N)=N-N/p-N/q+N/(p*q)$
    $\upsilon(N)=N(1-1/q)(1-1/p)$

  2. 放在N的全部质因子上的 欧拉函数 就为
    $\upsilon(N)=N(1-1/p_1)(1-1/p_2)…(1-1/p_i)$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//试除法分解质因数来求 欧拉函数值
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int n;
	cin >> n;
	int ans = n;
	for (int i=2; i<=sqrt(n); i++) {
		if (n%i == 0) {
			ans = ans / i * (i-1);
			while (n%i==0) n /= i; 
		}
	}
	if (n>1) ans = ans / n * (n-1);
	cout << ans; 
	return 0;
}

算数基本定理：
$N = p_1^{c_1} * p_2^{c_2}p_3^{c_3}……p_i^{c_i}$ ,其中p1,p2,..都是互质的
那么： $\upsilon(ab) = \upsilon(a)*\upsilon(b)$ （从欧拉函数推导过程i=2得来）

满足上述条件时， $\upsilon$ 也叫积性函数

延伸出来的欧拉函数的2个性质:(如果d是n的约数，记作d|n)

  1. p为质数,p|n 且 $p^2|n$ , 得 $p|(n/p)$
    带入欧拉函数然后得到 $\upsilon(n) = p\upsilon(n/p)$
    $\upsilon(n)=n    (1-p_1)(1-p_2)…$
    $\upsilon(n/p)=n/p*(1-p_1)(1-p_2)…$ ，然后相除
  2. p为质数,p|n且 $p^2 !|n$ ,( $p^2$不是n的约数),此时p与n/p互质，由基本性质得 $\upsilon(n)=\upsilon(n/p)*\upsilon(p)$ 以为p是个质数,1~p都与它互质，则 $\upsilon(p)=p-1$ ,
    则 $\upsilon(n)=(p-1)*\upsilon(n/p)$