习题十

作者: 洛玖言 | 来源:发表于2019-11-03 22:16 被阅读0次

【Python爬虫】-笨办法学 Python 习题01-10
整数与多项式-【目录】
习题十
【Python爬虫】-笨办法学 Python 习题18-26
【Python爬虫】-笨办法学 Python 习题18-26
【Python爬虫】-笨办法学 Python 习题27-34
【Python爬虫】-笨办法学 Python 习题27-34
【Python爬虫】-笨办法学 Python 习题13-17
【Python爬虫】01作业
【Python爬虫】-笨办法学 Python 习题01

习题十

1

设 $p$ 是奇素数， $a,\,b$ 为整数且 $p\not|\;a$ . 证明：
$\displaystyle\sum_{n=0}^{p-1}\left(\dfrac{an+b}{p}\right)=0$

证明:
$\because p$ 为奇素数.
$\therefore 0,1,2,\cdots,p-1$ 为 $p$ 的一个完系.
又 $p\not|a\Rightarrow (p,a)=1.$
$\therefore an+b\;(n=1,2,\cdots)$ 为 $p$ 的一个完系.
$\therefore$ 必有 $0\leqslant k\leqslant p-1$ 满足 $p|ak+b$ ，且有 $\frac{p-1}{2}$ 个二次剩余， $\frac{p-1}{2}$ 个二次非剩余
$\displaystyle\therefore\sum_{n=0}^{p-1}\left(\dfrac{an+b}{p}\right)=\dfrac{p-1}{2}\cdot1+0+\dfrac{p-1}{2}\cdot(-1)=0$
得证.

2

设 $p$ 是奇素数， $n$ 是 $1,2,\cdots,p-1$ 中最小的模 $p$ 二次非剩余. 证明 $n$ 是素数.

证明:
利用反证法.
若 $n$ 不为素数.
则有 $n=k_1k_2,\;k_1<n,\;k_2<n$
$\left(\dfrac{n}{p}\right)=-1$ 又 $\left(\dfrac{n}{p}\right)=\left(\dfrac{k_1}{p}\right)\left(\dfrac{k_2}{p}\right)=-1$
$\therefore\left(\dfrac{k_1}{p}\right)$ 和 $\displaystyle\left(\dfrac{k_2}{p}\right)$ 中有一个为 $-1$ .
不妨 $\displaystyle\left(\dfrac{k_1}{p}\right)=-1$
$\therefore k_1$ 是模 $p$ 的二次非剩余
又 $k_1<n$ .
与 $n$ 是最小二次剩余矛盾.
$\therefore n$ 为素数.

7

设 $p$ 是奇素数. 证明：
$\displaystyle\prod_{\overset{r=1}{(\frac rp)=1}}^{p-1}\;r\equiv-\left(\dfrac{-1}{p}\right)\pmod{p}.$

证明:

由推论1有
$\left(\dfrac{-1}{p}\right)\equiv(-1)^{\frac{p-1}{2}}\pmod{p}$
$\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=\begin{cases} 1,&\text{if}\;\;p\equiv1\pmod{4}\\ -1,&\text{if}\;\;p\equiv-1\pmod{4} \end{cases}$

$\left(\dfrac{r}{p}\right)=1$ 表示 $p$ 的二次剩余
$\therefore$ 所有的二次剩余在 $1^2,2^2,\cdots,\left(\dfrac{p-1}{2}\right)^2$ 所属的模 $p$ 的同余类中.

$\begin{aligned} \displaystyle\prod_{\overset{r=1}{(\frac rp)=1}}^{p-1}r &\equiv 1^2\cdot2^2\cdots\left(\dfrac{p-1}{2}\right)^2\equiv(-1)^{\frac{p-1}{2}}(p-1)!\pmod{p}\\ &\equiv(-1)^{\frac{p-1}{2}}\cdot(-1)\equiv-\left(\dfrac{-1}{p}\right)\pmod{p} \end{aligned}$
(这里的变换用到了 $k\equiv(-1)(p-k)\pmod{p}\;$ 这个前面我们见过的变换)