1. 第七章 因数分解与算数基本定理

   1. 习题7.1
   2. 习题7.2
   3. 习题7.3
   4. 习题7.4
   5. 习题7.5
   6. 习题7.6
   7. 习题7.7
   8. 代码-分解质因数
   9. 伯努利数
   10. 代码-伯努利数

2. 第八章 同余式

   1. 习题8.1
   2. 习题8.2
   3. 习题8.3
   4. 习题8.4
   5. 习题8.5
   6. 习题8.6
   7. 习题8.7
   8. 习题8.8
   9. 习题8.9
   10. 习题8.10
   11. 代码-一元一次同余方程
   12. 代码-整系数多项式同余方程

3. 其他

第七章 因数分解与算数基本定理

习题7.1

​ 假设$gcd(a,b)=1$，进而设 $a$ 整除乘积 $bc$. 证明 $a$ 必整除 $c$.

证： $\because gcd(a,b)\therefore \exists (x,y)\in N\text{使得}ax+by=1\text{,因此可以得到}acx+bcy=c$
又$\because a\mid ac,a\mid bc\therefore a\mid c=acx+bcy$.

习题7.2

​ 假设 $gcd(a,b)=1$，进而设$a\mid c，b\mid c$. 证明乘积$ab\mid c$.

证： $\because a\mid c\therefore c=ma,\text{又}\because b\mid c=ma，b\nmid a\therefore b\mid m，\therefore m=nb,\therefore c=nab$

习题7.3

​ 设 $s,t$ 为奇数， $s>t\ge 1，gcd(s,t)=1$， 证明

两两互素，即它们中的每一对都互素。在证明勾股定理(定理 $2.1$)时需用到这个结论。(提示：假设有一个公素因数， 应用引理$7.1$：如果一个素数整除某个乘积，则它必整除其中一个因数。)

证：（1）假设 $d\mid (st,\frac{s^2-t^2}{2})(d>1,\text{且}d\text{为素因数})$，不妨设$d\mid s，d\nmid t$，则$d\mid s^2$， 又 $d\mid (st,\frac{s^2-t^2}{2})$，得出$d\mid t^2\Rightarrow d\mid t$，这与$(s,t)=1$​矛盾。$s，t$ 是奇数。
（2） 假设$d\mid (\frac{s^2+t^2}{2},\frac{s^2-t^2}{2})(d>1,\text{且}d\text{为素因数})$，不妨设$d\mid \frac{s+t}{2}，d\nmid \frac{s-t}{2}$，令$s^{\prime }=\frac{s+t}{2},t^{\prime }=\frac{s-t}{2}$，则$\frac{s^2+t^2}{2}={s^{\prime }}^2+{t^{\prime }}^2,\frac{s^2-t^2}{2}=2s^{\prime }{t}^{\prime }$。根据假设可得$d\mid {t^{\prime }}^2$ 即 $d\mid t^{\prime }=\frac{s-t}{2}$矛盾。易证$(s,t)=1，s,t$均为奇数时， $(s+t,s-t)=2$.
(3) $(st,\frac{s^2+t^2}{2})=1$，证明同（1）

习题7.4

​ 给出下述公式的归纳证明。

• (a) $1+2+3+\cdots +n=\frac{n(n+1)}{2}$
• (b) $1^2+2^2+3^3+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}$
• (c) $1+a+a^2+a^3+\cdots +a^n=\frac{1-a^{n+1}}{1-a}，a\ne 1$
• (d) $\frac{1}{1\times 2}+\frac{1}{2\times 3}+\cdots +\frac{1}{(n-1)\times n}=\frac{n-1}{n}$

