定义：
欧拉函数是小于$n$的正整数中与n互质的数的数目（$varphi(1)=1$）。
通项公式：
$varphi (n)=nprod_{i=1}^k(1-frac{1}{p_i})$，其中$p_1,p_2...p_k$是$n$的所有素因子。
性质一：
若$n$为质数，则
$varphi (n)=varphi(2*n)$
证明：
因为$n$为质数，所以只有$n$的倍数与它不互质。
因为$varphi(n)=n-1$，$varphi(2*n)=2*n-n-1$($n$个偶数，$1$个$n$)，所以$varphi (n)=varphi(2*n)$。
性质二：
若$n$为一个质数$p$的k次方$p^k$，则
$varphi (p^k)=p^k-p^{k-1}$
证明：
因为因为$p$为质数，所以只有$p$的倍数与它不互质。
从$1$到$p^k$一共有$p^{k-1}$个$p$的倍数，所以$varphi(p^k)=p^k-p^{k-1}=p^k(1-frac {1}{p})$。
性质三：
$varphi(n)$是一个积性函数.
当$m$，$n$互质时，
$varphi(nm)=varphi(n)*varphi(m)$
证明：
构造以下矩阵
egin{matrix}
1& 2& 3&...&m\
n+1&n+2 & n+3&...& n+m\
2*n+1&2*n+2&2*n+3&...&2*n+m\
.&.& . & . & .\
.&.& . & . & .\
.&.& . & . & .\
(n-1)*m+1& (n-1)*m+2 & (n-1)*m+3 & ... & n*m
end{matrix}
这个$n*m$的矩阵包括了$1$到$n*m$的所有整数。我们发现第一行有$varphi(m)$个与$m$互质的数。因为若一个数$i$与$m$互质，$k*m+i$也与$m$互质。所以之后的$(n-1)$行也是每一行都有$varphi(m)$个与m互质的数。
那么每一列是不是也是$varphi(n)$个呢？是的。我们可以证明这$n$个数$mod n$互不相同。
我们假设存在两个数$mod n$相等。设这两个数为$k1$，$k2$。
因为两个数$mod n$相等，所以$k1=m1*n+r$，$k2=m2*n+r$。
又因为
$k1=q1*m+s,$，$k2=q2*m+s$
所以
$q1*m+s-q2*m-s=m1*n+r-m2*n-r$
$(q1-q2)*m=(m1-m2)*n$
因为$m$与$n$互质，所以$(q1-q2)$是$n$的倍数。又因为$(q1-q2)$最大值是$n-1$，所以$(q1-q2)$不是$n$的倍数，与假设矛盾。故没有两个数$mod n$相等。
通过上面的结论，我们可以得出每一行有$varphi(n)$个与$n$互质的数。
所以整个矩阵中与$n$和$m$都互质的数有$varphi(n)*varphi(m)$个，即$varphi(n*m)$。证毕。
证明通项公式：
因为$n$的所有质因子互质，所以$varphi(n)=varphi(prod_{i=1}^{k}p_i^{c_i})$。其中$p_i$是$n$的所有质因子，$c_i$是$p_i$的指数。
根据性质二，
$varphi(n)=prod_{i=1}^{k} p_i^{c_i}varphi(1-{}frac{1}{p_i})$
$varphi(n)=nprod_{i=1}^{k}varphi(1-{}frac{1}{p_i})$
所以欧拉函数通项公式为
$varphi(n)=nprod_{i=1}^{k}varphi(1-{}frac{1}{p_i})$。
性质四：欧拉定理
对于任意互质的两个正整数$a$，$n$，有$a^{varphi(n)}equiv 1(mod n)$。
证明：将$1$到$n$中的每一个与$m$互质的数按照$mod n$的大小排序：$x_1$，$x_2$，$x_3...x_{varphi(n)}$。
设$m_i=a*x_i$
1.$m$中的数$(mod n)$不同余。
证明：
假设$m_i$与$m_j$同余且$m_i>m_j$
则$a*x_i=q_i*n+r$，$a*x_j=q_j*n+r$
所以$a*(x_i-x_j)=n*(q_i-q_j)$
因为$a$与$n$互质，所以$(x_i-x_j)$必定为$n$的倍数。
又因为$(x_i-x_j)<n$
所以与假设矛盾。故$m$中的数$(mod n)$不同余。
2.$m$中的数与$n$取模的结果与$n$互质。
证明：设余数与$n$有公因子$r$
则$a*x_i=qn+pr=r(frac{qn}{r}+p)$
因为$frac{qn}{r}+p$是整数，所以$a*x_i$含有因数$r$，这意味着$a*x_i$与$n$不互质。而这与上面的结论矛盾。故$m$中的数与$n$取模的结果与$n$一定互质。
由1，2,可知，$m$中的数经过重新排列，必定模$n$同余于$x$
也就是
$prod_{i=1}^{varphi(n)}m_i equiv prod_{i=1}^{varphi(n)}x_i (mod n)$
变形
$a^{varphi(n)}prod_{i=1}^{varphi(n)}x_i equiv prod_{i=1}^{varphi(n)}x_i (mod n)$
$(a^{varphi(n)}-1)*prod_{i=1}^{varphi(n)}x_i equiv 0 (mod n)$
所以
$(a^{varphi(n)}-1)*prod_{i=1}^{varphi(n)}x_i|n$
因为$x_i$与$n$互质，所以
$a^{varphi(n)}-1 equiv 0 (mod n)$
$a^{varphi(n)} equiv 1 (mod n)$
性质五：
对于正整数$n$，有
$sum_{i|n}varphi(i)=n$。
证明：
设$F(n)$等于$sum_{i|n}varphi(i)$
设$m$是与$n$互质的一个正整数。
所以$F(n)*F(m)=sum_{i|n}varphi(i)*sum_{i|m}varphi(i)$
因为当$n$,$m$互质时，$varphi(n*m)=varphi(n)*varphi(m)$
又因为$n$，$m$互质，所以$n$和$m$的因数两两互质。
所以$F(n)*F(m)=sum_{i|n}sum_{j|m}varphi(i*j)$
因为$sum_{i|n}sum_{j|m}varphi(i*j)$包括了$n*m$的所有因数。
所以$F(n)*F(m)=F(n*m)$
所以$F(n)$是积性的。
考虑$n$的所有质因子$p$
$F(p_i^{c_i})=sum_{k=1}^{c_i-1}varphi(p_i^k)$
$F(p_i^{c_i})=sum_{k=1}^{c_i-1}p_i^k-p_i^{k-1}+1$
$F(p_i^{c_i})=p_i^{c_i}$
设$n$有$m$个质因子
$F(n)=prod_{i=1}^{m}p_i^{c_i}$
$F(n)=n$
性质六：
对于一个大于$2$的正整数$n$，$varphi(n) equiv 0 (mod 2)$。
证明：
假设$m$与$n$互质，且$n>m$，则$gcd(n,m)=gcd(n,n-m)=1$，这表明与$n$互质的数是成对存在的。
性质7：
对于一个正整数$n$和一个素数$p$
如果$p|n$且$p^2|n$，则$varphi(n)=varphi(frac{n}{p})*p$
如果$p|n$且$p^2 ot | n$，则$varphi(n)=varphi(frac{n}{p})*(p-1)$
证明：
因为$p|n$且$p^2|n$，所以$n$与$frac{n}{p}$有相同的质因子。
所以
$frac{varphi(n)}{varphi(frac{n}{p})}=frac{nprod_{i=1}^{k}(1-frac{1}{p_i})}{ frac{n}{p}prod_{i=1}^{k}(1-frac{1}{p_i})}=frac{n}{frac{n}{p}}=p$
如果$p|n$且$p^2
ot | n$，说明$p$与$frac{n}{p}$互质，
所以
$varphi(p*frac{n}{p})=varphi(p)*varphi(frac{n}{p})=varphi(frac{n}{p})*(n-1)$
线性筛：
void work(int n) { prime[1]=0; num[1]=1; int i,j; for(i=2;i<=n;i++) { if(!vis[i]) { vis[i]=1; prime[++prime[0]]=i; num[i]=i-1; continue; } for(j=1;j<=prime[0]&&prime[j]*i<n;j++) { vis[prime[j]*i]=1; if(i%prime[j]==0) { num[i*prime[j]]=num[i]*prime[j]; break; } num[prime[j]*i]=num[i]*(prime[j]-1); } } }
这是蒟蒻的第一篇数学博文，写的很丑请见谅。如果有错误的话，在评论里疯狂d我，我会fix的。