1. 第五章 整数性与最大公因数

   1. 习题5.1
   2. 习题5.2
   3. 习题5.3
   4. 习题5.4
   5. 习题5.5
   6. 习题5.6
   7. 代码-GCD与LCM
   8. 代码-冰雹数列

2. 第六章 线性方程与最大公因数

   1. 习题6.1
   2. 习题6.2
   3. 习题6.3
   4. 习题6.4
   5. 习题6.5
   6. 习题6.6
   7. 行列式求解GCD
   8. 代码-乘法逆元GCD法

3. 其他

第五章 整数性与最大公因数

习题5.1

​ 应用欧几里得算法计算下述最大公因数。
$(a)gcd(12345,67890),(b)gcd(54321,9876)$

(a) $gcd(12345,57890)=15$
(b) $gcd(54321,9876)=3$

习题5.2

​ 编写程序计算两个整数 a 与 b 的最大公因数 gcd(a, b), 即使 a 与 b 中的一个等于零，程序也应该运行，但要确保 a 与 b 都是 0 时不会出现死循环。

见代码部分

习题5.3

设$b=r_0,r_1,r_2,\cdots$ 是将欧几里得算法应用于 a 与 b 得到的相继余数，证明每两步会缩小余数至少一半。换句话说，验证：

由此证明欧几里得算法在至多$2{\log }_{2}b$步终止，其中${\log }_2$是以2为底的对数。特别地，证明步数至多是b的位数的7倍。(提示：${\log }_{2}10$的值是多少？)

证：$r_i=q_{i+1}{r}_{i+1}+r_{i+2},可知r_{i+2}<r_{i+1}$，又$r_{i+1}\le r_i\Rightarrow q_{i+1}\ge 1\Rightarrow r_i\ge r_{i+1}+r_{i+2}>2r_{i+2}\Rightarrow r_{i+2}<\frac{1}{2}{r}_i$
$2lo{g}_{2}b=2\frac{{\log }_{10}b}{{\log }_{10}2}<7{\log }_{10}b$

习题5.4

​ 如果 m 与 n 都整除L，则数 L 被称为 m 与 n 的公倍数。最小的这种 L 被称为 m 与 n 的最小公倍数，记为 $LCM(m,n)$.例如，$LCM(3,7)=21,LCM(12,66)=132$.

• (a) 求下述最小公倍数。

  • (i) $LCM(8,12)$ (ii) $LCM(20,30)$ (iii) $LCM(51,68)$ (iv) $LCM(23,18)$

• (b) 对于在(a)中计算的每个$LCM$, 比较$LCM(m,n)$与$m,n,gcd(m,n)$的值，试找出他们之间的关系。

• (c) 证明你说发现的关系对所有 m 与 n成立。

• (d) 用(b)中的结果计算$LCM(301337,307829)$.

• (e) 假设$gcd(m,n)=18$ 且 $LCM(m,n)=720$, 求m 与 n。存在一种以上的可能性吗？如果存在，求出所有的 m 与 n。

(a) $LCM(8,12)=24,LCM(20,30)=60,LCM(51,68)=204,LCM(23,18)=414$
(b) $LCM(m,n)=\frac{m\times n}{gcd(m,n)}$
(c) 证： 令 $d=gcd(m,n)$，则有$m=dp,n=dq\Rightarrow (p,q)=1$,否则存在更大的数 $d^{\prime }$整除 m 与 n。
显然$pq$ 是能被 p 和 q整除的最小公倍数。又有$m=dp\mid dpq,n=dq\mid dpq,(dp,q)=(p,dq)=1\Rightarrow LCM(m,n)=dpq=\frac{dp\times dq}{d}=\frac{m\times n}{gcd(m,n)}$​
(d) $LCM(301337,307829)=\frac{301337\times 307829}{gcd(301337,307829)}=\frac{301337\times 307829}{541}=171460753$​
(e) $m=18p,n=18q,且(p,q)=1,720=18\times pq\Rightarrow pq=40=2^3\times 5\Rightarrow (p,q)=(5,8)或(1,40)$

习题5.5

​ “$3n+1$”算法如下：从给定的正整数 n 出发。如果 n 是偶数则将他除以二；如果是奇数则把它替换成$3n+1$.如此反复进行下去。例如，如果由5开始，则得到数列