(a) $T_1=1，T_{n+1}=T_n+n+1=\frac{n(n+1)}{2}+n+1=\frac{(n+1)(n+2)}{2}$
(b) $T_1=1，T_{n+1}=T_n+(n+1{)}^2=\frac{n(n+1)(2n+1)}{6}+(n+1{)}^2=\frac{(n+1)(n+2)(2n+3)}{6}$
(c) $T_1=1，T_{n+1}=T_n+a^{n+1}=\frac{1-a^{n+1}}{1-a}+a^{n+1}=\frac{1-a^{n+1}+a^{n+1}-a^{n+2}}{1-a}=\frac{1-a^{n+2}}{1-a}$
(d) $T_1=\frac{1}{2}，T_{n+1}=T_n+\frac{1}{n(n+1)}=\frac{n-1}{n}+\frac{1}{n}-\frac{1}{n+1}=\frac{n}{n+1}$

​ 引申：可使用算两次的思想得出一些其他和式的公式。一时兴起算的，发现并不存在某种特定规律，就没往后算了。

• $\sum _{i=1}^n{i}^3=\frac{n^2(n+1{)}^2}{4}$
• $\sum _{i=1}^n{i}^4=\frac{n(n+1)(2n+1)}{30}(3n^2+3n-1)$
• $\sum _{i=1}^n{i}^5=\frac{n^2(n+1{)}^2}{12}(2n^2+2n-1)$

习题7.5

​ 本习题要求你继续研究$\mathrm{E}-$区域。牢记你所做的，本题中假设奇数不存在！

• (a) 叙述所有$\mathrm{E}-$素数。
• (b) 证明每个偶数可分解为$\mathrm{E}-$素数的乘积。（提示：模仿普通数这个事实的证明）
• (c) 我们看到 $180$ 有三种分解法分解成$\mathrm{E}-$素数的乘积。求有两种不同分解法分解成$\mathrm{E}-$素数乘积的最小数。$180$ 是有三种分解法的最小数吗？求有四种分解法的最小数。
• (d) 整数 $12$ 金有一种分解法分解成$\mathrm{E}-$素数的乘积：$12=2\times 6$. （像通常一样，我们认为$2\times 6$与$6\times 2$是相同的分解。）求仅有一种分解法分解成$\mathrm{E}-$素数乘积的所有偶数。

(a) 在$\mathrm{E}-$区域：无法分解为 $\mathrm{E}$数乘积的数。扩充到整数区域便于记忆的定义，所有质因子中$2$的个数仅有一个的偶数。
(b) $2$本身是$\mathrm{E}-$素数，得证。假设当$n<N$时，均可被分解为$\mathrm{E}$-素数的乘积，若$N$是$\mathrm{E}$-素数，得证，反之$N$可以被分解为$\mathrm{E}-$数乘积，不妨令$N=N_1{N}_2$，显然$N_1\le \frac{N}{2}<N$，同理$N_2\le \frac{N}{2}<N$，得证。
(c) （1）引入奇数以便于理解的写法，$2\times 3\times 2\times 3=6\times 6=2\times 18，2\times 3\times 2\times 5=6\times 10=2\times 30$​
（2） $180$是最小的。
（3） $540=2\times 2\times 3\times 3\times 3\times 5=2\times 270=6\times 90=18\times 30=54\times 10$​
(d) 引入奇数以便于理解的写法，$2^n\times d(n>1,d为奇质数)$

习题7.6

​ 欢迎进入 $\mathrm{M}-$ 世界，这里只有被 $4$ 除余 $1$ 的正整数。换句话说，$\mathrm{M}-$数是

（另一种叙述是形如 $4t+1(t=0,1,2,3,\cdots )$的数。）在 $\mathrm{M}-$ 世界中，我们不可能把数相加，但可以把数相乘，因为如果 $a$ 与 $b$ 都被 $4$ 除余 $1$ ，则它们的乘积也是这样。（你知道为什么成立吗？）如果对某 $\mathrm{M}-$ 数 $k$ 有 $n=mk$，则称 $m\mathrm{M}-$整数 $n$. 如果$n$ 的 $\mathrm{M}-$因数仅为 $1$ 与它自身，则称 $n$ 是 $\mathrm{M}-$ 素数。（当然，我们不认为 $1$ 本身是 $\mathrm{M}-$ 素数。）

