1.欧拉函数: 1~N中与N互质的数的个数被称为欧拉函数,记为ϕ(N) 若在算数基本定理中,N=p1^a1p2^a2……*pm^am,则: ϕ(N)= N×(p1−1)/p1×(p2−1)/p2×…×(pm−1)/pm。
用的是容斥原理!!! 就是ϕ(N)的展开式。 欧拉函数与质数出现的次数无关。 2.互质: 互质数指的是在两个或多个整数中,它们的最大公约数仅为1的非零自然数。