如果由7开始，则得到

注意到 1 后数列正好连续重复 $4,2,1$​.一般地，下述两种可能性之一将会出现。
(i) 可能最后会重复出现先前的某数a，这种情况下两个 a 之间的数段会无穷次重复，此时称算法在最后一个不重复值处终止，数列中不同项的个数叫做算法长度。例如，对 5 与 7，算法在 1 处终止。5的算法长度是 6， 7的算法长度是 17.
(ii) 可能从不重复相同的数，此时说算法没有终止。

• (a) 对 n 的下述每一个开始值，求$3n+1$​的算法长度与终止值。
  • (i) $n=21$，(ii) $n=13$，(iii) $n=31$
• (b) 作进一步实验， 是确定$3n+1$算法是否总是终止，如果终止的话， 它在何处终止？
• (c) 假定算法在 1 出终止， 设 $L(n)$是开始值为 n 的算法长度。例如$L(5)=6$与$L(7)=17$.证明$n=8k+4(k\ge 1)$时$L(n)=L(n+1)$.(提示: 如果开始值为$8k+4$与$8k+5$，算法的运行结果是什么？)
• (d) 证明 $n=128k+28$ 时 $L(n)=L(n+1)=L(n+2)$.
• (e) 类似于(c) 和 (d)， 找出其他条件使得 n 的相继值有相同长度。(使用下一道习题积累的数据可能是有帮助的。)

(a) $L(21)=8,L(13)=10,L(31)=107$
(b) 猜想：对于$n\ne 1,2,4$的 始终在 1 处终止
(c) $L(8k+4)\to L(4k+2)\to L(2k+1)\to L(6k+4)$
$L(8k+5)\to L(24k+16)\to L(12k+8)\to L(6k+4)$
(d)
$128k+28\to 64k+14\to 32k+7\to 96k+22\to 48k+11\to 144k+34\to 72k+17\to 216k+52\to 108k+26\to 54k+13\to 162k+40$
$128k+29\to 384k+88\to 192k+44\to 96k+22$
$128k+30\to 64k+15\to 192k+46\to 96k+23\to 288k+70\to 144k+35\to 432k+106\to 216k+53\to 648k+160\to 324k+80\to 162k+40$
(d)

$$\{\begin{array}{llccccccccccccccccccc}(2^{n}k+1,2^{n}k+1)& n\ge 3& & & & & & & & & & & & & & & & & & & \\ (2^{n}k+28,2^{n}k+29,2^{n}k+30)& n\ge 7& & & & & & & & & & & & & & & & & & & \\ (2^{n}k+36,2^{n}k+37,2^{n}k+38)& n\ge 5& & & & & & & & & & & & & & & & & & & \\ (2^{n}k+44,2^{n}k+45,2^{n}k+46)& n\ge 6& & & & & & & & & & & & & & & & & & & \end{array}$$

习题5.6

​ 编写程序来运行上题叙述的$3n+1$算法。用户输入 n，程序就会给出 $3n+1$算法的长度L(n)与终止值$$T(n). 用你的程序来制作一个表格，给出所有开始值 $1\le n\le 100$的算法长度与终止值。

见代码部分。

代码-GCD与LCM

public int gcd(int x, int y){
    while(y != 0){
        int t = x % y;
        x = y;
        y = t;
    }
    return x;
}
public int LCM(int x, int y){
    if(x == 0 || y == 0) return 0;
    return x * y / gcd(x, y);
}

代码-冰雹数列

public class HailSerial {
    int[] len;//算法长度
    int[] end;//终止值
    int n;//上限
    int ring;//临时变量,环值
    int ring_pre;//环尾值
    public void hail(int n){
        this.n = n;
        len = new int[n + 1];
        end = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ring = -1;
            //貌似只能使用哈希表，假设我们不知道终点是1，且终点可以是任何数字
            dfs(-1, i, new HashMap<>(), 1);
        }
    }
    private Pair<Integer, Integer> dfs(int last, int cur, Map<Integer, Integer> mp, int dep) {
        if(cur <= n && len[cur] > 0) return new Pair<>(len[cur], end[cur]);
        if(mp.containsKey(cur)){//发现环入口
            ring = cur;//设置环值并开始归的操作
            ring_pre = last;//设置环外的终止值
            return new Pair<>(dep - mp.get(cur), -1);
        }
        mp.put(cur, dep);
        Pair<Integer, Integer> s;
        if(cur % 2 == 0){
            s = dfs(cur, cur / 2, mp, dep + 1);
        }else {
            s = dfs(cur,cur * 3 + 1, mp, dep + 1);
        }
        Pair<Integer, Integer> rs;
        if(ring != -1){//还在环内
            if(cur == ring){//找到环入口，开始出环
                rs = new Pair<>(s.getKey(), ring_pre);
                ring = -1;
            }else {//还在环内，终止值是上一个，算法长度为环长
                rs = new Pair<>(s.getKey(), last);
            }
        }else {
            rs = new Pair<>(s.getKey() + 1, s.getValue());
        }
        if(cur <= n){
            len[cur] = rs.getKey();
            end[cur] = rs.getValue();
        }
        return rs;
    }
    @Test
    public void test(){
        hail(100);
        for (int i = 1; i <= 100; i++) {
            System.out.println(i + ":" + len[i] + ":" + end[i]);
        }
    }
}