• (a) 求前 $6$ 个 $\mathrm{M}-$素数。
• (b) 求有两种不同分解法分解成$\mathrm{M}-$素数乘积的$\mathrm{M}-$ 数 $n$.

(a) 质数筛法可得：$5,9,13,17,21,29$

$$\begin{gathered} \{1,5,9,13,17,21,25,29,33,37,41,45,49,\cdots \} \\ 选取5，排除5\times 5=25 \\ \{1,5,9,13,17,21,25,29,33,37,41,45,49,\cdots \} \\ 选取9，排除5\times 9=45和9\times 9=81 \\ \{1,5,9,13,17,21,25,29,33,37,41,45,49,\cdots \} \\ \cdots \\ 取前六即可得 \end{gathered}$$

(b) 构造：$3\times 3\times 7\times 7=9\times 49=21\times 21$​

习题7.7

​ 编写将（正）整数 $n$ 分解成素数乘积的程序。（如果 $n=0$，确保转到出错信息而不是出现死循环）。表示 $n$ 的因数分解的简便方法是 $2\times r$阶矩阵。因此，如果

则将 $n$ 的分解存储成矩阵

（如果你的计算机不允许动态存储分配，则必须确定允许存储多个因数的预存量）

• (a) 编写程序，通过试除每个可能因数 $d=2,3,4,5,6,\cdots$ 分解 $n$. （这是一种极其低效的方法，但常用作初学习题）

• (b) 修改程序存储前$100$ 个（或更多）素数，在找最大素因数前先将 $n$ 除去这些素数。如果你不管 $2$ 或 $3$ 或 $5$ 倍数的$d$，而只把较大的 $d$ 作为可能的因数，那么可提高程序运行速度。利用 $m$ 不能被 $2$ 与 $\sqrt{m}$ 之间的任何整数整除时 $m$ 必为素数的事实，也可提高效率。使用你的程序求$1\_000\_000$ 与 $1\_000\_030$ 间所有整数的完全因数分解。

• (c) 编写一段子程序以优美格式打印 $n$ 的因数分解。最令人满意的是指数出现在指数位置；但是，如果这不可能，则将（比如说）$n=75460=2^2\cdot 5\cdot 7^3\cdot 11$的因数分解打印成

  $$2\wedge 2\ast 5\ast 7\wedge 3\ast 11$$

  （为了便于阅读，不打印等于 $1$​ 的指数）

见代码部分。$n$ 的质因数个数至多有 $\log n$个。

代码-分解质因数

public class PrimeSplit {
    private int M;
    private List<Integer> ls;

    public PrimeSplit(int max) {
        M = (int) (Math.sqrt(max) + 1);
        boolean[] p = new boolean[M];
        ls = new ArrayList<>();
        Arrays.fill(p, true);
        for (int i = 2; i < M; i++) {
            if(p[i]) ls.add(i);
            for(int x: ls){
                if(x * i >= M) break;
                p[x * i] = false;
                if(i % x == 0) break;
            }
        }
    }
    public List<int[]> split(int n){
        List<int[]> res = new ArrayList<>();
        for (int x: ls) {
            if(x * x > n) break;
            int l = 0;
            while(n % x == 0){
                n /= x;
                l++;
            }
            if(l > 0) res.add(new int[]{x, l});
        }
        if(n > 1) res.add(new int[]{n, 1});
        return res;
    }
    public static void main(String[] args){
        int M = 1_000_030;
        PrimeSplit ps = new PrimeSplit(M);
        StringBuffer sb = new StringBuffer();
        for (int i = 1_000_000; i <= M; i++) {
            List<int[]> split = ps.split(i);
            sb.append(i);
            sb.append('=');
            boolean f = false;
            for (int[] x: split){
                if(f) sb.append('*');
                sb.append(x[0]);
                if(x[1] > 1){
                    sb.append('^');
                    sb.append(x[1]);
                }
                f = true;
            }
            System.out.println(sb);
            sb.setLength(0);
        }
    }
}

伯努利数

​ 前面手撕了部分自然数幂级求和公式，没找出明显规律，心想着不应该啊，然后去网上搜了搜，真被我发现了现成的结论，即伯努利数。

