基本概念和一次同余式

基本概念

同余式的定义：设$m\in Z_{+},f(x)=a_nx_n+a_{n-1}x^{n-1}+…+a_{1}x+a_0,a_i\in Z$，则$f(x)\equiv0(~mod~m)$叫做模m的同余式，若$a_i\not\equiv 0~(mod~m)$，则n叫做上述同余式的次数。

同余式解的定义：若a是使得$f(a)\equiv0~(mod~m)$成立的一个整数，则称a所在的模m的剩余类$k_a$为同余式的一个解(一类解)，记为$x\equiv a~(mod~m)$

一次同余式

一次同余式：形如$ax\equiv b~(mod~m)$，且满足$a\not\equiv 0~(mod~m)$，这样形式的式子称为一次同余式。

定理1：一次同余式$ax\equiv b~(mod~m),a\not\equiv 0~(mod~m)~~$当$(a,m)=1$时有唯一解。即当未知数系数与模数互质的时候有唯一解。

定理2：设$(a,m)=d$，则一次同余式$ax\equiv b~(mod~m),a\not\equiv 0~(mod~m)~~$,有解的充分必要条件是$d\mid b$，当该同余式有解时，它恰好有d个解

解一次同余方程

  • 熟悉完定理1和定理2的推导过程，其实可以了解到解一次同余方程其实就是解不定方程。下面俩个例题给出解同余方程的步骤。

求解同余方程步骤：

  1. 先求解$gcd(a,m)$，判断a和m是否互素。当$gcd(a,m)$互素可以得到该方程有唯一解，当不互素的时候令$gcd(a,m)=d$，判断d是否能整除b，能整除就说明有d个解，不能整除就说明该同余方程无解
  2. 当$gcd(a,m)=1$时，直接去解二元不定方程$as+mt=1$，求出s，得到唯一解为$x\equiv bs~mod(~m)$，就结束了。
  3. **当$gcd(a,m)=d$**并且同余方程有解时，我们就要将题目所给的同余方程中的a、b、m都除以d，得到一个唯一解的同余方程$a_1x\equiv b_1~mod(~m_1)$，通过解二元不定方程$as+mt=1$，求出s，得到$a_1x\equiv b_1~mod(~m_1)$唯一解$x\equiv b_1s~mod(~m_1)$
  4. 求出原同余方程$ax\equiv b~mod(~m)$的解，其解为$x\equiv b_1s + km_1~mod(~m),k=0,1,…,d-1$

例题1：求一次同余方程$2x\equiv 3~(mod~5)$的所有解

例题2：求一次同余方程$4x\equiv 6(mod~10)$的所有解

中国剩余定理(CRT)

中国剩余定理的个人认为算是基础部分最重要的一个定理，也是密码学中非常重要的一个定理。而二次互反律则是整个初等数论最重要的定理(听b站某位老师说的)。

  • 中国剩余定理是用来解同余方程组的，该同余方程组形式如下，特征有三个：
    • 未知数只有一个x
    • 每个同余式的模数不一样，但是一般要满足gcd(m1,m2,...,mk)=1才有解，否则需要使用拓展中国剩余定理
    • 每个同余式中b的值可以一样，也可以不一样

$$
\begin{cases}
x \equiv b_1(~mod~m_1)\
x \equiv b_2(~mod~m_2)\
…\
x \equiv b_k(~mod~m_k)
\end{cases}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(1)
$$

  • 先来说解法再说其相关定理,这里默认$gcd(m_1,m_2,…,m_k)=1$，按照从左到右的顺序计算出如下数据。
除数 余数 除数最小公倍数 衍数 乘率 各总
$m_1$ $b_1$ $m_1*m_2…m_k=m$ $M_1=\frac{m}{m_1}$ $y_1=M_1^{-1}~(mod~m_1)$ $b_1M_1y_1$
$m_2$ $b_2$ $m_1*m_2…m_k=m$ $M_2=\frac{m}{m_2}$ $y_2=M_2^{-1}~(mod~m_2)$ $b_2M_2y_2$
… … $m_1*m_2…m_k=m$ … …
$m_k$ $b_k$ $m_1*m_2…m_k=m$ $M_k=\frac{m}{m_k}$ $y_k=M_k^{-1}~(mod~m_k)$ $b_kM_ky_3$
  • 最后得到其中一个解：

$$
x\equiv b_1M_1y_1 + b_2M_2y_2+…+b_kM_ky_k~mod(~m)
$$

定理1(中国剩余定理):

设$m_1,m_2,…,m_k$是k个两两互素的正整数，$m=m_1m_2…m_k,m=m_iM_i(i=1,2,…,k)$，则同余式组(1)的解为：
$$
x\equiv M_1’M_1b_1+M_2’M_2b_2+…+M_k’M_kb_k~~~~~~(2)
$$
其中$M_i’M_i\equiv1(~mod~m_i),i=1,2,…,k$

定理2：

若$b_1,b_2,…,b_k$分别过模$m_1,m_2,…,m_k$的完全剩余系，则(2)过模$m=m_1m_2…m_k$的完全剩余系。

高次同余式的解数及解法

相关定理

定理1：

若$m_1,m_2,…,m_k$是k个两两互素的正整数，$m=m_1m_2…*m_k$,则同余式$f(x)\equiv0(~mod~m)$与下面同余式组等价(即任意适合$f(x)\equiv0(~mod~m)$都适合如下式子，反之也成立)。
$$
f(x)\equiv0(~mod~m_i),i=1,2,…,k
$$
并且若用$T_i$表示$f(x)\equiv0(mod~m_i),i=1,2,…,k$对模$m_i$的解数，T表示$f(x)\equiv0(~mod~m)$的解数,则解数之间有如下关系
$$
T=T_1T_2…T_K
$$

