欧拉函数

定义与 \(m\)互素的剩余类的个数记为\(\varphi(m), \varphi(m)\)称之为欧拉函数

关于欧拉函数的结论

定理1: (欧拉定理) 若\((k, m)=1,\) 则:\(k^{\varphi(m)} \equiv 1(\bmod m)\)
$定理2: (费尔玛小定理) 若 \(p\) 为素数, 则对所有的整数\(a, a^{p}=a(\bmod m)\)
$定理3: 若 \((m_{1}, m_{2})=1\), 则 \(\varphi(m_{1} m_{2})=\varphi(m_{1})\varphi(m_{2})\)
$ 定理4: 若 \(m=p_{1}^{l_1} p_{2}^{l_2} p_{3}^{l_3} \ldots p_{s}^{l_s},\\ p_{1}<p_{2}<p_{3}<\ldots<p_{s},\) 则 \(\varphi(m)\)=\(m\) \(\prod_{i=1}^{s}\)\((1 - \frac{1}{p_i })\)

同余方程的解

有解判定

对于同余方程\(ax=b(mod m)\)，有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有\(ax+my=b\)
定理1：设\(a，b，m\)为整数，则方程\(ax+my=b\)有整数解的充分必要条件\((a,m)|b\)。
定理2：设\(a，b，m\)为整数，\((a,m)=1，x0，y0\)是方程\(ax+my=b\)的一个整数解，则该方程的任意整数解，均可表示：
\(x=x0+mt，y=y0-at\)，其中\(t\)为整数

解的个数的判定

定理：设\(a，b，m\)为整数，\((a,m)|b\)则同余方程\(ax+b ≡0(mod m)\) 有\((a, m)\)个模\(m\)互不相同的解。
定理：设a，b，m为整数，则
(1) 同余方程ax+b≡0(mod m)
(2) 上述同余方程若满足(a, m)|b，则有(a, m)个模m互不相同的解。
若x0有是方程的一个解，则这(a, m)个模m互不相同的解为：
\(x_i = x_0 + \frac{m}{(a,m)}i(mod m)\), \(i = 0,1,\cdots ,(a,m)-1\)

高次同余方程

设\(f(x)=a_nx^{n}+a_{n-1}x^{n-1}+…+a_1x+a_0\)为一整系数多项式，\(m\)是一整数，\(m ∤a_n\)，则同余方程

称为\(n\)次模\(m\)同余方程
高次同余方程的解非常不规则
如：\(x^2+1 ≡0(mod 3)\)无解，$ x^3-x≡0(mod 6)$有6个解

m=\(m_1m_2\)时

定理：设\(m_1，m_2\)为正整数\((m_1，m_2)=1\)，则同余方程
\(f(x)≡0(mod m_1m_2)\)的解数为二方程\(f(x)≡0(mod m_1)\)，\(f(x)≡0(mod m_2)\)的解数之积

m为素数p的幂(我也没学明白)

定理1：

设p为素数，\(f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots+a_{1}x+a_{0}\)，则同余方程\(f(x)\equiv0(mod p)\)的解数小于等于n（重数计算在内）。
证明分析：利用数学归纳法，且不妨设\(p∤a_{n}\)。
1时成立，不妨假设n-1成立，只要证明对n成立即可
显然如果\(f(x)\equiv0（mod p)\)没解，结论成立，因此我们不妨假设\(f(x)\equiv0（mod p)\)有一个解x\(\equiv a_{1}（mod p)\)
\(f(x)=(x-a_{1})f_{1}(x)+r_{1},r_{1}=0\)
\(f(x)\equiv(x-a_{1})f_{1}(x)(mod p)\)
\(f_{1}(x)\equiv(x-a_{1})f_{2}(x)(mod p)\)
\(f(x)\equiv(x-a_{1})^{k}f_{k}(x)(mod p)\)
\(f_{k-1}(x)\equiv(x-a_{1})f_{k}(x)(mod p)\)

定义: 设\(f(x)=a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0\),
\(f'(x) = n a_n x^{n-1} + (n-1)a_{n-1} x^{n-2} + \ldots + a_1\),
\(f(x)\)的第\(k\)次导数为\(f(x)\)的第\(k-1\)次导数的导数, 记为\(f^{(k)}(x)\)

定理2 (泰勒展开)

设\(f(x)=a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0\), 则
\(f(a+b) = f(a) + f'(a)b + f''(a)b^2/2! + \ldots + f^{(n)}(a)b^n/n!\)
仅考虑\(x^m\), 其中\(0 \leq m \leq n\)
\((a+b)^m = \sum_{i=0}^{m} \binom{m}{i} a^{m-i} b^i\)

定理3：

设f(X)是一个整系数多项式，k≥2，r是如下同余方程的根
f(X)≡0(mod \(p^{k-1}\))
则：
(1)若\(f’(r)≠0(mod p)\)，则存在唯一整数t，0≤t≤p-1，使得
\(f(r+tp^{k-1})≡0(mod p^{k})\)，其中t由下式给出：
\(t ≡ [f’(r)]^{-1}(f(r)/p^{k-1})(mod p)\)。
(2)若\(f’(r)≡0(mod p)，f(r)≡0(mod p^{k})\)，则对所有整数t都有：
\(f(r+tp^{k-1})≡0(mod p^{k})\)。
(3)若\(f’(r)≡0(mod p)，f(r)≢ 0(mod p^{k})\)，则\(f(X)≡0(mod p^{k})\)不存在解\(X≡r(mod p^{k-1})\)。

定理4

：设\(f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\)
\(f'(x)=na_nx^{n-1}+(n-1)a_{n-1}x^{n-2}+\cdots+a_1\)
(1)若\(f(x)\equiv 0(mod\;p)\)和\(f'(x)\equiv 0(mod\;p)\)无公共解，
则：\(f(x)\equiv 0(mod\;p^k)\)的解数等于\(f(x)\equiv 0(mod\;p)\)的解数
(2)如果\(x_1\)是\(f(x)\equiv 0(mod\;p)\)的解，且
\((f'(x_1),p)=1\)，则\(f(x)\equiv 0(mod\;p^k)\)有解：
\(x\equiv x_k(mod\;p^k)\)
其中，\(x_i\)由递推公式得到(i=2,...,k):
\(x_i\equiv x_{i-1}+p^{i-1}t_{i-1}(mod\;p^i), t_{i-1}\equiv[f'(x_1)]^{-1}f(x_{i-1})/p^{i-1}(mod\;p)\)
\(x_1\equiv x_{i-1}-[f'(x_1)]^{-1}f(x_{i-1})(mod\;p^i)\)

推论

若\(p\)为素数，则：

\(x^{p-1} \equiv 1(modp)\)有\(p-1\)个解