第六章 线性方程与最大公因数

习题6.1

​ (a) 求方程

的一组整数解。
​ (b)求方程

的一组整数解。

(a) $(11,-2)$ (b) $(8231,-45273)$

习题6.2

​ 求下述方程的所有整数解：

• (a) $105x+121y=1$
• (b) $12345x+67890y=gcd(12345,67890)$
• (c) $54321x+9876y=gcd(54321,9876)$

(a) $(68-121k,-59+105k)$
(b) $(11-\frac{67890}{15}k,-2+\frac{12345}{15}k)=(11-4526k,-2+823k)$
(c) $(8231-\frac{9876}{3}k,-45273+\frac{54321}{3}k)=(8231-3292k,-45273+18107k)$

习题6.3

​ 本章叙述的求解$ax+by=gcd(a,b)$包含相当多的代数运算与回代。本题描述计算 $x$ 与 $y$ 的另一种方法，它容易在计算机上应用。

• (a) 证明图6.1中的算法能计算$a$ 与 $b$ 的最大公因数 $g$ 以及方程 $ax+by=gcd(a,b)$的一组特解 $(x,y)$.

  $$\begin{array}{cl}(1)& 置x=1,g=a,v=0与w=b.\\ (2)& 如果w=0，则置y=(g-ax)/b并返回值(g,x,y).\\ (3)& g除以w得到余数t，g=qw+t(0\le t<w).\\ (4)& 置s=x-qv\\ (5)& 置(x,g)=(v,w)\\ (6)& 置(v,w)=(s,t)\\ (7)& 转到第2步\end{array}$$

• (b) 运用你使用的计算机语言，在计算机上运行上述算法。

• (c) 用你的程序对下述有序对$(a,b)$计算$g=gcd(a,b)$以及 $ax+by=gcd(a,b)$的整数解.

  • (i) $(19789,23548)$ (ii) $(31875,8387)$ (iii) $(22241739,19848039)$

• (d) $b=0$时你的程序出问题吗？修改程序使得程序能正确处理这种情况。

• (e) 为了后面的应用，求出$x>0$是有用的。修改你的程序，使得程序总能得到$x>0$的解。(提示：如果$(x,y)$是解，则$(x+b,y-a)$也是解。)

(a) $x_0=1，g_0=a,x_1=0,g_1=b,q_1=0$,且有递推公式$x_i=x_{i-2}-q_i{x}_{i-1},g_i=g_{i-2}-q_i{g}_{i-1},q_i=\lfloor \frac{g_{i-2}}{g_{i-1}}\rfloor$,当$g_i=0$时返回$(g_{i-1},x_{i-1})$。使用矩阵法观察， 可以发现 $x_i$ 与 $g_i$ 具有相同的迭代矩阵。$\left(\begin{array}{cc}a& b\end{array}\right)\left(\begin{array}{cc}{x}_0& x_1\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}{g}_0& g_1\end{array}\right)⟹\left(\begin{array}{cc}a& b\end{array}\right)\left(\begin{array}{cc}{x}_0& x_1\\ 0& 1\end{array}\right)\prod _{k=2}^i\left(\begin{array}{cc}0& 1\\ 1& -q_i\end{array}\right)=\left(\begin{array}{cc}{g}_0& g_1\end{array}\right)\prod _{k=2}^i\left(\begin{array}{cc}0& 1\\ 1& -q_i\end{array}\right)$​
(b) 见代码部分
(c) (i) $(1303,-1095,7)$ (ii) $(8006,-30427,1)$ (iii) $(19839059,-22231676,237)$​
(d) 见代码部分
(e) 见代码部分

