本文最后更新于：1 年前

作业 $\mathbf{PDF}$ 文件下载请点击这里初等数论作业

$\large\textcolor{blue}{初等数论第一次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.2.22}$

习题 1.1.1

设 $n$ 是奇数, 则 $8 \mid n^{2}-1$.

证明：由 $n$ 是奇数，则令 $n=2k+1$，有 $n^2-1=(2k+1)^2-1=4k(k+1)$，由于 $k$ 和 $k+1$ 一奇一偶，从而 $2\mid k(k+1)$，则 $8\mid n^2-1$

习题1.1.2

设 $n \geqslant 3$ 是奇数, 证明: $\left(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n-1}\right)(n-1) !$ 被 $n$ 整除.

证明：由 $n\in \mbox{odd}$ 则可以依次首尾相加得到 \[ 1+\dfrac{1}{2}+\cdots+\dfrac{1}{n-1}=(1+\dfrac{1}{n-1})+(\dfrac{1}{2}+\dfrac{1}{n-2})+\cdots+(\dfrac{1}{\dfrac{n-1}{2}}+\dfrac{1}{\dfrac{n+1}{2}})\\ =n\cdot(\dfrac{1}{1\cdot(n-1)}+\dfrac{1}{2\cdot(n-2)}+\cdots+\dfrac{1}{\dfrac{n-1}{2}\cdot\dfrac{n+1}{2}}) \] 而 $(n-1)!$ 均有 $1,2,\cdots,n-1$ 的因子，从而 $n\mid (1+\dfrac{1}{2}+\cdots+\dfrac{1}{n-1})(n-1)!$

习题1.1.3

设 $m$ 和 $n$ 为正整数, $m \geqslant 3$. 证明: $2^{m}-1 \not\mid 2^{n}+1$.

引理 $1.1.1$ $q\in Z,x-1\mid x^{q}-1$，这是由于 $1+x+\cdots+x^{q-1}=\dfrac{x^{q}-1}{x-1}\in Z$

证明：显然当 $m>n$ 时结论不成立，假设结论不成立 $2^{m}-1\mid 2^{n}+1$，由带余除法定理有 $n=mq+r,r<m$ \[ \because 2^{n}+1=2^{mq+r}+1=2^{r}\cdot (2^{mq}-1)+2^{r}+1,2^{m}-1\mid 2^{mq}-1\\ \therefore 2^{m}-1\mid 2^{r}+1\ 而\ r<m,2^{m}-1>2^{r}+1\Longleftrightarrow 2^{m}>2^{r}+2\Longleftrightarrow 2^{m}-2^{r}>2^{m-1}\geq4>2 \] 从而假设不成立，$2^{m}-1\nmid 2^{n}+1$

习题1.1.4

设 $q$ 是大于 1 的整数. 证明:

$(i)$ 每个正整数 $n$ 可以惟一地表示成 \[ n=a_{0}+a_{1} q+a_{2} q^{2}+\cdots+a_{k} q^{k}, \] 其中 $a_{i}$ 是满足 $0 \leqslant a_{i} \leqslant q-1$ 的整数 $(0 \leqslant i \leqslant k)$, 并且 $a_{k} \neq$ 0. 这叫作 $n$ 的 $q$ 进制表示.

$(ii)$ $a_{i}=\left[\dfrac{n}{q^{i}}\right]-q\left[\dfrac{n}{q^{i+1}}\right](0 \leqslant i \leqslant k)$.

证明：$(i)$ 带余除法定理令 $n=b_0+m_1q,0\leq b_0\leq q-1$，对 $m_i$ 重复上述步骤有 \[ m_1=b_1+m_2q,0\leq b_1\leq q-1\cdots ,m_k=b_k,0\leq b_k\leq q-1 \] 则回代得到 $n=b_0+q(b_1+q(b_2+\cdots+(b_k)))$，展开得到 $n=a_0+a_1q+\cdots+a_kq^k$

唯一性的证明：若有两种表示方法 $n=a_0+a_1q+\cdots+a_kq^k=c_0+c_1q+\cdots+c_kq^k$，有 $q\mid a_0-c_0$，则由于 $0\leq a_0,c_0\leq q-1$ 得 $a_0=c_0$，代入消去有 $a_1+a_2q+\cdots+a_kq^k=c_1+c_2q+\cdots+c_kq^k$，同理有 $a_i=c_i$，则表示方法唯一

$(ii)$ 由 $(i)$ 中表示有 $n=a_0+a_1q+\cdots+a_kq^k$，两边除以 $q^{i}$ 有 \[ \dfrac{n}{q^{i}}=\dfrac{a_0}{q^{i}}+\dfrac{a_1}{q^{i-1}}+\cdots a_i+a_{i+1}q+a_{i+2}q^2+\cdots+a_{k}q^{k-i} \] 由 $0\leq a_i\leq q-1$ 且有取整函数的定义可知 $[\dfrac{n}{q^{i}}]=a_i+a_{i+1}q+a_{i+2}q^2+\cdots+a_{k}q^{k-i}$

除以 $q^{i+1}$ 重复上述步骤得 $[\dfrac{n}{q^{i+1}}]=a_{i+1}+a_{i+2}q+\cdots+a_{k}q^{k-i-1}$，比对上述两式得 $a_i=[\dfrac{n}{q^{i}}]-q[\dfrac{n}{q^{i+1}}]$

习题1.1.5

设 $\alpha_{1}, \cdots, \alpha_{n}$ 为实数 $(n \geqslant 2)$, 证明： \[ \begin{aligned} {\left[\alpha_{1}\right]+\left[\alpha_{2}\right]+\cdots+\left[\alpha_{n}\right] } & \leqslant\left[\alpha_{1}+\alpha_{2}+\cdots+\alpha_{n}\right] \\ & \leqslant\left[\alpha_{1}\right]+\left[\alpha_{2}\right]+\cdots+\left[\alpha_{n}\right]+n-1 \end{aligned} \]

证明：记 $\alpha_i=[\alpha_i]+\{\alpha_i\},\forall \ x\in R,\{x\}\in[0,1)$，从而有 $\displaystyle [\sum_{i=1}^n\alpha_i]=\sum_{i=1}^n[\alpha_i]+[\sum_{i=1}^{n}\{\alpha_i\}]\geq\sum_{i=1}^n[\alpha_i]$

而 $\displaystyle [\sum_{i=1}^{n}\{\alpha_i\}]<[\sum_{i=1}^{n}1]=n$，由取整特性 $\displaystyle [\sum_{i=1}^{n}\{\alpha_i\}]\leq n-1$，则 $\displaystyle\sum_{i=1}^n[\alpha_i]\leq [\sum_{i=1}^n\alpha_i]\leq \displaystyle\sum_{i=1}^n[\alpha_i]+n-1$

习题1.1.11

设 $n$ 为正整数, $n \geqslant 2$. 如果 $n$ 没有小于或等于 $\sqrt{n}$ 的素数因子, 则 $n$ 为素数.

证明：反证法，若 $n$ 为合数，则 $n$ 有素因子 $q$，则 $n=mq,m,q\in Z$，由于 $n$ 没有 $\leq\sqrt{n}$ 的素数因子 \[ \therefore m,q>\sqrt{n},mq>n \] 与假设矛盾，从而 $n$ 为素数

习题1.1.12

对每个整数 $n \geqslant 3, n$ 和 $n !$ 之间必有素数. 由此证明素数有无限多个.

证明：反证法，假设 $n$ 和 $n!$ 之间全为合数，则 $n!-1$ 为合数，其一定有素数因子，由假设知 $n+1，n+2,\cdots,n!$ 全为合数，不可能是 $n!-1$ 的素数因子，另一方面，$\forall \ n\geq a\geq 2,a\mid n!$，从而 \[ P=\{p\mid p\in[2,n]\ \cap\ \mbox{p is prime} \},\forall \ x\in P,x\nmid n!-1 \] 则 $n!-1$ 没有小于其自身的素数因子，从而 $n!-1$ 为素数，与假设矛盾，从而 $n$ 和 $n!$ 之间一定有素数

从 $3$ 开始， $(3,3!)$ 之间有素数，$(3!,(3!)!)$ 之间有素数，进而构造数列 \[ a_1=3,a_{n+1}=a_n! \] 有 $(a_n,a_{n+1})$ 之间必有素数，且区间之间无交集，将自然数集分成无穷多个区间，从而有无穷多个素数

习题1.2.1

设 $n$ 是正整数, 证明: $\dfrac{21 n+4}{14 n+3}$ 是既约分数.

证明：反证法，假设 $\dfrac{21n+4}{14n+3}$ 不是既约分数，则 $21n+4$ 和 $14n+3$ 有共同素因子 $d$ ，即 \[ \because (21n+4,14n+3)=d,21n+4=dm,14n+3=dn\\ \therefore 3\cdot dn-2\cdot dm=42n+9-(42n+8)=1=d(3n-2m) \] 而 $d$ 为大于 $1$ 的素因子，$1\nmid d$，从而与假设矛盾，则 $\dfrac{21n+4}{14n+3}$ 是既约分数

习题1.2.2

设 $m, n$ 为正整数, $m$ 为奇数,证明： \[ \left(2^{m}-1,2^{n}+1\right)=1 \]

证明：令 $(2^{m}-1,2^{n}+1)=d$，且有 $2^{m}-1=dx,2^{n}+1=dy,x,y\in Z$，$d$ 为奇数 \[ \because 2^m=dx+1,2^n=dy-1\ \therefore 2^{mn}=(dx+1)^{n}=(dy-1)^m \] 将其二项式展开有 $\displaystyle \sum_{i=0}^nC_n^i(dx)^i=\sum_{i=0}^mC_m^i(dy)^i(-1)^{m-i}$，两边同时除以 $d$ 得到 \[ \displaystyle \sum_{i=1}^nC_n^id^{i-1}x^{i}+\dfrac{1}{d}=\sum_{i=1}^mC_m^id^{i-1}y^i(-1)^{m-i}+(-1)^m\cdot d^{-1} \] 由于 $m$ 是奇数，若 $d\geq 3$，两边取整有 $\dfrac{1}{d}=1-\dfrac{1}{d}$，矛盾，从而 $d=1$

习题1.2.3

设 $m, n, a$ 均为正整数, $a \geqslant 2$, 证明: \[ \left(a^{m}-1, a^{n}-1\right)=a^{(m, n)}-1 \text {. } \]

证明：令 $(m,n)=d$，且有 $m=dx,n=dy,(x,y)=1$，由引理 $1.1.1$ 知 \[ a^{d}-1\mid a^{dx}-1,\ a^{dx}-1=(a^d-1)\cdot(1+a^d+a^{2d}+\cdots+a^{(x-1)d})\\ a^{d}-1\mid a^{dy}-1,\ a^{dy}-1=(a^d-1)\cdot(1+a^d+a^{2d}+\cdots+a^{(y-1)d}),\\ \] 考虑辗转相除法，不妨设 $x>y$， \[ 1+a^d+a^{2d}+\cdots+a^{(x-1)d}=a^{(x-y)d}(1+a^d+\cdots+a^{(y-1)d})+1+a^d+a^{2d}+\cdots+a^{(x-y-1)d} \] 继续判断 $x$ 和 $y$ 的大小关系，辗转相除，而 $(x,y)=1$，则 \[ (1+a^d+a^{2d}+\cdots+a^{(x-1)d},1+a^d+a^{2d}+\cdots+a^{(y-1)d})=1 \] 从而 $a^{d}-1=a^{(m,n)}-1$ 即为 $a^{m}-1$ 和 $a^{n}-1$ 的最大公因数

$\large\textcolor{blue}{初等数论第二次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.3.2}$

习题1.2.4

设 $a,b,c\in Z,a\neq 0$。则 $a\mid bc$ 当且仅当 $\dfrac{a}{(a,b)}\mid c$

证明：取 $d=(a,b)$，令 $a=dx,b=dy$，且有 $(x,y)=1$

$(1)$ 若 $a\mid bc$， $\exists \ t\in Z,\ bc=at\ \therefore yc=xt \ \ x\mid yc$，由于 $(x,y)=1$，得 $x\mid c$，即 $\dfrac{a}{(a,b)}\mid c$；

$(2)$ 若 $\dfrac{a}{(a,b)}\mid c$，则 $\exists \ t\in Z,\ c=\dfrac{a}{(a,b)}\cdot t\ \therefore (a,b)\cdot c=at=dc=dxt$，即 $c=xt$，两边乘

以 $b=dy$ 得 $bc=xydt=ayt$，从而 $a\mid bc$。

综上，$a\mid bc \Longleftrightarrow \dfrac{a}{(a,b)}\mid c$

习题1.2.5

$m$ 和 $n$ 是互素的正整数，证明：

$\ \ \ (1)$ 对每个整数 $a$，$(a,mn)=(a,m)(a,n)$；

$\ \ \ (2)$ $mn$ 的每个正因子 $d$ 均可唯一地表示成 $d=d_1d_2$，其中 $d_1$ 和 $d_2$ 分别为 $m$ 和 $n$ 的正因子。

证明：$(1)$ 对 $(a,mn)=(a,m)\cdot(\dfrac{a}{(a,m)},\dfrac{mn}{(a,m)})$，由于 $\dfrac{a}{(a,m)}$ 和 $\dfrac{m}{(a,m)}$ 互素，则 \[ (a,mn)=(a,m)\cdot (\dfrac{a}{(a,m)},\dfrac{mn}{(a,m)})=(a,m)\cdot \normalsize (\dfrac{a}{(a,m)},n)令\ a=k_1x,m=k_2x\ \\ \because (m,n)=1\therefore(k_2x,n)=(x,n)=1,(\dfrac{a}{(a,m)},n)=(k_1,n)=(k_1x,n)=(a,n) \] 则有 $(a,mn)=(a,m)(a,n)$

$(2)$ 由算术基本定理，令 $m=p_1^{_1}p_2^{_2}p_r^{_r},n=q_1^{_1}q_2^{_2}q_k^{_k},1_i,_i $，由 $(m,n)=1$

$\forall \ 1\leq i\leq r,1\leq j\leq k,p_i\neq q_j$，否则设相等素数为 $p_{i_{0}}$ $(m,n)\geq p_{i_0}>1$ 矛盾，则有新序列集合

$\mathbb{S}=\{p_1,\cdots,p_r,q_1,\cdots,q_k\}$，有 $mn=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\cdot q_1^{\beta_1}\cdots q_k^{\beta_k}$，若 $d$ 为 $mn$ 的因子，则

总有 $d=p_1^{\gamma_1}\cdots p_{r}^{\gamma_{r}}\cdot q_{1}^{\lambda_{1}}\cdots q_{k}^{\lambda_{k}},0\leq\gamma_{i},\lambda_{i}$，则分离 $d_1=p_1^{\gamma_1}\cdots p_{r}^{\gamma_{r}},d_2=q_{1}^{\lambda_{1}}\cdots q_{k}^{\lambda_{k}}$

使得 $d=d_1d_2$，且由于 $p_i$ 和 $q_i$ 完全不同，该分解存在且唯一

习题1.2.6

设 $n$ 为正整数，$a,b$ 是不全为零的整数，证明：

$\ \ \ (1)$ $(a^n,b^n)=(a,b)^n$；

$\ \ \ (2)$ 若 $a$ 和 $b$ 是互素的正整数，$ab=c^n,c\in Z$，则 $a$ 和 $b$ 都是正整数的 $n$ 次方幂。

证明：$(1)$ 记 $(a,b)=d$，则有 $a=dx,b=dy,x,y\in Z$，从而 $a^n=d^nx^n,b^n=d^ny^n$

从而 $d^n\mid a^n,d^n\mid b^n,d^n\mid (a^n,b^n)$，则令 $(a^n,b^n)=td^n,t\in Z$，代入上式有

$\dfrac{a^n}{(a^n,b^n)}=tx^n,\ \dfrac{b^n}{(a^n,b^n)}=ty^n$，结合 $(x^n,y^n)=1$ 有 $1=(\dfrac{a^n}{(a^n,b^n)},\dfrac{b^n}{(a^n,b^n)})=t$，

$\therefore (a^n,b^n)=1\cdot d^n=(a,b)^n$

$(2)$ 由算术基本定理，令 $a=p_1^{_1}p_2^{_2}p_r^{_r},b=q_1^{_1}q_2^{_2}q_k^{_k},1_i,_i $，由 $(a,b)=1$

$\forall \ 1\leq i\leq r,1\leq j\leq k,p_i\neq q_j$，否则设相等素数为 $p_{i_{0}}$ $(m,n)\geq p_{i_0}>1$ 矛盾，则有新序列集合

$\mathbb{S}=\{p_1,\cdots,p_r,q_1,\cdots,q_k\}$，有 $ab=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\cdot q_1^{\beta_1}\cdots q_k^{\beta_k}=c^n$，同理对 $c$ 分解有

$c=m_1^{\gamma_1}\cdots m_l^{\gamma_{l}}$，代入有 $p_1^{\alpha_1}\cdots p_r^{\alpha_r}\cdot q_1^{\beta_1}\cdots q_k^{\beta_k}=m_1^{n\gamma_1}\cdots m_l^{n\gamma_{l}}$，由算术基本定理有

$\alpha_{i}=n\gamma_{a_{i}},\beta_{i}=n\gamma_{b_{i}}$，则 $a$ 和 $b$ 均能写成某个正整数的 $n$ 次幂

习题1.29

求 $963x+657y=(963,657)$ 的全部整数解。

解：由欧几里得辗转相除法有 \[ 963=657+306\longrightarrow 657=306\times 2+45\longrightarrow 306=45\times 6+36\\ \longrightarrow 45=36\times 1+9\longrightarrow 36=9\times 4 \] 从而 $(963,657)=9$，依次反向欧几里得算法有 \[ 9=45-36\times 1=45-(306-45\times 6)=45\times 7-306=(657-306\times 2)\times7-306\\ =657\times 7-306\times 15=657\times 7-306\times 15=657\times 7-(963-657)\times 15\\ =963\times(-15)+657\times22 \] 则 $963x+657y=(963,657)=9$，可以化为 $107x+73y=1$，从而其解为 \[ \begin{cases} x=-15+73t\\ y=22-107t \end{cases} \ \ \ \ t\in Z \]

习题1.2.10

求下列方程的全部整数解：

$\ \ \ (1)$ $6x+20y-15z=23$；

$\ \ \ (2)$ $25x+13y+7z=2$。

$(1)$ 由 $(20,15)=5$，则 $6x+20y-15z=23\Longleftrightarrow \begin{cases}20y-15z=5\omega\cdots\boldsymbol ①\\6x+5\omega=23\cdots\boldsymbol ②\end{cases}$

对 $\boldsymbol ②$，由 $6=5\times 1+1$，则 $1=6\times1+5\times(-1)$，则 $\boldsymbol ②$ 解为 $\begin{cases}x=23+5t\\\omega=-23-6t\end{cases}$

代入 $\boldsymbol ①$ 变形为 $4y-3z=\omega=-23-6t$，由 $4=3\times1+1$，则解 $\begin{cases}y=\omega+3u\\z=\omega+4u\end{cases}$

