数论基础-二次同余式与平方剩余

• 二次同余式中有非常多重点、难点，并且还有整个数论最重要的东西即二次互反律

二次同余式

定义1：

式子$ax^2+bx+c\equiv0(~mod~m),a\not\equiv0~(mod~m)$称为二次同余式

注解：

设模m的标准分解式是$m=p^{\alpha_1}_1...p^{\alpha_k}_k$，则由前面的高次同余式的知识点可知$ax^{2}+bx+c\equiv0~(~mod~m)$有解的充分必要条件是同余式$ax^{2}+bx+c\equiv 0(~mod~p^{\alpha_i}_i)$有解。所以讨论二次同余式解的问题都转换为讨论$ax^{2}+bx+c\equiv 0(~mod~p^{\alpha})$的解的问题。

定义2：

设$p、a$是两个整数$p>0$，如果$p^{r}|a$，但是$p^{r+1}\not\mid a$，则称$p^{r}$恰整除a，记$p^{r}\mid\mid a$

定义3：

若同余式$x^{2}\equiv a(~mod~m),(a,m)=1$有解，则a叫做模m的平方剩余，若同余式$x^{2}\equiv a~mod(~m)$无解，则a叫做模m的平方非剩余。

注意：$x\equiv 0(~mod~m)$是$x^{2}\equiv a(~mod~m)$的解，但不是$x^{2}\equiv a(~mod~m),(a,m)=1$的解，所以由同余式的定义，a可以从模m的一个完全剩余系中选取。

注解：一般的二次同余式的解的问题，最终讨论的是$x^{2}\equiv a(~mod~p^{\alpha}),(\alpha,p^{\alpha})=1$，而该式子可以进一步转换为$x^{2}\equiv a(~mod~m),(a,m)=1$是否有解的问题，从而引出了平方剩余与平方非剩余。

接下来讨论二次同余式解的情况

命题1：

对于二次同余式$ax^{2}+bx+c\equiv0(~mod~p^{\alpha})$

