欧拉反演 欧拉定理
emptysetvvvv · · 个人记录
前置芝士：欧拉函数
1\ [ 欧拉定理]
- 【笔记】
欧拉定理：
特别的，当
证明：与费马小定理类似，由引理
\bigstar 这是由于 $kn\mod m$ 一定与 $m$ 互质，否则令 $a=kn\mod m$，$m$ 是 $a$ 的倍数，$kn$ 也是 $a$ 的倍数 即 $n$ 也是 $a$ 的倍数，矛盾。 $$∴\displaystyle \prod_{k\perp m}^{0<k<m}kn\mod m=\prod_{k\perp m}^{0<k<m}k$$ 即 $$\displaystyle \prod_{k\perp m}^{0<k<m}kn\equiv\prod_{k\perp m}^{0<k<m}k(\bmod\ m)$$ 又 $∵\prod_{k\perp m}^{0<k<m}k$ 与 $m$ 互质 $$∴\prod_{k\perp m}^{0<k<m} n\equiv1 \pmod m$$ 即 $$n^{\varphi(m)}\equiv1\pmod m$$ Q.e.d.
2\ [ 扩展欧拉定理]
- 【笔记】
扩展欧拉定理：
若有
对于末式进行证明：
我们从简单情况入手，
n 与m 不互素，不妨设p^\alpha\mid n ，p^\beta \mid m ，先来证明若\alpha\geqslant \varphi(m) ，则\large p^{\alpha}\equiv\ p^{\alpha\mod \varphi(m)+\varphi(m)}\normalsize\pmod m ，令
\displaystyle s=\frac{m}{p^\beta} ，则\gcd(s,p)=1 ，由欧拉定理，\large p^{\varphi(s)}\equiv 1\normalsize\pmod s ，又因为欧拉函数为积性函数，故
\varphi(s)\mid\varphi(m) ，从而有\large p^{\varphi(m)}\equiv 1\normalsize\pmod s ，也就是说
p^{\varphi(m)}-1 是s 的倍数，得出\large p^{\varphi(m)+\beta}-p^\beta 是m 的倍数，即\large p^{\varphi(m)+\beta}\equiv p^\beta\normalsize\pmod m ，又因为
\alpha\geqslant\varphi(m)\geqslant \beta （很容易证明），所以\large p^\alpha\equiv p^{\alpha-\beta+\beta}\equiv p^{\varphi(m)+\alpha} ，前提\alpha\geqslant \varphi(m) ，接下来证明这对于素数的幂亦成立，
最终，我们有$\displaystyle n^k=(\prod p_i^{\alpha_i})^k$，每一个$(p_i^{\alpha_i})^k$均满足上式，故结论成立，Qed. 对“容易证明”进行说明：$\varphi(m)\geqslant\varphi(p^\beta)=p^\beta-p^{\beta-1}\geqslant p^{\beta-1}$，结合图像可知超越方程$p^{\beta-1}=\beta$最多有两个解，观察得$p$最小取$2$时$1,2$为解，又因为指数函数在正半轴增长更快，所以$p^{\beta-1}\geqslant \beta$.
- 【题目】求：
【分析】
由扩展欧拉定理，有
2^\infty\equiv 2^{(2^{\infty}\mod \varphi(m)+\varphi(m))}\pmod m. 显然，我们只需要求出
2^{\infty}\mod \varphi(m)+\varphi(m) 即可用快速幂解决。相似的问题，显然将 $\varphi(m)$ 作为新的 $m$，递归解决。 由于 $\varphi(m)<m$，所以每次的 $m$ 严格递降，降为 $1$ 时，返回 $0$ 即可。 显然，对于任意的 $x\in \mathbb{N^+}$， 均可解决。
3\ [ 欧拉反演]
- 【笔记】
欧拉反演：
即
提示：利用积性函数证明。
证明：设
\displaystyle \sigma(n)=\sum_{d|n}\varphi(d) 首先证明
\sigma(n) 为积性函数，设n\perp m ，显然除了1 以外没有任何的k 满足k|n 且k|m ，则\displaystyle \sigma(n)\cdot \sigma(m)=\sum_{p|n}\varphi(p)\cdot \sum_{q|m}\varphi(q)=\sum_{p|n}\sum_{q|m}\varphi(p)\cdot \varphi(q)=\sum_{p|n}\sum_{q|m}\varphi(pq) $$\sum_{p|n}\sum_{q|m}\varphi(pq)=\sigma(nm)$$ 即 $\sigma(n)\cdot \sigma(m)=\sigma(nm)$，$\sigma$ 为积性函数。 再证明 $\sigma(n)=n$，对于素数 $p$，$\sigma(p)=\varphi(1)+\varphi(p)=1+(p-1)=p \displaystyle\sigma(p^k)=\sum_{i=0}^{k}\varphi(p^i)=1+(p-1)+(p^2-p)+\cdots+(p^k-p^{k-1})=p^k. 故对于合数
n=\prod p_i^{k_i} ，\sigma(n)=\prod \sigma (p_i^{k_i})=\prod p_i^{k_i}=n. Q.E.D.
值得一提的是，
\sigma 其实就是\text{id} .
- 【题目】求有多少整数对
(i,j) 满足1\leqslant i,j\leqslant n 且\gcd(i,j)=k .
【分析】
\displaystyle\sum_{i=1}^n\sum_{j=1}^n\left[\gcd(i,j)=k\right] =\displaystyle\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}\left[\gcd(i,j)=1\right] =\displaystyle 2\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^i\left[\gcd(i,j)=1\right]-1 =\displaystyle 2\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor} \varphi(i)-1. （乘
2 是因为i,j 可以互换，减1 是因为i=j 时计重）
- 【题目】求
\displaystyle\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j).
【分析】
\displaystyle\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j) =\displaystyle\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid \gcd(i,j)}\varphi(d) =\sum_{d}\varphi(d)\lfloor\frac{n}{d}\rfloor\cdot\lfloor\frac{m}{d}\rfloor
- 【题目】P3166 [CQOI2014]数三角形
【分析】
- 【题目】求有多少整数对
(i,j) 满足1\leqslant i,j\leqslant n 且\gcd(i,j) 为素数.
【分析】
\displaystyle\sum_{p\in\mathrm{prime}}^{p<n}\sum_{i=1}^n\sum_{j=1}^n\left[\gcd(i,j)=p\right] =\displaystyle\sum_{p\in\mathrm{prime}}^{p<n}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}\left[\gcd(i,j)=1\right] =\displaystyle\sum_{p\in\mathrm{prime}}^{p<n}\left(2\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^i\left[\gcd(i,j)=1\right]-1\right) =\displaystyle\sum_{p\in\mathrm{prime}}^{p<n}\left(2\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor} \varphi(i)-1\right).
- 【题目】若
m<n,m,n\in\mathbb Z ，那么[1,n!] 中有多少个数与m! 互质.
【分析】
求
\displaystyle\sum_{i=1}^{n!}[\gcd(i,m!)=1] 考虑
\gcd(i,m!)=\gcd(i+m!,m!) 我们将
[1,n!] 划分为若干个区间(0,m!],(m!,2m!]\cdots(n!-m!,n!] 每段区间内符合要求的数的个数相等
故答案为
\displaystyle\frac{n!}{m!}\varphi(m!)=\frac{n!}{m!}\cdot m!\prod_{p\mid m!}^{p\in\text{prime}}\frac{p-1}{p} =\large n!\prod_{p\leqslant m}^{p\in\text{prime}}\frac{p-1}{p}