1. 第九章 同余式、幂与费马小定理

   1. 习题9.1
   2. 习题9.2
   3. 习题9.3
   4. 习题9.4

2. 第十章 同余式、幂与欧拉公式

   1. 习题10.1
   2. 习题10.2
   3. 习题10.3

3. 第十一章 欧拉函数与中国剩余定理

   1. 习题11.1
   2. 习题11.2
   3. 习题11.3
   4. 习题11.4
   5. 习题11.5
   6. 习题11.6
   7. 习题11.7
   8. 习题11.8
   9. 习题11.9
   10. 习题11.10
   11. 习题11.11
   12. 习题11.12
   13. 习题11.13

4. 代码-乘法快速幂

5. 代码-解同余式

6. 其他

第九章 同余式、幂与费马小定理

习题9.1

​ 利用费马小定理求解下述题目。

• (a) 求数 $0\le a<73$，使得 $a\equiv 9^{794}\mathrm{mod}73$.
• (b) 解 $x^{86}\equiv 6\mathrm{mod}29$
• (c) 解 $x^{39}\equiv 3\mathrm{mod}13$

(a) $a\equiv 9^{794}\equiv 9^{72\times 11+2}\equiv 9^2\equiv 8\mathrm{mod}73$
(b) $x^{86}\equiv x^{28\times 3+2}\equiv x^2\equiv 6\mathrm{mod}29\Rightarrow x\equiv 8,21\mathrm{mod}29$​
(c) $x^{39}\equiv x^{12\times 3+3}\equiv x^3\equiv 3\mathrm{mod}13\Rightarrow$ 无解

习题9.2

​ 虽然我们不需要知道 $(p-1)!\mathrm{mod}p$ 的值，但是 $(p-1)!\mathrm{mod}p$ 出现在费马小定理的证明中。

• (a) 对某些小的 $p$ 值，计算 $(p-1)!\mathrm{mod}p$ ，找出模式并提出猜想
• (b) 证明你的猜想是正确的。（对小的 $p$ 值，试寻找 $(p-1)!\mathrm{mod}p$ 产生这种数值的原因，然后推广你的观察，证明结论对所有 $p$ 成立。）

(a)

