定义
对于任意两整数 a , b a,b a,b,若 g c d ( a , b ) = 1 gcd(a,b)=1 gcd(a,b)=1,则称 a , b a,b a,b互质。
对于三个数或更多数的情况，我们称 g c d ( a , b , c ) gcd(a,b,c) gcd(a,b,c)为 a , b , c a,b,c a,b,c互质，若 g c d ( a , b ) = g c d ( b , c ) = g c d ( a , c ) = 1 gcd(a,b)=gcd(b,c)=gcd(a,c)=1 gcd(a,b)=gcd(b,c)=gcd(a,c)=1，则称 a , b , c a,b,c a,b,c两两互质。
欧拉定理
对于正整数n，欧拉函数 φ （ n ） \varphi（n） φ（n）是小于等于n中与n互质的数的个数
（ φ （ 1 ） = 1 ） （\varphi（1）=1） （φ（1）=1）
那么有： φ ( n ) = n ∗ p 1 − 1 p 1 ∗ p 2 − 1 p 2 ∗ . . . ∗ p m − 1 p m = ∏ 1 m ( 1 − 1 / p i ) \varphi(n)=n*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*...*\frac{p_m-1}{p_m}=\prod_{1}^{m}(1-1/p_i) φ(n)=n∗p1p1−1∗p2p2−1∗...∗pmpm−1=∏1m(1−1/pi)
其中 p 1 , p 2 … p n p_1,p_2…p_n p1,p2…pn为 n n n的所有质因数。
如果n为质数，那么 φ ( n ) = n − 1 \varphi(n)=n-1 φ(n)=n−1。
证明
设p为n的质因子之一，1 ~ n中p的倍数共有n/p个，同理，对于另一个质因子q，1 ~ n*有n/q个q的倍数，若要把这n/p+n/q个数去掉，则p*q的倍数被排除了两次，需要再加回来，因此1 ~ n中与n互质的数的个数为
n − n p − n q + n p q = n ∗ ( 1 − n p − n q + n p q ) = N ∗ ( 1 − 1 p ) ∗ ( 1 − 1 q ) n-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq}=n*(1-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq})=N*(1-\frac{1}{p})*(1-\frac{1}{q}) n−pn−qn+pqn=n∗(1−pn−qn+pqn)=N∗(1−p1)∗(1−q1)
性质
1. 1. 1.对于任意大于一的正整数，1 ~ n中与n互质的数的和为 n ∗ φ ( n ) / 2 n*\varphi (n)/2 n∗φ(n)/2。
2. 2. 2. 若a,b互质，则 φ ( a ∗ b ) = φ ( a ) ∗ φ ( b ) \varphi(a*b)=\varphi(a)*\varphi(b) φ(a∗b)=φ(a)∗φ(b)。
证明
因为
g
c
d
(
n
,
x
)
=
g
c
d
(
n
,
n
−
x
)
gcd(n,x)=gcd(n,n-x)
gcd(n,x)=gcd(n,n−x),所以与n不互质的数
x
x
x和
n
−
x
n-x
n−x成对出现，平均值为
n
/
2
n/2
n/2，因此与n互质的数的平均数也是
n
/
2
n/2
n/2