大SB·DEL翘课颓到广图什么都不想干,看了一下午不是很熟悉的数论公式。
有些甚至还不会证,先摆上来。
因为没有多少时间,且之后可能几个月没办法继续维护,就先将就放着了。
注意 无行文逻辑。

中国剩余定理 Chinese Remainder Theorem

问题:求同余方程组 $$ x \equiv a_i \pmod {m_i} \tag{1} \label{1} $$ 的通解,其中 $ (m_i, m_j)=1 $。

其实这并不是一个算法,而只是一个特别巧妙地构造解的技巧而已……思维上很有难度,但一旦作为一个定理证明则特别简单。

Theorem 1 (CRT) 令 $ M = \prod_i m_i, w_i = M / m_i $,且令 $ e_i, f_i \in \mathbb Z_+ $ 满足 $ w_ie_i+m_if_i=(w_i,m_i)=1 $$,则 $$ \eqref{1} $ 的通解为 $$ x equiv sum_i a_ie_iw_i pmod M $$

Proof 考察解之于每一个$ m_i $,注意到每一项除了$ a_ie_iw_i $均因被$ m_i $整除而被约去,而$ w_ie_i+m_if_i=1 $变形即得$ w_ie_i \equiv 1 \pmod {m_i} $,故该通解 satisfying 原题一切方程。Q.E.D.

Mathjax 没有小黑方块真不爽

在 OI 里面的运用的话,也就一个拓欧求各 $ e_i $ 而已。

指数循环节(proof under-given)

在模 $ p \in \mathbb P $ 剩余系 $ \mathbb Z/p \mathbb Z $ 下所有数均为该群的生成元。即对$ a \in \mathbb Z/p \mathbb Z $,$ a^i $ 表示之内所有数。
由(Fermat's) $ a^{p-1} \equiv 1 \pmod p $ 可知每 $ p-1 $ 次幂一循环。

拓展由(Euler's)$ a^{\varphi(n)} \equiv 1 \pmod n, (a,n)=1 $给出,当$ a,n $互质时,每$ \varphi(n) $次幂一循环。

更通用情况为$ a^x \equiv a^{x \text{mod} \varphi(n) + \varphi(n)} \pmod n $。无任何互质要求。

二次剩余:欧拉准则 Quadratic Residue: Euler's criterion (proof under-given)

(Euler's)

$$ a^{\frac{p-1}{2}} \equiv \begin{cases} 1 \pmod p, & \text{if there is an interger} x \text{such that} x^2 \equiv a \pmod p \\\\ -1 \pmod p, & \text{otherwise} \end{cases} $$

标签: none

添加新评论