$$\{\begin{array}{ll}p=2& (p-1)!=1\equiv p-1\mathrm{mod}p\\ p=3& (p-1)!=2\equiv p-1\mathrm{mod}p\\ p=5& (p-1)!=24\equiv p-1\mathrm{mod}p\\ p=7& (p-1)!=720\equiv p-1\mathrm{mod}p\end{array}$$

(b) 证：$(p-1)!\equiv p-1\mathrm{mod}p$。可先证下面三个结论，即可得证。当 $p$ 为奇素数时，满足：

$$\{\begin{array}{ll}p>2时，a^2\equiv 1\mathrm{mod}p仅有\pm 1两个解& 模p多项式根定理\\ 当a\ne \pm 1时，ax\equiv 1\mathrm{mod}p恰有一个解，且x\not\equiv a\mathrm{mod}p& 线性同余式定理并结合第一给出的证明\\ 当a\not\equiv b\mathrm{mod}p，则a^{-1}\not\equiv b^{-1}\mathrm{mod}p& 反证法\end{array}$$

习题9.3

​ 当 $p$ 是素数时，习题9.2要求你确定 $(p-1)!\mathrm{mod}p$ 的值。

• (a) 对某些小的合数m的值，计算$(m-1)!\mathrm{mod}m$ 。你能得到对素数所发现的相同模式吗？
• (b) 如果已知$(n-1)!\mathrm{mod}n$的值，如何使用这个值明确判断 $n$ 是合数还是素数？

答：$m$ 是合数，则 $m$ 一定可以表示为 $m=m_1{m}_2(m_1,m_2<m)$的形式，而$(m-1)!$必然包含$m_1,m_2$，由此可知$(m-1)!\equiv 0\mathrm{mod}m$.

习题9.4

​ 如果 $p$ 是素数，$a\not\equiv 0\mathrm{mod}p$，则由费马小定理可知 $a^{p-1}\equiv 1\mathrm{mod}p$.

• (a) 同余式$7^{1734250}\equiv 1660565\mathrm{mod}1734251$ 成立，你能得到$1734251$​是合数的结论吗？
• (b) 同余式$129^{64026}\equiv 15179\mathrm{mod}64027$ 成立，你能得到$64027$​是合数的结论吗？
• (c) 同余式$2^{52632}\equiv 1\mathrm{mod}52633$ 成立，你能得到$52633$是素数的结论吗？

答：若 $p$ 是素数，$a\not\equiv 0\mathrm{mod}p$，则 $a^{p-1}\equiv 1\mathrm{mod}p$.其逆否命题为：
若存在$a\not\equiv 0\mathrm{mod}m$ 满足 $a^{m-1}\not\equiv 1\mathrm{mod}m$，则 $m$​ 一定是合数。
(a) 可以确定1734251是合数 (b) 可以确定64027是合数 (c) 52633有可能是素数，也有可能是合数

第十章 同余式、幂与欧拉公式

习题10.1

​ 设 $b_1<b_2<\cdots <b_{\varphi (m)}$ 是 $1$ 与 $m$ 之间且与 $m$ 互素的整数（包括 $1$）, $B=b_1{b}_2\cdots b_{\varphi (m)}$是他们的乘积。$B$ 来自于欧拉公式的证明。

• (a) 证明 $B\equiv 1\mathrm{mod}m$ 或 $B\equiv -1\mathrm{mod}m$ 。
• (b) 对某些小的 $m$ 值计算 $B$ , 试寻找当它等于 $1\mathrm{mod}m$ 和 $-1\mathrm{mod}m$时的模式。

(a) 1. 由$(b_i,m)=1$可知，存在$1\le x<m$ 使得 $b_{i}x\equiv 1\mathrm{mod}m$，同样可证明$(x,m)=1$，即 $x\in \{b_1,b_2,\cdots ,b_{\varphi (m)}\}$，也可用反证法证明当$i\ne j$时，$b_i^{-1}\not\equiv b_j^{-1}\mathrm{mod}m$. 现从集合$\{b_1,b_2,\cdots ,b_{\varphi (m)}\}$中去除$b_i^{-1}\mathrm{mod}{b}_i\mathrm{mod}m$ 即 $b_i^2\equiv 1\mathrm{mod}p$的元素，并令$b_{i}x\equiv 1\mathrm{mod}m$的解 $x=b_j$ 与 $b_i$可构成一对 $(b_i,b_j),b_i{b}_j\equiv 1\mathrm{mod}m$，得$\prod ^{b_i^2\not\equiv 1\mathrm{mod}m}{b}_i\equiv 1\mathrm{mod}m$.

2. 若$b_i^2\equiv 1\mathrm{mod}m\Rightarrow (-b_i{)}^2\Rightarrow 1\mathrm{mod}m\Rightarrow b_i\times (-b_i)\equiv -1\mathrm{mod}m$，可令$(b_i,-b_i)$​构成一对。
3. 当 $m$ 为奇数时，显然不存在 $b^{\prime }=m-b^{\prime }$，当 $m$ 为偶数时，显然$b^{\prime }=\frac{m}{2}\mid m$，即(2)中所述的数对不存在$b_i\equiv -b_i\mathrm{mod}m$ 的情形。

(b)

$$\{\begin{array}{llcccccccccccccccccccccccccccccccc}m=4& B=-1& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ m=6& B=-1& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ m=8& B=1& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ m=9& B=-1& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ m=10& B=1& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \end{array}$$

猜想：$a^2\equiv 1\mathrm{mod}m$的解的个数为 $4$ 的倍数时，值为 $1$，否则为 $-1$。(a) 中已给出证明。

那什么时候解的个数为 $4$ 的倍数呢？说下发现，质因数$2$至多只能提供四个解，
其余奇质因数最多只能提供两个解。描述：若 $m=2^c{p}_1^{k_1}{p}_2^{k_2}\cdots p_r^{k_r}，m$为合数，$a^2\equiv 1\mathrm{mod}m$的解的个数$2^{max(0,min(c-1,2))+r}$​个。暂无法给出证明。

习题10.2

​ 可以验证数 $3750$ 满足 $\varphi (3750)=1000$.求满足下述三个性质的数$a$

• (i) $a\equiv 7^{3003}\mathrm{mod}3750$
• (ii) $1\le a\le 5000$
• (iii) $a$ 不被 $7$ 整除。

答：$(7,3750)=1\Rightarrow a\equiv 7^{3003}=7^{1000\times 3+3}\equiv 7^3=343\mathrm{mod}3750，1\le a\le 5000，\Rightarrow a=343+3750=4093$

习题10.3

​ 如果对每个整数 $a(gcd(a,m)=1)$ ，同余式 $a^{m-1}\equiv 1\mathrm{mod}m$ 成立，则称合数是卡米歇尔数。

• (a) 验证 $m=561=3\cdot 11\cdot 17$ 是卡米歇尔数。（提示：不必对 $a$ 的所有320个值计算 $a^{m-1}\mathrm{mod}m$，而是使用费马小定理验证对整除 $m$ 的每个素数 $p$ ，有 $a^{m-1}\equiv 1\mathrm{mod}p$，然后解释为什么这蕴含 $a^{m-1}\equiv 1\mathrm{mod}m$.）
• (b) 试求另一个卡米歇尔数。你认为存在无穷多个卡米歇尔数吗？

(a) $a^{560}\equiv a^{2\times 280}\equiv 1\mathrm{mod}3，a^{560}\equiv a^{10\times 56}\equiv 1\mathrm{mod}11，a^{560}\equiv a^{16\times 35}\equiv 1\mathrm{mod}17$

结论：若$b\equiv c\mathrm{mod}{p}_1，b\equiv c\mathrm{mod}{p}_2，(p_1,p_2)=1，则b\equiv c\mathrm{mod}{p}_1{p}_2$
证：$p_{1}x+p_{2}y=1，b=p_1{k}_1+c=p_2{k}_2+c\Rightarrow k_1=p_2(x{k}_2+y{k}_1)\Rightarrow b=p_1{p}_2(x{k}_2+y{k}_1)+c$

(b) $1105=5\times 13\times 17$

第十一章 欧拉函数与中国剩余定理

习题11.1

​ (a) 求 $\varphi (97)$ 的值。
​ (b) 求 $\varphi (8800)$ 的值。

(a) $\varphi (97)=96$.
(b) $\varphi (8800)=\varphi (2^5)\varphi (5^2)\varphi (11)=1\cdot 2^4\cdot 4\cdot 5\cdot 10=3200$

习题11.2

​ (a) 如果 $m\ge 3$，解释为什么 $\varphi (m)$ 总是偶数。
​ (b) $\varphi (m)$ “经常” 被 $4$ 整除。叙述 $\varphi (m)$ 不被 $4$ 整除的所有 $m$.

(a) $\varphi (p^k)=(p-1)p^k，p$为质数，$p$ 为 $2$ 时 $p^k\ge 2$ 为偶数，$p$ 为质数时 $p-1$ 为偶数。

(b) $m=2,4或2^{k_0}{p}^{k_1}，0\le k_0\le 1，p\equiv 3\mathrm{mod}4$，p为质数

习题11.3

​ 假设 $p_1,p_2,\cdots ,p_r$ 是整除 $m$ 的不同素数。证明 $\varphi (m)$ 的下述公式成立。

使用这个公式计算 $\varphi (1\_000\_000)$.

$$\begin{gathered} m=p_1^{k_1}{p}_2^{k_2}\cdots p_r^{k_r}\Rightarrow \varphi (m)=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})\cdots (p_r^{k_r}-p_r^{k_r-1}) \\ =p_1^{k_1}(1-\frac{1}{p_1})\cdots p_r^{k_r}(1-\frac{1}{p_r})=p_1^{k_1}\cdots p_r^{k_r}(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_r})=m(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_r}) \end{gathered}$$​

