欧拉反演 欧拉定理

· · 个人记录

前置芝士：欧拉函数

1\ [欧拉定理]

欧拉定理：

\displaystyle n^{\varphi(m)}\equiv1(\bmod\ m),\quad n\perp m.

特别的，当m为质数时，即为费马小定理。

证明：与费马小定理类似，由引理\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\ [扩展欧拉定理]

扩展欧拉定理：

若有 k\geqslant \varphi(m)，则

n^k\equiv \begin{cases}n^{k \mod \varphi(m)}& n\perp m\\n^{k\mod \varphi(m)+\varphi(m)}& n\not\perp m\end{cases}\pmod m

对于末式进行证明：

我们从简单情况入手，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\mod m.

【分析】

由扩展欧拉定理，有

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\ [欧拉反演]

欧拉反演：n的所有因子的欧拉函数和为n。

即

\displaystyle\sum_{d\mid n}\varphi(d)=n.

提示：利用积性函数证明。

证明：设 \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}.

【分析】

\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\sum_{d\mid \gcd(i,j)}\varphi(d)
=\sum_{d}\varphi(d)\lfloor\frac{n}{d}\rfloor\cdot\lfloor\frac{m}{d}\rfloor

【分析】

【分析】

\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).

【分析】

求\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}