习题6.4

​ (a) 求方程

的整数解$x,y,z$.
​ (b) $a,b,c$ 满足什么条件时方程

有整数解？当有解时给出求解的一般方法.
​ (c) 使用 (b) 中的方法求方程

的一组整数解.

(a)$(1-5k_1-10k_2,1+2k_1-4k_3,-1+3k_2+3k_3)$​
(b) 答： $a,b,c$满足 $(a,b,c)=1$时有整数解

• (i) 求解 $gcd(a,b)=(x_0,y_0,g_0)\to a{x}_0+b{y}_0=g_0(1)$
• (ii) 求解$gcd(g_0,b)=(x_1,y_1,g_1)$ 且$g_1\ne 1$时方程无整数解，$g_0{x}_1+c{y}_1=1(2)$.
• (iii) 联和(1) (2)求得一组特解， $a{x}_0{x}_1+b{y}_0{x}_1+c{y}_1=1(x_0{x}_1,y_0{x}_1,y_1)$​
• (iv) 求得所有整数解 $(x_0{x}_1-\frac{b{k}_1}{gcd(a,b)}-\frac{c{k}_2}{gcd(a,c)},y_0{x}_1+\frac{a{k}_1}{gcd(a,b)}-\frac{c{k}_3}{gcd(b,c)},y_1+\frac{a{k}_2}{gcd(a,c)}+\frac{b{k}_3}{gcd(b,c)})$​

(c) $(155,341)=(-2,1,31)$，$(31,385)=(-149,12,1)\to (1,-14,12)$

习题6.5

​ 假设 $gcd(a,b)=1$. 证明对每个整数 $c$，方程$ax+by=c$ 有整数解 $x$ 与 $y$ . (提示：先求$ax+by=1$ 的解再乘以 $c$ .)求方程$37x+47y=103$的一组解，尽量让$x,y$比较小.

$(37,47)=(14,-11,1)⟹(14\times 103,-11\times 103,103)\to (1442-47\times 31,-1133+37\times 31,103)=(-15,14,103)$

习题6.6

​ 有时我们仅对方程$ax+by=c$的非负整数解感兴趣.

• (a) 解释为什么方程$ax+5y=4$没有整数解 $x\ge 0$ 与 $y\ge 0$.

• (b) 制作形如$3x+5y(x\ge 0,y\ge 0)$的数值表，给出不可能出现的数值的猜想，然后证明你的猜想是正确的。

• (c) 对 $(a,b)$的下述值，求不能表示成 $ax+by(x\ge 0,y\ge 0)$​形式的最大整数.

  ​ (i) $(a,b)=(3,7)$ (ii) $(a,b)=(5,7)$ (iii) $(a,b)=(4,11)$

• (d) 设$gcd(a,b)=1$.使用 (c) 中的结果猜想出不能表示成$ax+by(x\ge 0,y\ge 0)$形式的最大整数(用 $a$ 与 $b$ 表示)。对$(a,b)$的至少两个值检验你的猜测。

• (e) 证明你在 (d) 中猜出的公式是正确的.

• (f) 试将上述问题推广到三项和 $ax+by+cz(x\ge 0,y\ge 0,z\ge 0)$.例如，不能表示成 $6x+10y+15z(x\ge 0,y\ge 0,z\ge 0)$的最大整数是什么。

(a) $\because x\ge 0,y\ge 0,ax+5y=4\therefore y=0\therefore x=\frac{4}{a}$???懵了，这不是在特定情况下有解么

(b)

$$\begin{array}{cccccc}0& 5& 10& 15& 20& 25\\ 3& 8& 13& 18& 23& 28\\ 6& 11& 16& 21& 26& 31\\ 9& 14& 19& 24& 29& 34\\ 12& 17& 22& 27& 32& 37\end{array}$$

