多项式学习笔记

1. 阶

1.1. 定义

假设模数 m 和底数 a 互质。

对于 \(n\in Z\)，\(a^n \bmod m\) 呈循环结构，这种循环节的最小长度就是 a 模 m 的阶。

准确来说，对于 \(a\bot m\)，满足同余式 \(a^n\equiv 1(\bmod m)\) 的最小正整数 n 称作 a 模 m 的阶，记作 \(\delta_m(a)\)。

1.2. 幂的循环结构

利用阶，就可以刻画幂的循环结构，对于 \(a^n\bmod m\)，记 \(n=k\delta_m(a)+r\),则 \(a^n\equiv a^r(\bmod m)\)。

性质1：对于 \(a\in Z,m\in N+,a\bot m\)，\(a^0,a^1,\dots a^{\delta_m(a)-1}\) 模 m 余数互不相同。

性质2：对于 \(a,n\in Z,m\in N+,a\bot m\)，\(a^n\equiv 1(\bmod m)\) 成立当且仅当 \(n|\delta_m(a)\)

根据欧拉定理 \(a^{\varphi(m)}\equiv 1(\bmod m)\)，所以对于所有 \(a\bot m\)，必有 \(\delta_m(a)|\varphi(m)\)，即 \(\varphi(m)\) 是所有 \(a\bot m\) 的阶的公倍数。

性质3：对于 \(a,k\in Z,m\in N+,a\bot m\)，有 \(\delta_m(a^k)=\dfrac{\delta_m(a)}{gcd(\delta_m(a),k)}\)

1.3. 乘积的阶

设 a,b 是与 m 互质的不同整数，已知阶 \(\delta_m(a)\) 和 \(\delta_m(b)\)，那么可以得到：

性质4：

\(\dfrac{[\delta_m(a),\delta_m(b)]}{(\delta_m(a),\delta_m(b))}|\delta_m(ab)|[\delta_m(a),\delta_m(b)]\)

后半部分根据性质2易得，考虑前半段：

因为 \(1\equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)\delta_m(b)}(\bmod m)\)，所以
\(\delta_m(a)|\delta_m(ab)\delta_m(b)\)

两侧消去 \((\delta_m(a),\delta_m(b))\)，去掉互质部分，得到

\[\dfrac{\delta_m(a)}{(\delta_m(a),\delta_m(b))}|\delta_m(ab) \]

同理，

\[\dfrac{\delta_m(b)}{(\delta_m(a),\delta_m(b))}|\delta_m(ab) \]

因为左侧互质，所以就是之前的结论了。

同时 \(\delta_m(ab)=\delta_m(a)\delta_m(b)\Leftrightarrow \delta_m(a)\bot \delta_m(b)\)

性质5：对于 \(a,b\in Z,m\in N+,a,b\bot m\)，存在 \(c\in Z\) 且 \(c\bot m\) 使得：\(\delta_m(c)=[\delta_m(a),\delta_m(b)]\)

设 \(\delta_m(a)=\prod_p p^{a_p},\delta_m(b)=\prod_p p^{b_p}\)

根据 \(a_p\) 和 \(b_p\) 的大小关系分成两类：

\[A=\{p:a_p\ge b_p\},B=A=\{p:a_p< b_p\} \]

\[xA=\prod_{p\in A} p^{a_p},xB=\prod_{p\in B} p^{b_p},yA=\prod_{p\in B} p^{a_p},yB=\prod_{p\in A} p^{b_p} \]

所以：\(\delta_m(a)=xAyA,\delta_m(b)=xByB\)

\[\delta_m(a^{yA})=xA，\delta_m(a^{yB})=xB \]

因为 \(xA\bot xB\)

所以：\(\delta_m(a^{yA}b_{yB})=xAxB=[\delta_m(a),\delta_m(b)]\)