• $\sum _{i=0}^{n-1}{i}^1=\frac{1}{2}{n}^2-\frac{1}{2}n$
• $\sum _{i=0}^{n-1}{i}^2=\frac{1}{3}{n}^3-\frac{1}{2}{n}^2+\frac{1}{6}n$
• $\sum _{i=0}^{n-1}{i}^3=\frac{1}{4}{n}^4-\frac{1}{2}{n}^3+\frac{1}{4}{n}^2$
• $\sum _{i=0}^{n-1}{i}^4=\frac{1}{5}{n}^5-\frac{1}{2}{n}^4+\frac{1}{3}{n}^3-\frac{1}{30}n$
• $\sum _{i=0}^{n-1}{i}^5=\frac{1}{6}{n}^6-\frac{1}{2}{n}^5+\frac{5}{12}{n}^4-\frac{1}{12}{n}^2$
• $\sum _{i=0}^{n-1}{i}^6=\frac{1}{7}{n}^7-\frac{1}{2}{n}^6+\frac{1}{2}{n}^5-\frac{1}{6}{n}^3+\frac{1}{42}n$

制作表格

得到伯努利数$[1,-\frac{1}{2},\frac{1}{6},0,-\frac{1}{30},0,\frac{1}{42},0,-\frac{1}{30},\cdots ]$。

​ 观察$S_n(k)=\sum _{i=0}^{n-1}{i}^k$通项公式的系数，将其相加总是得到 $0$，事实上将 $n=1$ 代入即可。因此我们有$\frac{1}{k+1}\sum _{i=0}^k{(}_i^{k+1})B_i=0$，消去$\frac{1}{k+1}$ 提出$B_k$项，即有$B_k=-\frac{1}{k+1}\sum _{i=0}^{k-1}{(}_i^{k+1})B_i$。以计算$B_6$为例

​ 也可以考虑将$(B+1{)}^k-B^k=0$展开，将$B^i$替换为伯努利数$B_i$，也能得到上述公式。伯努利数的性质和应用远不止这一点，而且还有很多没弄明白。伯努利数虽然可以计算出来，但本身没啥规律，或者是规律不够明显？

代码-伯努利数

public BigInteger[][] bernoulli(int n){
    //包含分子分母各两项
    BigInteger[][] b = new BigInteger[n + 1][2];
    b[0] = new BigInteger[]{BigInteger.ONE, BigInteger.ONE};
    BigInteger[] f = new BigInteger[n + 2];
    Arrays.fill(f, BigInteger.ONE);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j > 0; j--) {
            //C(i, j),也即C(i, i - j)
            f[j] = f[j].add(f[j - 1]);
        }
        b[i] = new BigInteger[]{BigInteger.ZERO, BigInteger.ONE};
        //根据已有结论：大于1的奇数项为0.可进行剪枝
        if(i > 1 && i % 2 == 1) continue;
        for (int j = 0; j < i; j++) {
            if(j > 1 && j % 2 == 1) continue;
            sub(b[i], b[j], f[j]);
        }
        gcd(b[i], i + 1);
    }
    return b;
}

private void gcd(BigInteger[] t, int i) {
    //gcd法约分
    t[1] = t[1].multiply(BigInteger.valueOf(i));
    BigInteger a = t[1], b = t[0].abs();
    while(b.compareTo(BigInteger.ZERO) > 0){
        BigInteger tp = a.mod(b);
        a = b;
        b = tp;
    }
    t[0] = t[0].divide(a);
    t[1] = t[1].divide(a);
}

public void sub(BigInteger[] a, BigInteger[] b, BigInteger mul){
    //通分
    a[0] = a[0].multiply(b[1]).subtract(b[0].multiply(a[1]).multiply(mul));
    a[1] = a[1].multiply(b[1]);
}

第八章 同余式

习题8.1

​ 假设 $a_1\equiv b_1\mathrm{mod}m$ 与 $a_2\equiv b_2\mathrm{mod}m$ .