$\varphi (1\_000\_000)=1\_000\_000\cdot \frac{1}{2}\cdot \frac{4}{5}=400\_000$

习题11.4

​ 编写程序计算欧拉公式 $\varphi (n)$ 的值。应该使用 $n$ 的素因数分解来计算 $\varphi (n)$ ，而不是通过求与 $n$ 互素的 $1$ 到 $n$ 之间的所有 $a$ 来计算 $\varphi (n)$.

略。可使用习题11.3的结论来简化计算。1. 找出 $n$ 的所有质因子，2. 初始化 $\varphi (m)=m$，3. 对每个不同的质因子 $p_i$ 执行 $\varphi (m)=\frac{(p_i-1)\times \varphi (m)}{p_i}$ 的操作。

习题11.5

​ 对每个同余式组求其解 $x$ .

• (a) $x\equiv 3(mod7),x\equiv 5(mod9)$
• (b) $x\equiv 3(mod37),x\equiv 1(mod87)$
• (c) $x\equiv 5(mod7),x\equiv 2(mod12),x\equiv 8(mod13)$

(a) $x\equiv 3\times 9\times 9^{\prime }+5\times 7\times 7^{\prime }(mod7\times 9)\Rightarrow x\equiv 27\times (-3)+35\times 4\equiv 59(mod63)$

