信息安全数学基础-数论
信息安全数学基础-数论
本节数学公式稍多，页面渲染加载时间较长。
整除
设$a,b$是任意两个整数，其中$b\not=0$，若存在$q\in\mathbb{Z}$使等式$a=qb$成立，则称$b$整除$a$或$a$被$b$整除，记作$b\mid a$，并把$b$叫做$a$的因数，把$a$叫做$b$的倍数。人们常将$q$写成$a/b$或$\dfrac{a}{b}$。否则称$b$不能整除$a$或$a$不能被$b$整除，记作$b\not\mid a$。
设$a,b\not=0,c\not=0$为仨整数，若$b\mid a,c\mid b$，则$c\mid a$。
设$c\not=0,c\in\mathbb{Z}$，若$c\mid a_1,\cdots,a_n\in\mathbb{Z}$，则$\forall s_1,\cdots,s_n\in\mathbb{Z}$有$\displaystyle c\left|\sum_{i=1}^ns_ia_i\right.$。
设$a,b$为非零整数，若$a\mid b,b\mid a$，则$a=\pm b$。
设整数$n\neq0,\pm1$，若$n$除了因数$\pm1,\pm n$外没有其他因数，则$n$叫做素数（或质数、不可约数），否则$n$叫合数。设$n$是一个正合数，$p$是$n$的一个大于$1$的最小正因数，则$p$一定是素数且$p\leqslant\sqrt n$。设$n\in\mathbb{N}_+$，若对所有素数$p\leqslant\sqrt n$都有$p\not\mid n$，则$n\in\mathbb P$。素数有无穷多个。
设$a,b$是两个整数，其中$b>0$，则存在唯一整数$q,r$使得$a=qb+r,0\leqslant r<b$。其中$q$叫做$a$被$b$除所得的不完全商，$r$叫做$a$被$b$所除所得的余数。
设$x\in\mathbb{R}$，称$x$的整数部分为小于等于$x$的最大整数，记成$[x]$，这时有$[x]\leqslant x<[x]+1$。
设$f(x)$和$g(x)$都是$n\in\mathbb{Z_+}$的正值函数。若存在常数$C>0$，使得对任意$n\in\mathbb{Z_+}$都有$f(x)\leqslant Cg(n)$，就称$g(n)$为$f(n)$的界，记作$f(n)=O\left(g(n)\right)$，简记为$f=O(g)$。若对任意小的$\epsilon>0$，存在一个$N_0\in\mathbb{Z_+}$使得对任意正整数$n>N_0$都有$f(n)<\epsilon g(n)$，就称$g(n)$是比$f(n)$高阶的无穷量，记作$f(n)=o\left(g(n)\right)$，简记为$f=o\left(g\right)$。
设$a_1,\cdots,a_n$是$n(n\geqslant2)$个整数。若$d\in\mathbb Z$是他们中每个数的因数，则$d$为$a_1,\cdots,a_n$的一个公因数。若整数$a_1,\cdots,a_n$不全为零，则$a_1,\cdots,a_n$的所有公因数中最大的一个公因数叫做最大公因数，记作$(a_1,\cdots,a_n)$。当$(a_1,\cdots,a_n)=1$时称$a_1,\cdots,a_n$互素或互质。设$a_1,\cdots,a_n$是$n$个不全为零的整数，则$a_1,\cdots,a_n$与$\mid a_1\mid,\cdots,\mid a_n\mid$的公因数相同，$(a_1,\cdots,a_n)=(\mid a_1\mid,\cdots,\mid a_n\mid)$。设$b\in\mathbb N_+$则$(0,b)=b$。
设$a,b,c$是仨不全为零等整数，若$a=qb+c,q\in\mathbb Z$，则$(a,b)=(b,c)$。
广义欧几里得除法：设$a,b$是任意两个正整数，记$r_{-2}=a,r_{-1}=b$，有：
$$
\begin{align}
r_{-2}&=&q_0r_{-1}&+&r_0,&0<r_0<r_{-1},\\
r_{-1}&=&q_1r_0&+&r_1,&0<r1<r_0,\\
r_0&=&q_2r_1&+&r_2,&0<r_2<r_1,\\
&&\vdots\\
r_{n-2}&=&q_nr_{n-1}&+&r_n,&0<r_n<r_{n-1},\\
r_{n-1}&=&q_{n+1}r_n&+&r_{n+1},&r_{n+1}=0
\end{align}
$$
设$a,b$是任意两个正整数，则$r_n=0$时有$n\leqslant5\log b$。此时有$(a,b)=r_n$，且当$a>b$时计算$(a,b)$的时间为$。
设$a,b$是任意两个正整数，则存在整数$s,t$使得$sa+tb=(a,b)$，这叫做Bézout等式。
设$a,b$是任意两个正整数，记$r_{-2}=a,r_{-1}=b$，有：
$$
\begin{pmatrix}
r_{-2}\\
r_{-1}
\end{pmatrix}
=\begin{pmatrix}
q_0&1\\
1&0
\end{pmatrix}
\begin{pmatrix}
r_{-1}\\
r_0
\end{pmatrix}
=\left(
\prod_{i=0}^{j+1}\begin{pmatrix}
q_{i}&1\\
1&0
\end{pmatrix}
\right)
\begin{pmatrix}
r_j\\
r_{j+1}
\end{pmatrix}
$$
从而有：
$$
\begin{pmatrix}
r_j\\
r_{j+1}
\end{pmatrix}
=\left(
\prod_{i=j+1}^0\begin{pmatrix}
0&1\\
1&-q_i
\end{pmatrix}
\begin{pmatrix}
r_{-2}\\
r_{-1}
\end{pmatrix}
\right)
$$
记：
$$
A_j=\begin{pmatrix}
s_j&t_j\\
u_j&v_j
\end{pmatrix}
$$
则有：
$$
\begin{pmatrix}
r_j\\
r_{j+1}
\end{pmatrix}
=A_j\begin{pmatrix}
r_{-2}\\
r_{-1}
\end{pmatrix},-2\leqslant j\leqslant n
$$
此时有：
$$
\begin{cases}
s_{-2}=1,\\
s_{-1}=0
\end{cases}
,\begin{cases}
t_{-2}=0,\\
t_{-1}=1
\end{cases}
,\begin{cases}
s_j=u_{j-1},\\
t_j=v_{j-1}
\end{cases}
,-1\leqslant j\leqslant n
$$
以及：
$$
\begin{pmatrix}
s_j\\
s_{j-1}
\end{pmatrix}
=\begin{pmatrix}
-q_j&1\\
1&0
\end{pmatrix}
\begin{pmatrix}
s_{j-1}\\
s_{j-2}
\end{pmatrix}
,\begin{pmatrix}
t_j\\
t_{j-1}
\end{pmatrix}
=\begin{pmatrix}
-q_j&1\\
1&0
\end{pmatrix}
\begin{pmatrix}
t_{j-1}\\
t_{j-2}
\end{pmatrix}
$$
即为广义欧几里得除法：设$a,b$为任意两个正整数，则$s_na+t_nb=(a,b)$，对于$0\leqslant j\leqslant n$，定义为：
$$
\begin{cases}
s_{-2}=1,s_{-1}=0,\\
t_{-2}=0,t_{-1}=1,\\
s_j=(-q_j)s_{j-1}+s_{j-2},\\
t_j=(-q_j)t_{j-1}+t_{j-2}
\end{cases}
,0\leqslant j\leqslant n
$$
其中$q_j=\left[\dfrac{r_{j-2}}{r_{j-1}}\right]$为不完全商。
$a,b\in\mathbb Z$互素的充分必要条件是存在$s,t\in\mathbb Z$使得$sa+tb=1$。
设$a,b$是任意两个不全为0的整数。若$m$是任一正整数，则$(ma,mb)=m(a,b)$。若非0整数$d$满足$d\mid a,d\mid b$，则：
$$
\left(
\dfrac{a}{d},\dfrac{b}{d}
\right)
=\dfrac{(a,b)}{|d|},\left(
\dfrac{a}{(a,b)},\dfrac{b}{(a,b)}
\right)
=1
$$
设$a,b,c$是三个整数，且$b\neq0,c\neq0$，若$(a,c)=1$，则$(a,b,c)=(b,c)$。设$a_1,\cdots,a_n,c\in\mathbb Z$，若$(a_i,c)=1,1\leqslant i\leqslant n$，则$(a_1,\cdots,a_n,c)=1$。
设$a,b,u,v,q,r,s,t\in\mathbb Z$，且$a=qu+rv,b=su+tv,qt-rs=1$，则$(a,b)=(u,v)$。
设$a_1,\cdots,a_n$为整数，且$a_1\neq0$，令：
$$
\begin{cases}
(a_1,a_2)&=d_2\\
(d_2,a_3)&=d_3\\
&\cdots\\
(d_{n-1},a_n)&=d_n
\end{cases}
$$
则$(a_1,a_2,\cdots,a_n)=d_n$且$\displaystyle\exists s_1,s_2,\cdots,s_n\in\mathbb Z,\sum_{i=1}^ns_ia_i=d_n$。
设$a,b\in\mathbb Z_+$，则$2^a-1$被$2^b-1$除的最小非负余数是$2^r-1$，其中$r$是$a$被$b$除的最小非负余数。$(2^a-1,2^b-1)=2^{(a,b)}-1$。
设$a,b,c\in\mathbb Z,c\neq0$，若$c\mid ab,(a,b)=1$，则$c\mid b$。设$p\in\mathbb P$，若$p\mid ab$，则$p\mid a$或$p\mid b$。设$a_1,\cdots,a_n\in\mathbb Z,p\in\mathbb P$，若$\displaystyle p\left|\prod_{i=1}^na_i\right.$，则$\exists 1\leqslant k\leqslant n,p\mid a_k$。
设$a_1,\cdots,a_n\in\mathbb Z$，若$D$为该$n$个数的倍数，则$D$叫做这$n$个数的一个公倍数，$a_1,\cdots,a_n$所有公倍数中最小正整数叫做最小公倍数，记作$[a_1,\cdots,a_n]$。设$a,b\in\mathbb{Z_+}$，有$[a,b]=ab$，且若$a\mid D,b\mid D$则$ab\mid D$。设$a,b\in\mathbb{Z_+}$，有$[a,b]=\dfrac{ab}{(a,b)}$，且若$a\mid D,b\mid D$则$[a,b]\mid D$。
设$a_1,\cdots,a_n\in\mathbb Z$，令：
$$
\begin{cases}
[a_1,a_2]&=D_2,\\
[D_2,a_3]&=D_3,\\
&\cdots,\\
[D_{n-1},a_n]&=D_n
\end{cases}
$$
则$[a_1,\cdots,a_n]=D_n$。若$\forall 1\leqslant k\leqslant n,a_k\mid D$，则$[a_1,\cdots,a_n]\mid D$。
整数分解定理：给定合数$n>1$，若$\exists a,b\in\mathbb Z,n\mid a^2-b^2,n\not\mid a-b,n\not\mid a+b$，则$(n,a-b)$和$(n,a+b)$都是$n$的真因数。
算数基本定理：任一整数$n>1$都可表示成素数的乘积，不考虑乘积顺序的情况下，表达式是唯一的，即$\displaystyle n=\prod_{i=1}^sp_i,p_1\leqslant\cdots\leqslant p_s,p_i\in\mathbb P$。
标准分解式：任一整数$n>1$可唯一表示成$\displaystyle n=\prod_{i=1}^sp^{\alpha_i},\alpha_i>0,p_i<p_j(i<j)\in\mathbb P$。
设整数$n>1$，有$\displaystyle n=\prod_{i=1}^sp_i^{\alpha_i},\alpha_i>0,i\in[1,s]$，则$d\mid n,d>0$当且仅当$d$右因数分解式$\displaystyle d=\prod_{i=1}^sp_i^{\beta_i},\alpha_i\geqslant\beta_i\geqslant0,i\in[1,s]$。
设$a_1,a_2,\cdots,a_k\in\mathbb{Z}_+$且都有素因数分解式：$\displaystyle a_j=\prod_{i=1}^sp_i^{\alpha_{ij}},\alpha_{ij}\geqslant0,1\leqslant i\leqslant s,1\leqslant j\leqslant k$，则有$\displaystyle\left(a_1,a_2,\cdots,a_k\right)=\prod_{i=1}^sp_s^{\gamma_i},\gamma_i=\min\left(\alpha_{i1},\alpha_{i2},\cdots,\alpha_{ik}\right),i\in[1,s]$和$\displaystyle\left[a_1,a_2,\cdots,a_k\right]=\prod_{i=1}^sp_i^{\delta_i},\delta_i=\max\left(\alpha_{i1},\alpha_{i2},\cdots,\alpha_{ik}\right),i\in[1,s]$。
设$a,b\in\mathbb{Z}_+$，则$(a,b)[a,b]=ab$。
设$a,b\in\mathbb{Z}_+$，则$\exists a’,b’\in\mathbb{Z},a’\mid a,b’\mid b$使得$a’b’=[a,b],(a’,b’)=1$。
定义$\displaystyle\pi(x)=\sum_{p\leqslant x}1$。
切比雪夫不等式：设$x\geqslant2$，有$\dfrac{x\ln2}{3\ln x}<\pi(x)<6\ln\dfrac{2x}{\ln x}$和$\dfrac{n\ln n}{6\ln 2}<p_n<\dfrac{8n\ln n}{\ln2},n\geqslant2$，其中$p_n$为第$n$个素数。
同余
给定$m\in\mathbb{Z}_+,\quad a,b\in\mathbb{Z}$。如果$m\mid a-b$，则叫做$a,b$模$m$同余，记作$a\equiv b\pmod m$。否则叫做模$m$不同余，记作$a\not\equiv b\pmod m$。
设$m\in\mathbb{Z}_+,\quad a,b\in\mathbb{Z}$，则$a\equiv b\pmod m$的充要条件是$\exists q\in\mathbb{Z}$使得$a=b+qm$。
设$m\in\mathbb{Z}_+$，则有：
- 自反性：$\forall a\in\mathbb{Z}$有$a\equiv a\pmod m$。
- 对称性：若$a\equiv b\pmod m$则$b\equiv a\pmod m$。
- 传递性：若$a\equiv b\pmod m,b\equiv c\pmod m$则$a\equiv c\pmod m$。
设$m\in\mathbb{Z}_+$，则$a\equiv b\pmod m,\quad a,b\in\mathbb{Z}$的充要条件是$a\bmod m=b\bmod m$。
若$x\equiv y\pmod m,a_i\equiv b_i\pmod m,0\leqslant i\leqslant k$，则$\displaystyle\sum_{i=0}^ka_ix^i\equiv\sum_{i=0}^kb_iy^i\pmod m$。
同余的性质：设$m\in\mathbb Z_+$，设$da\equiv db\pmod m$，若$(d,m)=1$，则$a\equiv b\pmod m$；设$m\in\mathbb Z_+$，设$a\equiv b\pmod m,d>0$，则$da\equiv db\pmod{dm}$；设$m\in\mathbb Z_+$，设$a\equiv b\pmod m$，若$d\in\mathbb Z,d\mid(a,b,m)$，则$\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\dfrac{m}{d}\right)$；设$m\in\mathbb Z_+,a\equiv b\pmod m$，若$d\mid m$，则$a\equiv b\pmod d$；设$m_1,m_2,\cdots,m_k\in\mathbb Z_+$，设$a\equiv b\pmod{m_i},i=1,\cdots,k$，则$a\equiv b\left(\bmod\left[m_1,m_2,\cdots,m_k\right]\right)$；设$a\equiv b\pmod m$，则$(a,m)=(b,m)$。
设$m\in\mathbb Z_+$，且设$\forall a\in\mathbb Z,C_a=\lbrace c\mid c\in\mathbb Z,c\equiv a\pmod m\rbrace$，则：任一整数必包含在一个$C_r$中；$C_a=C_b\Leftrightarrow a\equiv b\pmod m$；$C_a\cap C_b=\varnothing\Leftrightarrow a\not\equiv b\pmod m$。
$C_a$叫做模$m$的$a$的剩余类，一个剩余类中任一数叫做该类的剩余或代表元。若$r_0,r_1,\cdots,r_{m-1}\in\mathbb Z$，且其中任何两个数都不在同一个剩余类里，则$r_0,r_1,\cdots,r_{m-1}$叫做模$m$的一个完全剩余系。模$m$的剩余类组成一个新集合，记作$\mathbb Z/m\mathbb Z=\lbrace C_a\mid 0\leqslant a\leqslant m-1\rbrace$。当$m\in\mathbb P$时，写成$\mathbb F_p=\mathbb Z/p\mathbb Z$。定义$\mathbb Z/m\mathbb Z$中元素间的加法运算为$C_a\oplus C_b\triangleq C_{a+b}$，乘法运算定义为$C_a\otimes C_b\triangleq C_{ab}$。记$(\mathbb Z/m\mathbb Z)^*=\lbrace C_a\mid C_a\in\mathbb Z/m\mathbb Z,(a,m)=1\rbrace$，且有$\forall C_a,C_b\in(\mathbb Z/m\mathbb Z)^*,C_{ab}\in(\mathbb Z/m\mathbb Z)^*$。
设$m\in\mathbb Z_+,\quad a,b\in\mathbb Z,a\bot m$，若$k$遍历模$m$的一个完全剩余系，则$ak+b$也遍历模$m$的一个完全剩余系。设$m_1,m_2,\cdots,m_k\in\mathbb Z_+$互素，$x_1,x_2,\cdots,x_k$分别遍历模$m_1,m_2,\cdots,m_k$的完全剩余系，则$\displaystyle\sum_{i=1}^kx_i\dfrac{\displaystyle\prod_{j=1}^km_j}{m_i}$遍历模$\displaystyle\prod_{i=1}^km_i$的完全剩余系。
设$m\in\mathbb Z_+$，则$1,2,\cdots,m\in\mathbb Z$中与$m$互素的个数记作$\varphi(m)$，叫做欧拉函数。对于$m=p^{\alpha},p\in\mathbb P$，有$\displaystyle\varphi(m)=p^{\alpha}-p^{\alpha-1}=m\prod_{p\mid m}\left(1-\dfrac{1}{p}\right)$。设$p,q\in\mathbb P,p\neq q$，则$\varphi(pq)=pq-p-q+1$。设$m\in\mathbb Z_+$，则$\displaystyle\sum_{d\mid m}\varphi(d)=m$。设$m,n\in\mathbb Z_+,m\bot n$，则$\varphi(mn)=\varphi(m)\varphi(n)$。
若一个模$m$的剩余类中存在一个与$m$互素的剩余，叫做简化剩余类，其中的剩余叫做简化剩余，两个简化剩余的乘积仍是简化剩余。设$r_1,r_2$是同一模$m$剩余类的两个剩余，则$r_1\bot m\Leftrightarrow r_2\bot m$。设$m\in\mathbb Z_+$，在模$m$的所有不同简化剩余类中，从每个类中任取一个数组成的整数的集合叫做模$m$的一个简化剩余系，元素个数为$\varphi(m)$。换句话说，设$m\in\mathbb Z_+$，$r_1,\cdots,r_{\varphi(m)}$是与$m$互素的整数且两两模$m$不同余，则$r_1,\cdots,r_{\varphi(m)}$是模$m$的一个简化剩余系。
设$m\in\mathbb Z_+,(a,m)=1,a\in\mathbb Z$，若$k$遍历模$m$的一个简化剩余系，则$ak$也遍历模$m$的一个简化剩余系。设$m\in\mathbb Z_+,a\bot m,a\in\mathbb Z$，则存在唯一$1\leqslant a’<m,a’\in\mathbb Z$使得$aa’\equiv1\pmod m$。设$m_1,m_2\in\mathbb Z_+,m_1\bot m_2$，若$k_1,k_2$分别遍历模$m_1$和$m_2$的简化剩余系，则$m_2k_1+m_1k_2$遍历模$m_1m_2$的简化剩余系。
欧拉定理：设$m>1,m\in\mathbb Z$，若$a\bot m,a\in\mathbb Z$，则$a^{\varphi(m)}\equiv1\pmod m$。
费马小定理：设$p\in\mathbb P$，则$\forall a\in\mathbb Z$有$a^p\equiv a\pmod p$。
Wilson定理：设$p\in\mathbb P$，则$(p-1)!\equiv -1\pmod p$。或设$p\in\mathbb P$，有$\displaystyle\forall x\in\mathbb Z,x^{p-1}-1\equiv\prod_{i=1}^{p-1}(x-i)\pmod p$。
同余式
设$m\in\mathbb Z_+$，$\displaystyle f(x)=\sum_{i=0}^na_ix^i,a_i\in\mathbb Z$，则$f(x)\equiv0\pmod m$叫做模$m$的同余式。若$a_n\not\equiv0\pmod m$，则$n$叫做$f(x)$的次数，记作$\deg f$。当$x=a$时成立，则$x\equiv a\pmod m$叫做同余式的解。
一次同余式：设$m\in\mathbb Z_+,a\in\mathbb Z,m\not\mid a$，则$ax\equiv1\pmod m$有解的充分必要条件为$a\bot m$，有解时解唯一。设$m\in\mathbb Z_+,a\in\mathbb Z$，若$\exists a’\in\mathbb Z$使得$aa’\equiv a’a\equiv1\pmod m$，则$a$为模$m$的可逆元。$a’$唯一存在，叫做$a$的模$m$逆元，记作$a’=a^{-1}\pmod m$。
设$m\in\mathbb Z_+,a\in\mathbb Z,m\not\mid a$，则$ax\equiv b\pmod m$有解的充分必要条件为$(a,m)\mid b$，解为$x\equiv\dfrac{b}{(a,m)}\left(\left(\dfrac{a}{(a,m)}\right)^{-1}\left(\bmod\dfrac{m}{(a,m)}\right)\right)+t\dfrac{m}{(a,m)}\pmod m,t=0,1,\cdots,(a,m)-1$。
中国剩余定理：设$m_1,m_2,\cdots,m_k\in\mathbb Z_+$两两互素，则$\forall b_1,b_2,\cdots,b_k\in\mathbb Z$，同余式组$\begin{cases}x\equiv b_1&\pmod{m_1}\\ &\vdots \\ x\equiv b_k&\pmod{m_k}\end{cases}$一定有解且唯一。若令$\displaystyle m=\prod_{i=1}^km_i,m=m_iM_i,i=1,2,\cdots,k$，且$M_i’M_i\equiv1\pmod{m_i},i=1,2,\cdots,k$，则同余式组的解为$\displaystyle x\equiv\sum_{i=1}^kb_iM_i’M_i\pmod m$。若令$\displaystyle N_i=\prod_{j=1}^im_j,i=1,2,\cdots,k-1$，其中$N_i’N_i\equiv1\pmod{m_{i+1}},i=1,2,\cdots,k-1$，$x_i$为$\begin{cases}x\equiv b_1&\pmod{m_1}\\ &\vdots\\ x\equiv b_i&\pmod{m_i}\end{cases},i=1,2,\cdots,k$的解，且满足递推式$\displaystyle x_i\equiv x_{i-1}+\left(\left(b_i-x_{i-1}\right)N_{i-1}’(\bmod{m_i})\right)N_{i-1}\left(\bmod\prod_{j=1}^im_j\right),i=2,3,\cdots,k$，则原同余式组的解为$\displaystyle x\equiv x_k\left(\bmod\prod_{i=1}^km_i\right)$。
设$m_1,m_2,\cdots,m_k\in\mathbb Z_+$两两互素，$\displaystyle m=\prod_{i=1}^km_i$，则高次同余式$f(x)\equiv0\pmod m$与同余式组$\begin{cases}f(x)\equiv0&\pmod{m_1}\\ &\vdots\\ f(x)\equiv0&\pmod{m_k}\end{cases}$等价。设符号$T$为解数，则原同余式解数为$\displaystyle T=\prod_{i=1}^kT_i$。
为求解高次同余式$f(x)\equiv0\pmod{p^{\alpha}}$，设$\displaystyle f(x)=\sum_{i=0}^na_ix^i$为整系数多项式，则记$\displaystyle f’(x)=\sum_{i=1}^nna_nx^{n-1}$为$f(x)$的导式。
设$x\equiv x_1\pmod p$时高次同余式$f(x)\equiv0\pmod p$的一个解，且$f’(x_1)\bot p$，则原同余式有解$x\equiv x_{\alpha}\pmod{p^{\alpha}}$，其中有递推式$x_i\equiv x_{i-1}+t_{i-1}p^{i-1}\left(\bmod p^i\right),t_{i-1}\equiv\dfrac{-f(x_{i-1})}{p^{i-1}}\left(f’(x_1)^{-1}(\bmod p)\right)\pmod p,i=2,3,\cdots,\alpha$。
设$\displaystyle f(x)=\sum_{i=0}^na_ix^i,g(x)=x^m+\sum_{i=0}^{m-1}b_ix^i,m\geqslant1$分别为$n$次整系数多项式和$m$次首一整系数多项式，则存在整系数多项式$q(x),r(x)$使得$f(x)=q(x)g(x)+r(x),\deg r(x)<\deg g(x)$。
模$p$素数模同余式与一个次数不超过$p-1$的模$p$同余式等价。设$1\leqslant k\leqslant n$，若$x\equiv a_i\pmod p,i=1,2,\cdots,k$是素数模同余式的$k$个不同解，则$\displaystyle\forall x\in\mathbb Z,f(x)\equiv f_k(x)\prod_{i=1}^k(x-a_i)\pmod p$，其中$f_k(x)$是$n-k$次多项式，首项系数是$a_n$。
同余式的解数不超过它的次数。设$p\in\mathbb P,n\in\mathbb Z_+,n\leqslant p$，则$\displaystyle f(x)=x^n+\sum_{i=0}^{n-1}a_ix^i\equiv0\pmod p$有$n$个解的充分必要条件是$x^p-x$被$f(x)$除所得余式的所有系数都是$p$的倍数。
二次同余式与平方剩余
二次同余式一般形式是$ax^2+bx+c\equiv0\pmod m,a\not\equiv0\pmod m$。因为$\displaystyle m\in\mathbb Z_+,m=\prod_{i=1}^kp_i^{\alpha_i}$，所以本节只需讨论$ax^2+bx+c\equiv0\pmod{p^{\alpha}},p\not\mid a$。
设$m\in\mathbb Z_+$，若$x^2\equiv a\pmod m,a\bot m$有解，则$a$叫做模$m$的平方剩余或二次剩余，否则$a$叫做模$m$的平方非剩余或二次非剩余。
欧拉判别条件：设$p$为奇素数，$a\bot p$，则$a$是模$p$的平方剩余的充要条件是$a^{\frac{p-1}{2}}\equiv1\pmod p$，此时原二次同余式$x^2\equiv a\pmod p,a\bot p$有两解；$a$是模$p$的平方非剩余的充要条件是$a^{\frac{p-1}{2}}\equiv -1\pmod p$。
设$p$是奇素数，$a_1\bot p,a_2\bot p$，则：若$a_1,a_2$都是模$p$的平方剩余，则$a_1a_2$是模$p$的平方剩余；若$a_1,a_2$都是模$p$的平方非剩余，则$a_1a_2$是模$p$的平方剩余；若$a_1$是模$p$的平方剩余而$a_2$是模$p$的平方非剩余，则$a_1a_2$是模$p$的平方非剩余；模$p$的简化剩余系中平方剩余与平方非剩余的个数各为$\dfrac{p-1}{2}$。
设$p\in\mathbb P$，勒让德符号定义为：$\left(\dfrac{a}{p}\right)=\begin{cases}1&:若a是模p的平方剩余\\ -1&:若a是模p的平方非剩余\\ 0&:若p\mid a\end{cases}$。
欧拉判别法则：设$p$是奇素数，则$\forall a\in\mathbb Z,\left(\dfrac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$。
设$p$是奇素数，则：
- 周期性：$\left(\dfrac{a+p}{p}\right)=\left(\dfrac{a}{p}\right)$；
- 完全可乘性：$\left(\dfrac{ab}{p}\right)=\left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right)$；
- 设$a\bot p$，则$\left(\dfrac{a^2}{p}\right)=1$。
- 若$a\equiv b\pmod p,\quad a,b\in\mathbb Z$，则$\left(\dfrac{a}{p}\right)=\left(\dfrac{b}{p}\right)$。
高斯引理：设$p$是奇素数，$a\in\mathbb Z,a\bot p$，若整数$a,2a,\cdots,a\dfrac{p-1}{2}$中模$p$的最小正剩余大于$\dfrac{p}{2}$的个数是$m$，则$\left(\dfrac{a}{p}\right)=(-1)^m$；有$\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$；若$a\bot 2p$，则$\left(\dfrac{a}{p}\right)=(-1)^{\sum_{k=1}^{\frac{p-1}{2}}\frac{ak}{p}}$。
二次互反律：若$p\bot q$都为奇素数，则$\left(\dfrac{a}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{2}}\left(\dfrac{p}{q}\right)$。
设$p_1,p_2,\cdots,p_r$是奇素数，且$\displaystyle m=\prod_{i=1}^rp_i$，则定义雅可比符号$\displaystyle\forall a\in\mathbb Z,\left(\dfrac{a}{m}\right)=\prod_{i=1}^r\left(\dfrac{a}{p_i}\right)$。雅可比符号为$-1$可判断$a$是模$m$平方非剩余，但为$1$不能判断$a$是模$m$平方剩余。设$m$是正奇数，则：$\left(\dfrac{a+m}{m}\right)=\left(\dfrac{a}{m}\right)$；$\left(\dfrac{ab}{m}\right)=\left(\dfrac{a}{m}\right)\left(\dfrac{b}{m}\right)$；设$a\bot m$，则$\left(\dfrac{a^2}{m}\right)=1$。
设$\displaystyle m=\prod_{i=1}^rp_i$为奇数，则$\displaystyle\dfrac{m-1}{2}\equiv\sum_{i=1}^r\dfrac{p_i-1}{2}\pmod 2,\dfrac{m^2-1}{8}\equiv\sum_{i=1}^r\dfrac{p^2_i-1}{8}\pmod 2$；且有$\left(\dfrac{1}{m}\right)=1,\left(\dfrac{-1}{m}\right)=(-1)^{\frac{m-1}{2}},\left(\dfrac{2}{m}\right)=(-1)^{\frac{m^2-1}{8}}$。
设$m,n$为奇数，则$\left(\dfrac{n}{m}\right)=(-1)^{\frac{(m-1)(n-1)}{2}}\left(\dfrac{m}{n}\right)$。
设$p$是形为$4k+3$的素数，若$x^2\equiv a\pmod p$有解，则解为$x\equiv\pm a^{\frac{p+1}{4}}\pmod p$。设$p,q$是形为$4k+3$的不同素数，若$\left(\dfrac{a}{p}\right)=\left(\dfrac{a}{q}\right)=1,a\in\mathbb Z$，则$x^2\equiv a\pmod{pq}$有解$x\equiv\pm\left(a^{\frac{p+1}{4}}(\bmod p)\right)sq\pm\left(a^{\frac{p+1}{4}}(\bmod q)\right)tp\pmod{pq},sq+tp=1$。
设$p$是奇素数，$p-1=2^ts,t\geqslant1,s\in\mathbb Z,s\bmod 2=1$，设$n$是模$p$平方非剩余，$b\triangleq n^s\pmod p$，若$x^2\equiv a\pmod p$有解则满足$\left(a^{-1}x_{t-k-1}^2\right)^{2^{t-k-1}}\equiv1\pmod p,k=0,1,\cdots,t-1$，这里$x_{t-1}\triangleq a^{\frac{s+1}{2}}\pmod p,x_{t-k-1}=x_{t-k}b^{j_{k-1}2^{k-1}}$，其中$j_{k-1}=\begin{cases}0&:\left(a^{-1}x_{t-k}^2\right)^{2^{t-k-1}}\equiv1\pmod p\\ 1&:\left(a^{-1}x_{t-k}^2\right)^{2^{t-k-1}}\equiv-1\pmod p\end{cases}$，$x_0$是原同余式的解。
当求解模$m$为合数的二次同余式$x^2\equiv a\pmod m,a\bot m$时，设$\displaystyle m=2^{\delta}\prod_{i=1}^kp_i^{\alpha_i}$，则等价于求解几个模为奇素数幂$p^{\alpha}$的二次同余式$x^2\equiv a\pmod{p^{\alpha}},a\bot p,\alpha>0$。设$p$是奇素数，则模$p^{\alpha}$二次同余式的解数为$1+\left(\dfrac{a}{p}\right)$。对于同余式$x^2\equiv a\pmod{2^{\alpha}},a\bot2,\alpha>0$，有解的必要条件是$\alpha=2,a\equiv1\pmod 4$或$\alpha\geqslant3,a\equiv1\pmod 8$，前者解数为$2$，后者为$4$。
设$p\in\mathbb P$，则$x^2+y^2=p$有解的充要条件是$p=2$或$p=4k+1$。
原根与指标
一个序列$u=\lbrace u_k\mid k\geqslant1\rbrace$若$\exists L\in\mathbb Z,L\geqslant1,\forall k\in\mathbb Z,k\geqslant1,u_{k+L}=u_k$则称为有限周期序列或周期序列。$L$称为序列$u$的一个周期，最小周期$L_0$称为序列$u$的周期，记作$p(u)$。设$L$是周期序列$u$的一个周期，则它一定是$p(u)$的倍数。定义$u=\lbrace u_k\mid k\geqslant1\rbrace,v=\lbrace v_k\mid k\geqslant1\rbrace$的和序列和积序列为$u+v\triangleq\lbrace u_k+v_k\mid k\geqslant 1\rbrace,uv\triangleq\lbrace u_kv_k\mid k\geqslant1\rbrace$。若$u,v$是周期序列，则$p(u)p(v)$是$u+v$和$uv$的周期。
设$m\in\mathbb Z,m>1,a\in\mathbb Z_+,a\bot m$，则使得$a^e\equiv1\pmod m$成立的最小$e\in\mathbb Z_+$叫做$a$对模$m$的指数，记作$\operatorname{ord}_m(a)$。若$\operatorname{ord}_m(a)=\varphi(m)$则$a$叫做模$m$的原根。$\operatorname{ord}_m(a)$是序列$u=\lbrace u_k=a^k\bmod m\mid k\geqslant1\rbrace$的$p(u)$。
设$m,a\in\mathbb Z,m>1,a\bot m$，则$d\in\mathbb Z$使得$a^d\equiv1\pmod m$的充要条件是$\operatorname{ord}_m(a)\mid d$。
设$m,a\in\mathbb Z,m>1,a\bot m$，则$\operatorname{ord}_m(a)\mid\varphi(m)$。
设$p$是奇素数，$\dfrac{p-1}{2}\in\mathbb P$，若$a\in\mathbb Z,a\bmod p\neq0,\pm1$，则$\operatorname{ord}_p(a)=\dfrac{p-1}{2}$或$p-1$。
设$m,a\in\mathbb Z,m>1,a\bot m$，有性质：
- 若$b\equiv a\pmod m$，则$\operatorname{ord}_m(b)=\operatorname{ord}_m(a)$。
- 设$a^{-1}$使得$a^{-1}a\equiv1\pmod m$，则$\operatorname{ord}_m(a^{-1})=\operatorname{ord}_m(a)$。
设$m,a\in\mathbb Z,m>1,a\bot m$，则$1,a,\cdots,a^{\operatorname{ord}_m(a)-1}$模$m$两两不同余。特别当$\operatorname{ord}_m(a)=\varphi(m)$时，它们组成模$m$的简化剩余系。
设$m,a\in\mathbb Z,m>1,a\bot m$，则$a^d\equiv a^k\pmod m$的充要条件时$d\equiv k\pmod{\operatorname{ord}_m(a)}$。
设$m,a,d\in\mathbb Z,m>1,a\bot m,d\geqslant0$，则$\operatorname{ord}_m\left(a^d\right)=\dfrac{\operatorname{ord}_m(a)}{(d,\operatorname{ord}_m(a))}$。
设$m\in\mathbb Z,m>1$，$g$是模$m$的原根。设$d\in\mathbb Z,d\geqslant0$，则$g^d$是模$m$的原根当且仅当$d\bot\varphi(m)$。设$m,a\in\mathbb Z,k\in\mathbb Z_+,m>1,a\bot m,k\mid\operatorname{ord}_m(a)$，则满足$\left.\dfrac{\operatorname{ord}_m(a)}{k}\right|d,d\in\mathbb Z_+$的$d$的个数有$\varphi(k)$个。
设$m\in\mathbb Z,m>1$，若模$m$存在一个原根$g$，则模$m$有$\varphi(\varphi(m))$个不同的原根。
设$m,a,b\in\mathbb Z,m>1,\quad a,b\bot m$，若$\operatorname{ord}_m(a)\bot\operatorname{ord}_m(b)$则$\operatorname{ord}_m(ab)=\operatorname{ord}_m(a)\operatorname{ord}_m(b)$，反之亦然。
设$m,n,a\in\mathbb Z,\quad m,n>1,a\bot m$，则：
- 若$n\mid m$则$\operatorname{ord}_n(a)\mid \operatorname{ord}_m(a)$。
- 若$m\bot n$则$\operatorname{ord}_{mn}(a)=[\operatorname{ord}_m(a),\operatorname{ord}_n(a)]$。
设$p,q$是两个不同奇素数，$a\in\mathbb Z,a\bot pq$，则$\operatorname{ord}_{pq}(a)=[\operatorname{ord}_p(a),\operatorname{ord}_q(a)]\mid [p-1,q-1]$。当$q=2p-1$时有$\operatorname{ord}_{pq}(a)=[\operatorname{ord}_p(a),\operatorname{ord}_q(a)]\mid q-1$。
设$m,n\in\mathbb Z,\quad m,n>1,m\bot n$，且$\forall a_1,a_2\in\mathbb Z,\quad a_1,a_2\bot mn$，有$\exists a\in\mathbb Z,\operatorname{ord}_{mn}(a)=[\operatorname{ord}_m(a_1),\operatorname{ord}_n(a_2)]$。
设$m\in\mathbb Z,m>1$，则$\forall a,b\in\mathbb Z,\quad a,b\bot m$，有$\exists c\in\mathbb Z,\operatorname{ord}_m(c)=\left[\operatorname{ord}_m(a),\operatorname{ord}_m(b)\right]$。
设$m\in\mathbb Z,m>1$，$a_1,a_2,\cdots,a_{\varphi(m)}$是模$m$的简化剩余系，$e$是使得$a^e_k\equiv1\pmod m,1\leqslant k\leqslant\varphi(m)$成立的最小正整数，则$\exists a\in\mathbb Z,e=\operatorname{ord}_m(a)=\left[\operatorname{ord}_m(a_1),\operatorname{ord}_m(a_2),\cdots,\operatorname{ord}_m\left(a_{\varphi(m)}\right)\right]$。其中$e$叫做模$m$的简化剩余系指数，记作$e=\operatorname{ord}((\mathbb Z/m\mathbb Z)^*)$，当$m=p,p\in\mathbb P$时有$e=\varphi(p)$。
设$p$是奇素数，则模$p$的原根存在，且有$\varphi(p-1)$个原根。当$d\mid p-1,d>0$，则模$p$指数为$d$的元素存在。
设$p$是奇素数，$p-1$的所有不同素因子是$q_1,q_2,\cdots,q_s$，则$g$是模$p$原根的充要条件是$g^{\frac{p-1}{q_i}}\not\equiv1\pmod p,i=1,2,\cdots,s$。
设$p$是奇素数，若$g\in\mathbb Z$是模$p$原根，则有$g^{p-1}\equiv1\left(\bmod p^2\right)$或$(g+p)^{p-1}\not\equiv1\left(\bmod p^2\right)$。
设$p$是奇素数，若$g\in\mathbb Z$满足$g^{p-1}=1+u_0p,u_0\bot p$，则$\forall k\in\mathbb Z,k>2$，$\exists u_{k-2}\in\mathbb Z$使得$g^{p^{k-2}(p-1)}=1+u_{k-2}p^{k-1},u_{k-2}\bot p$。
设$p$是奇素数，$k\geqslant2$，若模$p$原根$g$满足$g^{p^{k-2}(p-1)}=1+u_{k-2}p^{k-1},u_{k-2}\bot p$则$g$也是模$p^k$原根。
设$g$是模$p$的一个原根，则$g$或$g+p$是模$p^2$原根。
设$p$是奇素数，则$\forall\alpha\in\mathbb Z_+$，模$p^{\alpha}$原根存在。
设$\alpha\geqslant1$，$g$是模$p^{\alpha}$的一个原根，则$g$与$g+p^{\alpha}$中的奇数时模$2p^{\alpha}$的一个原根。
设$a$是奇整数，若$a^2=1+u_12^t,u_1\bot2,t\geqslant3$，则$\forall k\in\mathbb Z,k>t$，有$\exists u_{k-t}\in\mathbb Z$使得$a^{2^{k-t}}=1+u_{k-t}2^{k-1},u_{k-t}\bot 2$。
设$t,k\in\mathbb Z,t\geqslant3,k>t$，若奇整数$a$有$a^{2^{k-t}}=1+u_{k-t}2^{k-1},u_{k-t}\bot2$则$a$模$2^k$的指数为$2^{k-t+1}$。
设$a$是奇整数，则$\forall\alpha\in\mathbb Z,\alpha\geqslant3$，有$a^{\frac{\varphi\left(2^{\alpha}\right)}{2}}\equiv a^{2^{\alpha-2}}\equiv1\left(\bmod 2^{\alpha}\right)$。
设$\alpha\in\mathbb Z,\alpha\geqslant3$，则$\operatorname{ord}_{2^{\alpha}}(5)=\frac{\varphi(2^{\alpha})}{2}=2^{\alpha-2}$。
模$m$原根存在的充要条件是$m=2,4,p^{\alpha},2p^{\alpha}$，$p$是奇素数。
设$m,a\in\mathbb Z,m>1,a\bot m$，$g$是模$m$的一个原根，则存在唯一$r\in\mathbb Z$使得$g^r\equiv a\pmod m,1\leqslant r\leqslant\varphi(m)$。$r$叫做以$g$为底的$a$对模$m$的一个指标，记作$r=\operatorname{ind}_g(a)$。
设$m,a\in\mathbb Z,m>1,a\bot m$，$g$是模$m$的一个原根，若$r$使$g^r\equiv a\pmod m$成立则$r$满足$r\equiv\operatorname{ind}_g(a)\pmod{\varphi(m)}$，且有$\operatorname{ind}_g(1)=\equiv0\pmod{\varphi(m)}$。
设$m,r\in\mathbb Z,m>1,1\leqslant r\leqslant\varphi(m)$，$g$是模$m$的一个原根，则以$g$为底的对模$m$有相同指标$r$的所有整数全体是模$m$的一个简化剩余类。
设$m\in\mathbb Z,m>1$，$g$是模$m$的一个原根，若$a_1,a_2,\cdots,a_n\in\mathbb Z$与$m$互素，则$\displaystyle\operatorname{ind}_g\left(\prod_{i=1}^na_i\right)\equiv\sum_{i=1}^n\operatorname{ind}_g(a_i)\pmod{\varphi(m)}$。
设$m,a\in\mathbb Z,m>1,a\bot m$，若$n$次同余式$x^n\equiv a\pmod m$有解，则$a$叫做对模$m$的$n$次剩余，否则叫做对模$m$的$n$次非剩余。
设$m,a\in\mathbb Z,m>1,a\bot m$，$g$是模$m$的一个原根，则$x^n\equiv a\pmod m$有解的充要条件是$(n,\varphi(m))\mid\operatorname{ind}_g(a)$，且有解时解数为$(n,\varphi(m))$。且$a$是模$m$的$n$次剩余的充要条件是$a^{\frac{\varphi(m)}{d}}\equiv1\pmod m,d=(n,\varphi(m))$。
设$m,a\in\mathbb Z,m>1,a\bot m$，$g$是模$m$的一个原根，则$a$对模$m$的指数是$e=\dfrac{\varphi(m)}{(\operatorname{ind}_g(a),\varphi(m))}$。
设$m\in\mathbb Z,m>1$，$g$是模$m$的一个原根，则模$m$的简化剩余系中，指数是$e$的整数个数是$\varphi(e)$。