• (a) 验证 $a_1+a_2\equiv b_1+b_2\mathrm{mod}m$ 与 $a_1-a_2\equiv b_1-b_2\mathrm{mod}m$ .
• (b) 验证 $a_1{a}_2\equiv b_1{b}_2\mathrm{mod}m$​.

(a) $a_1=pm+b_1$，$a_2=qm+b_2$
$a_1+a_2=m(p+q)+b_1+b_2$，$a_1-a_2=m(p-q)+b_1-b_2$
(b) $a_1{a}_2=m(pqm+p{b}_2+q{b}_1)+b_1{b}_2$

习题8.2

​ 假设 $ac\equiv bc\mathrm{mod}m$ 和 $gcd(c,m)=1$. 证明 $a\equiv b\mathrm{mod}m$.

$ac=pm+bc$，$cx+my=1\to c=\frac{1-my}{x}$，代入，即得 $a=m(px+ay-by)+b$

习题8.3

​ 求下述同余式的所有不同余解。

• (a) $7x\equiv 3\mathrm{mod}15$
• (b) $6x\equiv 5\mathrm{mod}15$
• (c) $x^2\equiv 1\mathrm{mod}8$
• (d) $x^2\equiv 2\mathrm{mod}7$
• (e) $x^2\equiv 3\mathrm{mod}7$

(a) $x\equiv 9\mathrm{mod}15$

(b) 无解

(c) $x\equiv 1,3,5,7\mathrm{mod}8$

(d) $x\equiv 3,4\mathrm{mod}7$

(e) 无解

习题8.4

​ 证明下述整除性试验结果.

• (a) 数 $a$ 被 4 整除但且仅当它的末尾两位数被 4 整除。
• (b) 数 $a$​ 被 8整除但且仅当它的末尾三位数被 8 整除。
• (c) 数 $a$​ 被 3 整除但且仅当它的各位数字之和被 3 整除。
• (d) 数 $a$​ 被 9 整除但且仅当它的各位数字之和被 9 整除。
• (e) 数 $a$ 被 11 整除但且仅当它的各位数字交错和被 11 整除。（如果 $a=\overline{a_1{a}_2{a}_3\cdots a_{d-1}{a}_d}$，则交错和值交替加、减$a_1-a_2+a_3-\cdots$​）

(a) $$\begin{gathered} 100\equiv 0\mathrm{mod}4\Rightarrow a=\overline{a_d{a}_{d-1}\cdots a_1{a}_0}=a_{d}10^d+a_{d-1}10^{d-1}+\cdots +a_{1}10+a_0 \\ \equiv a_{1}10+a_0=\overline{a_1{a}_0}\mathrm{mod}4 \end{gathered}$$

(b) $$\begin{gathered} 1000\equiv 0\mathrm{mod}8\Rightarrow a=\overline{a_d{a}_{d-1}\cdots a_1{a}_0}=a_{d}10^d+a_{d-1}10^{d-1}+\cdots +a_{1}10+a_0 \\ \equiv a_{1}10+a_0=\overline{a_2{a}_1{a}_0}\mathrm{mod}8 \end{gathered}$$​

(c) $$\begin{gathered} 10\equiv 1\mathrm{mod}3\Rightarrow a=\overline{a_d{a}_{d-1}\cdots a_1{a}_0}=a_{d}10^d+a_{d-1}10^{d-1}+\cdots +a_{1}10+a_0 \\ \equiv a_d+a_{d-1}+\cdots +a_1+a_0\mathrm{mod}3 \end{gathered}$$

(d) $$\begin{gathered} 10\equiv 1\mathrm{mod}9\Rightarrow a=\overline{a_d{a}_{d-1}\cdots a_1{a}_0}=a_{d}10^d+a_{d-1}10^{d-1}+\cdots +a_{1}10+a_0 \\ \equiv a_d+a_{d-1}+\cdots +a_1+a_0\mathrm{mod}9 \end{gathered}$$

