整数的可除性

一、整除的概念

1. 什么是 b 整除 a 或 a 被 b 整除？因数、倍数的定义？对“定义域”有什么要求？什么是不整除？

2. 若 c|a，c|b，那么 c|(sa+tb)吗？

3. 对于一个数而言，什么是显然因数？素数和合数的定义？没有特别声明时素数总是指正整数。什么是安全素数？什么是索菲热尔曼素数？

4. n 为正合数，p 是大于 1 的 n 的最小正因数，那么 p 有怎样的性质？怎么证明？

5. 爱拉托斯散筛法是怎么筛出素数的？什么是素数的平凡判别？
   查看参考代码。

6. 证明素数有无穷多个？

7. 欧几里得除法（对于最小非负余数）、不完全商、余数定义？怎么证明（存在性，唯一性）？怎么证明一般余数形式的欧几里得除法？注意最小非负余数和最小正余数。
   查看求商、余数参考代码。

8. 什么是 x 的整数部分？

二、最大公因数

1. 公因数、最大公因数、互质的定义。(0, b) 是多少？a = qb + c 和最大公因数有什么关系，以及这一关系有什么定义域要求？如何证明这一关系？
   如果素数不是另一整数的因数，那么这两数互素。

2. 有哪个算法是用来求解最大公因数的？证明此算法。P23。可以用哪种余数来简化计算？P24
   查看参考代码。

3. 什么是贝祖等式？贝祖等式怎么用来判断互素？怎么证明贝祖等式？（个人认为可以参考百度百科）怎么求其中的 s，t？P25 ad-bc=1 时 a，b，c，d 满足什么关系？P33
   查看参考代码求 s、t。

4. 当正整数 d 满足：(i) d|a，d|b (ii) 若 e|a，e|b，则 e|d ；那么 d =(a, b) 是充要的吗？如何证明？P33

5. m 是正整数时，(m·a, m·b) 等于？$(\frac{a}{d},\frac{b}{d})$ 在   条件下可以进行哪种变形？怎么证明？P33

6. 当 (a, c) = 1 时 (ab, c) 等于？如何证明？P34
   “加入互素成分不影响最大公因数”

7. 如果 (a_i, c) = 1，那么 (a₁a₂…a_n, c) 等于多少？证明。P35（我觉得可以用标准分解式）

8. a=qu+rv，b=su+tv，qt-rs=1 时 (a, b) 和 (u, v) 有什么关系？P35

9. 如何递归计算多个整数的最大公因数？P36

10. 当 a 和 b 是两个正整数时，2^a-1 和 2^b-1 的最大公因数是多少？证明。（提示：往指数的对应关系+广义欧几里得算法上靠）P37

11. c|ab，(a, c)=1，那么 c 和 b 存在什么关系？证明。P37
    “扣去互素成分不影响是否是因数”

12. p 是素数，p|a₁a₂，能得什么？扩展到 a_n 呢？证明。P38
    “两数之积能被素数整除，则这两数必有一个能被素数整除。”
    上面部分证明主要用 d|a，a|d → a=d，存在 s，t 使得 sa+tb=(a,b)

三、最小公倍数

1. 公倍数的定义？最小公倍数的定义？P38
   “最小公倍数是其他公倍数的因数，最大公因数是其他公因数的倍数”
2. [ma, mb] 在什么时候等于 m[a, b]？怎么证明？P39，P50T39
   证明，利用最小公倍数的定义。
3. [a, b]，ab 和 (a, b) 有什么关系？怎么证明？
   （共有的成分在最小公倍数里只计算入一次，即要从乘积里面扣除去最大公因数）

四、算术基本定理

1. 什么是算术基本定理？怎样证明？P42

2. 什么是 n > 1 整数的标准分解式？P43；d 是 n 的正因数，则其标准分解式之间存在什么关系？是充要的吗？证明。P44；某个数的正因数个数和其标准分解式之间存在什么关系？P44；两数的最大公因数和最小公倍数与其标准分解式有什么关系？怎么证明？P45；多个数呢？

3. 是否能找出 a 的因数 a’，b 的因数 b’ 且 a’，b’ 互素，使得 [a, b]=a’b’？证明。P46
   （对于两数都有的成分，要删去一边）

五、整数的表示

1. 正整数 n 在什么条件下能用 b 的 0 到 k-1 次幂线性表出？这种表示具有怎样的性质？怎样证明？P9
   （证明和欧几里得除法有些类似）

2. 什么是整数 n 的 b 进制表示？

3. 怎样进行进制转换？

4. 怎样进行 b 进制加、减、乘法运算？