数论基础-同余式

基本概念和一次同余式

基本概念

同余式的定义：设$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_1*M_1*y_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_2*M_2*y_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_k*M_k*y_3$

• 最后得到其中一个解：

$$x\equiv b_1*M_1*y_1 + b_2*M_2*y_2+....+b_k*M_k*y_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_1*m_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+p*x_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的倍数。