(e) $$\begin{gathered} 10\equiv -1\mathrm{mod}11\Rightarrow a=\overline{a_d{a}_{d-1}\cdots a_1{a}_0}=a_{d}10^d+a_{d-1}10^{d-1}+\cdots +a_{1}10+a_0 \\ \equiv a_d(-1{)}^d+a_{d-1}(-1{)}^{d-1}+\cdots +a_1(-1{)}^1+a_0(-1{)}^0\mathrm{mod}11 \end{gathered}$$

习题8.5

​ 求下述线性同余式的所有不同余解。

• (a) $8x\equiv 6\mathrm{mod}14$
• (b) $66x\equiv 100\mathrm{mod}121$
• (c) $21x\equiv 14\mathrm{mod}91$

(a) $x\equiv 12,5\mathrm{mod}14$
(b) 无解
(c) $x\equiv 44,57,70,83,5,18,31\mathrm{mod}91$

习题8.6

​ 确定下述同余式的不同余解的个数。无需求出解。

• (a) $72x\equiv 47\mathrm{mod}200$
• (b) $4183x\equiv 5781\mathrm{mod}15087$
• (c) $1537x\equiv 2863\mathrm{mod}6731$

(a) $(200,72)=8，8\nmid 47$，无解
(b) $(15087,4183)=47,47\mid 5781$，有$47$个解
(c) $(6731,1537)=53，53\nmid 2863$，无解

习题8.7

​ 编写程序解同余式 $ax\equiv c\mathrm{mod}m$. （如果$gcd(a,m)$不整除 c, 则输出出错信息和 $gcd(a,m)$的值）测试程序，求出习题8.6中同余式的所有解。

见代码部分

习题8.8

​ 编写程序，输入正整数 $m$ 和 整系数多项式 $f(X)$，输出同余式$f(X)\equiv 0\mathrm{mod}m$ 的所有解。（无需细想，只需让 $X$ 分别取 $0,1,2,\cdots ,m-1$，看看哪些值是解。）取多项式

对下述每个 $m$ 值

通过解同余式$f(X)\equiv 0\mathrm{mod}m$ 来测试程序。

见代码部分

习题8.9

​ (a) 同余式

有多少个解？有四个解嘛？还是少于四个解？

​ (b) 考察同余式 $X^2-1\equiv 0\mathrm{mod}8$，当 $0\le X<8$时它有几个解？注意它的解多余两个。为什么这个结果与模 $p$ 多项式根定理(定理 8.2)矛盾？

(a) 使用习题8.8的程序验证，得两个解。事实上原式$=(X-1)(X+2)[(X+2{)}^2-2]$，而 $2$ 不是 $11$ 的平方剩余。
(b) 答：四个解。8 不是素数。

习题8.10

​ 设 $p,q$ 为不同素数。同余式

最多可能有多少个解？这里我们照样只关心模 $pq$ 不同余的解。

答：4 个。$(X+a)(X-a)\equiv 0\mathrm{mod}pq\Rightarrow X\pm a\equiv 0\mathrm{mod}p$ 和 $X\pm a\equiv q$，最多各两个解，进而两两组合解同余式，最多可得四个解。

代码-一元一次同余方程

public Pair<Boolean, List<Integer>> remainder(int a, int c, int m){
    //欧几里得扩展法
    int[] g = _gcd(a, m);
    List<Integer> ls = new ArrayList<>();
    if(c % g[2] != 0){
        ls.add(g[2]);
        return new Pair<>(false, ls);
    }
    c = c * g[0] / g[2];
    for (int i = 0; i < g[2]; i++) {
        ls.add(c);
        c = (c + m / g[2]) % m;
    }
    return new Pair<>(true, ls);
}

代码-整系数多项式同余方程

public List<Integer> remainder(int[] F, int m){
    List<Integer> ls = new ArrayList<>();
    for (int i = 0; i < m; i++) {
        int x = 1;
        int M = 0;
        for (int f : F) {
            M = (M + f * x) % m;
            x = x * i % m;
        }
        if(M == 0) ls.add(i);
    }
    return ls;
}

其他

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