1. 若$p^{\alpha}\mid(a,b,c)$，则任一整数都满足$ax^{2}+bx+c\equiv0(~mod~p^{\alpha})$
2. 若$p^{r}\mid\mid (a,b,c)$，$2<r<\alpha$，则该二次同余式可以化为一个形如$ax^{2}+bx+c\equiv0~(mod~p^{\alpha'})$

命题2：

设$p\not\mid(a,b,c)$则同余式$ax^{2}+bx+c\equiv0(~mod~p^{\alpha})$的解的情况为：

1. 若$p|a$，$p|b$，但$p\not\mid c$，$ax^{2}+bx+c\equiv0(~mod~p^{\alpha})$无解
2. 若$p\mid a$，$p\not\mid b$，则$ax^{2}+bx+c\equiv0(~mod~p^{\alpha})$有解
3. 若$p\not\mid a,p>2$，则$ax^{2}+bx+c\equiv0(~mod~p^{\alpha})$有解的充分必要条件为$y^{2}-A\equiv0~(mod~p^{\alpha})$有解，其中$y^2=(2ax+b),A=b^{2}-4ac$，即$(2ax+b)^{2}\equiv b^2-4ac~(mod~p^{\alpha})$
4. 若$2\not\mid a$，$2\not\mid b$，则$ax^{2}+bx+c\equiv0(~mod~p^{\alpha})$有解的充要条件为,$2\mid c$
5. 若$2\not\mid$a，$2\mid b$，则$ax^{2}+bx+c\equiv0(~mod~p^{\alpha})$有解的充要条件是$y^{2}-A\equiv0~(mod~p^{\alpha})$有解

命题3：

对于$y^{2}-A\equiv0~(mod~p^{\alpha})$，其中$y^2=(2ax+b),A=b^{2}-4ac$，即$(2ax+b)^{2}\equiv b^2-4ac~(mod~p^{\alpha})$

若$p^{\alpha}\mid A$，则$y^{2}-A\equiv0~(mod~p^{\alpha})$有解

命题4：

对于$y^{2}-A\equiv0~(mod~p^{\alpha})$，其中$y^2=(2ax+b),A=b^{2}-4ac$，即$(2ax+b)^{2}\equiv b^2-4ac~(mod~p^{\alpha})$

若$p^{\alpha}\mid A$，则同余式$y^2-A\equiv0(~mod~p^{\alpha})$有解的充分必要条件是$t^{2}-A_1\equiv0(~p^{\alpha-\beta}),(A_1,p^{\alpha-\beta})=1$有解。其中

$y=p^{r}t,A=p^{\beta}A_1$

奇素数模的平方剩余

• 注意：模2的平方剩余不存在，所以讨论素数模的平方剩余就变成了只讨论奇素数的平方剩余。所以约定本章使用p表示大于2的素数。

• 模p的平方剩余和平方非剩余构成模$p$的即约剩余系：$1,2,...,p-1$，共偶数多个即p-1个

定理1（欧拉判别条件）：

若(a,p)=1，则a是模p的平方剩余的充分条件是$a^{\frac{p-1}{2}}\equiv1(~mod~p)$

而a是模p的平方非剩余的充分必要条件是$a^{\frac{p-1}{2}}\equiv-1(~mod~p)$

且若a是模p的平方剩余，则$x^{2}\equiv a ~(mod~p)$恰有俩解

定理2：模p的既约剩余系中的平方剩余与平方非剩余的个数各为$\frac{p-1}{2}$，而且$\frac{p-1}{2}$个平方剩余分别与序列$1^2,2^{2},...,(\frac{p-1}{2})^{2}$中之一数同余，且仅与一数同余。

勒让德符号

定义1：

设p是一个奇素数，a是任意一个整数，定义如下分段函数为勒让德符号，并称$(\frac{a}{p})$，为勒让德符号，读作a对p的勒让德符号

$\frac{a}{p}=\begin{cases} 1,&a是模p的平方剩余\\ -1,&a是模p的平方非剩余\\ 0,&p\mid a \end{cases}$

注意：勒让德符号其实是一个函数，定义域是整数集，而值域其实就是${0,1,-1}$。并且由勒让德符号的定义可以看出，如果能够很快的计算出它的值，那么也就会立即知道同余式$x^{2}\equiv a~(mod~p)$有解与否

勒让德符号的运算：

1. $(\frac{a}{p})\equiv a^{\frac{p-1}{2}}~(mod~p)$
2. $(\frac{1}{p})=1$
3. $(\frac{-1}{p})=(-1)^{\frac{p-1}{2}}$
4. $(\frac{a_1a_2...a_n}{p})=(\frac{a_1}{p})(\frac{a_2}{p})...(\frac{a_n}{p})$
5. $(\frac{ab^2}{p})=(\frac{a}{p}),p\not\mid b$

定理：

1. $(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$

2. 若$(a,p)=1,2\not\mid a$，则$(\frac{a}{p})=(-1)^{\sum^{p_1}_{k=1}[\frac{ak}{p}]}$，其中$p1=\frac{p-1}{2}$

推论：

1. 当$p=8*m\pm1$时，2是p的平方剩余
2. 当$p=8*m\pm3$时，2是p的平方非剩余

勒让德与二次剩余：

设p是奇素数，a是任意整数，$(a,p)=1$，则二次同余式$x^{2}\equiv a~(mod~p)$有解当且仅当$(\frac{a}{p})=1$

雅可比符号

• 雅可比符号其实是勒让德符号的一个拓展

定义1：

设m是一个大于1的奇数，a是任意一个整数，且$m=p_1p_2...p_r,p_i是素数$，则定义$(\frac{a}{m})=(\frac{a}{p_1})(\frac{a}{p_2})...(\frac{a}{p_r})$。

并称$(\frac{a}{m})$为雅可比符号，读作a对m的雅可比符号，这里$(\frac{a}{p_i})$是a对$p_i$的勒让德符号。

注意：

1. 雅可比符号可以视为勒让德符号的自然推广，所以大多数勒让德符号的运算都适用于雅可比符号
2. 勒让德符号与二次同余式有密切关系，但雅可比符号不如此

雅可比符号的运算

1. 若$a\equiv a_1~(mod~p)$，则$(\frac{a}{m})=(\frac{a_1}{m})$

2. $(\frac{1}{m})=1$

3. $(\frac{-1}{m})=(-1)^{\frac{m-1}{2}}$

4. $(\frac{a_1a_2...a_n}{m})=(\frac{a_1}{m})(\frac{a_2}{m})...(\frac{a_n}{m})$

5. $(\frac{ab^{2}}{m})=(\frac{a}{m}),(b,m)=1$

6. $(\frac{2}{m})=(-1^{\frac{m^2-1}{8}})$

二次互反律

二次互反律勒让德符号：

若$p,q$都是奇素数，$(p,q)=1$，则有$(\frac{q}{p})=(-1)^{\frac{p-1}{2}*\frac{q-1}{2}}(\frac{p}{q})$

二次互反律雅可比符号：

若m，n都是奇数，则$(\frac{n}{m})=(-1)^{\frac{m-1}{2}*\frac{n-1}{2}}(\frac{m}{n})$

合数模的平方剩余

• 对于合数模的平方剩余讨论的是如下同余式有无解的问题：

$x^2\equiv a~(mod~m),m=2^{\alpha}p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$

注解：设$m=2^{\alpha}p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$，则上面同余式有解的充分必要条件就是同余式组$x^2\equiv a~(mod~2^{\alpha})$和$x^{2}\equiv a(mod~p_i^{\alpha_i})$有解，并且其解数为同余式组中各个同余式解的个数的乘积$T=T_0T_1T_2...T_k$

定理1：

$x^{2}\equiv a~(mod~p^{\alpha}),\alpha>0,(a,p)=1$有解的充分必要条件是$(\frac{a}{p})=1$，并且在有解的情况下$x^{2}\equiv a~(mod~p^{\alpha})$的解数为2

定理2：

设$\alpha>1$，则$x^2\equiv a~(mod~2^{\alpha}),(a,2)=1$有解的必要条件是

1. 当$\alpha=2$时，$a\equiv1~(mod~4)$
2. 当$\alpha≥3$时，$a\equiv1~(mod~8)$

若上述条件成立，则$x^{2}\equiv a~(mod~2^{\alpha}),(a,2)=1$有解且当$\alpha=2$时，有两解，当$\alpha≥3$时有四解。

定理3：

同余式$x^2 \equiv a~(mod~m),m=2^{\alpha}p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},(a,m)=1$有解的必要条件是：当$\alpha=2$时，$a\equiv1~(mod~4)$；当$\alpha≥3$时，$a\equiv1~(mod~8)$，并且$(\frac{a}{p_i})=1$，若上述条件成立，则有解，并且有以下情况：

1. 当$\alpha=0、1$时，解数是$2^{k}$
2. 当$\alpha=2$时，解数是$2^{k+1}$
3. 当$\alpha≥3$时，解数是$2^{k+2}$