从而 $6x+20y-15z=23$ 的通解为 $\begin{cases}x=23+5t\\y=-23-6t+3u\\z=-23-6t+4u\end{cases}\ \ \ \ \ t,u\in Z$

$(2)$ 由 $(13,7)=1$，则 $25x+13y+7z=2\Longleftrightarrow \begin{cases}13y+7z=\omega\cdots\boldsymbol ①\\25x+\omega=1\cdots\boldsymbol ②\end{cases}$

对 $\boldsymbol ②$，由 $25=25\times 1$，则 $1=25\times 0+1\times1$，则 $\boldsymbol ②$ 解为 $\begin{cases}x=t\\\omega=1-25t\end{cases}$

代入 $\boldsymbol ①$ 变形为 $13y+7z=\omega=1-25t$，由 $1=7\times 2-13$，则解 $\begin{cases}y=-\omega+7u\\z=2\omega-13u\end{cases}$

从而 $25x+13y+7z=2$ 的通解为 $\begin{cases}x=t\\y=-1+25t+7u\\z=2-50t-13u\end{cases}\ \ \ \ \ t,u\in Z$

习题1.2.12

设 $f(x)=x^n+a_1x^{n-1}+\cdots +a_{n-1}x+a_n$ 为首项系数为 $1$ 的整系数多项式，

则 $f(x)$ 的每个有理根必为整数。

证明：若整系数多项式 $x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n=0$ 有理根为 $\dfrac{p}{q}(p,q\in Z,q\neq 0)$ \[ \because (p,q)=1,(\dfrac{p}{q})^{n}+a_1(\dfrac{p}{q})^{n-1}+\cdots+a_{n-1}\dfrac{p}{q}+a_n=0\\ \therefore p^{n}=-(a_1p^{n-1}q+\cdots+a_{n-1}pq^{n-1}+a_nq^{n})\therefore q\mid p^{n}\Longrightarrow q=1 \] 从而所有有理根必为整数

习题1.2.13

设 $m$ 和 $n$ 为正整数，则在 $n,2n,\cdots,mn$ 这 $m$ 个数当中恰有 $(m,n)$ 个是 $m$ 的倍数。

证明：令 $d=(m,n)$，且 $m=dx,n=dy,(x,y)=1$，从而 $kn,k=1,2,\cdots,m$ 满足

$m\mid kn,dx\mid kdy\Longrightarrow x\mid ky$，由于 $(x,y)=1$，则 $x\mid k$，即 $k$ 是 $x$ 的倍数，即 $k=xt,t\in Z$

而 $m=dx$，恰好为 $1\cdot x,2\cdot x\cdots ,d\cdot x$ ，恰共有 $d =(m,n)$ 个

习题1.2.16

设 $m$ 和 $n$ 是互素的非零整数。证明对整数 $a$，若 $m\mid a,n\mid a$，则 $mn\mid a$

证明：已知 $(m,n)=1$，由 $m,n\mid a$，设 $a=mx=ny,x,y\in Z$，有 $(mx,nx)=x(m,n)=x$

代入 $mx=ny$ 得 $x=(ny,nx)=n(y,x)$，则 $n\mid x,mn\mid mx=a$，即 $mn\mid a$

习题1.3.3

设 $a,b,c$ 为正整数，证明

$\ \ \ (1)$ $(a,[b,c])=[(a,b),(a,c)]$；

$\ \ \ (2)$ $[a,(b,c)]=([a,b],[a,c])$。

证明：由算术基本定理，设 $a,b,c$ 三者分解下所有质因数的交集为 $\{p_1\cdots p_N\}$，且三者对应的

幂次为 $\{a_n\},\{b_n\},\{c_{n}\},0\leq a_i,b_i,c_i\in Z$，即 $a,b,c=\displaystyle \prod p_{i}^{a_i,b_i,c_i}$

$(1)$ $(a,[b,c])=\displaystyle \prod p_{i}^{\min(a_i,\max({b_i,c_i}))}$ 和 $[(a,b),(a,c)]=\displaystyle \prod p_{i}^{\max(\min(a_i,b_i),\min(a_i,c_i))}$

$(a,[b,c])=[(a,b),(a,c)]\Longleftrightarrow \min(a_i,\max(b_i,c_i))=\max(\min(a_i,b_i),\min(a_i,c_i))$

而对后者，调换 $b$ 和 $c$ 对等式左右两边都不变，不妨设 $b\leq c$，从而分类以下三种情况： \[ \begin{gathered} i) a \leq b \leq c;\ \ \ \ ii) b \leq a \leq c;\ \ \ \ iii) b \leq c \leq a\\ i) \max \{a, \min \{b, c\}\}=\max \{a, b\}=b, \min \{\max \{a, b\}, \max \{a, c\}\}=\min \{b, c\}=b;\\ ii) \max \{a, \min \{b, c\}\}=\max \{a, b\}=a, \min \{\max \{a, b\}, \max \{a, c\}\}=\min \{a, c\}=a;\\ iii) \max \{a, \min \{b, c\}\}=\max \{a, b\}=a, \min \{\max \{a, b\}, \max \{a, c\}\}=\min \{a, a\}=a; \end{gathered} \] 从而后者成立，有 $(a,[b,c])=[(a,b),(a,c)]$ 成立

$(2)$ 仿照 $\small (1)$ 讨论 $\max(a_i,\min(b_i,c_i))=\min(\max(a_i,b_i),\max(a_i,c_i))$，也不妨设 $b\leq c$ \[ \begin{gathered} i) a \leq b \leq c;\ \ \ \ ii) b \leq a \leq c;\ \ \ \ iii) b \leq c \leq a\\ i) \min \{a, \max \{b, c\}\}=\min \{a, c\}=a, \max \{\min \{a, b\}, \min \{a, c\}\}=\max \{a, a\}=a;\\ ii) \min \{a, \max \{b, c\}\}=\min \{a, c\}=a, \max \{\min \{a, b\}, \min \{a, c\}\}=\max \{b, a\}=a;\\ iii) \min \{a, \max \{b, c\}\}=\min \{a, c\}=c, \max \{\min \{a, b\}, \min \{a, c\}\}=\max \{b, c\}=c;\\ \end{gathered} \] 从而同理可得 $[a,(b,c)]=([a,b],[a,c])$

习题1.3.4

不存在整数 $m\geq 2$ ，使得 $m^2\mid n$ 的正整数 $n$ 为无平方因子，证明：

$\ \ \ (1)$ 正整数 $n$ 是无平方因子当且仅当 $n=1$ 或者是不素因子的乘积；

$\ \ \ (2)$ 每个正整数 $n$ 可以唯一地表示成 $n=m^2\cdot n'$，其中 $m^2$ 为平方数，而 $n'$ 为无平方因子整数。

证明：$(1)$ 若 $n=1$ ，$\forall m\geq 2,\ m^2\nmid n$，从而 $1$ 为无平方因子，若 $n\geq 2$，由算术基本定理

令 $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_r^{\alpha_r}$，若 $\exists\ \alpha _i\geq 2$，则取 $p_i^{2}\mid p_{i}^{\alpha_{i}}\mid n$，则不是无平方因子，从而

$\forall \ \alpha_{i}\leq 1$，而 $\alpha_i=0$ 无意义（$p_{i}^{0}=1$），从而此时 $n$ 为不同素因子乘积

又若 $n=1$ 或者 $n$ 为不同素因子乘积，显然满足无平方因子条件，从而两者等价

$(2)$ 若 $n$ 为无平方因子，则 $n=1^2\cdot n'$ 满足条件，若 $n$ 不为无平方因子，由 $\small (1)$ 得，$\exists\ \alpha_i\geq 2$

则挑选 $\mathbb{A}=\{i\mid \alpha_i\geq 2\}$，对 $\forall\ x\in \mathbb{A}$ 取 ${i}=2,{i}=_i-_i=0,1 $

则所有非 $\mathbb{A}$ 中的 $\alpha_{j}$ 以及 $\gamma_{i}$ 对应素数幂次的乘积组成无平方因子 $n'=\displaystyle \prod_{\alpha_{j}\notin\mathbb{A}}p_{j}^{\alpha_{j}}\cdot \prod_{\alpha_{i}\in\mathbb{A}}p_{i}^{\gamma_{i}}$

其余组成完全平方数 $m^2=\displaystyle \prod_{\alpha_{i}\in\mathbb{A}}p_{i}^{\beta_{i}}=\prod_{\alpha_{i}\in\mathbb{A}}p_{i}^{2\lfloor\frac{\alpha_i}{2}\rfloor}$，即 $m=\displaystyle \prod_{\alpha_{i}\in\mathbb{A}}p_{i}^{\lfloor\frac{\alpha_i}{2}\rfloor}$，使得 $n=m^2\cdot n'$

下证其唯一性：若有两组 $(m_1,n'_1),(m_2,n_2')$ 使得 $n=m_1^2n_1'=m_2^2n_2'$，由 $\small(1)$ 知

$n_1$ 和 $n_2$ 为 $1$ 或者是不同素数的乘积，若两者不相同，则两边消去相同部分后总会剩余成单素数

即 $n''=m_1^2\displaystyle \prod p_i=m_2^2\prod q_i$，考察 $p_i$ 对应的幂次有左侧为奇次幂，右侧为偶次幂

这与 $n''$ 的算术基本定理矛盾，从而每个正整数能唯一地表示成完全平方数和无平方因子的乘积

$\large\textcolor{blue}{初等数论第三次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.3.8}$

习题1.2.1

设 $m$ 为正整数, $(a, m)=1$. 我们用 $a^{-1}$ 表示同余方程 $a x \equiv 1$ $(\bmod m)$ 的任何一个整数解 (即

$\left.a^{-1} \in \mathbf{Z}, a a^{-1} \equiv 1(\bmod m)\right)$. 证明：

若 $(a, m)=(b, m)=1$, 则 $a \equiv b(\bmod m)$ $$ $a^{-1} \equiv$ $b^{-1}(\bmod m)$；
若 $\{r_{1}, r_{2}, \cdots, r_{\varphi(m)}\}$ 是模 $m$ 的缩系, 则 $\{r_{1}^{-1}, r_{2}^{-1}, \cdots, r_{\varphi(m)}^{-1}\}$ 也是模 $m$ 的缩系。

证明：$(1)$ 若 $a\equiv b(\mbox{mod}\ m)$，即 $a-b=k_1m,k_1\in Z$，令 $a^{-1}$ 与 $b^{-1}$ 中最小的正整数为

$a_{-},b_{-}$，对上式乘以 $a_{-},b_{-}$ 得 $aa_{-}b_{-}-a_{-}(bb_{-})=k_1ma_{-}b_{-}$，两边对 $m$ 求同余有

$a_{-}\equiv b_{-}(\mbox{mod}\ m)$，而 $\overline{a^{-1}}=a_{-}+km,k\in Z,\overline{b^{-1}}=b_{-}+km,k\in Z$

则 $a\equiv b(\mbox{mod}\ m)\Longrightarrow a^{-1}\equiv b^{-1}(\mbox{mod}\ m)$，由对称性（$(a^{-1})^{-1}=a$），两者等价

$(2)$ 由 $r_{i}r_{i}^{-1}\equiv 1(\mbox{mod}\ m)$，若 $(r_{i}^{-1},m)\geq 2$，则 $(r_{i}r_{i}^{-1},m)\geq 2$，与 $r_{i}r_{i}^{-1}\equiv 1(\mbox{mod}\ m)$

矛盾，从而所有的 $r_{i}^{-1}$ 与 $m$ 互素；又若 $ ij,r_{i}^{-1}=r_{j}{-1} $，由 $(1)$ 得 $r_{i}=r_{j}$ ，矛盾

而 $m$ 的缩系有 $\varphi(m)$ 个，从而 $\{r_{1}^{-1},\cdots ,r_{\varphi (m)}^{-1}\}$ 也为缩系

习题1.2.2

设正整数 $n$ 的十进制表示为

\[ n=a_{0}+a_{1} \cdot 10+a_{2} \cdot 10^{2}+\cdots+a_{k} \cdot 10^{k}, \]

