学习笔记 - 数论/数学 - 欧拉函数与莫比乌斯函数

zjcOvO · 2021-09-26 20:53:10 · 个人记录

欧拉函数

欧拉函数表示小于等于 n 的正整数中与 n 互质的数的个数，记作 \varphi(n)

举个例子：小于等于 10 的正整数有 {1,2,3,4,5,6,7,8,9,10}，其中有且只有 {1,3,7,9} 与 10 互质，故 \varphi(10)=4

OEIS 上的欧拉函数序列：

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	...

欧拉函数的性质

积性函数

\text{if } \gcd(a,b)=1 \implies\varphi(a)\times\varphi(b)=\varphi(a\times b)

（特别的，n\in\text{odd}\implies\varphi(2n)=\varphi(n)）

n=\sum_{d|n}\varphi(d)

（特别的，n\in\text{prime}\iff\varphi(n)=n-1）

把 n 分解质因数：n=\prod_{i=1}^s p_i\;(p_i\in\text{prime})\implies\varphi(n)=n\times\prod_{i=1}^s \dfrac{p_i-1}{p_i}
欧拉定理

\gcd(a,m)=1\implies a^{\varphi(m)}\equiv1\pmod m

例： 5^{\varphi(6)}=5^2=25\equiv1\pmod6

\qquad\,7^{\varphi(12)}=7^4=2401\equiv1\pmod{12}

\qquad\,.\,.\,.\;.\,.\,.

扩展欧拉定理

a^b=\begin{cases}a^{b\bmod\varphi(b)},&\gcd(a,p)=1\\a^b,&\gcd(a,p)\ne1,b<\varphi(p)\\a^{(b\bmod\varphi(p))+\varphi(p)},&\gcd(a,p)\ne1,b\ge\varphi(p)\end{cases}\quad\pmod p

求 \varphi(n)

挖坑

莫比乌斯函数

\mu(n)=\begin{cases}1,&n=1\\0,&n=k\cdot z^2\;(k,z\in\mathbb Z)\\(-1)^k,&n=\prod_{i=1}^kp_i,\;p_i\in\text{prime}\end{cases}

举个例子：10=2\times5 ，故 \mu(10)=(-1)^2=1
\qquad\qquad\;\;24=2^3\times3$，故 $24=6\times2^2$，$\mu(24)=0

莫比乌斯函数的性质

积性函数

\text{if } \gcd(a,b)=1 \implies\mu(a)\times\mu(b)=\mu(a\times b)

\sum\limits_{d|n}\mu(d)\;=\begin{cases}1,&n=1\\0,&n\ne1\end{cases}

求 \mu(n)

挖坑