猜想$(a,b)=1$时， $ax+by(x\ge 0,y\ge 0)$不能表示的最大数为 $ab-a-b$
(c) (i) $(3,7)=3\times 7-3-7=11$ (ii) $(5,7)=5\times 7-5-7=23$ (iii) $(4,11)=4\times 11-4-11=29$
(d) 如(b)中所猜想.
(e) 证：$(a,b)=1$时， $ax+by(x\ge 0,y\ge 0)$不能表示的最大数为 $ab-a-b$

1. 假设存在 $(x,y)$ 使得 $ax+by=ab-a-b$， 则有$ab=a(x+1)+b(y+1)$
   ​ $\because a\mid ab\text{且}a\mid a(x+1)⟹a\mid b(y+1)$
   ​ 又$\because y\ge 0\text{且}(a,b）=1\therefore y+1=a⟹a(x+1)=0⟹x+1=0$，与$x\ge 0$矛盾，$⟹ax+by(x\ge 0,y\ge 0)\text{无法表示}ab-a-b$

2. 令$M=ab-a-b+m(m>0)$

   $\because (a,b)=1,\therefore 存在(x^{\prime },y^{\prime })使得a{x}^{\prime }-b{y}^{\prime }=1(x^{\prime }\ge 0,y^{\prime }\ge 0)$

   等式两边同时乘以 $m$ 可得$am{x}^{\prime }-bm{y}^{\prime }=m,M=a(m{x}^{\prime }-1)+b(a-1-m{y}^{\prime })$​

   若$m{y}^{\prime }\ge a,\text{可令}p=\lfloor \frac{m{y}^{\prime }}{a}\rfloor ,可得0\le m{y}^{\prime }-pa<a即0\le m{y}^{\prime }-pa<=a-1$

   $\because m{y}^{\prime }-pa\ge 0\text{和}a(m{x}^{\prime }-pb)-b(m{y}^{\prime }-pa)=m>0\therefore m{x}^{\prime }-pb>0$​

   $\therefore M=a(m{x}^{\prime }-pb-1)+b(a-1-m{y}^{\prime }+pa)\text{其中}m{x}^{\prime }-pb-1\ge 0,a-1-m{y}^{\prime }+pa\ge 0$

   即对所有$M=ab-a-b+m(m>0)$都可以表示成 $ax+by(x\ge 0,y\ge 0)$​的形式

(f) 但$(a,b,c)=1$时， 设$ax+by+cz(x\ge 0,y\ge 0,z\ge 0)$不能表示的最大数为M，则有

$$\{\begin{array}{ll}c>\frac{ab}{(a,b{)}^2}-\frac{a}{(a,b)}-\frac{b}{(a,b)}& M=\frac{ab}{(a,b)}+c\times (a,b)-a-b-c\\ others& M\le \frac{ab}{(a,b)}+c\times (a,b)-a-b-c\end{array}$$

$M=\frac{6\times 10}{(6,10)}+15\times (6,10)-6-10-15=\frac{60}{2}+15\times 2-31=29$

行列式求解GCD

​ 有时候我们会思考，如果身边只有纸和笔，如何快速有效的算出$(x,y,g)$， 现提供一种有效的方法， 行列式法。以$(6,10,15)$为例。（虽然这种方法是我临时想出来的，但我觉得它早已有之）

​ 那如何用行列式求通解系数呢,观察上式行列式计算结果，取第一行和第三行(行列式右边为0的行)。

代码-乘法逆元GCD法

public int[] _gcd(int a, int b) {
    if(a == 0) return new int[]{0, 1, b};
    if(b == 0) return new int[]{1, 0, a};
    int x = 1, g = a, v = 0, w = b;
    while (w > 0) {
        int q = g / w;
        int t = g % w;
        int s = x - q * v;
        x = v;
        g = w;
        v = s;
        w = t;
    }
    x %= v;
    if(x < 0) x += Math.abs(v);
    int y = (g - a * x) / b;
    //特别地，当g = 1时，称 x 是 a 模 b 下的乘法逆元
    return new int[]{x, y, g};
}

其他

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