证明: $\left\{\begin{array}{l}n \equiv a_{0}+a_{1}+\cdots+a_{k}(\bmod 9), \\ n \equiv a_{0}-a_{1}+a_{2}-\cdots+(-1)^{k} a_{k}(\bmod 11) .\end{array}\right.$ 用这些结果来计算 $12345 \times 6789$ 被 $9$ 和

被 $11$ 除所得的余数。

证明：由 $u=\displaystyle \sum_{i=0}^ka_i10^{i}$，且 $10^{i}\equiv(9+1)^{i}\equiv1+9^{i}\equiv1(\mbox{mod}\ m)$

$10^{i}\equiv (11-1)^{i}\equiv(-1)^{i}+11^{i}\equiv (-1)^{i}(\mbox{mod}\ m)$，代入则得到

\[ \left\{\begin{array}{l}n \equiv \displaystyle \sum_{i=0}^ka_i(\bmod 9), \\ n \equiv \displaystyle \sum_{i=0}^k(-1)^{i}a_i(\bmod 11) .\end{array}\right. \] 代入计算 $12345\times 6789\equiv 15\times 30\equiv 0(\mbox{mod}\ 9)$，$12345\times 6789\equiv 3\times2\equiv 6(\mbox{mod}\ 11)$

习题1.2.6

证明：当 $n \geqslant 3$ 时, $\varphi(n)$ 为偶数。

证明：$\boldsymbol ①$ 若 $n$ 有奇素数因子，则 $\varphi(n)=\displaystyle \prod_{i}(p_{i}^{\alpha_{i}}-p_{i}^{\alpha _{i}-1})$ 中对奇素数因子 $(p_{i}^{\alpha_{i}}-p_{i}^{\alpha _{i}-1})$

总为偶数，从而此时 $(n)( 2) $

$\boldsymbol ②$ 若 $n$ 没有奇素数因子，由于 $n\geq 3$，则 $n=2^{k},k\geq 2$，此时 $\varphi(n)=2^{k-1}$ 也为偶数

从而 $\forall\ n\geq 3$，$\varphi(n)$ 为偶数

习题1.2.7

设 $m$ 和 $n$ 是正整数，$m=n t(t \in \mathbf{Z})$. 证明: 模 $n$ 的每个同余类都是模 $m$ 的 $t$ 个同余类之并。

证明：对 $m$ 中特定 $\overline{a}$ ，取 $\overline{a},\overline{a}+\overline{n},\cdots ,\overline{a}+(t-1)\overline{n}$ 共 $t$ 个同余类，这些元素均模 $n$ 余数为 $a$ 模

$n$，而 $\overline{a}$ 取遍 $0,1,\cdots,n-1$，得到模 $n$ 的每个同余类。

习题1.2.10

设 $a, m \in \mathbf{Z}, m \geqslant 2,(a, m)=1$. 计算 $\displaystyle \sum_{x=0}^{m-1}\left[\frac{a x}{m}\right]$.

解：由于 $\{ax\big |x=0,1,\cdots ,m-1\}$ 为 $m$ 的完系，则拆开 $\displaystyle \left[\frac{a x}{m}\right]=\dfrac{ax}{m}-\{\dfrac{ax}{m}\}$，则 \[ \begin{gathered} \displaystyle \sum_{x=0}^{m-1}\left[\frac{a x}{m}\right]=\dfrac{a}{m}\sum_{x=0}^{m-1}x-\dfrac{1}{m}(0+1+\cdots +(m-1))=\dfrac{a}{m}\cdot\dfrac{m(m-1)}{2}-\dfrac{m(m-1)}{2m}\\=\dfrac{a(m-1)}{2}-\dfrac{m-1}{2}=\dfrac{(a-1)(m-1)}{2} \end{gathered} \]

更一般地，对 $\forall \ a,m\in \mathbf{Z}$，都有 $\displaystyle \sum_{x=0}^{m-1}\left[\frac{a x}{m}\right]=\dfrac{am-a-m+(a,m)}{2}$

习题2.2.1

设 $\alpha$ 是环 $Z_{m}$ 中非零元素。若存在 $Z_{m}$ 中非零元素 $\beta(\neq \overline{0})$, 使得 $\alpha \beta=\overline{0}$, 称 $\alpha$ 是零因子，证明：

$(1)$ 非零元素 $\alpha$ 是零因子当且仅当 $\alpha$ 不可逆. 从而 $Z_{m}$ 由彼此不同的三类元素构成：$\overline{0}, \varphi(m)$ 个可逆

元和 $m-\varphi(m)-1$ 个零因子;

$(2)$ $Z_{m}$ 中没有零因子当且仅当 $m$ 是素数。

证明：$(1)$ 若 $\alpha (\neq \overline{0})$ 是零因子，反证法，若 $$ 可逆，则 $\alpha\alpha^{-1}\equiv 1(\mbox{mod}\ m)$，两边乘以 $\beta(\neq \overline{0})$

得 $\alpha \beta \alpha^{-1}\equiv \beta(\mbox{mod}\ m)$，左边为 $0$，右边不为 $0$，矛盾，从而 $$ 不可逆；又若 $$ 不可逆，则有

$\forall \ \beta\neq 0,\alpha \beta\neq 1$。则考虑 $\{0,\overline{\alpha },\overline{2\alpha},\cdots,\overline{(m-1)\alpha}\}$ ，该集合不为模 $m$ 的同余类，否则一定能

找到 $\overline{1}$ 与 $$ 不可逆的条件矛盾，则 $\exists\ i,j\in[1,m-1],\overline{i\alpha}=\overline{j\alpha}$，从而取 $\beta=i-j$，$$ 为零因子

$(2)$ 若 $m$ 为素数，$\varphi(m)=m-1$，则有 $m-\varphi(m)-1=0$ 个零因子

若 $m-\varphi(m)-1=0$ 成立，则 $\varphi(m)=m-1$，若 $m$ 为合数，$m=ab$，则 $a$ 和 $b$ 为零因子，

$\varphi(m)\leq m-1-2$ 矛盾

习题2.2.2

$(1)$ 对于环 $Z_{m}$ 中任何元素 $\alpha$，$m$ 个 $\alpha$ 相加为 $\overline{0}$.

$(2)$ 设 $p$ 为素数. 对于域 $Z_{p}$ 中非零元素 $\alpha$ 和正整数 $n$，证明： $n$ 个 $\alpha$ 相加为 $\overline{0}$ 当且仅当 $p \mid n$。

证明：$(1)$ 由 $\alpha_{i}=\alpha_{0}+k_{i}\cdot m$，这些 $m$ 个 $$ 之和为 $m\alpha_{0}+m\displaystyle \sum_{i=1}^{m}k_{i}$，均模 $m$ 余 $0$

而且对于 $\overline{0}$ 中的所有元素 $Km$，都能找到 $k_{i}$ 使得 $\alpha_{0}+\displaystyle \sum_{k=1}^{m}k_{i}=K$，则相加为 $\overline{0}$

$(2)$ 若 $p\mid n$，有 $n$ 个 $$ 相加后模 $m$ 为 $0$，则 $n$ 个 $\alpha$ 相加为 $\overline{0}$；又若 $n$ 个 $\alpha$ 相加为 $\overline{0}$ 时

令 $\alpha_{i}=\alpha_{0}+k_{i}\cdot m$，相加后模 $m$ 得 $n\alpha_{0}\equiv 0(\mbox{mod}\ p)$，而 $\alpha_{0}=0,1,\cdots ,p-1$

$(\alpha_{0},p)=1$，则 $n\equiv 0(\mbox{mod}\ p)$，即 $p\mid n$

习题2.2.3

证明当 $p$ 为奇素数时，$2^{p-1} \cdot\left(\left(\dfrac{p-1}{2}\right) !\right)^{2} \equiv(-1)^{\frac{p+1}{2}}(\bmod p)$。

证明：$2^{p-1}(\dfrac{p-1}{2}\cdot\dfrac{p-3}{2}\cdots\dfrac{4}{2}\cdot \dfrac{2}{2})^{2}=(p-1)^{2}(p-3)^2\cdots 4^2\cdot 2^2$，使用补偿法有 \[ \begin{gathered} (p-1)^2(p-3)^2\cdots4^2\cdot2^2\equiv2\cdot 4\cdot 6\cdots(p-1)\cdot (p-1)\cdot (p-3)\cdots 4\cdot 2\\ \equiv2\cdot 4\cdot 6\cdots (p-1)\cdot (p-(p-1))\cdot (p-(p-3))\cdots (p-4)\cdot (p-2)\cdot (-1)^{\frac{p-1}{2}}\\ \equiv2\cdot 4\cdots (p-1)\cdot 3\cdot 5\cdots (p-2)\cdot (-1)^{\frac{p-1}{2}} \equiv (p-1)!(-1)^{\frac{p-1}{2}}\equiv (-1)^{\frac{p+1}{2}}(\mbox{mod}\ p) \end{gathered} \] 其中使用威尔逊定理，对素数 $p$ ，有 $(p-1)!\equiv-1(\mbox{mod}\ p)$

习题2.2.4

对于整数 $m \geqslant 2$, 证明: $(m-1) ! \equiv-1(\bmod m)$ 当且仅当 $m$ 是素数。 (判别 $m$ 是否为素数)

证明：若 $m$ 为素数，则由威尔逊定理得 $(m-1)!\equiv -1(\mbox{mod}\ m)$；若 $m$ 为合数，则 $m=ab$，

其中 $2\leq a\leq b$，则 $1\leq a,b\leq m-1$，从而 $(m-1)!$ 中一定能凑齐 $m$，此时模为 $0$

习题2.2.5

若 $Z_{m}^{*}=\left\{\alpha_{1}, \cdots, \alpha_{\phi(m)}\right\}$，则 $Z_{m}^{*}=\left\{\alpha_{1}^{-1}, \cdots, \alpha_{\phi(m)}^{-1}\right\}$。如何将它转述成同余的语言?

证明：缩系等价性证明在习题 $1.2.1$ 中。定义 $\alpha_{i}x_i\equiv 1(\mbox{mod}\ m)$ 中 $x_{i}$ 的可取值为 $\alpha_{i}^{-1}$

转述为 $(\alpha_{i},m)=1$，所有 $\alpha_{i}$ 构成 $Z_{m}^*$，由 $\alpha_{i}x_{i}\equiv 1(\mbox{mod}\ m)$中，所有 $x_{i}$ 也构成 $Z_{m}^*$

习题2.3.1

设 $n$ 和 $m$ 是互素的正整数，证明： $m^{\varphi(n)}+n^{\varphi(m)}\equiv1(\bmod m n)$。

证明：由欧拉-费马定理，$m^{\varphi(n)}\equiv1(\mbox{mod}\ n),n^{\varphi(m)}\equiv1(\mbox{mod}\ m)$，且由$\varphi(x)\geq 1$，得

$m^{\varphi(n)}\equiv0(\mbox{mod}\ m),n^{\varphi(m)}\equiv0(\mbox{mod}\ n)$，从而 \[ m^{\varphi(n)}+n^{\varphi(m)}\equiv 1(\bmod m),m^{\varphi(n)}+n^{\varphi(m)}\equiv 1(\bmod n) \] 则 $m^{\varphi(n)}+n^{\varphi(m)}=1+mk_1=1+nk_2$，由于 $(m,n)=1$，则 $n\mid k_1$，原式成立

习题2.3.2

$(1)$ 对每个与 $10$ 互素的整数 $a$, 证明: $a^{20} \equiv 1(\bmod 100)$；

$(2)$ 求 $3^{193}$ 的十进制表达式中的个位和十位数字。

解：$(1)$ 由 $\varphi(4)=2,\varphi(25)=20$，结合 $(a,4)=(a,25)=1$ 有 $a^{20}\equiv 1(\bmod 25)$，

$a^2\equiv 1(\bmod 4)$，$a^{20}\equiv (a^2)^{10}\equiv 1(\bmod 4)$，而 $(4,25)=1$，则 $a^{20}\equiv 1(\bmod 100)$

$(2)$ 由 $3^{193}\equiv 3^{160}\cdot 3^{33}\equiv 27^{11}\equiv 2^{11}\equiv 23(\bmod 25)$，且 $3^{193}\equiv (-1)^{193}\equiv 3(\bmod 4)$，

从而最后两位为 $23$

习题2.3.3

$(1)$ 设 $a, b \in \mathbf{Z}, n \geqslant 1, p$ 为素数。如果 $a \equiv b\left(\bmod p^{n}\right)$，证明：对每个整数 $k \geqslant 0$，

\[ a^{p^{k}} \equiv b^{p^{k}}\left(\bmod p^{n+k}\right) \] $(2)$ 证明: 对每个奇数 $a$ 和 $k \geqslant 1, a^{2^{k}} \equiv 1\left(\bmod 2^{k+2}\right)$.

证明：$(1)$ 令 $b=a+x\cdot p^{n},x\in Z$，代入使用二项式展开有 \[ b^{p^{k}}-a^{p^{k}}=(a+x\cdot p^{n})^{p^{k}}-a^{p^{k}}=\displaystyle \sum_{i=1}^{k}C_{p^{k}}^{i}b^{i}(x\cdot p^{n})^{p^{k}-i} \] 其中 $p^{k}\mid C_{p^{k}}^{i}$，且有 $p^{n}\mid (x\cdot p^{n})^{p^{k}-i}$，从而 $a^{p^{k}} \equiv b^{p^{k}}\left(\bmod p^{n+k}\right)$

$(2)$ 由 $a$ 为奇数，令 $a=2i+1$，则 $a^{2}=4i(i+1)+1$，且 $i$ 和 $i+1$ 一奇一偶，从而

$a^{2}\equiv 1(\bmod 2^{3})$，代入 $\small (1)$ 中结论有 $(a^2)^{2^k}\equiv 1(\bmod 2^{3+k})$，令 $k'=k+1\geq 1$ 则有

$k' \geqslant 1, a^{2^{k'}} \equiv 1\left(\bmod 2^{k'+2}\right)$，得证

$\large\textcolor{blue}{初等数论第四次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.3.15}$

习题2.1.3

解下列同余方程。

$(1)$ $8 x \equiv 5(\bmod 23)$; $(2)$ $60 x \equiv 7(\bmod 37)$.

解：$(1)$ 由 $(8,23)=1$，则在 $Z_{23}$ 中有唯一解，利用费马小定理 \[ x\equiv 8^{\varphi(23)-1}\cdot 5\equiv 8^{21}\cdot 5\equiv 64^{10}\cdot 40\equiv 5^{10}\cdot( -6)\equiv -(25)^{5}\cdot 6\equiv -2^{5}\cdot 6\equiv 15\pmod {23} \] $(2)$ 由 $(60,37)=1$，则在 $Z_{37}$ 中有唯一解，利用费马小定理 \[ \begin{gathered} x\equiv 60^{\varphi(37)-1}\cdot 7\equiv(-14)^{35}\cdot 7\equiv 196^{17}\cdot 13\equiv 11^{17}\cdot 13\\\equiv 10^{8}\cdot (-5)\equiv -5\cdot 11^4 \equiv -5\cdot 10^2\equiv (-5)\cdot (-11)\equiv 18\pmod{37} \end{gathered} \]

习题2.1.4

对每个整数 $n$，证明： \[ \begin{gathered} (1) n^{2} \neq 2(\bmod 3);&(2) n^{2} \equiv 0 或 1(\bmod 4);\\ (3) n^{3} \equiv 0,1 或 -1(\bmod 9) ;&(4) n^{4} \equiv 0 或 1(\bmod 16). \end{gathered} \]

证明：$(1)$ 由费马小定理，若 $(n,3)=1,n^{\varphi(3)}\equiv n^2\equiv 1\pmod 3$，且若 $(n,3)>1$，则 $3\mid n$，

此时有 $n^2\equiv 0\pmod 3$，则 $n^2\neq2 \pmod 3$

$(2)$ 由费马小定理，若 $(n,4)=1,n^{\varphi(4)}\equiv n^2\equiv 1\pmod 4$，且若 $(n,4)>0$，有 $2\mid 4$

此时有 $n^2\equiv 0\pmod 4$，则 $n^2\equiv 0或1 \pmod 4$

$(3)$ 由费马小定理，若 $(n,9)=1,n^{\varphi(9)}\equiv n^6\equiv 1\pmod 9$，即此时 $n^{3}\equiv \pm 1\pmod 9$

若 $(n,9)>1$，则 $3\mid 9$，此时 $n^3\equiv 0\pmod 9$，则 $n^3\equiv 0,\pm 1\pmod 9$

$(4)$ 由费马小定理，若 $(n,16)=1,n^{\varphi(16)}\equiv n^{8}\equiv 1\pmod {16}$，此时分解因式有 \[ (n^4-1)(n^4+1)\equiv 0\pmod{16} \] 而 $n^4\equiv 1\pmod{8}$，故 $n^4\equiv 1,9\pmod{16}$ 综上有 $n^4\equiv 0,1\pmod{16}$

习题2.1.5

设 $a$ 为奇数, $n \geqslant 1 .$ 证明: $a^{2^{n}} \equiv 1\left(\bmod 2^{n+2}\right)$

证明：（使用归纳法，二项式展开较复杂）对 $n=1$ 时成立（第一次作业第一题）

若 $n=k$ 时成立，即 $a^{2^{k}}\equiv 1\pmod {2^{k+2}}$则存在 $t\in Z ,a^{2^{k}}=1+2^{k+2}\cdot t$，则 \[ a^{2^{k+1}}\equiv(a^{2^{k}})^2\equiv(1+2^{k+2}t)^2\equiv1+2^{k+3}t+2^{2k+4}t^2\equiv 1\pmod{2^{k+3}} \] 由数学归纳法知，对 $\forall \ n\geq 1$ 均成立

习题2.4.1

解下列同余方程：$(1)$ $32 x \equiv 12(\bmod 8)$; $(2)$ $28 x \equiv 124(\bmod 116)$; $ 5 x ()$

解：$(1)$ 由判定 $(32,8)=8\nmid 12$，则在 $Z_{8}$ 下无解

$(2)$ 由判定 $(28,116)=4\mid 124$，则在 $Z_{116}$ 下有 $4$ 组解， $7x\equiv 31\pmod{29}$，由费马小定理 \[ x\equiv 7^{\varphi(29)-1}\cdot 31\equiv 7^{27}\cdot 2\equiv 49^{13}\cdot 14\equiv -9^{13}\cdot 14\equiv 6^{6}\cdot 19\equiv 7^{3}\cdot 19\equiv 21\pmod {29} \] 则解为 $x\equiv 21,50,79,108$

$(3)$ 由判定 $(5,81)=1\mid 44$，则在 $Z_{81}$ 下有 $1$ 组解，有 $5x\equiv 44\equiv 125\pmod{81}$

得 $x\equiv 25\pmod{81}$

习题2.4.2

解下列同余方程组：

$(1)$ $\left\{\begin{array}{l}x \equiv 1(\bmod 3), \\ x \equiv 1(\bmod 5), \\ x \equiv 2(\bmod 7) ;\end{array} \quad\right.$ $(2)$ $\left\{\begin{array}{l}x \equiv 2(\bmod 4), \\ x \equiv 3(\bmod 5) \\ x \equiv 7(\bmod 9)\end{array}\right.$

解：$(1)$ 由中国剩余定理，有 $M_1=35,M_2=21,M_3=15$，而对应有 \[ 35M_1^{-1}\equiv 1\pmod{3},\ 21M_{2}^{-1}\equiv 1\pmod{5},\ 15M_{3}^{-1}\equiv 1\pmod{7} \] 得 $M_1^{-1}=2,M_{2}^{-1}=1,M_{3}^{-1}=1$，则 $x\equiv 35\cdot 2\cdot 1+21\cdot 1\cdot 1+15\cdot 1\cdot 2\equiv 16\pmod{105}$

$(2)$ 由中国剩余定理，有 $M_1=45,M_2=36,M_3=20$，而对应有 \[ 45M_1^{-1}\equiv 1\pmod{4},\ 36M_{2}^{-1}\equiv 1\pmod{5},\ 20M_{3}^{-1}\equiv 1\pmod{9} \] 得 $M_1^{-1}=1,M_{2}^{-1}=1,M_{3}^{-1}=5$，则 $x\equiv 45\cdot 1\cdot 2+36\cdot 1\cdot 3+20\cdot 5\cdot 7\equiv 178\pmod{180}$

习题2.4.3

用中国剩余定理解同余方程 $37 x \equiv 31(\bmod 77)$.

解：由 $77=7\cdot 11$，对质因数 $7$ 而言， $37x\equiv 31\equiv185\pmod{7}$，则 $x\equiv 5\pmod{7}$

对质因数 $11$ 而言，$37x\equiv 31\equiv 185\pmod{11}$，则 $x\equiv 5\pmod{11}$

则由中国剩余定理，显然 $x\equiv 5\pmod{77}$，为原方程的解，且该解唯一

习题2.4.4

求 $2^{400}$ 被 $319$ 除的余数.

解：$319=11\cdot 29$，对质因数 $11$ ，$2^{400}\equiv32^{80}\equiv (-1)^{80}\equiv 1\pmod{11}$，对质因数 $29$ \[ 2^{400}\equiv 32^{80}\equiv 3^{80}\equiv 27^{26}\cdot 9\equiv 2^{26}\cdot 9\equiv 32^{5}\cdot 18\equiv 3^{5}\cdot 18\equiv 27^2\cdot 6\equiv 24\pmod{29} \] 则转化成一次同余方程组 $\begin{cases}2^{400}\equiv 1\pmod{11}\\2^{400}\equiv 24\pmod{29}\end{cases}$，由中国剩余定理有

$M_1=29,M_2=11,M_1^{-1}\cdot 29\equiv 1\pmod{11},M_2^{-1}\cdot 11\equiv 1\pmod{29}$

解得 $M_1^{-1}=8,M_{2}^{-1}=8$，则 $2^{400}\equiv 29\cdot 8+11\cdot 8\cdot 24\equiv 2344\equiv 111\pmod{319}$

习题2.4.5

设 $m_{1}, m_{2}$ 是正整数, $b_{1}, b_{2} \in \mathbf{Z}$. 证明: 同余方程组 \[ \left\{\begin{array}{l}x \equiv b_{1}\left(\bmod m_{1}\right), \\x \equiv b_{2}\left(\bmod m_{2}\right)\end{array}\right. \] 有整数解的充分必要条件是 $\left(m_{1}, m_{2}\right) \mid b_{1}-b_{2}$，且此条件成立时, 解为模 $\left[m_{1}, m_{2}\right]$ 的一个同余类.

证明：$(1)$ 充要性：若 $\left\{\begin{array}{l}x \equiv b_{1}\left(\bmod m_{1}\right), \\x \equiv b_{2}\left(\bmod m_{2}\right)\end{array}\right.$ 有整数解，则 $x=m_1y_1+b_1=m_2y_2+b_2$，

两边除以 $(m_1,m_2)$ 得到 $\dfrac{b_1-b_2}{(m_1,m_2)}=\dfrac{m_2y_2-m_1y_1}{(m_1,m_2)}\in Z$，此时有 $(m_1,m_2)\mid b_1-b_2$

若 $(m_1,m_2)\mid b_1-b_2$，有 $\dfrac{m_2y_2-m_1y_1}{(m_1,m_2)}=\dfrac{b_1-b_2}{(m_1,m_2)}\in Z$，而 $(\dfrac{m_1}{(m_1,m_2)},\dfrac{m_2}{(m_1,m_2)})=1$

由辗转相除法知，一定存在 $y_{10},y_{20}$，使得 $\dfrac{-m_1}{(m_1,m_2)}y_{10}+\dfrac{m_2}{(m_1,m_2)}y_{20}=1$

则扩大 $\dfrac{b_1-b_2}{(m_1,m_2)}$ 倍得到 $y_1,y_2$ 的解，从而原同余方程组有解

$(2)$ 同余类：若上述条件成立时，对 $\dfrac{-m_1}{(m_1,m_2)}y_{10}+\dfrac{m_2}{(m_1,m_2)}y_{20}=1$ 有 $y_{10}$ 对应解

所在同余类为模 $\dfrac{m_2}{(m_1,m_2)}$ ，而 $x=m_1y_1+b_1$ 则解为模 $\dfrac{m_1m_2}{(m_1,m_2)}=[m_1,m_2]$

习题2.4.6

设 $m_{1}$ 和 $m_{2}$ 是互素的正整数. 证明:

$(1)$ 若 $S_{1}$ 和 $S_{2}$ 分别是模 $m_{1}$ 和模 $m_{2}$ 的完系. 则 \[ S=\left\{m_{1} x_{1}+m_{2} x_{2} \mid x_{1} \in S_{2}, x_{2} \in S_{1}\right\} \] 是模 $m_{1} m_{2}$ 的完系;

若 $S_{1}$ 和 $S_{2}$ 分别是模 $m_{1}$ 和模 $m_{2}$ 的缩系, 则 \[ S=\left\{m_{1} x_{1}+m_{2} x_{2} \mid x_{1} \in S_{2}, x_{2} \in S_{1}\right\} \] 是模 $m_{1} m_{2}$ 的缩系. (由此可知 $\varphi\left(m_{1} m_{2}\right)=\varphi\left(m_{1}\right) \varphi\left(m_{2}\right)$ )

解：$(1)$ 对 $S$ 中的每个元素 $x_1=m_2y_1+t_1\in S_2,x_2=m_1y_2+t_2\in S_1$

$m_1x_1+m_2x_2=m_1m_2(y_1+y_2)+t_1m_1+t_2m_2$，其中， $y_1+y_2\in Z$ 能取遍所有整数

又由 $(m_1,m_2)=1$，由辗转相除法知 $\exists\ t_{10},t_{20}\in Z$，使得 $t_{10}m_1+t_{20}m_2=1$，

从而 $t_1m_1+t_2m_2$ 也能取遍 $0,1,\cdots ,m_1m_2-1$，则 $S$ 为模 $m_1m_2$ 的完系

$(2)$ 与 $\small(1)$ 相比，对 $t_1m_1+t_2m_2$ 中 $t_1,t_2$ 不是任意整数，需满足 $(t_1,m_2)=1,(t_2,m_1)=1$

此时 $t_1m_1+t_2m_2\nmid m_1m_2$，且由辗转相除法知，存在 $t_{10},t_{20}$ 使得 $t_{10}m_1+t_{20}m_2=1$

且反证法若 $d=(t_{10},m_2)>1$，则上式对 $d$ 同余有 $1\equiv 0\pmod{d}$，矛盾，$t_{10},t_{20}$ 满足条件

对 $\forall \ 0\leq x\leq m_1m_2-1,(x,m_1m_2)=1$ $(x,m_1)=(x,m_2)=1$，取 $xt_{10},xt_{20}$ 满足条件

从而 $S$ 为 $m_1m_2$ 的缩系

习题2.4.7

设 $n$ 为正整数，证明：必有连续 $n$ 个正整数，其中每个整数均被某个大于 $1$ 的整数的平方所除尽。

证明：构造一次同余方程 $\begin{cases}x\equiv 0\pmod{2^2}\\x\equiv -1\pmod{3^2}\\x\equiv -2\pmod{5^2}\\\qquad\vdots\\x\equiv -(n-1)\pmod{p_{n}^2}\end{cases}$，其中 $p_n$ 为第 $n$ 个素数

对 $\forall \ p_i,p_j,(p_i^{2},p_j^2)=1$，由中国剩余定理，一定有最小正整数解 $x_{min}(n)$ 满足上述方程

该 $x_{min}$ 能保证序列 $x_{min},x_{min}+1,\cdots,x_{min}+(n-1)$ 中任何数能被某个大于 $1$ 的整数平方整除

$\large\textcolor{blue}{初等数论第五次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.3.22}$

习题3.1.2

$a$ 对模 $m$ 和模 $n$ 的阶分别为 $s$ 和 $t$, 证明: $a$ 对模 $[m, n]$ 的阶为 $[s, t]$.

证明：由 $a$ 对模 $m$ 和模 $n$ 的阶为 $s,t$，则 $a^{s}\equiv 1\pmod m,a^{t}\equiv 1\pmod n$

则令 $a$ 对 $[m,n]$ 的阶为 $r$，即 $a^{r}\equiv 1\pmod{[m,n]}$，有 $m,n\mid [m,n]$，则 $s,t\mid r$，则 $[s,t]\mid r$

又 $a^{[s,t]}\equiv (a^{s})^{\frac{[s,t]}{s}}\equiv 1\pmod{m},a^{[s,t]}\equiv (a^{t})^{\frac{[s,t]}{t}}\equiv 1\pmod{n}$，则 $a^{[s,t]}\equiv 1\mod{[m,n]}$

从而 $r\mid [s,t]$，则 $r=[s,t]$，即 $a$ 对模 $[m,n]$ 的阶为 $[s,t]$

习题3.1.5

若 $n$ 和 $a$ 均是正整数, $a \geqslant 2$. 证明: $n \mid \varphi\left(a^{n}-1\right)$.

证明：考虑 $a$ 模 $a^{n}-1$ 的阶 $r$，有 $a^{n}\equiv 1\pmod{a^{n}-1}$，则 $r\mid n$，若 $r=\dfrac{n}{d},d\geq 2$

但 $a^{r}=\sqrt[d]{a^{n}}\leq a^{n}-1$，则此时 $a^{r}\not\equiv 1\pmod{a^{n}-1}$，从而 $d=1$，即 $a$ 模 $a^{n}-1$ 阶为 $n$

由 $a$ 模 $a^{n}-1$ 阶一定为 $\varphi(a^{n}-1)$ 的因子，从而 $n\mid \varphi(a^{n}-1)$

习题3.1.6

如果 $n \geqslant 2$, 证明: $n \not\mid 2^{n}-1$.

证明：由于 $2^n-1\equiv 1\pmod{2}$，若 $2\mid n$，则 $n\not\mid 2^{n}-1$，若 $2\not\mid n$，令 $n$ 最小奇素数因子 $p$

则 $n=pt,t\in Z$，反证法若 $n\mid 2^n-1$，令 $2^n=1+nx=2^{pt}=1+ptx,x\in Z$

有 $2^{pt}\equiv 1\pmod{p}$，而费马小定理给出 $2^{p-1}\equiv 1\pmod{p},2^p\equiv 2\pmod{p}$ 由 $pt\mid p-1$ 矛盾

习题3.1.7

设 $p$ 是奇素数, $n \geqslant 1$. 证明: \[ \sum_{k=1}^{p-1} k^{n} \equiv \begin{cases}-1(\bmod p), & \text { 如果 } p-1 \mid n, \\ 0(\bmod p), & \text { 如果 } p-1 \not\mid n .\end{cases} \]

证明：由于 $p$ 为奇素数，令其原根为 $g$，则 $Z_{p}=\{1,2,\cdots ,p-1\}=\{g,g^2,\cdots,g^{p-1}\}$

从而求和式 $\displaystyle \sum_{k=1}^{p-1}k^{n}\equiv \sum_{k=1}^{p-1}g^{n}\pmod{p}$，若 $p-1\mid n$，由费马小定理 $g^{n}\equiv g^{p-1}\equiv 1\pmod{p}$

此时 $\displaystyle \sum_{k=1}^{p-1}k^{n}\equiv \sum_{k=1}^{p-1}1\equiv -1\pmod{p}$，若 $p-1\not\mid n$，则由等比数列求和 \[ \sum_{k=1}^{p-1}g^n\equiv \dfrac{g^{n}(1-g^{p-1})}{1-g^{n}}\equiv \dfrac{g^{n}\cdot 0}{1-g^{n}}(1-g^{n}\neq 0)\equiv 0\pmod{p} \] 从而 $\sum_{k=1}^{p-1} k^{n} \equiv \begin{cases}-1(\bmod p), & \text { if } p-1 \mid n, \\ 0(\bmod p), & \text { if } p-1 \not\mid n .\end{cases}$

习题3.1.8

$(1)$ 设 $F_{n}=2^{2^{n}}+1$ (费马数), $n \geqslant 1$. 证明: $F_{n}$ 的每个素因子都有形式 $2^{n+1} x+1(x \in \mathbf{Z})$.

$(2)$ 对任意给定的整数 $l \geqslant 1$, 证明: 有无穷多个素数模 $2^{l}$ 余 1 .

证明：$(1)$ 对每个 $F_{n}$ 的奇素数因子 $p$，有 $2^{p-1}\equiv 1\pmod{p}$，而 $2^{2^{n}}\equiv -1\pmod{p}$，两边平方

$2^{2^{n+1}}\equiv 1\pmod{p}$，从而令 $2$ 模 $p$ 的次数为 $r$，则 $r\mid2^{n+1}$，$r=2^{k}$，显然 $k\neq n$，因为

$2^{2^{n}}\equiv -1\pmod{p}$，若 $k<n$，则重复 $n-k$ 次平方操作得到 $2^{2^{n}}\equiv 1\pmod{p}$ 与条件矛盾

从而 $r=2^{n+1}$，结合 $2^{p-1}\equiv 1\pmod{p}$ 可得 $2^{n+1}\mid p-1$

$(2)$ 对任意两个不相同的费马数，$F_{m},F_{n}$ ，不妨设 $m\geq n,m=n+k,k\geq 1\in Z$

则 $F_{m}=2^{2^{m+n}}+1=(2^{2^{n}})^{2^k}+1=(F_{n}-1)^{2^k}+1=p(F_n)+2$，其中 $p(F_n)$ 为多项式

从而 $(F_{m},F_n)\mid 2$，又 $x\not\mid F_{n},F_m$，则 $(F_m,F_n)=1$，即所有费马数两两互素，而每个 $F_n$

都至少有一个素因子模 $2^{n+1}$ 余 $1$，且不同费马数素因子不重合，则对给定的 $l$，取 $n\geq l-1$

则这些无穷个的费马数模 $2^{n+1}$ 余 $1$，则也模 $2^{l}$ 余 $1$

习题3.1.9

$(1)$ 设 $p$ 为奇素数, $a \geqslant 2$. 证明: 若 $a^{p}-1$ 的素因子 $q$ 不整除 $a-1$，则必有形式 $q=2 p x+1(x \in Z)$.

$(2)$ 设 $p$ 为给定的奇素数, 证明：形如 $2 p x+1(x \in \mathbb{Z})$ 的素数有无限多个.

证明：$(1)$ 由于 $q$ 为 $a^{p}-1$ 素因子，则 $a^p\equiv 1\pmod{q}$，由 $q\not\mid a-1$，得 $a\not\equiv 1\pmod{q}$

设 $a$ 为模 $q$ 的阶为 $r$，则有 $r\mid p$，又 $r\neq 1$，从而 $r=p$，有费马小定理 $a^{q-1}\equiv 1\pmod{q}$

从而 $r=p\mid q-1$；另一方面考虑奇偶性，若 $2 \mid a$，$2\not \mid a^{p}-1$，素因子 $q$ 为奇数，若 $2\not\mid a$，

$a^{p}-1$ 有素因子 $2$，但此时要求 $q$ 不整除 $a-1$，从而 $q\neq 2$，素因子 $q$ 也为奇数，则 $q-1$ 中

有素因子 $2$，而 $p$ 为奇素数，从而 $2p \mid q-1$

$(2)$ 构造 $a_1=2^{p}-1,a_n=(\displaystyle \prod_{i=1}^{n-1}a_i)^{p}-1$，满足两两互素，$a^{p}-1$ 总能有不整除 $a-1$ 的素因子

否则所有素因子 $p_i=\dfrac{a-1}{k_i},k_i\geq 2\in Z$，相乘有 $a^p-1=\dfrac{(a-1)^{x}}{\displaystyle \prod_{i=1}^{x}k_i}$ 移项后有

$(a^p-1)\displaystyle \prod _{i=1}^{x}k_i=(a-1)^x$，两边对 $a$ 取模得 $-\displaystyle \prod_{i=1}^xk_i\equiv (-1)^x\pmod{a}$ 矛盾

则两两互素的无穷整数数列 $\{a_n\}$ 中每个数都存在形如 $2px+1$ 的素因子，共无穷多个

柯召讲义5.1

证明: $m$ 是一个素数的充分必要条件是存在某个整数 $a, a$ 对模数 $m$ 的次数为 $m-1$.

证明：$1^{\circ}$ 若 $m$ 为一个素数，由素数必有原根可知，$\exists\ a\in Z$，使得 $a$ 模 $m$ 的阶数为 $m-1$

$2^{\circ}$ 若对某个 $a\in Z$，$a^{r}\equiv 1\pmod{m}$ 的最小正整数（阶数 $r$ ）为 $m-1$，有 $(a,m)=1$

由费马小定理 $a^{\varphi(m)}\equiv 1\pmod{m}$，得 $m-1\mid \varphi(m)$，若 $m$ 不是素数，$m\geq 2$，令 \[ m=p_1^{l_1}\cdots p_{s}^{l_s},\varphi(m)=m\prod _{i=1}^{s}(1-\dfrac{1}{p_i})\leq m\prod _{i=1}^{s}(1-\dfrac{1}{p_i^{l_i}})< m(1-\prod_{i=1}^{s}\dfrac{1}{p_i^{l_i}})=m-1 \] 从而 $m$ 为素数

柯召讲义5.2

设 $g$ 是奇素数 $p$ 的一个原根, 证明: 当 $p \equiv 1(\bmod 4)$ 时, $-g$ 也是 $p$ 的一个原根; 当 $p \equiv 3(\bmod 4)$ 时, $-g$ 对 $p$ 的次数为 $\dfrac{p-1}{2}$.

证明：若 $g$ 是奇素数 $p$ 的一个原根，则满足 $g^{r}\equiv 1\pmod{p}$ 的最小 $r=p-1$，而 $2\mid p-1$

则 $(-g)^{p-1}\equiv g^{p-1}\equiv 1\pmod{p}$，且若存在 $1\leq r'< p-1$，使得 $(-g)^{r'}\equiv 1\pmod{p}$

$r'$ 不能是偶数，否则与阶数矛盾，则 $2\not \mid p$，有 $g^{r'}\equiv -1\pmod{p}$，则 \[ g^{2r'}-1\equiv (g^{r'}+1)\cdot (g^{r'}-1)\equiv 0\pmod{p},g^{2r'}\equiv 1\pmod{p} \] 则 $2r'\mid r$，由于 $r'$ 为奇数，若 $p\equiv 1\pmod{4}$，则 $4\mid p-1$，此时 $r'$ 不存在，从而 $-g$ 也为原根

若 $p\equiv 3\pmod{4}$ ，有 \[ g^{p-1}-1\equiv (g^{\frac{p-1}{2}}-1)\cdot (g^{\frac{p-1}{2}}+1)\equiv 0\pmod{p} \] 且 $g^{\frac{p-1}{2}}\not \equiv 1\pmod{p}$ 否则不满足阶数的性质，则 $(-g)^{\frac{p-1}{2}}\equiv 1\pmod{p}$，若 $1\leq r''< \dfrac{p-1}{2}$

使得 $(-g)^{r''}\equiv 1\pmod{p}$，首先 $r''$ 不为偶数，若 $r''$ 为奇数，则 $g^{r''}\equiv -1\pmod{p}$

从而平方 $g^{2r''}\equiv 1\pmod{p}$，则有 $22r''<p-1 $ 使得 $g^{2r''}\equiv 1\pmod{p}$ 与阶数矛盾

从而此时 $-g$ 对 $p$ 的阶数为 $\dfrac{p-1}{2}$

$\large\textcolor{blue}{初等数论第六次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.4.1}$

习题3.1.1

设 $m \geqslant 2$, 整数 $a$ 和 $b$ 模 $m$ 的阶分别为 $s$ 和 $t$, 并且 $(s, t)=1$. 证明 $a b$ 模 $m$ 的阶为 $s t$.

证明：设 $ab$ 模 $m$ 的阶为 $r$，$(ab)^{r}\equiv 1\pmod{m}$，由 $(ab)^{st}\equiv (a^{s})^{r}\cdot (b^r)^{s}\equiv 1\pmod{m}$

得 $r\mid st$，则设 $st=pr,p\in Z \mbox{\ and \ p is\ prime}$，由 $(s,t)=1$，则 $p\mid s$ 或 $p \mid t$，不妨设 $ ps$

令 $s=px,xt=r$，有 $(ab)^{r}\equiv (ab)^{xt}\equiv a^{xt}\cdot 1\equiv 1 \pmod{m}$

则 $s\mid xt$，由 $(s,t)=1$，得 $s\mid x$，又 $x\mid s$，可得 $s=x,p=1$，即 $r=st$

习题3.1.4

$(1)$ 对于 $p=5,7,11,13,23$, 求模 $p$ 的最小正原根.

$(2)$ 求模 $7^{2}$ 的全部原根.

解：$(1)$ 由在 $Z_5$ 下 $\{2,2^2,2^3,2^4\}=\{2,4,3,1\}$ ，则 $2$ 为 $5$ 的最小正原根

在 $Z_7$ 下 $\{2,2^2,2^3,2^4,2^5,2^6\}=\{2,4,1,2,4,1\},\{3,3^2,3^3,3^4,3^5,3^6\}=\{3,2,6,4,5,1\}$

则 $3$ 为 $7$ 的最小正原根

在 $Z_{11}$ 下 $\{2,2^2,2^3,2^4,2^5,2^6,2^7,2^8,2^9,2^{10}\}=\{2,4,8,5,10,9,7,3,6,1\}$ ，则 $2$ 为 $11$ 的

最小正原根

在 $Z_{13}$ 下 $\{2,2^2,2^3,2^4,2^5,2^6,2^7,2^8,2^9,2^{10},2^{11},2^{12}\}=\{2,4,8,3,6,12,11,9,5,10,7,1\}$

则 $2$ 为 $13$ 的最小正原根

在 $Z_{23}$ 下 $\{2,2^2,2^3,2^4,2^5,2^6,2^7,2^8,2^9,2^{10},2^{11}\}=\{2,4,8,16,9,18,13,3,6,12,1\}$

$\{3,3^2,3^3,3^4\}=\{3,6,12,1\}$ 对 $5$ 而言 \[ \begin{gathered} \{5,5^2,5^3,5^4,5^5,5^6,5^7,5^8,5^9,5^{10},5^{11},5^{12},5^{13},5^{14},5^{15},5^{16},5^{17},5^{18},5^{19},5^{20},5^{21},5^{22}\}=\\ \{5,2,10,4,20,8,17,16,11,9,22,18,21,13,19,3,15,6,7,12,14,1\} \end{gathered} \] 则 $5$ 为 $23$ 的最小正原根

$(2)$ 由定理， $7$ 有原根 $3$，则 $3$ 和 $10$ 必有一个为 $49$ 的原根，有 \[ 3^{2},3^{4},3^{6},3^{8},3^{12},3^{16},3^{24}\equiv 9,32,43,44,36,25,22\pmod{49} \] 从而 $3$ 为 $49$ 的原根，有 $\varphi(\varphi(49))=\varphi(42)=12$ 个原根，有 $3^{r},(r,42)=1$ 均为原根，计算有

$\{3,3^{5},3^{11},3^{13},3^{17},3^{19},3^{23},3^{25},3^{29},3^{31},3^{37},3^{41}\}=\{3,47,12,10,26,38,40,17,5,45,24,33\}$

则 $49$ 的所有原根为 $\begin{equation}\boxed{3, 5, 10 , 12, 17 , 24 , 26 , 33 , 38 , 40 , 45, 47}\end{equation}$，共 $12$ 个

习题3.2.1

解同余方程:

$(1)$ $x^{8} \equiv 3 \pmod{13}$;

$(2)$ $x^{8} \equiv 3\pmod {143}$;

$(3)$ $7^{x} \equiv 4\pmod{17}$.

解：$(1)$ 由上题知 $2$ 为 $13$ 的一个原根，则原式等价于 $8\mbox{ind}_2x\equiv \mbox{ind}_{2}3\pmod{12}$

由 $2^{4}\equiv 3\pmod{13}$ 得 $8\mbox{ind}_2x\equiv 4\pmod{12}$ 且 $(8,12)=4\mid 4$，代换有

$2\mbox{ind}_2x\equiv 1\equiv 4\pmod{3}$，$\mbox{ind}_2{x}\equiv 2,5,8,11$，得解为 $x_1\equiv 4,6,7,9\pmod{13}$

$(2)$ 结合 $x^8\equiv 3\pmod{11}$，由 $2$ 为 $11$ 的一个原根，等价于 $8\mbox{ind}_2x\equiv \mbox{ind}_23\equiv 8\pmod{10}$

由 $(8,10)=2\mid 10$，则有两个解，$\mbox{ind}_2x\equiv 1,6\pmod{10}$，则 $x_2\equiv 2,9\pmod{11}$

使用中国剩余定理，$11^{-1}\equiv 6\pmod{13},13^{-1}\equiv 6\pmod{11}$ 对应计算 $x_1\cdot 6\cdot 13+x_2\cdot 6\cdot 11$ \[ x\equiv 9,20,35,46,97,108,123,134 \pmod{143} \] $(3)$ 对 $2$ 计算 $2^1,2^2,2^4,2^8\equiv 2,4,16,1\pmod{17}$，则 $2$ 不是 $17$ 的原根，同理对 $3$ 计算有

$3^1,3^2,3^4,3^8\equiv 3,9,13,16\pmod{17}$，则 $3$ 是 $17$ 的原根，则对 $7^{x} \equiv 4\pmod{17}$ 变换有

$x\mbox{ind}_{3}7\equiv \mbox{ind}_34\pmod{16}$ 有 $\mbox{ind}_37=11,\mbox{ind}_34=12$，则 $11x\equiv 12\pmod{16}$

$(11,16)=1\mid 12$ 只有一个整数解，得 $x\equiv 4\pmod{17}$

习题3.2.2

$(1)$ 写出模 $37$ 的全部 $8$ 次剩余和 $15$ 次剩余.

$(2)$ 写出模 $11$ 的全部二次剩余.

解：$(1)$ 取 $37$ 的一个原根 $2$，由 $(8,36)=4$，因此八次剩余 $a$ 满足的条件为： $4 \mid \operatorname{ind}_{2} a$ ，故

$\operatorname{ind}_{2} a=4,8,12, \cdots, 36$ ，因此模 $37$ 的全部 $8$ 次剩余为: $a \equiv 2^{4}, 2^{8}, \cdots, 2^{36}(\bmod 37)$； \[ a\equiv 16,34,26,9,33,10,12,7,1\pmod{37} \] 而 $(15,36)=3$ ，因此 $15$ 剩余 $a$ 满足的条件为：$3 \operatorname{ind}_{2} a$ ，故 $\operatorname{ind}_{2} a=3,6, \cdots, 36$ ，因此解为:

\[ a \equiv 2^{3}, 2^{6}, \cdots, 2^{36}\equiv 8,27,31,26,23,36,29,10,6,11,14,1 (\bmod 37) \] $(2)$ 模 $11$ 的全部二次剩余为: $1^{2}, 2^{2}, \cdots, 5^{2}$ ，即 $1,3,4,5,9$

习题3.2.3

设 $p$ 为素数, $p \equiv 2(\bmod 3), a$ 和 $b$ 是整数. 证明： $a^{3} \equiv b^{3}(\bmod p)$ 当且仅当 $a \equiv b(\bmod p)$.

证明：若 $(a,p)=p$，则 $a\equiv b\equiv 0\pmod{p}$，否则 $(a,p)=1$ 令 $p=3k+2,k\geq 1$，有

$a^{3}\equiv b^{3}\equiv c\pmod{p}$，且 $(c,p)=1$，由欧拉定理 $a^{3k+1}\equiv b^{3k+1}\equiv c^ka\equiv c^kb\equiv 1\pmod{p}$

从而 $a\equiv c^{-k}\equiv b\pmod{p}$

设 $a^{3} \equiv b^{3} \equiv k(\bmod p)$ ，因为 $(3, p-1)=1$ ，故 $x^{3} \equiv k(\bmod p)$ 在模 $p$ 意义下仅有一个解，故得证

习题3.2.4

设 $p$ 为奇素数, 整数 $a$ 模 $p$ 的阶为 $3$，求 $\dfrac{a}{a+1}$ 模 $p$ 的阶.

解：由题设定义 $a$ 的数论倒数为 $b$，即 $ab\equiv 1\pmod{p}$，有 $(\dfrac{a}{a+1})^{-1}=1+\dfrac{1}{a}=1+b$

由 $x$ 与 $x^{-1}$ 模 $p$ 的阶是一样的，从而考虑 $1+b$ 模 $p$ 的阶，由满足 $a^{r}\equiv 1\pmod{p}$ 的最小正整数

为 $3$ ，也有 $b^3\equiv 1\pmod{p}$，$b^2+b+1\equiv 0\pmod{p}$，令 $1+b$ 模 $p$ 的阶为 $r'$，

有 $(1+b)^{r'}\equiv 1\pmod{p}$ ，有 $(1+b)^{1}\not\equiv 1\pmod{p},(1+b)^2\equiv b\not\equiv 1\pmod{p}$

但 $(1+b)^3\equiv 3(b^2+b+1)-2+b^3\equiv -1\pmod{p}$，而 $(1+b)^4\equiv -1\not\equiv 1\pmod{p}$

$(1+b)^5\equiv -b\not\equiv 1\pmod{p}$，且 $(1+b)^{6}\equiv 1\pmod{p}$，则 $\dfrac{a}{a+1}$ 模 $p$ 的阶为 $6$

习题4.1.2

设 $p$ 为奇素数, $n$ 是最小正整数使得 $\left(\dfrac{n}{p}\right)=-1$. 证明: $n$ 为素数

证明：由勒让德符号定义不存在整数 $x$ 使得 $x^2\equiv n\pmod{p}$，取 $p$ 的原根 $g$ 有 $n=g^{2j+1}$

若 $n$ 为合数，即 $n=n_1n_2$，由 $\left(\dfrac{n}{p}\right)=\left(\dfrac{n_1}{p}\right)\left(\dfrac{n_2}{p}\right)$ 可知 $n_1$ 和 $n_2$ 一定一者为 $1$，另一者为 $-1$

而显然为 $-1$ 的一者对应的 $n_i$ 更小，与题设矛盾，从而 $n$ 为素数

$\large\textcolor{blue}{初等数论第七次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.4.16}$

习题4.1.1

设 $p$ 为奇素数, $a, b \in \mathbf{Z},(a, p)=1$. 证明： \[ \sum_{n=0}^{p-1}\left(\frac{a n+b}{p}\right)=0 \]

证明：由于 $(a,p)=1$，则 $a,a+b,\cdots,a(p-1)+b$ 构成模 $p$ 的完系，可用反证法证明

其中模 $p$ 的二次剩余和非二次剩余都为 $\dfrac{p-1}{2}$ 个，最后剩一个能被 $p$ 整除的

则 $\displaystyle \sum_{n=0}^{p-1}\left(\frac{a n+b}{p}\right)=\dfrac{p-1}{2}+(-1)\cdot \dfrac{p-1}{2}+0=0$

习题4.1.3

证明形如 $8m+3,8m+5,8m+7$ 的素数均有无穷多个

解：$(1)$ 反证，假设 $8m+3$ 的素数有限个，设为 $p_1.p_2,\cdots ,p_s$ 构造 $n=2(p_1p_2\cdots p_s)^2+1$ ，

由 $n\equiv 2\cdot (3^2)^{s}+1\equiv 3\pmod{8}$，则由假设 $n$ 为合数

设其素因子为 $p$，有 $2(p_1p_2\cdots p_s)^2\equiv -1\pmod{p}$，两边乘以 $2$，取勒让德符号 \[ (\dfrac{-2}{p})=1=(\dfrac{2}{p})(\dfrac{-1}{p})=(-1)^{\frac{p^2-1}{8}+\frac{p-1}{2}}=(-1)^{\frac{(p-1)(p+5)}{8}} \] 从而 $2\mid \dfrac{(p-1)(p+5)}{8}$，从而 $p\equiv 1,3\pmod{8}$。但 $n\equiv 3\pmod{8}$，$n$ 的所有素因子不可能

均模 $8$ 余 $3$，从而一定存在一个模 $8$ 余 $3$ 的素因子，而该素因子不为 $p_1,\cdots ,p_s$，这是因为

$n\equiv 1\pmod{p_i}$，从而矛盾，$8m+3$ 型素数有无穷多个

$(2)$ 假设 $8m+5$ 的素数有限个，设为 $p_1,p_2,\cdots,p_s$，构造 $n=4(p_1\cdots p_s)^2+1$ 有

$n\equiv 5\pmod{8}$，其为合数，设其素因子为 $p$

有 $(2p_1\cdots p_s)^2\equiv -1\pmod{p}$，取勒让德符号有 $(\dfrac{-1}{p})=1=(-1)^{\frac{p-1}{2}}$

则 $p\equiv 1,5\pmod{8}$ 而 $n\equiv 5\pmod{5}$，$n$ 的所有素因子不可能全为 $1$，则其存在一个

不为 $p_i$ 的素因子，与假设矛盾，从而 $8m+5$ 型素数有无穷多个

$(3)$ 假设 $8m+7$ 的素数有限个，设为 $p_1,p_2,\cdots,p_s$，构造 $n=8(p_1\cdots p_s)^2-1$ 有

$n\equiv 7\pmod{8}$，其为合数，设其素因子为 $p$

有 $(4p_1\cdots p_s)^2\equiv 2\pmod{p}$，使用勒让德符号有 $(\dfrac{2}{p})=1=(-1)^{\frac{p^2-1}{8}}$

则 $p\equiv 1,7$，又由于 $n\equiv 7\pmod{8}$，$n$ 所有素因子不可能全为 $1$，则其存在一个

不为 $p_i$ 的素因子，与假设矛盾，从而 $8m+7$ 型素数有无穷多个

习题4.1.4

设 $p$ 为奇素数. 证明: 有无穷多的素数是模 $p$ 的二次非剩余.

证明：假设满足是模 $p$ 二次非剩余的素数有限，为 $p_1,p_2,\cdots p_s$，有 $(\dfrac{p_i}{p})=-1$，取模 $p$ 的

一个二次非剩余 $a$，由中国剩余定理，满足 $x\equiv a\pmod{p},x\equiv 1\pmod{p_i}$ 同余方程的解

存在，设其中一个解为 $x$

则 $(\dfrac{x}{p})=(\dfrac{a}{p})=-1$，$x$ 必有素因子为二次非剩余，且使得该素因子与 $p_i$ 均互素，这样与

有限个满足条件的素数矛盾，从而有无穷多个素数模 $p$ 二次剩余

习题4.1.5

设 $p$ 和 $q=2 p+1$ 都是素数. 证明:

$(1)$ 当 $p \equiv 1(\bmod 4)$ 时, $2$ 是模 $q$ 的原根;

$(2)$ 当 $p \equiv 3(\bmod 4)$ 时,$-2$ 是模 $q$ 的原根.

解：$(1)$ 由于 $q-1=2p$ 只有素因子 $2$ 和 $p$ ，有 $2^2\equiv 4\not\equiv 1\pmod{q}$ 而对$2^{p}\equiv 2^{\frac{q-1}{2}}$，计算

$(\dfrac{2}{q})=(-1)^{\frac{q^2-1}{8}}=(-1)^{\frac{p(p+1)}{2}}=-1$，则 $2$ 为模 $q$ 的二次非剩余，则取 $q$ 的原根 $g$，有 $2=g^{2j+1}$，代入计算 $2^{p}=g^{(2j+1)p}=(g^{p})^{2j+1}=(g^{\frac{q-1}{2}})^{2j+1}=(-1)^{2j+1}=-1$，从而 $2,p$ 均不是模 $p$

下 $2$ 的阶数，从而 $2$ 为模 $p $ 的原根

$(2)$ 同上，只需考虑 $(-2)^{p}$，$p\neq 2$，计算 $(\dfrac{-2}{q})=(\dfrac{-1}{q})(\dfrac{2}{q})=(-1)^{\frac{q-1}{2}}(-1)^{\frac{q^2-1}{8}}=-1$，

则取 $q$ 的原根 $g$，有 $-2=g^{2j+1}$，代入 $(-2)^{p}=(g^{\frac{q-1}{2}})^{2j}=(-1)^{2j+1}=-1$

从而 $2,p$ 均不是模 $p$ 下 $-2$ 的阶数，从而 $-2$ 为模 $p $ 的原根

习题4.1.6

设 $p$ 为素数, $p \equiv 3(\bmod 4)$. 记 $q=2 p+1$. 则 $q$ 为素数当且仅当 $q \mid 2^{p}-1$.

证明：由上题知，若 $q$ 为素数，$-2$ 为 $q$ 的原根 \[ 2^{p}\equiv -(-2)^{p}\equiv -(-2)^{\frac{q-1}{2}}\equiv -(-1)\equiv 1\pmod{p} \] 则 $q\mid 2^{p}-1$ 。又若 $q\mid 2^{p}-1$ ，由欧拉定理 $2^{\varphi(q)}\equiv 1\pmod{q}$，即 $q\mid 2^{\varphi(q)}-1$

则 $p\mid \varphi(q)=\varphi(2p+1)$，若 $q$ 不是素数，$\varphi(2p+1)<2p$，则 $p=\varphi(2p+1)$，而对于奇数

的欧拉函数为偶数，从而矛盾，则 $q$ 为素数

习题4.1.7

设 $p$ 为奇素数. 证明： \[ \large \prod_{\substack{r=1 \\ \\ \\ \large (\frac{r}{p})=1}}^{p-1} \normalsize r \equiv-\left(\frac{-1}{p}\right)(\bmod p) \]

解：满足 $(\dfrac{r}{p})=1$ 的所有 $r$ 为 $g^0,g^2,\cdots ,g^{p-3}$。其中 $g$ 为 $p$ 的一个原根，则 \[ \displaystyle \prod r =g^{0+2+\cdots p-3}=g^{\frac{(p-3)(p-1)}{4}}=(g^{\frac{p-1}{2}})^{\frac{p-3}{2}}=(-1)^{\frac{p-3}{2}} \] 而 $-(\dfrac{-1}{p})=-(-1)^{\frac{p-1}{2}}=(-1)^{\frac{p-3}{2}}$，两者相等

习题4.1.8

设 $p$ 为素数,

$(1)$ 若 $p \equiv 1(\bmod 4)$, 则 \[ \sum_{\substack{r=1 \\\left(\frac{r}{p}\right)=1}}^{p-1} r=\frac{p(p-1)}{4}, \quad \sum_{a=1}^{p-1} a\left(\frac{a}{p}\right)=0 \] (2) 若 $p \equiv 3(\bmod 4)$, 并且 $p \geqslant 7$, 则 \[ \sum_{\substack{r=1 \\\left(\frac{r}{p}\right)=1}}^{p-1} r \equiv 0(\bmod p), \sum_{r=1}^{p-1} a\left(\frac{a}{p}\right) \equiv 0(\bmod p) . \]

证明：$(1)$ 由 $(\dfrac{p-x}{p})=(\dfrac{-x}{p})=(\dfrac{x}{p})(\dfrac{-1}{p})=(\dfrac{x}{p})(-1)^{\frac{p-1}{2}}=(\dfrac{x}{p})$

从而 $(i,p-i)$ 每对勒让德符号相同，从而所有满足 $(\dfrac{r}{p})=1$ 的 $r$ 一定能配成和为 $p$ 的 $\mbox{pairs}$

且共有 $\dfrac{p-1}{4}$ 对，求和为 $\dfrac{p(p-1)}{4}$，同理分离得到 $\displaystyle \sum_{a=1}^{p-1}a(\dfrac{a}{p})=0+\sum_{\substack{r=1 \\\left(\frac{r}{p}\right)=1}}^{p-1} r-\sum_{\substack{r=1 \\\left(\frac{r}{p}\right)\neq 1}}^{p-1} r=0$

$(2)$ 和上题类似，得到 $(\dfrac{p-x}{p})=-(\dfrac{x}{p})$，从而 $(i,p-i)$ 勒让德符号相反，有记 \[ \sum_{\substack{r=1 \\\left(\frac{r}{p}\right)=1}}^{p-1} r \equiv A(\bmod p),\sum_{\substack{r=1 \\\left(\frac{r}{p}\right)\neq 1}}^{p-1} r \equiv B(\bmod p) \] 取模 $p$ 的一个原根 $g$ ，则 $g$ 是模 $p$ 的一个二次非剩，$(\dfrac{g}{p})=-1$ \[ \begin{aligned} &\sum_{r=1,\left(\frac{r}{p}\right)=1}^{p-1} r \equiv 1+g^{2}+\cdots+g^{p-3} \equiv \frac{1-g^{\frac{p-1}{2}\cdot 2}}{1-g^{2}} \equiv 0 \quad(\bmod p) \\ &\sum_{a=1}^{p-1} a\left(\frac{a}{p}\right) \equiv \sum_{i=0}^{p-2} g^{i}\left(\frac{g^{i}}{p}\right) \equiv \sum_{i=0}^{p-2} g^{i}(-1)^{i} \equiv \sum_{i=0}^{p-1}(-g)^{i} \equiv \frac{1-g^{p-1}}{1+g} \equiv 0 \quad(\bmod p) . \end{aligned} \]

习题4.2.1

计算 $\left(\dfrac{17}{23}\right),\left(\dfrac{19}{37}\right),\left(\dfrac{92}{101}\right)$.

由二次互反律计算有 \[ \left(\dfrac{17}{23}\right)=\left(\dfrac{23}{17}\right)(-1)^{11 \cdot 8}=\left(\dfrac{23}{17}\right)=\left(\dfrac{6}{17}\right)=\left(\dfrac{2}{17}\right)\left(\dfrac{3}{17}\right)\\=(-1)^{\frac{17^{2}-1}{8}}\left(\dfrac{17}{3}\right)(-1)^{8}=\left(\dfrac{17}{3}\right)=\left(\dfrac{2}{3}\right)=-1\\ \left(\dfrac{19}{37}\right)=\left(\dfrac{37}{19}\right)(-1)^{9 \cdot 18}=\left(\dfrac{37}{19}\right)=\left(\dfrac{-1}{19}\right)=(-1)^{9}=-1\\ \left(\dfrac{92}{101}\right)=\left(\dfrac{2}{101}\right)^{2}\left(\dfrac{23}{101}\right)=(-1)^{\dfrac{101^{2}-1}{8}}\left(\dfrac{23}{101}\right)=\\\left(\dfrac{23}{101}\right)=\left(\dfrac{101}{23}\right)(-1)^{50 \cdot 11}=\left(\dfrac{101}{23}\right)=\left(\dfrac{9}{23}\right)=\left(\dfrac{3}{23}\right)^{2}=1 \]

习题4.2.4

若 $p=10 m-1$ 为素数, 证明: $p \mid 5^{5 m-1}-1$.

证明：计算 $(\dfrac{5}{p})=(\dfrac{p}{5})(-1)^{2\cdot \frac{p-1}{2}}=(\dfrac{p}{5})=(\dfrac{-1}{5})=(-1)^2=1$，则 $5$ 是 $p$ 的二次剩余

令 $g$ 为 $p$ 的二次剩余，$5\equiv g^{2j}$，有 $5^{5m-1}\equiv (g^{2j})^{\frac{p-1}{2}}\equiv (g^{p-1})^{j}\equiv 1\pmod{p}$

习题4.2.5

设 $n \geqslant 2, p=2^{n}+1$ 为素数. 证明：

$(1)$ 对每个 $a \in \mathbf{Z}, a$ 为模 $p$ 的原根当且仅当 $\left(\dfrac{a}{p}\right)=-1$;

$(2)$ 证明 $3$ 和 $7$ 均为模 $p$ 的原根.

证明：$(1)$ 若 $a$ 为模 $p$ 的原根，有 $(\dfrac{a}{p})=-1$；若 $(\dfrac{a}{p})=-1$，若 $a$ 不是模 $p$ 的原根，则对

$p-1=2^n$ 的因子为对应的阶，总有 $a^{2}\equiv 1\pmod{p}$，这与 $(\dfrac{a}{p})=-1$ 矛盾，从而 $a$ 是模 $p$ 的原根

$(2)$ 由于 $p=2^{n}+1$ 为素数，故 $n=2^{k}$ ，其中 $k \geq 1$.

由 $(\dfrac{3}{p})=(\dfrac{p}{3})(-1)^{1\cdot \frac{p-1}{2}}=(\dfrac{p}{3})$ ，而 $2^{2^n}+1\equiv (-1)^{2^n}+1\equiv 2\pmod{3}$

有 $(\dfrac{2}{3})=-1$，则 $(\dfrac{3}{p})=-1$，从而 $3$ 为模 $p$ 的原根；同理 $(\dfrac{7}{p})=(\dfrac{p}{7})$

若 $2^{k} \equiv 1(\bmod 3)$ ，则 $\left(\dfrac{2^{2^{k}}+1}{7}\right)=\left(\dfrac{\left(2^{3}\right)^{t} \cdot 2+1}{7}\right)=\left(\dfrac{3}{7}\right)=-\left(\dfrac{7}{3}\right)=-1$.

若 $2^{k} \equiv-1(\bmod 3)$ ，则 $\left(\dfrac{2^{2^{k}}+1}{7}\right)=\left(\dfrac{\left(2^{3}\right)^{t} \cdot 2^{2}+1}{7}\right)=\left(\dfrac{5}{7}\right)=\left(\dfrac{7}{5}\right)=\left(\dfrac{2}{5}\right)=(-1)^{\frac{5^{2}-1}{8}}=-1$.

因此 $\left(\dfrac{7}{p}\right)=-1$ ，故 $7$ 是模 $p$ 的原根.

$\large\textcolor{blue}{初等数论第八次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.4.23}$

习题4.2.2

确定以 $a$ 为二次剩余的素数, 其中 $a=-3,5$ 和 $15$ .

$a=-3$ 时，$2$ 满足题意，此外， $\dfrac{1}{2} \varphi(3)=1$. 且 $7$ 满足题意，则解为奇素数 $p=3 k+1$ 和 $2$

$a=5\equiv 1\pmod{4}$，$2$ 满足题意. 此外， $\dfrac{1}{2} \varphi(5)=2$ ，且 $11,19$ 均满足题意. 故 $2$ 和奇素数 $5 k \pm 1$ 满足题意.

$a=15$ 时， $2$ 满足题意. $\dfrac{1}{2} \varphi(60)=8$ ，且经过验证， $7,11,17,43,53,59,109,181$ 都满足.

解为 $2$ 和素数 $60 k+1,60 k+7,60 k+11,60 k+17,60 k+43,60 k+49,60 k+53,60 k+59$

习题4.2.3

设 $p=4 k+1$ 是素数, $a$ 是 $k$ 的因子, 证明: $\left(\dfrac{a}{p}\right)=1$.

证明：由二次互反律 $(\dfrac{a}{p})=(\dfrac{p}{a})(-1)^{\frac{p-1}{2}\frac{a-1}{2}}=(\dfrac{p}{a})=(\dfrac{4k+1}{a})=(\dfrac{4ax+1}{a})=(\dfrac{1}{a})=1$

习题4.2.6

$(1)$ 设 $n=2^{m} a+1$, 其中 $m \geqslant 2,1 \leqslant a<2^{m}$. 如果 $p$ 为奇素数, 并且 $\left(\dfrac{n}{p}\right)=-1$, 证明: $n$ 是素数当且仅当 $p^{\frac{n-1}{2}} \equiv-1(\bmod n)$.

$(2)$ 设 $n=2^{m}+1, m \geqslant 2$. 证明: $n$ 为素数当且仅当 $3^{\frac{n-1}{2}} \equiv-1$ $(\bmod n)$.

证明：$(1)$ 若 $n$ 为素数，由于 $n=2^ma+1$ 故 $\left(\dfrac{n}{p}\right)=\left(\dfrac{p}{n}\right)=-1$ ，故 $p^{\frac{n-1}{2}} \equiv-1(\bmod n)$.

另一方面，若 $p^ \frac{n-1}{2} \equiv-1(\bmod n)$ ，任取 $n$ 的一个素因子 $q ， q \geq 3$. 令 $d$ 为 $p$ 模 $q$ 的阶，由于

$p^{\frac{n-1}{2}} \equiv-1(\bmod q)$ ，故 $p^{2^{m-1} a} \equiv-1(\bmod q)$ ，因此 $2^{m}\mid d$ ，又 $d \mid q-1$ ，则 $2^{m} \mid q-1$

$q \geq 2^{m}+1$. 由于 $n=2^{m} a+1 ， a<2^{m}$ ，所以 $q^2>n$，这样的 $q$ 只能为 $n$ 本身，则 $n$ 为素数

$(2)$ 在 $\small(1)$ 中取 $a=1, p=3$ 当 $n$ 为素数时，满足 $m$ 为奇数，否则 $3$ 为 $n$ 的素因子，此时

$\left(\dfrac{2^{m}+1}{3}\right)=\left(\dfrac{2}{3}\right)=-1$ ，故满足 $\small(1)$ 的条件，则 $3^{\frac{n-1}{2}} \equiv-1$

若 $3^{\frac{n-1}{2}} \equiv-1$，由 $\small (1)$ 中的推导中没有使用到 $\left(\dfrac{n}{p}\right)=-1$ 条件知 $n$ 为素数

习题4.3.2

设 $f(x, y)$ 是关于 $x, y$ 的整系数多项式. $(x, y)=(a, b)$ 和 $(c, d)$ 均是同余方程

$f(x, y) \equiv 0(\bmod m)$ 的整数解, 即 $f(a, b) \equiv 0$ $(\bmod m), f(c, d) \equiv 0(\bmod m)$.

称这两组解为模 $m$ 的同一个解, 是指 $a \equiv c(\bmod m)$, 并且 $b \equiv d(\bmod m)$.

$(1)$ 设 $p$ 为奇素数, $a$ 为整数. 证明:同余方程 \[ x^{2}-y^{2} \equiv a \quad(\bmod p) \] 的模 $p$ 解数为 $p-1$ （若 $p\not\mid a$）或 $2 p-1$ （若 $p\mid a$）.

$(2)$ 证明： \[ \sum_{y=0}^{p-1}\left(\frac{y^{2}+a}{p}\right)= \begin{cases}-1, & \text { 若 } p \nmid a, \\ p-1, & \text { 若 } p \mid a .\end{cases} \]

证明：$(1)$ 当 $p \nmid a$ 时， $(x+y)(x-y) \equiv a(\bmod p)$. 设 $x+y \equiv b(\bmod p)$ ，其中 $(b, p)=1$.

则 $x-y \equiv a b^{-1}(\bmod p)$. 从而 $(x, y)=\left(\dfrac{b+a b^{-1}}{2}, \dfrac{b-a b^{-1}}{2}\right)$. 因此解数为 $b$ 的个数 $p-1$.

当 $p \mid a$ 时， $p \mid(x+y)(x-y)$ ，所以 $x \equiv y(\bmod p)$ 或 $x \equiv-y(\bmod p)$.

共有 $(0,0),(b,-b),(-b, b)$ 即 $2\cdotp(p-1)+1=2p-1$ 组解.

$(2)$ 设 $x^{2} \equiv y^{2}+a(\bmod p) .\left(\dfrac{y^{2}+a}{p}\right)=1$ 时，有两组解， $\left(\dfrac{y^{2}+a}{p}\right)=-1$ 时，无解

计算其总解数为 $\sum_{y=0}^{p-1}\left(1+\left(\frac{y^{2}+a}{p}\right)\right)=p+\sum_{y=0}^{p-1}\left(\frac{y^{2}+a}{p}\right)= \begin{cases}p-1, & p \nmid a \\ 2 p-1, & p \mid a\end{cases}$ 因此 $\sum_{y=0}^{p-1}\left(\frac{y^{2}+a}{p}\right)= \begin{cases}-1, & p \nmid a \\ p-1, & p \mid a\end{cases}$

习题4.3.3

设 $p$ 为奇素数, $a, b, c \in \mathbf{Z}, p \nmid a, D=b^{2}-4 a c$. 证明: \[ \sum_{x=0}^{p-1}\left(\frac{a x^{2}+b x+c}{p}\right)=\left\{\begin{array}{l} -\left(\dfrac{a}{p}\right), \quad \text { 若 } p \not\mid D, \\ (p-1)\left(\dfrac{a}{p}\right), \text { 若 } p \mid D . \end{array}\right. \]

证明：令 $y=x+\dfrac{b}{2a}=x+b\cdot 2^{-1}\cdot a^{-1},a^{\prime}=c-b^2\cdot 4^{-1}\cdot a^{-1}$ 代入上题结论得到 \[ \sum_{y=\frac{b}{2a}}^{\frac{b}{2a}+p-1}(\dfrac{ay^2+a'}{p})=\sum_{y=0}^{p-1}(\dfrac{ay^2+a'}{p})=(\dfrac{a}{p})\sum_{y=0}^{p-1}(\dfrac{y^2+a'a^{-1}}{p})=\left\{\begin{array}{l} -\left(\dfrac{a}{p}\right), \quad \text { 若 } p \not\mid D, \\ (p-1)\left(\dfrac{a}{p}\right), \text { 若 } p \mid D . \end{array}\right. \]

习题4.2.4

设 $a, b, c \in \mathbf{Z}, p \not\mid a b$, 则同余方程 \[ a x^{2}+b y^{2} \equiv c \quad(\bmod p) \] 模 $p$ 的解数为 \[ N=\left\{\begin{array}{l} p+(p-1)\left(\dfrac{-a b}{p}\right), \quad \text { 若 } p \mid c, \\ p-\left(\dfrac{-a b}{p}\right), \quad \text { 若 } p \not\mid c . \end{array}\right. \]

证明：$a x^{2}+b y^{2} \equiv c(\bmod p)$ 等价于 $x^{2} \equiv-a^{-1} b y^{2}+a^{-1} c(\bmod p) .$ $(a,p)=(b,p)=1$ 解数 \[ \sum_{y=0}^{p-1}\left(1+\left(\frac{-a^{-1} b y^{2}+a^{-1} c}{p}\right)\right)=p+\sum_{y=0}^{p-1}\left(\frac{-a^{-1} b}{p}\right)\left(\frac{y^{2}-c b^{-1}}{p}\right)\\ =p+\left(\frac{-a b}{p}\right) \sum_{y=0}^{p-1}\left(\frac{y^{2}-c b^{-1}}{p}\right)= \begin{cases}p+(p-1)\left(\dfrac{-a b}{p}\right), & p \mid c \\ p-\left(\dfrac{-a b}{p}\right), & p \nmid c\end{cases} \] 其中用到上题结论 $\displaystyle \sum_{x=0}^{p-1}\left(\frac{a x^{2}+b x+c}{p}\right)=\left\{\begin{array}{l} -\left(\dfrac{a}{p}\right), \quad \text { 若 } p \not\mid D, \\ (p-1)\left(\dfrac{a}{p}\right), \text { 若 } p \mid D . \end{array}\right.$

$\large\textcolor{blue}{初等数论第九次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.4.30}$

习题4.3.1

解下列同余方程:

$(1)$ $2 x^{2}+3 x+1 \equiv 0 \quad(\bmod 28)$;

$(2)$ $x^{2} \equiv-1 \quad(\bmod 169)$;

$(3)$ $x^{2} \equiv 2 \quad(\bmod 98)$;

$(4)$ $3 x^{2}+x+6 \equiv 0 \quad(\bmod 45)$.

解：$(1)$ $28 \mid(2 x+1)(x+1)$. 且有 $(2 x+1, x+1)=(1, x+1)=1$ 两者互素，且 $28=4\times 7$ 则

$2 x+1 \equiv 0(\bmod 4), x+1 \equiv 0(\bmod 7)$ 或者 $2 x+1 (), x+1 () $

又或者 $x+1\equiv 0\pmod{28}$ 解得 $x \equiv 3,27(\bmod 28)$.

$(2)$ $x^{2} \equiv-1(\bmod 13)$ 解得 $x=13 k+5,13 k+8$. 代入 $(13 k+5)^{2} \equiv-1(\bmod 169)$ 可以化简得

$10 k+2 \equiv 0(\bmod 13)$. 解得 $k \equiv 5(\bmod 13)$. $(13 k+8)^{2} \equiv-1(\bmod 169)$ 化简得: $3 k \equiv-5(\bmod 13)$

解得 $k \equiv 7(\bmod 13)$. 从而 $x \equiv 70,99(\bmod 169)$.

$(3)$ $x^{2} \equiv 2(\bmod 98)$ $x$ 为偶数. 设 $x=2 k$ ，则 $2 k^{2} \equiv 1(\bmod 49)$. 即 $k^{2} \equiv 25(\bmod 49)$. 考虑

$k^{2} \equiv 25(\bmod 7)$ ，解得 $k=7 m+2,7 m+5 .$ 分别代入 $k^{2} \equiv 25(\bmod 49)$ 解得

$k \equiv 44,5(\bmod 49)$. 因此 $x \equiv 10,88(\bmod 98) .$

$(4)$ $3 x^{2}+x+6 \equiv 0(\bmod 45)$. 两边模 $3$ 有 $x \equiv 0(\bmod 3)$. 令 $x=3 y$. 代入 $9 y^{2}+y+2 \equiv 0(\bmod 15) .$

模 $3$ 知， $y \equiv 1(\bmod 3)$. 设 $y=3 z+1$ ，代入可知 $2 z^{2}-z-1 \equiv 0(\bmod 5)$. $(2 z+1)(z-1) \equiv 0(\bmod 5)$.

解得 $z \equiv 1,2(\bmod 5)$. 从而 $x \equiv 12,21(\bmod 45)$.

习题5.1.1

求下列方程的全部整数解：

$(1)$ $2 x^{2}-5 y^{2}=7$; $(2)$ $x^{2}-2 x y^{2}+5 z^{3}+3=0$;

$(3)$ $y^{2}=41 x^{3}+3$; $(4)$ $x^{2}-x y+y^{2}-x-y=0$;

$(5)$ $y^{2}=x^{3}-6$ $\tiny\ $ $(6)$ $y^{2}=x^{3}-x$.

解：$(1)$ $x^{2} \equiv 0,1,2,4(\bmod 7) .$ 对原方程两边模 $7$ 知: $x^{2}+y^{2} \equiv 0(\bmod 7)$. 因此 $x \equiv y \equiv 0(\bmod 7)$.

两边模 $49$ 有 $0\equiv 7\pmod{49}$ 矛盾，从而无解

$(2)$ 方程两边模 $5$ 知 $x^{2}-2 x y^{2}+3 \equiv 0(\bmod 5)$ ，故 $\left(x-y^{2}\right)^{2} \equiv y^{4}-3(\bmod 5)$. 注意到

$x^{2} \equiv 0,1,-1(\bmod 5),x^{4} \equiv 0,1(\bmod 5)$ ，则 $y^4\equiv 2,3,4\pmod{5}$ 矛盾，从而无解

$(3)$ 两边模 $41$ 可知: $y^{2} \equiv 3(\bmod 41)$. 而 $\left(\dfrac{3}{41}\right)=\left(\dfrac{41}{3}\right)=\left(\dfrac{-1}{3}\right)=-1$ ，故没有整数解.

$(4)$ $x^{2}-x y+y^{2}-x-y=0$ 主元后 $x^2-(y+1)x+y^2-y=0$ 其判别式

$\Delta=\sqrt{(y+1)^2-4(y^2-y)}=\sqrt{-3y^2+6y+1}$ 为整数，则 $-3y^2+6y+1=t^2$

$3y^2-6y+(t^2-1)=0$ 其判别式 $\Delta =\sqrt{6^2-4\cdot 3\cdot (t^2-1)}=2\sqrt{3(4-t^2)}$ 也为完全平方数

从而 $3(4-t^2)$ 为完全平方数，可以得到 $t^2=1,4$ 解得 $y=0,1,2$ 回代解得

$(x,y)=(0,0),(0,1),(1,0),(1,2),(2,1),(2,2)$

$(5)$ 方程两边模 $8$. 注意到 $y^{2} \equiv 0,1,4(\bmod 8) ， x^{3} \equiv 0, \pm 1, \pm 3(\bmod 8)$ ，对比有 $x \equiv 7(\bmod 8)$.

$y^{2}-2=x^{3}-8=(x-2)\left(x^{2}+2 x+4\right)=(x-2)\left((x+1)^{2}+3\right)$. 其中 $(x+1)^{2}+3 \equiv 3(\bmod 8) .$

任取它的一个素因子 $p ， p$ 为奇数. $y^{2} \equiv 2(\bmod p)$. 因此 $1=\left(\dfrac{2}{p}\right)$ ，则 $p \equiv \pm 1(\bmod 8)$.

这与 $(x+1)^{2}+3 \equiv 3(\bmod 8)$ 矛盾，所以原方程没有整数解.

$(6)$ $y^{2}=x(x-1)(x+1)$ ，当 $x=0, \pm 1$ 时， $y=0$. $|x| \geq 2$ 时，若 $x$ 是偶数，$x, x+1, x-1$ 两两互素.

因此存在整数 $a, b$ 使得 $x=a^{2}, x+1=b^{2}$ ，即 $b^{2}-a^{2}=1$ ，其中 $b>a>1$. 显然这是无解的.

若 $x$ 是奇数，则 $\left(\dfrac{y}{2}\right)^{2}=x \cdot \dfrac{x+1}{2} \cdot \dfrac{x-1}{2}$. 其中 $x, \dfrac{x-1}{2}, \dfrac{x+1}{2}$ 两两互素，同理，存在整数 $a,b$ 使得

$a^2=\dfrac{x+1}{2},b^2=\dfrac{x-1}{2},a^2-b^2=1$ 故原方程的解为 $(0,0),(1,0),(-1,0)$.

$\large\textcolor{blue}{初等数论第十次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.5.8}$

习题5.2.1

求所有正整数 $m$ 和 $n$,使 $2^{m}+3^{n}$ 是完全平方.

解：由题设 $2^m+3^n=x^2$ 有 $2,3\not\mid x$ 方程两边模 $3$ 有 $(-1)^{m}\equiv x^2\equiv 1\pmod{3}$ 则 $m\equiv 0\pmod{2}$

$m\geq 2,2^{m}\geq 4,2^m\equiv 0\pmod{4}$，方程两边模 $4$ 有 $0+(-1)^{n}\equiv x^2\pmod{4}$ 而 $x^2\equiv 0,1\pmod{4}$

则 $n\equiv 0\pmod{2}$。令 $m=2k,n=2t$，原方程化为费马方程 $(2^k)^2+(3^t)^2=x^2$ 本原解满足 \[ 2^k=2mn,3^t=m^2-n^2 \] 且 $m,n$ 一奇一偶，而 $2^{k-1}=mn$ 则 $n=1,m=2^{k-1}$ 代入有 \[ 3^t=2^{2(k-1)}-1\Longrightarrow 3^t=(2^{k-1}+1)(2^{k-1}-1) \] 而 $(2^{k-1}-1,2^{k-1}+1)=1$，则 $2^{k-1}-1=1,k=2,t=1$ 则仅有唯一解 $m=4,n=2,2^4+3^2=5^2$

习题5.2.2

求不定方程 $3^{x}+4^{y}=5^{z}$ 的所有正整数解.

解：方程模 $3$ 有 $1\equiv 2^z\equiv (-1)^z\pmod{3}$ 得到 $z\equiv0\pmod{2}$。方程模 $4$ 有 $(-1)^x\equiv 1\pmod{5}$

则 $x\equiv 0\pmod{2}$，令 $x=2r,z=2k$，原方程化为费马方程 $(3^r)^2+(2^y)^2=(5^k)^2$ 本原解满足 \[ 2^y=2mn,3^r=m^2-n^2=(m-n)(m+n) \] 由 $2^{y-1}=mn$ 知 $m=2^s,n=2^t$。有 $(m+n)-(m-n)=2n=2^{t+1},3\not\mid 2^{t+1}$ 则 $m-n=1$

有 $2^s=2^t+1$，只有 $t=0,s=1$ 唯一解，回代得到唯一解 $(x,y,z)=(2,2,2)$

习题5.2.4

证明: $x^{4}+4 y^{4}=z^{2}$ 没有正整数解.

证明：假设有解 $(x,y,z)$ 若 $(x,y)>1$ 记素数 $p$ 为 $(x,y)$ 的一个约数，有 $p^4\mid x^4+4y^4=z^2$ 得到 $p^2\mid z$ 从而

$(\dfrac{x}{p},\dfrac{y}{p},\dfrac{z}{p^2})$ 为原方程的整数解，则有限步操作后总能使得 $(x,y)=1=(x^2,y^2)$ 若 $2\mid x$ 令 $x=2t$ 有 $2\not\mid y$

则 $16t^4+4y^4=z^2\Longrightarrow y^4+4t^4=(\dfrac{z}{2})^2$ 与原方程相同，且 $2\not\mid y$ ，总可以化为 $2\not\mid x$，有 $(x^2,2y^2)=1$

则 $x^2,2y^2,z$ 为费马方程的本原解。令 $z$ 为解中最小的，由 $2\mid 2y^2$ 可知，$m,n$ 一奇一偶，$(m,n)=1,m>n$ \[ x^2=m^2-n^2,2y^2=2mn,z^2=m^2+n^2 \] 有 $m^2=x^2+n^2$ 因为 $(m,n)=1$，则 $(x,n)=1$，$(x,n,m) $ 也为费马方程的本原解，由 $x$ 为奇数 \[ x=c^2-d^2,n=2cd,m=c^2+d^2,y^2=mn=2cd(c^2+d^2) \] 由 $2 \mid mn=y^2,2\mid y$，则 $\dfrac{cd(c^2+d^2)}{2}=(\dfrac{y}{2})^2$ 为完全平方数，设 $c,d$ 中偶数、奇数为 $s,t$

$\dfrac{st(s^2+t^2)}{2}=(\dfrac{y}{2})^2$ 也成立，令 $s=2k$ 有 $kt(4k^2+t^2)=(\dfrac{y}{2})^2$ 又 $(c,d)=1=(k,t)$ 三者为完全平方数

则 $k=a^2,t=b^2,4k^2+t^2=c^2$ 消元有 $b^4+4a^4=c^2$ 而 $c^2=m-d^2<m=\sqrt{z^2-n^2}<z<z^2$

与假设最小矛盾，从而原方程无解

习题5.2.6

证明: $1$ 不是同余数, 即不存在面积为 $1 、$ 三边长为有理数的直角三角形.

证明：原问题等价于满足 $a^2+b^2=c^2,ab=2d^2$ 的正整数解不存在，假设存在有若 $(a,b)=2$，则

$2\mid c,4\mid ab=2d^2,2\mid d$，从而 $(\dfrac{a}{2},\dfrac{b}{2},\dfrac{c}{2},\dfrac{d}{2})$ 也为解，若 $(a,b)=p\geq 3$ 则 $p^2 \mid c^2,d^2$ 同理

$(\dfrac{a}{p},\dfrac{b}{p},\dfrac{c}{p},\dfrac{d}{p})$ 也为解，在有限步之后，总能使得 $(a,b)=1$，满足费马方程，$a,b$ 一奇一偶，不妨设 $a=2k$

有 $bk=d^2,(b,k)=1$ 则 $b=x^2,k=y^2$ 代入 $a^2+b^2=c^2$ 有 $4y^4+x^4=c^2$，由上题知该方程无解

习题5.3.1

证明: 形如 $4^{a}(8 k+7)$ 的正整数不能表为三个整数的平方和.

证明：由 $x^2\equiv 0,1,4\pmod{8}$ 计算 $a^2+b^2+c^2\equiv 0,1,2,3,4,5,6\not\equiv 7\pmod{8}$ 从而 $8k+7$ 的正整数

不能表示为三个整数平方和。对 $4(8k+7)=a^2+b^2+c^2$ 有 $x^2\equiv 0,1\pmod{4}$，而三者之和模 $0$，则

$a^2\equiv b^2\equiv c^2\pmod{4}$，有 $a,b,c\equiv 0\pmod{2}$，则可以转化为 $a'^2+b'^2+c'^2=8k+7$ 的情况

从而 $4^a(8k+7)$ 均与 $8k+7$ 等价，从而不能表示为三个整数的平方和

习题5.3.2

$(1)$ 确定哪些整数可表为两个整数的平方差.

$(2)$ 证明: 对任意整数 $n$, 不定方程 \[ x^{2}+y^{2}-z^{2}=n \] 均有无穷多组正整数解.

解：$(1)$ $z=x^2-y^2=(x+y)(x-y)$，而 $(x+y)-(x-y)=2y$ 从而 $z\equiv 0,1,3\pmod{4}$

而只要 $z\not\equiv 2\pmod{4}$，分三种情况 $z=4k=2\cdot 2k,z=4k+1=1\cdot(4k+1),z=4k+3=1\cdot (4k+3)$

三种情况都对应有 $x,y$ 解，从而当且仅当 $z\not\equiv 2\pmod{4}$ 时该整数可以表示为两个整数的平方差

$(2)$ 由 $y^2-z^2=n-x^2$ 且上问给出只要 $n-x^2\not \equiv 2\pmod{4}$，就一定有解，而 $x^2\equiv 0,1\pmod{4}$

对 $n\equiv 0,1,2,3\pmod{4}$，所有情况都有 $x^2\equiv 0,0,1,0\pmod{4}$ 使得 $n-x^2\not \equiv 2\pmod{4}$ 成立

而满足上述条件的 $x$ 有无穷多个，从而对应解 $(x,y,z)$ 也有无穷多个

习题5.3.3

证明: 对任意给定的 $n \geqslant 1$, 均存在连续 $n$ 个正整数, 其中每个都不是两个整数的平方和.

证明：取 $4k+3$ 型素数 $n$ 个，存在正整数 $N$ 使得 \[ N=-i+p_{i}\left(\bmod p_{i}^{2}\right) \quad(1 \leqslant i \leqslant n) \] 从而 $N+i(1\leq i\leq n)$ 分解后 $p_i$ 的幂次为 $1$，从而不能写成两个整数平方和，则 $N+1,\cdots,N+n$ 为所求

$\large\textcolor{blue}{初等数论第十一次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.5.11}$

1

设 $F$ 是一个域, $f(x), g(x) \in F[x]$ 。

$(1)$ 证明存在多项式 $q(x), r(x) \in F[x]$ 使得 $f(x)=g(x) q(x)+r(x)$ 且 $r(x)$ 的次数严格小于 $g(x)$;

$(2)$ 设 $h(x)=(f(x), g(x))$ 是首项系数为 1 的最大公因式, 则存在 $p(x), q(x) \in F(x)$ 使得 \[ f(x) p(x)+g(x) q(x)=h(x) \] $(3)$ 设 $f(x) \in F_{p}[x]$ 且 $g(x)$ 是模 $f(x)$ 的一个缩同余类。则存在 $h(x)$ 使得 $g(x) h(x) \equiv 1$ $(\bmod f(x))$ 。

证明：$(1)$ 设 $f(x),g(x)$ 最高幂次为 $x^{n_1},x^{n_2}$，且系数分别为 $a,b$，不妨设 $n_1\geq n_2$，由非零元素存在乘法逆元

构造 $h(x)=ab^{-1}x^{n_1-n_2}$，有 $ax^{n_1}-bx^{n_2}\cdot ab^{-1}x^{n_1-n_2}=0$，则 $f(x)-h(x)g(x)$ 首项系数被消去。如此

新的最高幂次不超过 $n_1-1$，执行上述操作 $n_1-n_2+1$ 之后，总能得到 $h_{tot}(x)=\displaystyle \sum_{i=1}^{n_1-n_2+1}h_{i}(x)$

使得 $f(x)-g(x)h(x)$ 的最高次数严格小于 $g(x)$

$(2)$ 由 $\small(1)$ 中可知，实际上给出了域上的多项式有带余除法，使用辗转相除法 \[ f(x)=g(x)q_1(x)+f_1(x),g(x)=f_1(x)q_2(x)+g_1(x),\cdots \] 最终得到 $f_N(x),g_{N-1}(x)=ah(x)$，从而 $h(x)=a^{-1}f_{N}(x)$，一直回代，每次保证为线性组合

从而有限次数之后总能找到 $f(x)q(x)+g(x)p(x)=h(x)$

$(3)$ 由 $\small(2)$ 可以得到，当 $(f(x),g(x))=1$ 时，存在 $p(x),h(x)$ 使得 $f(x)p(x)+g(x)h(x)=1$，从而 \[ g(x)q(x)\equiv 1\pmod{f(x)} \]

2

证明 $\left(x^{a}-1, x^{b}-1\right)=\left(x^{(a, b)}-1\right)$ 。特别的, $\left(x^{a^{m}-1}-1, x^{a^{n}-1}-1\right)=x^{a^{(m, n)}}-1$ 。

证明：不妨设 $a\geq b$，$(x^a-1,x^b-1)=(x^b-1,x^a-x^b)=(x^b-1,x^b(x^{a-b}-1))$

而 $(x^b-1,x^b)=(1,x^b)=1$，则 $(x^a-1,x^b-1)=(x^{a-b}-1,x^b-1)$ 相当于指数项可以相互加减

则类比辗转相除法，经过有限步辗转相除后 $(x^a-1,x^b-1)=(x^{(a,b)}-1,x^{\lambda(a,b)}-1)=x^{(a,b)}-1$

3

设 $f(x) \in F_{p}[x]$ 。

$(1)$ 证明 $f(x)^{p}=f\left(x^{p}\right)$;

$(2)$ 证明 $f(x)$ 的导函数为 $0$ 当且仅当存在 $g(x) \in F_{p}[x]$ 使得 $f(x)=g\left(x^{p}\right)$ 。

$(1)$ 由费马小定理 $f(x)^p=\displaystyle (\sum_{i=0}^{n-1}a_ix^i)^{p}=\sum_{i=0}^{n-1}a_i^px^{ip}+pg(x)=\sum_{i=0}^{n-1}a_i^{p-1}a_i(x^{p})^i=\sum_{i=0}^{n-1}a_i(x^p)^{i}=f(x^p)$

$(2)$ 由 $f(x)=\displaystyle \sum_{i=0}^{n-1}a_ix^i,f'(x)=\sum_{i=1}^{n-1}ia_ix^{i-1}=0$ 从而存在数论倒数的 $p\not\mid j$，$ja_jx^{j-1}=0\Longrightarrow a_j=0$

从而剩下 $p\mid i$，使得 $a_i$ 不一定为 $0$，则 $f(x)=\displaystyle \sum_{p\mid i}a_ix^i=g(x^{p})$

4

证明 $F:=\left\{a+b i \mid a, b \in \mathbb{Z}_{5}\right\}$ 不是一个域。

证明：假设 $F$ 为一个域，由域有乘法逆元，考虑 $1+2i$ 的逆，在 $F$ 中设为 $a+bi$，显然 $F$ 的乘法单位元为 $1$，

故 $(1+2i)(a+bi)\equiv 1\pmod{5}$，整理为 $a\equiv 2b+1\pmod{5},2a\equiv -b\pmod{5}$，得 $0\equiv 1\pmod{5}$ ，矛盾

$\large\textcolor{blue}{初等数论第十二次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.5.21}$

柯召7.22

求出 $F_{2}$ 上的全部四次不可约多项式.

解：计算 $\Phi_{2}(4)=\dfrac{1}{4}(\mu(1)2^4+\mu(2)2^2+\mu(4)2^1)=3 \text {. }$从而共有 $3$ 个四次不可约多项式， $F_2$ 上，有

一次不可约多项式为 $x, x+1$. 有 $x^2\equiv x\pmod{2}$ 从而当且仅当 $f(x)$ 的非零系数有偶数个时都不是不可约多项式（验证）

$F_{2}$ 上的多项式 $f(x)$ 被 $x$ 整除当且仅当 $f(0)=0$ 从而排除掉上述情况有 $\mathrm{F}_{2}$ 上的不含有一次因子的四次多项式 \[ x^{4}+x^{3}+x^{2}+x+1, x^{4}+x^{3}+1, x^{4}+x^{2}+1, x^{4}+x+1 \] 而 $x^{4}+x^{2}+1=\left(x^{2}+x+1\right)^{2}$ 可约，则该多项式排除，则 $F_{2}$ 上的全部四次不可约多项式为 \[ x^{4}+x^{3}+x^{2}+x+1, x^{4}+x^{3}+1, x^{4}+x+1 \]

柯召7.23

证明：若 $p \neq q$ 是两个奇素数, 则 $F_{p}$ 上首项系数为 $1$ 的 $q$ 次不可约多项式的个数为 $\dfrac{p^{q}-p}{q}$.

证明：由 $\Phi_{p}(q)=\displaystyle \frac{1}{q} \sum_{l \mid q} \mu(l) p^{\frac{q}{l}}=\dfrac{1}{q}(1\cdot p^q+(-1)\cdot p)=\dfrac{p^q-p}{q}$

柯召7.27

证明: 若 $\left(r, p^{n}-1\right)=1$, 则 $F_{p^{n}}$ 中任一个元 $\alpha$ 是 $F_{p^n}$ 中的 $r$ 次幂元，若 $r \mid p^n-1$，则 $\alpha$ 是 $F_{p^n}$ 中的 $r$ 次幂元

的充分必要条件是 $\alpha^{\frac{p^n-1}{r}}=1$

证明：若 $\left(r, p^{n}-1\right)=1$ ，则 $r$ 存在数论倒数 $r^{-1}$。取 $F_{p}[x]$ 中的一个 $n$ 次不可约多项式，取模 $f$ 的原根 $g$.

则对任意的 $\alpha \in F_{p^{n}}$ ，都存在整数 $s$ ，使得 $\alpha \equiv g^{s}(\bmod f)$. 令 $t=s r^{-1}$ ，则 $\left(g^{t}\right)^{r} \equiv g^{s} \equiv \alpha(\bmod f)$

从而 $\alpha$ 是 $r$ 次幂元

若 $r\mid p^n-1$，$\Longrightarrow:$ $\alpha=\beta^r,\alpha^{\frac{p^n-1}{r}}=\beta^{p^n-1}\equiv 1\pmod{f}$ $\Longleftarrow:$ 设 $\alpha=g^s$ 代入有 \[ \alpha^{\frac{p^n-1}{r}}=1=g^{\frac{s(p^n-1)}{r}}\equiv 1\pmod{f} \] 由原根的性质可得 $r\mid s$ 从而 $\alpha$ 为 $r$ 次幂元

柯召7.28

证明：设 $\alpha_{1}, \cdots, \alpha_{p^{n}-1}$ 是 $F_{p^{n}}$ 中的全体非蕶元, 则 \[ \alpha_{1} \cdots \alpha_{p^{n}-1}=-1 \text {. } \]

证明：类比威尔逊定理的证明，取 $F_{p}[x]$ 中的一个 $n$ 次不可约多项式，然后取其原根 $g$ 则 \[ \alpha_{1} \cdots \alpha_{p^{n}-1} \equiv g^{1+2+\cdots+\left(p^{n}-1\right)} \equiv\left(g^{\frac{p^{n}-1}{2}}\right)^{p^{n}} \equiv(-1)^{p^{n}} \equiv-1(\bmod f) \] 其中 $g^{\frac{p^n-1}{2}}\equiv -1\pmod{p^n-1}$ 为原根的性质

特殊情况，考虑 $p=2$ 有 $(-1)^{p^n}\equiv 1\equiv -1\pmod{f}$ 从而对所有素数成立

柯召7.32

证明：若 $F_{p}$ 上 $n$ 次不可约多项式的周期为 $l$, 则 $p$ 模 $l$ 的次数为 $n$.

证明：由原根的性质可知，$l\mid p^n-1$，令 $p^x\equiv 1\pmod{l}$ 显然次数 $r$ 满足 $r\mid n$，

于是 $f \mid x^{p^{r}}-x$ ，但 $f$ 是 $n$ 次的，故 $n \leq r$. 于是 $r=n$ ，即 $p$ 模 $l$ 的次数为 $n$.

$\large\textcolor{blue}{初等数论第十三次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.5.28}$

柯召7.34

分别求出 $F_{2}$ 上多项式 $f(x)=(x+1)\left(x^{3}+x+1\right)\left(x^{3}+x^{2}+1\right)$ 和 $g(x) = (x^2+x+1)$

$\left(x^{4}+x+1\right)^{3}$ 的周期.

解：由定理可知周期等于 $[l_1,\cdots,l_n]e,e=\{2^r:r\in Z,r\geq 0,2^r\geq 1(f(x)),3(g(x))\}=1,4$，求 $l_i$

由 $x+1\mid x-1$ 最小正整数为 $1$，则对 $f(x)$ 中 $(x+1)$ 的周期为 $1$，对 $(x^3+x+1)$ 和 $(x^3+x^2+1)$

均为不可约多项式，且 $2^3-1=7$ 为素数，从而两者周期均为 $7$，故 $f(x)$ 周期为 $[1,7,7]\cdot 1=7$

$x^2-1=3$ 为素数，且 $x^2+x+1$ 为不可约多项式，则其周期为 $3$

对 $(x^4+x+1)$ 有 $2^4-1=15$ 为合数，而分别计算 $x^5,x31 $ \[ \begin{gathered} x^5=x\cdot x^4\equiv x(-x-1)\equiv -x^2-x\equiv -x(x+1)\not \equiv 1\pmod{x^4+x+1}\\ x^3\not\equiv1\pmod{x^4+x+1} \end{gathered} \]

故 $15$ 为 $x^4+x+1$ 的周期，$g(x)$ 周期为 $[3,15]\cdot 4=60$，故 $f(x)$ 和 $g(x)$ 的周期为 $7$ 和 $60$

柯召7.36

求 $F_{2}$ 上多项式 $x^{2 \cdot 3^{k}}+x^{3^{k}}+1$ 的周期, 并证明它是不可约的。

解：由立方差公式 $x^{3\cdot 3^{k}}-1=(x^{2 \cdot 3^{k}}+x^{3^{k}}+1)(x^{3^{k}}-1)$ 则 $x^{2 \cdot 3^{k}}+x^{3^{k}}+1\mid x^{3^{k+1}}-1$ 令其周期为 $r$

有 $r\mid 3^{k+1}$，而考虑 $x^{2 \cdot 3^{k}}+x^{3^{k}}+1\mid x^r-1$ 的最高次项，$r\geq 2\cdot 3^k$，故 $r=3^{k+1}$

假设该多项式不可约，则其能被分解为若干个不可约多项式之积，由不可约多项式周期相关定理有 \[ 3^{k+1}=[l_1,l_2,\cdots,l_n]e \] 由 $e=2^r$ 则 $e=1,\exists\ s\in[1,n],s.t.l_s=3^{k+1}$ 令该不可约多项式为 $p(x)$ 令其最高幂次项为 $n$，有 \[ 3^{k+1}\mid 2^n-1 \] 两边模 $3$ 有 $(-1)^n\equiv 1\pmod{3}$，则 $n\equiv 0\pmod{2}$，取 $n=2t$ 代入有 $3^{k+1}\mid 4^t-1$

将其展开 $4^t-1=(1+3)^t-1$ 其中 $3$ 的最小幂次为 $k+1$ 则 $3^{k+1}\mid 3t,3^k\mid t$ 则 $n=2t\geq 2\cdot 3^k$

恰为 $f(x)$ 的最高幂次，从而该多项式即为其本身，故其不可约

柯召8.16

设 $p$ 是一个奇素数, $d=(m, p-1)$, 证明: $N\left(x^{m}=a\right)=N\left(x^{d}=a\right)$.

证明：当 $x^d\equiv a\pmod{p}$ 无解时，$x^m\equiv a\pmod{p}$ 也无解（否则 $(x^{\frac{m}{d}})^d$ 为前者的解）

又当 $x^d\equiv a\pmod{p}$ 有解时，其解有 $d$ 个，设为 $x_1,\cdots,x_d$ ，又注意到 $(\dfrac{m}{d},p-1)=1$ 则有

$p-1$ 的完系均为 $\dfrac{m}{d}$ 次剩余，则 $x^m\equiv a\pmod{p}$ 等价于 $x^{\frac{m}{d}}\equiv x_i\pmod{p}$ ，每个方程都只有一解

（取 $p$ 的原根 $g$，有 $\dfrac{m}{d}\mbox{ind}_gx\equiv \mbox{ind}_gx_i\pmod{p-1}$ 则只有一解）故两者解为 $d$ 个

柯召8.21

证明：若 $k \mid p-1, \chi$ 是 $F_{p}$ 上一个 $k$ 阶特征, 则 \[ \sum_{j=0}^{k-1} \chi^{j}(-1)=\left\{\begin{array}{l} k, \quad \text { 当 }\left(\dfrac{-1}{p}\right)_{k}=1 \text { 时, } \\ 0 , \quad \text { 当 }\left(\dfrac{-1}{p}\right)_{k}\neq 1 \text { 时. } \end{array}\right. \]

证明：由定理可知，$\displaystyle \sum_{j=0}^{k-1} \chi^{j}(-1)=N(x^k=-1)$，则当 $(\dfrac{-1}{p})_k=1$ 时，显然该方程有 $k$ 个解，当 $(\dfrac{-1}{p})_k=1$ 时，该方程无解，故 $\sum_{j=0}^{k-1} \chi^{j}(-1)=\left\{\begin{array}{l} k, \quad \text { 当 }\left(\dfrac{-1}{p}\right)_{k}=1 \text { 时, } \\ 0 , \quad \text { 当 }\left(\dfrac{-1}{p}\right)_{k}\neq 1 \text { 时. } \end{array}\right.$

$\large\textcolor{blue}{初等数论第十四次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.6.2}$

阶以及雅可比和

设 $\chi \neq \chi_{0}$ 是 $F_{p}$ 上的一个特征。设 $\rho(a)=\left(\dfrac{a}{p}\right)$ 是唯一的 $2$ 阶特征。设 $p \neq 2$ 。

$(1)$ 证明 \[ \sum_{t \in F_{p}} \chi\left(1-t^{2}\right)=J(\chi, \rho) \] $(2)$ 设 $0 \neq k \in F_{p}$ 。证明 \[ \sum_{t \in F_{p}} \chi(t(k-t))=\frac{\chi\left(k^{2}\right)}{\chi\left(2^{2}\right)} J(\chi, \rho) \] (提示：利用 $(1)$ )

$(3)$ 证明 $J(\chi, \chi)=\chi(2)^{-2} J(\chi, \rho)$; (提示：利用 $(2)$)

$(4)$ 设 $\chi^{2} \neq \chi_{0}$ 。证明 $g_{1}(\chi)^{2}=\chi(2)^{-2} J(\chi, \rho) g_{1}\left(\chi^{2}\right)$;

$(5)$ 设 $p \equiv 1(\bmod 3)$ 且 $\chi$ 是一个 $3$ 阶特征。证明 $g_1(\chi)^{3}=p \cdot \chi(2) J(\chi, \rho)$;

$(6)$ 设 $p \equiv 1(\bmod 4)$ 且 $\chi$ 是一个 $4$ 阶特征。证明 $\chi^{2}=\rho$ 且 $J(\chi, \chi)=\chi(-1) J(\chi, \rho)$ 。

(提示: 证明 $\chi(-1)=(\dfrac{2}{p})$)

解：$(1)$ 由雅可比定义，代入 $\left(\dfrac{a}{p}\right)=N(x^2=a)-1$ 有 \[ \begin{gathered} J(\chi,\rho)=\displaystyle \sum_{t\in F_p}\chi(1-t)\rho(t)=\sum_{t\in F_p}\chi(1-t)(N(x^2=t)-1)\\ =\sum_{t\in F_p}\chi(1-t)N(x^2=t)-\sum_{t\in F_p}\chi(1-t) =\sum_{t\in F_p}\chi(1-t)N(x^2=t) \end{gathered} \] 而 $N(x^2=t)$ 对求和有贡献的有两类，当 $N(x^2=t)=1$ 时 $t=0$，当 $N(x^2=t)=2$ 时，$t$ 为二次剩余 \[ J(\chi,\rho)=\chi(1-0)\cdot 1+2\cdot \sum_{(\frac{t}{p})=1}\chi(1-t) \] 而对每一个二次剩余 $t=b^2$，且 $\chi(1-b^2)$ 中 $\pm b$ 对应同一个 $t$，且保证所有的 $b$ 不同，构成 $F_p$ 中所有非零元素 \[ J(\chi,\rho)=1+2\cdot \sum_{b\in F_p,b\neq 0}\chi(1-b^2)=\sum_{t \in F_{p}} \chi\left(1-t^{2}\right) \] $(2)$ 由 $(2,p)=1$ 以及 $(k,p)=1$，则 $\{2t\ |\ t\in F_p\}$ 和 $\{kt\ |\ t\in F_p\}$ 构成 $F_p$ 中的完系，则 \[ \begin{gathered} \chi(k)^2\sum_{t\in F_p}\chi(1+t)\chi (1-t)=\sum_{t\in F_p}\chi(k+kt)\chi (k-kt)=\chi(k)^2\sum_{t\in F_p}\chi(1-t^2)=\sum_{t\in F_p}\chi(k+t)\chi (k-t)\\=\sum_{t\in F_p}\chi(t)\chi (2k-t) =\sum_{t\in F_p}\chi(2t)\chi (2k-2t)=\chi(2)^2\sum_{t\in F_p}\chi(t)\chi (k-t) \end{gathered} \] 代入 $\small (1)$ 中结论 $\displaystyle \sum_{t \in F_{p}} \chi\left(1-t^{2}\right)=J(\chi, \rho)$ 则得到 $\displaystyle \sum_{t \in F_{p}} \chi(t(k-t))=\frac{\chi\left(k^{2}\right)}{\chi\left(2^{2}\right)} J(\chi, \rho)$

$(3)$ 取 $k=1$ 有 $\displaystyle \sum_{t \in F_{p}} \chi(t(1-t))=\frac{\chi\left(1^2\right)}{\chi\left(2^{2}\right)} J(\chi, \rho)=\sum_{t \in F_{p}}\chi(t)\chi(1-t)=J(\chi,\chi)$

而 $\chi(1)=1$，代入得 $J(\chi, \chi)=\chi(2)^{-2} J(\chi, \rho)$

$(4)$ 由雅可比和与高斯和之间的关系有 $J(\chi,\chi)=\dfrac{g_1(\chi)\cdot g_1(\chi )}{g_1(\chi ^2)}=\chi(2)^{-2} J(\chi, \rho)$

移项整理得到 $g_{1}(\chi)^{2}=\chi(2)^{-2} J(\chi, \rho) g_{1}\left(\chi^{2}\right)$

$(5)$ 在 $\small(4)$ 等式左右乘以 $g_1(\chi)$ 可以得到 $g_{1}(\chi)^{3}=\chi(2)^{-2} J(\chi, \rho) g_{1}\left(\chi^{2}\right)g_1(\chi)$，而由于 $\chi$ 为 $3$ 阶特征

则 $\chi(2)^3=1$ 则 $g_{1}(\chi)^{3}=\chi(2) J(\chi, \rho) g_{1}\left(\chi^{2}\right)g_1(\chi)$ 由于 \[ \overline{g(\chi)}=\sum_{t} \overline{\chi(t)} \zeta^{-t}=\chi(-1) \sum_{t} \overline{\chi(-t)} \zeta(-t)=\chi(-1) g(\chi) \] 有 $\chi(-1)^3=1$ 且 $\chi(-1)^2=\chi(1)=1$，故 $\chi(-1)=1$，代入有 \[ g\left(\chi^{2}\right) g(\chi)=g(\bar{\chi}) g(\chi)=\overline{g(\chi)} g(\chi)=|g(\chi)|^{2}=p \] 则 $g_1(\chi)^{3}=p \cdot \chi(2) J(\chi, \rho)$

$(6)$ 由于 $\chi$ 的阶为 $4$，则 $\chi^2$ 的阶为 $2$，而 $\rho$ 为唯一的二阶特征，故 $\chi ^2=\rho$，由高斯和与雅可比和之间关系 \[ g(\chi)^{4}=\chi(-1) p J(\chi, \chi) J\left(\chi, \chi^{2}\right)=\chi(-1) p J(\chi, \chi) J(\chi, \rho) \] 又对 $\small(4)$ 中的等式两边平方得到 \[ g(\chi)^{4}=\chi(2)^{-4} J(\chi, \rho)^{2}\left[g\left(\chi^{2}\right)\right]^{2} \] 而由 $4$ 阶特征可以得到 $\chi\left(2^{4}\right)=\chi^{4}(2)=\chi_0(2)=1$, and $g\left(\chi^{2}\right)=g(\rho)=g$, so $\left[g\left(\chi^{2}\right)\right]^{2}=g^{2}$ ，而有 \[ g_{a} g_{-a}=(\dfrac{a}{p})(\dfrac{-a}{p}) g^{2}=(\dfrac{-1}{p}) g^{2}\Longrightarrow\sum_{a} g_{a} g_{-a}=\left(\frac{-1}{p}\right)(p-1) g^{2} \] 而使用另一种方法计算左边有 \[ g_{a} g_{-a}=\sum_{x} \sum_{y}\left(\frac{x}{p}\right)\left(\frac{y}{p}\right) \zeta^{a(x-y)}=\sum_{x} \sum_{y}\left(\frac{x}{p}\right)\left(\frac{y}{p}\right) \delta(x, y) p=(p-1) p \] 两式对比有 $g^{2}=(\dfrac{-1}{p})p$ 由于 $p\equiv 1\pmod{4}$ 则 $(\dfrac{-1}{p})=1$ 则 $g^2=p$，则有 \[ \chi(-1) p J(\chi, \chi) J(\chi, \rho)=J(\chi, \rho)^{2} p \] 由于 $g(\chi)^{4} \neq 0$ 以及 $|g(\chi)|^{2}=p$，有 $J(\chi, \rho) \neq 0$, 则两边约去 $pJ(\chi,\rho)$ 有 \[ \chi(-1) J(\chi, \chi)=J(\chi, \rho) \] $[\chi(-1)]^{2}=\chi\left((-1)^{2}\right)=\chi(1)=1$, 故 $\chi(-1)=\pm 1$, 从而 $\chi(-1)^{-1}=\chi(-1)$, 移项得到 \[ J(\chi, \chi)=\chi(-1) J(\chi, \rho) \]

$\large\textcolor{blue}{初等数论第十五次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.6.12}$

雅可比和以及加密解密

设 $p$ 是一个奇素数, 计算

$(1)$ $N\left(x^{3}-y^{3}=1\right), p=37$;

$(2)$ $N\left(9 x^{2}+8 y^{2}=a\right), p=17, a \in F_{17}^{*}$ 。
使用加密密钥 $E(x) \equiv x+3(\bmod 26)$ 将信息 “mathematics” 加密.
已知加密密钥 $E(x) \equiv x+5(\bmod 26)$ 。将信息 "lttijajsnsl" 解密.
假设加密密钥 $E(x) \equiv 3 x+1(\bmod 26)$, 求去密密钥 $D(y)$, 并将信息 “EBOBO BEBOK" 解密。

1、解：$(1)$ 计算 $M(x^3+(-y)^3=1)=\displaystyle \sum_{i=0}^2\sum_{j=0}^2\chi ^i(a)\chi^j(1-a)=p+J(\chi,\chi)+J(\chi^2,\chi^2)-2\chi(-1)$

$=p-2+J(\chi,\chi)+J(\chi^2,\chi^2)=p-2+J(\chi,\chi)+\overline{J(\chi,\chi)}$ 令 $J(\chi,\chi)=a+b\omega,\omega=-\dfrac{1}{2}+\dfrac{\sqrt{3}}{2}i$

得到 $p-2+2a-b$，由分解定理 $4p=(2a-b)^2+27(\dfrac{b}{3})^2=148=11^2+27\cdot 1\Longrightarrow a=7,b=3$ 要求 $2a-b\equiv 1\pmod{3}$

则 $2a-b=-11$ $N(x^3-y^3=1)=37-2+(-11)=24$

$(2)$ 由 $p=17$ 得 $N(9x^2+8y^2=a)=N(9(x^2-y^2)=a)$ 而 $\{3x\}$ 与 $\{x\}$ 均取遍所有 $F_{p}^*$，故化解为 $N(x^2-y^2=a)$

由 $(\dfrac{-1}{p})=(-1)^{\frac{p-1}{2}}=1$ 知 $-1$ 为二次剩余，从而 $-y^2=(a_0)^2(y)^2=(a_0y)^2$ 又可化解为 $N(x^2+y^2=a)$ \[ \begin{gathered} N(x^2+y^2=a)=\displaystyle \sum_{i=0}^1\sum_{j=0}^1\chi ^i(t)\chi^j(a-t)=p+J(\chi,\chi_0)+J(\chi_0,\chi)+J(\chi,\chi)\\ =p-\chi(-1)=p+\sum_{c\in F_p}\chi(\dfrac{c}{a-c}) \end{gathered} \] 而 $\dfrac{c}{a-c}=t\Longrightarrow c=\dfrac{at}{t+1}$ 只有 $t=-1$ 元素没有遍历，从而 $\displaystyle \sum_{c\in F_p}\chi(\dfrac{c}{a-c})=0-\chi(-1)=-1$

故原方程有 $17+(-1)=16$ 个解

2、使用 $\mbox{python}$ 编程计算，代码如下，加密结果为 $\mathbf{pdwkhpdwlfv}$

charList = "abcdefghijklmnopqrstuvwxyz"
word = "mathematics"
for i in word:
    print(charList[(ord(i) - ord("a") + 3) % 26], end = "")

3、只需改动一行代码，解密结果为 $\mathbf{goodevening}$

1	`print(charList[(ord(i) - ord("a") - 5) % 26], end = "")`

4、反解同余方程得 $x\equiv 9\cdot (y-1)\equiv 9y+17\pmod{26}$，代码如下，解密结果为 $\mathbf{BANAN\ \ ABAND}$

1	`print(charList[(9 * (ord(i) - ord("A")) + 17) % 26], end = "`

数学 > 初等数论

#初等数论

Elementary number theory homework 1-15

https://lr-tsinghua11.github.io/2022/06/17/%E6%95%B0%E5%AD%A6/%E5%88%9D%E7%AD%89%E6%95%B0%E8%AE%BA%E4%BD%9C%E4%B8%9A%E5%90%88%E9%9B%86%EF%BC%881-15%EF%BC%89/

作者

Learning_rate

发布于

2022年6月17日

许可协议

Calculus-A2-homework all 上一篇

The Saltwater Room 下一篇

Elementary number theory homework 1-15

\(\large\textcolor{blue}{初等数论第一次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.2.22}\)

习题 1.1.1

习题1.1.2

习题1.1.3

习题1.1.4

习题1.1.5

习题1.1.11

习题1.1.12

习题1.2.1

习题1.2.2

习题1.2.3

\(\large\textcolor{blue}{初等数论第二次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.3.2}\)

习题1.2.4

习题1.2.5

习题1.2.6

习题1.29

习题1.2.10

习题1.2.12

习题1.2.13

习题1.2.16

习题1.3.3

习题1.3.4

\(\large\textcolor{blue}{初等数论第三次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.3.8}\)

习题1.2.1

习题1.2.2

习题1.2.6

习题1.2.7

习题1.2.10

习题2.2.1

习题2.2.2

习题2.2.3

习题2.2.4

习题2.2.5

习题2.3.1

习题2.3.2

习题2.3.3

\(\large\textcolor{blue}{初等数论第四次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.3.15}\)

习题2.1.3

习题2.1.4

习题2.1.5

习题2.4.1

习题2.4.2

习题2.4.3

习题2.4.4

习题2.4.5

习题2.4.6

习题2.4.7

\(\large\textcolor{blue}{初等数论第五次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.3.22}\)

习题3.1.2

习题3.1.5

习题3.1.6

习题3.1.7

习题3.1.8

习题3.1.9

柯召讲义5.1

柯召讲义5.2

\(\large\textcolor{blue}{初等数论第六次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.4.1}\)

习题3.1.1

习题3.1.4

习题3.2.1

习题3.2.2

习题3.2.3

习题3.2.4

习题4.1.2

\(\large\textcolor{blue}{初等数论第七次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.4.16}\)

习题4.1.1

习题4.1.3

习题4.1.4

习题4.1.5

习题4.1.6

习题4.1.7

习题4.1.8

习题4.2.1

习题4.2.4

习题4.2.5

\(\large\textcolor{blue}{初等数论第八次作业}\ \ \ \ \ \ _\textcolor{blue}{2022.4.23}\)

习题4.2.2

习题4.2.3

习题4.2.6