本帖最后由 hbghlyj 于 2023-8-16 04:41 编辑
多项式除法解高次同余_黄嘉威.pdf
(129.69 KB, 下载次数: 0)
1. 引言由费马小定理开始高次同余有了计算方法,欧拉定理把它推广到合数情况,Carmichael函数更使同余运算更进一步.
本文将透过多项式除法让高次同余运算得到更大的发展.2. 费马小定理的推广费马小定理,即当$a$与$p$互素,且$p$为素数时,有$a^{p-1}≡1 \pmod p$.
这意味着多项式$x^p-x$整除$p$［1］,也意味着 $(x^p- x)^m$ 整除$p^m$. 展开即定理 2.1 $x^{m p} \equiv \sum_{i=1}^m(-1)^{i-1} \mathrm{C}_m^i x^{m p-(p-1) i}\pmod{p^m}$ 用一个例子比较一下这个递推式与欧拉定理$a^{φ( n)}≡1\pmod n.$\begin{align*}x^{14}&\equiv 2 x^8-x^2\pmod{7^2}\\x^{44}&\equiv x^2\pmod{7^2}\end{align*}前者能在更小次方的情况下递推,更多的情况下$mp$小于$( p - 1) p^{m-1}+ m$.
要是用前者递推高次同余,没能一步过的话会很麻烦,欧拉定理却能一步过.\begin{aligned} x^{1000}&\equiv 2 x^{994}-x^{988} \equiv 3 x^{988}-2 x^{982} \equiv \cdots\pmod{7^2}\\ x^{1000}&\equiv x^{34}\pmod{7^2}\end{aligned}定理2.2 $x^{m p+(p-1) n} \equiv \sum_{i=1}^m(-1)^{i-1} \mathrm{C}_{n+i-1}^{i-1} \mathrm{C}_{n+m}^{m-i} x^{m p-(p-1) i}\pmod{p^m}$ \begin{aligned} & x^{14+6 n} \equiv \mathrm{C}_{n+2}^1 x^8-\mathrm{C}_{n+1}^1 x^2\pmod{7^2} \\ & x^{1000} \equiv 166 x^{10}-165 x^4 \equiv 19 x^{10}-18 x^4\pmod{7^2} \\ & n=0 \text { 时为定理2.1}\end{aligned}假如 $x^{m p+(p-1) k} \equiv \sum_{i=1}^m(-1)^{i-1} \mathrm{C}_{k+i-1}^{i-1} \mathrm{C}_{k+m}^{m-i} x^{m p-(p-1) i}\pmod{p^m}$ 成立,\begin{aligned}& x^{m p+(p-1)(k+1)} \equiv \sum_{i=1}^m(-1)^{i-1} \mathrm{C}_{k+i-1}^{i-1} \mathrm{C}_{k+m}^{m-i} x^{m p-(p-1)(i-1)} \equiv \mathrm{C}_{k+m}^{m-1} x^{m p}+\sum_{i=2}^m(-1)^{i-1} \mathrm{C}_{k+i-1}^{i-1} \mathrm{C}_{k+m}^{m-i} x^{m p-(p-1)(i-1)} \\
& \equiv \sum_{i=1}^m(-1)^{i-1} \mathrm{C}_{k+m}^{m-1} \mathrm{C}_m^i x^{m p-(p-1) i}+\sum_{i=1}^{m-1}(-1)^i \mathrm{C}_{k+i}^i \mathrm{C}_{k+m}^{m-i-1} x^{m p-(p-1) i} \\
& \equiv(-1)^{i-1} \mathrm{C}_{k+m}^{m-1} x^m+\sum_{i=1}^{m-1}(-1)^{i-1}\left(\mathrm{C}_{k+m}^{m-1} \mathrm{C}_m^i-\mathrm{C}_{k+i}^i \mathrm{C}_{k+m}^{m-i-1}\right) x^{m p-(p-1) i}\pmod{p^m}\end{aligned}由于 $(-1)^{m-1} \mathrm{C}_{k+1+m-1}^{m-1} \mathrm{C}_{k+m}^{m-m} x^{m p-(p-1) m}=(-1)^{i-1} \mathrm{C}_{k+m}^{m-1} x^m$, 接下来只需证明一条恒等式:
$$\mathrm{C}_{k+m}^{m-1} \mathrm{C}_m^i-\mathrm{C}_{k+i}^i \mathrm{C}_{k+m}^{m-i-1}=\mathrm{C}_{k+i}^{i-1} \mathrm{C}_{k+1+m}^{m-i}$$
拆开后得到:
\begin{aligned} & \frac{(k+m) ! m !}{(m-1) !(k+1) ! i !(m-i) !}-\frac{(k+i) !(k+m) !}{i ! k !(m-i-1) !(k+i+1) !}=\frac{(k+i) !(k+m+1) !}{(i-1) !(k+1) !(m-i) !(k+i+1) !} \\ & \Leftrightarrow(k+i+1) m-(m-i)(k+1)=i(k+m+1) \\ & \Leftrightarrow k m+i m+m-k m-m+i k+i=i k+i m+i .\end{aligned}3. 递推与组合数待定因为$P^m_x= m! C^m_x$,所以多项式 $P(x,m)$ 必然整除对应的阶乘$m!$.定理3.1 $P^m_x≡x(x - 1)(x - 2)\dots(x - m + 1)≡0\pmod{m!}$. 考虑$x^3≡3x^2- 2x\pmod 6$,经过两次递推得到$x^4$同余次数小于3的多项式:
\[x^4≡3x^3- 2x^2≡3 (3x^2- 2x) - 2x^2≡7x^2- 6x^2≡x^2\pmod 6.\]定理3.2 必然存在常系数$c_i$使得$x^n \equiv \sum_{i=0}^{m-1} c_i x^i\pmod{m!}$［2］ 由于存在着递推关系$P^m_x≡0\pmod{m!}$, $x^n$必然与次数小于$m$的多项式模$m!$同余
待定后,当$x=0$时$x^n$为0,所以它必然是一个没有常数项的多项式.
例如:\begin{aligned}& x^n \equiv c_1 x+c_0\pmod{2 !} \\
& \left\{\begin{array} { l }
{ c _ { 0 } = 0 } \\
{ c _ { 1 } + c _ { 0 } = 1 }
\end{array} \rightarrow \left\{\begin{array}{l}
c_0=0 \\
c_1=1\end{array} \rightarrow x^n \equiv x\pmod{2!} .\right.\right. \\& x^n \equiv c_2 x^2+c_1 x+c_0\pmod{3!}. \\& \left\{\begin{array} { l } { c _ { 0 } = 0 } \\
{ c _ { 2 } + c _ { 1 } + c _ { 0 } = 1 } \\
{ 4 c _ { 2 } + 2 c _ { 1 } + c _ { 0 } = 2 ^ { n } }\end{array} \rightarrow \left\{\begin{array}{l}
c_0=0 \\
c_1=2-2^{n-1} \rightarrow x^n \equiv\left(2^{n-1}-1\right) x^2+\left(2-2^{n-1}\right) x\pmod{3 !} . \\
c_2=2^{n-1}-1
\end{array}\right.\right.\end{aligned}引理3.3 $m - 2$次多项式能待定成含有帕斯卡矩阵的通项［3］:$$
\left(\begin{array}{cccc}
\mathrm{C}_{x-1}^0 & \mathrm{C}_{x-1}^1 & \cdots & \mathrm{C}_{x-1}^{m-2}
\end{array}\right)\left(\begin{array}{cccc}
1 & 0 & \cdots & 0 \\
-1 & 1 & \cdots & 0 \\
\cdots & \cdots & \cdots & \cdots \\
(-1)^{m-2} & (-1)^{m-1} \mathrm{C}_{m-2}^1 & \cdots & 1
\end{array}\right)\left(\begin{array}{c}
1^n \\
2^n \\
\cdots \\
(m-1)^n
\end{array}\right) .
$$ 推论 3.4 $x^{n+1} \equiv \sum_{i=1}^{m-1} c_i x^i \equiv x \sum_{i=0}^{m-2} d_i \mathrm{C}_{x-1}^i\pmod{m !},n \geqslant m-1$
$$
x^{n+1} \equiv x\left(\begin{array}{cccc}
\mathrm{C}_{x-1}^0 & \mathrm{C}_{x-1}^1 & \cdots & \mathrm{C}_{x-1}^{m-2}
\end{array}\right)\pmatrix{1 & 0 & \cdots & 0 \\-1 & 1 & \cdots & 0 \\\cdots & \cdots & \cdots & \cdots \\(-1)^{m-2} & (-1)^{m-1} \mathrm{C}_{m-2}^1 & \cdots & 1}\left(\begin{array}{c}
1^n \\
2^n \\
\cdots \\
(m-1)^n
\end{array}\right)$$例如:\begin{aligned}x^{n+1}&\equiv x\left(\mathrm{C}_{x-1}^0\right)(1)\left(1^n\right) \equiv x\pmod2.
\\x^{n+1}&\equiv x\pmatrix{\mathrm C_{x-1}^0&\mathrm C_{x-1}^1}\pmatrix{1 & 0 \\ -1 & 1}\pmatrix{1^n \\ 2^n}\equiv x\pmatrix{1&x-1}\pmatrix{1 \\ 2^n-1}\equiv x\left[1+\left(2^n-1\right)(x-1)\right]\\&\equiv\left(2^n-1\right) x^2+\left(2-2^n\right) x\pmod 6 .\end{aligned}代入 $n=2,3$ 可得 $x^3 \equiv 3 x^2-2 x\pmod 6, x^4 \equiv 7 x^2-6 x \equiv x^2\pmod 6$.
参考文献
［1］潘承洞． 数论基础［M］． 北京: 高等教育出版，2012
［2］韩士安，林磊． 近世代数［M］． 北京: 科学出版社，2009
［3］黄婷，车茂林，彭杰，张莉． 自然数幂和通项公式证明的新方法［J］． 内江师范学院学报，2011.8 | 