定理2——命题1：

设$\alpha$是大于等于2的正整数,则适合$f(x)\equiv0~(mod~p^{\alpha})$,p为素数。适合上式的每个整数都适合同余式$f(x)\equiv 0~(p^{\alpha-1})$。

进而适合$f(x)\equiv0~(mod~p^{\alpha})$的每个正数都适合同余式$f(x)\equiv0~(mod~p)$。

因此解$f(x)\equiv0~(mod~p^{\alpha})$，可以转换为求$f(x)\equiv0~(mod~p^{\alpha})$的解。

定理2：

设$x\equiv x_1~(mod~p)$即$x=x_1+pt_1,t\in Z$是$f(x)\equiv0~(mod~p)$的一解，并且$p\nmid f’(x_1)$($f’(x)$是$f(x)$的导函数），

则$x=x_1+pt_1$刚好给出$f(x)\equiv0~(mod~p^{\alpha})$的一解，对于模$p^{\alpha}$来说：
$$
x=x_{\alpha}+p^{\alpha}t_{\alpha},t_{\alpha}\in Z
$$
即$x\equiv x_{\alpha}(~mod~p^{\alpha})$，其中$x_{\alpha}\equiv x_1~mod(~p)$

解高次同余式

情形一：
$$
f(x)\equiv0(~mod~m)\
m=m_1m_2…m_k
$$

解法：

  1. 利用定理一将同余式转化为$f(x)\equiv0(~mod~m_i),i=1,2,…,k$
  2. 分别解出这些转化后的同余方程的解
  3. 列出同余方程组，使用CRT即可求得原方程的解

$$
\begin{cases}
x\equiv b_1 ~(mod~m_1)\
x\equiv b_2 ~(mod~m_2)\
…\
x\equiv b_k ~(mod~m_k)
\end{cases}
$$

情形二：
$$
f(x)\equiv0(~mod~p^{\alpha})
$$

解法：

  1. 转化为解同余方程$f(x)\equiv0~(mod~p)$的解

  2. 求出$f(x)\equiv0~(mod~p)$的解后可以得到$x=x_1+pt_1,t\in Z$，将$x_1$带入$f(x)+f’(x)*pt_1\equiv0(mod~p^{2})$，并求出$t_1\equiv x_2~(mod~p^{2})$，这样就有$t_1=x_2+p^{2}*t_2$

  3. 将$t_1=x_2+p^{2}t_2$带回去$x=x_1+pt_1$，可以得到$x=x_1+p(x_2+p^{3}t_2)=(x_1+px_2)+p^{3}t_2$从而得到$x\equiv x_1+p*x_2~mod(~p^{2})$

  4. 之后将$x=(x_1+p*x_2)+p^{3}t_2$，带入到$f(x)+f’(x)*p^{2}t_2\equiv0(mod~p^{3})$并且重复2、3步骤，直到带回到$f(x)\equiv0(~mod~p^{\alpha})$

情形三：
$$
f(x)\equiv0(~mod~m)\
m=p_1^{\alpha_1}p_2^{\alpha_2}…p^{\alpha_{n}}
$$

  1. 先使用定理一，将同余方程转换为$f(x)\equiv0(~mod~p_i^{\alpha_i})$，即转换为情形二的情况

  2. 根据情形二的情况去解出$f(x)\equiv0(~mod~p_i^{\alpha_i})$的解，每组方程都需要求出解。

  3. 求出每个方程的所有解后，可以构造出如下同余方程组，使用CRT，即可求出情形三的所有解：

$$
\begin{cases}
x\equiv b_1 ~(mod~p^{\alpha_1}_1)\
x\equiv b_2 ~(mod~p^{\alpha_2}_2)\
…\
x\equiv b_k ~(mod~p^{\alpha_k}_k)
\end{cases}
$$

素数模的同余式

主要是利用如下定理化简素数模的多项式同余式

定理1：

设p是素数，则同余式$f(x)=a_nx^{n}+a_{n-1}x^{n-1}+…+a_0 \equiv 0(~mod~p),a_n\not\equiv 0~mod(~p)$，与一个次数不超过p-1的素数模p同余式等价。

定理2：

设$k≤n,x\equiv \alpha_i(~mod~p)(i=1,2,…,k)$是同余式$f(x)=a_nx^{n}+a_{n-1}x^{n-1}+…+a_0 \equiv 0(~mod~p),a_n\not\equiv 0~mod(~p)$的k个不同解，则对任何整数x来说，有如下式子：
$$
f(x)\equiv(x-\alpha_1)(x-\alpha_2)…(x-\alpha_k)f_k(x)(~mod~p)
$$
其中$f_k(x)$是首项系数$a_n$的$n-k$次多项式.

定理3——(1)：

对于任何整数x来说，都有如下式子：
$$
x^{p-1}\equiv(x-1)(x-2)…(x-(p-1))~(mod~p)
$$

定理3——(2)：又称威尔逊定理
$$
(p-1)!+1\equiv0(~mod~p)
$$

定理4：

同余式$f(x)=a_nx^{n}+a_{n-1}x^{n-1}+…+a_0 \equiv 0(~mod~p),a_n\not\equiv 0~mod(~p)$的解数不超过它的次数。

定理5——命题1:

同余式$f(x)=a_nx^{n}+a_{n-1}x^{n-1}+…+a_0 \equiv 0(~mod~p),a_n\not\equiv 0~mod(~p)$总和某个次数的首一同余式等价。

定理5：

若$n≤p$，则同余式$f(x)=x^{n}+a_{n-1}x^{n-1}+…+a_0 \equiv 0(~mod~p)$，有n个解的充分必要条件是$(x^{p}-x)/f(x)$所得余式的一切系数都是p的倍数。