(b) $x\equiv 3\times 87\times 87^{\prime }+1\times 37\times 37^{\prime }=3\times 87\times (-17)+1\times 37\times 40\equiv 262(mod3219)$

(c) $$\begin{gathered} x\equiv 5\times \frac{7\times 12\times 13}{7}\times (\frac{7\times 12\times 13}{7}{)}^{\prime }+2\times \frac{7\times 12\times 13}{12}\times (\frac{7\times 12\times 13}{12}{)}^{\prime }+ \\ 8\times \frac{7\times 12\times 13}{13}\times (\frac{7\times 12\times 13}{13}{)}^{\prime } \\ =5\times 156\times (-3)+2\times 91\times (-5)+8\times 84\times (-2)\equiv 866(mod1092) \end{gathered}$$​

注：上述计算来自中国剩余定理。

证明：

$$\{\begin{array}{l}x\equiv c_1(mod{a}_1)\\ x\equiv c_2(mod{a}_2)\\ \cdots \\ x\equiv c_r(mod{a}_r)\\ (a_i,a_j)=1,(i\ne j)\end{array}\Rightarrow \{\begin{array}{l}M=a_1{a}_2\cdots a_r\\ M_i=\frac{M}{a_i}\\ M_i{M}_i^{\prime }+a_i{a}_i^{\prime }=1\\ x=c_1{M}_1{M}_1^{\prime }+c_2{M}_2{M}_2^{\prime }+\cdots +c_r{M}_r{M}_r^{\prime }(modM)\end{array}$$

观察其中某一项 $T_i=c_i{M}_i{M}_i^{\prime }$ 可得知，该项满足 $T_i\equiv c_i(mod{a}_i)$，对于$j\ne i$ 均有$T_i\equiv 0(mod{a}_j)$. 因此该式确为原方程的解。

习题11.6

​ 解“历史插曲”提到的《孙子算经》中已有1700年历史的中国剩余问题。

$x\equiv 2(mod3),x\equiv 3(mod5),x\equiv 2(mod7)\Rightarrow x\equiv 23(mod105)$

习题11.7

​ 一个农夫在去集市的路上，流星打中了他的小货车，击碎了他的鸡蛋，为申请保险索赔，他需要知道打碎了多少鸡蛋。他知道两两数之于一，三三数之余一，四四数之余一，五五数之余一，六六数之余一，七七数之余零。问小货车里鸡蛋的最少个数是多少？

简化计算，利用上一章习题中的推论：若 $(a_1,a_2)=1，x\equiv c(mod{a}_1)，x\equiv c(mod{a}_2)$，则有 $x\equiv c(mod{a}_1{a}_2)$。
将该结论做个引申：若 $(a_1,a_2)=g，x\equiv c(mod{a}_1)，x\equiv c(mod{a}_2)$，则有 $x\equiv c(mod\frac{a_1{a}_2}{g})$​。
则该题化简为：$x\equiv 1(mod60)，x\equiv 0(mod7)$，可得$x\equiv 301(mod420)$.

证明：$a_{1}x+a_{2}y=g，x=k_1{a}_1+c=k_2{a}_2+c\Rightarrow x=\frac{a_1{a}_2}{g}(k_{2}x+k_{1}y)+c$

习题11.8

​ 编写程序，取四个整数 $(b,m,c,n)，(m,n)=1$作为输入，计算满足

的整数解。

见代码部分。

习题11.9

​ 在本习题中将证明三个同余式的中国剩余定理，设 $m_1,m_2,m_3$ 是两两互素的正整数，即

设 $a_1,a_2,a_3$ 是任意三个整数。证明同余式组

在区间 $0\le x<m_1{m}_2{m}_3$ 恰有一个整数解。你能找出将这个问题推广到处理多个同余式

的模式吗？特别的 $m_1,m_2,\cdots ,m_r$ 需要满足什么条件呢？

答：由中国剩余定理可知 $x\equiv a_1(mod{m}_1),x\equiv a_2(mod{m}_2)$ 在 $0\le x<m_1{m}_2$ 上恰有一解，记为 $a_1^{\prime }$，又 $(m_1{m}_2,m_3)=1$，可知$x\equiv a_1^{\prime }(mod{m}_1{m}_2),x\equiv a_3(mod{m}_3)$，在 $0\le x<m_1{m}_2{m}_3$ 上恰有一解$a_3^{\prime }$。即原方程在 $0\le x<m_1{m}_2{m}_3$ 恰有一个整数解。

模式：如习题11.5中所提。

习题11.10

​ 若 $\varphi (n)$ 是素数，你能说出 $n$ 有什么模式吗？如果 $\varphi (n)$ 是素数的平方，$n$ 有满足什么模式呢？

答：由习题11.2可知，当 $n\ge 3$​ 时，$\varphi (n)$​ 总是偶数。因此：
(i) 若 $\varphi (n)$​ 是素数，则 $n=3,4$​
(ii) 如果 $\varphi (n)$​ 是素数的平方，则 $n=5,10,8,12$​

习题11.11

​ (a) 求 $\varphi (n)=160$ 的至少5个不同整数。你能求出更多吗？

​ (b) 假设整数 $n$ 满足 $\varphi (n)=1000$。列出可能整除 $n$ 的所有素数。

​ (c) 由(b) 求出所有满足 $\varphi (n)=1000$ 的所有整数。

(a) 答：$160=2\times 2\times 2\times 2\times 2\times 5$

$$\{\begin{array}{l}17\times 11\\ 2\times 17\times 11\\ 32\times 11\\ 16\times 3\times 11\\ 8\times 25\\ 4\times 3\times 25\\ 8\times 41\\ 4\times 3\times 41\\ 161\\ 2\times 161\end{array}$$

(b)(c) 答：$1000=2\times 2\times 2\times 5\times 5\times 5$

$$\{\begin{array}{l}8\times 251\\ 4\times 3\times 251\\ 5\times 251\\ 2\times 5\times 251\\ 4\times 5^4\\ 3\times 5^4\\ 2\times 3\times 5^4\\ 11\times 5^3\\ 2\times 11\times 5^3\\ 11\times 101\\ 2\times 11\times 101\\ 51\times 5^2\\ 2\times 51\times 5^2\\ 4\times 11\times 51\\ 3\times 11\times 51\\ 2\times 3\times 11\times 51\end{array}$$

挺多的，就是排列组合。两组之间不能构造出相同的数即可。

习题11.12

​ 解下述方程，求 $n$ 的所有值。

• (a) $\varphi (n)=\frac{n}{2}$.
• (b) $\varphi (n)=\frac{n}{3}$
• (c) $\varphi (n)=\frac{n}{6}$

(a) $\varphi (n)=n\cdot \frac{1}{2}\Rightarrow n=2^k,k\ge 1$
(b) $\varphi (n)=n\cdot \frac{1}{2}\cdot \frac{2}{3}\Rightarrow n=2^{k_0}{3}^{k_1},k_0,k_1\ge 1$​
(c) $\varphi (n)=n\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots \frac{p_r-1}{p_r},p_i\ge 2$，若原式有解，则必然存在 $p_i\mid 6$，经验证$p_i,p_j=2,3$时均不是方程的解。

习题11.13

​ (a) 对每个整数 $2\le a\le 10$，求 $a^{1000}$ 的最末四位数。
​ (b) 基于 (a) 的试验（如果有必要的话，进一步试验），给出一种简单判别法，使得可由 $a$ 的值预测 $a^{1000}$ 的最末四位数。
​ (c) 证明 (b) 中你的判别法是正确的。

答：

$$\{\begin{array}{llccccccccccccccccccccccc}2\nmid a,5\nmid a& a^{1000}\equiv 1(mod10000)& & & & & & & & & & & & & & & & & & & & & & & \\ 2\mid a,5\nmid a& a^{1000}\equiv 9376(mod10000)& & & & & & & & & & & & & & & & & & & & & & & \\ 2\nmid a,5\mid a& a^{1000}\equiv 625(mod10000)& & & & & & & & & & & & & & & & & & & & & & & \\ 2\mid a,5\mid a& a^{1000}\equiv 0(mod10000)& & & & & & & & & & & & & & & & & & & & & & & \end{array}$$

(i) 使用快速幂计算可得$2^{1000}\equiv 9376(mod10000),5^{1000}\equiv 625(mod10000)$，$2,5$ 的计算只能硬算，其余可省略。
(ii) $9376\times 9376\equiv 9376(mod10000),625\times 625\equiv 625(mod10000),9376\times 625\equiv 0(mod10000)$
(iii) $(a,10000)=1$ 时，$a^{1000}=a^{8\times 125}=a^{\varphi (16)\times 125}\equiv 1(mod16),a^{1000}=a^{8\times 125}=a^{\varphi (625)\times 4}\equiv 1(mod625)$
因$(16,625)=1$，于是 $a^{1000}\equiv 1(mod10000)$
(iv) 令$a=2^m{5}^{n}p,(p,10000)=1$，则 $a^{1000}\equiv 2^{1000\times m}{5}^{1000\times n}{p}^{1000}\equiv 9376^{min(m,1)}\times 625^{min(n,1)}\times 1(mod10000)$

代码-乘法快速幂

public int qpow(int x, int n, int m){
    long t = 1, r = x;
    while(n > 0){
        if(n % 2 == 1) t = t * r % m;
        r = r * r % m;
        n >>= 1;
    }
    return (int) t;
}

代码-解同余式

public Pair<Boolean, Integer> remainder(int b, int m, int c, int n){
    //欧几里得扩展法
    int[] g = _gcd(m, n);
    //不互质时，返回false，与最大公约数，代表无确定解，不代表无解
    //不互质时，可能无解，也可能有多个解
    if (g[2] > 1) return new Pair<>(false, g[2]);
    int r = (n * g[1] * b + m * g[0] * c) % (m * n);
    if(r < 0) r += m * n;
    return new Pair<>(true, r);
}

其他

1. 数论概论$\cdot$第一部分
2. 数论概论$\cdot$第二部分
3. 数论概论$\cdot$第三部分
4. 数论概论$\cdot$第四部分
5. 数论概论$\cdot$第六部分