整除的可能性

我也不知道应该怎么整理这个笔记，先整理着试一试吧

整除的一些概念

b整除a记作 $b|a$
当b遍历整数a的所有因子时，-b和 $\frac{a}{b}$ 也遍历a的所有因数
特殊数字的整除：
- 0是任何非零整数的倍数
- 1是任何整数的因数
- 任何非零整数a数其自身的倍数，也是其自身的因数
整除具有传递性：
- 若 $b\mid a ，c\mid b$
整除的性质在加法和减法运算以及线性组合中都是可以保持
- 若 $c | a,c|b$ 被 c 整除
这个整数也可以被推广到多个整数的线性组合
如果两个数互相整除，那么这两个数不是相等就是互为相反数
素数
- 总是正整数
- 从了1和自身没有一个数再能整除它了
- 如何快速的找到素数？==》平凡除法 / 厄拉托赛师（Eratosthenes）算法
- 素数有无穷多个
欧几里得除法——最小非负余数
设a,b是两个整数，其中b>0，则存在唯一的整数q和r使得 $a = q \cdot b + r, 0 < r < b$ ，q叫做a被b除所得的不完全商

最大公因子与广义欧几里德除法

最大公因数：因数中最大的一个，a和b的最大公因数记作（a，b）
一堆不全为0的数的公因数与这堆数加上绝对值后的公因数相同
Bezout等式的计算 ==》太难说明了，结合矩阵图理解吧
广义欧几里得算法：简单的来说就是当两个数比较大的时候来求这两个数的最大公因子，时间复杂度为O(n)

"""
贝祖公式的实现
"""
import math

j = []
s_j = []
t_j = []
q_j_1 = []
r_j_1 = []

# 规定a和b
a = 3589
b = 1613
temp_a = a
temp_b = b
# 先求r_j_1和q_j_1
r_j_1.append(temp_a)
r_j_1.append(temp_b)
while temp_a % temp_b != 0:
    # 向下取整
    q = math.floor(temp_a / temp_b)
    q_j_1.append(q)
    r_j_1.append(temp_a - temp_b * q)
    temp = temp_b
    temp_b = temp_a - temp_b * q
    temp_a = temp
# r_j_1.append(0)
# q_j_1.append(math.floor(a / b))

# 求s_j 和 t_j    q12
# 初始化s_j 和 t_j
s_j.append(1)
t_j.append(0)
s_j.append(0)
t_j.append(1)
for i in range(len(q_j_1)):
    s_j.append(-q_j_1[i] * s_j[i + 1] + s_j[i])
    t_j.append(-q_j_1[i] * t_j[i + 1] + t_j[i])

print(r_j_1)
print(q_j_1)
print(s_j)
print(t_j)
print(s_j[-1] * a + t_j[-1] * b)

最大公因子进一步的性质
- 如何找到两个较小的互素的整数，或者说如何构造互素的整数
$(\frac{a}{(a \cdot b)},\frac{b}{(a,b)}) = 1$
- m为任意个正整数，则 $m \cdot a,m \cdot b = m \cdot (a \cdot b)$
- 若非零整数d满足，d｜a且d｜b，则
$(\frac{a}{d},\frac{b}{d}) = \frac{(a,b)}{|d|}$
- 设a，b，c是三个整数，且 $b \neq 0,c \neq 0$ 如果（a，c）= 1 则
$(ab,c) = (b,c)$
- 如果c和一组数中的每一个数都互素，则它和这一组数的乘积也互素
- 设a，b，u，v都是不全为0的整数，如果
$a = q \cdot u + r \cdot v,b=s \cdot + t \cdot v,$

其中q, r , s, t是整数，且 $q \cdot t - r \cdot s = 1$ ，则(a,b) = (u,v)
- 如果计算多个数的最大公因数？ == 》两个两个算即可
- $2^\alpha-1$ 的整数及其最大公因数
  - 设a和b是两个正整数，则 $2^a-1和2^b-1除的最小非负余数是2^r-1,其中r是a被b除的最小非负余数$
  - $2^a-1和2^b-1的最大公因数是2^{(a,b)}-1$
整除的进一步性质
- 如果 c ｜ ab，（a，c）=1，则c｜b。其实很好理解因为a和c的最大公因子为1了，就可以推出来c一定是可以整出b的。
如果 p ｜ab 则 p｜a 或 p｜b ，这个也是比较明显的
最小公倍数
- a和b的最小公倍数记作 $[a,b]$
若a｜D，b｜D，则[a,b] | D;
- 最小公倍数的一种计算方法（最小公倍数与最大公因数的关系）： $[a,b] = \frac{a \cdot b}{(a \dot b)}$
- 如何计算多个最小公倍数？==》两个两个计算
整数分解
- 整数分解定理

重要知识点

如何证明一个数是素数：

用Eratosthenes筛法（平凡判别P7）具体：对于一个数n，所有 $p< n^{1/2}$ ，均无法整除n，则n是一个素数
其欧拉函数即 $φ(m)=m−1$ 的时候，m是一个素数 P68
对于模m的最小正数完全剩余系等于其最小正数简化剩余系的时候，m是一个素数
利用Wilson定理，如果一个整数n， $(n-1)!+1 \equiv 0 (mod \ n)$ 时，n是一个素数 P118

N的B进制的表示： P9

$N = A_{k-1}B_{k-1}+......+A_1B+A_0$

如何确定一个整数d是 $a_n ...... a_0$ 的最大公因数： P20

（1） $d|a_n,d|a_{n-1}...,d|a_0$

（2）对于一个数e，若 $e|a_n ... e|a_0$ 则e|d;

如何计算两个数的最大公因数？

1.广义欧几里得除法： P22

利用（a，b）=（b，c），一步一步的缩小

2.贝祖公式 P25 🌿

贝祖等式：sa+tb=（a，b）证明在 P27

如何求s和t？

上面已经给出了Python代码的实现；

3. 如果形式为 $(2^a-1,2^b-1)$

其最大公因数为 $2^{(a,b)}-1$ ,P37

4. 如果知道最小公倍数 P39

$(a,b)=\frac{a \cdot b}{[a,b]}$

如何确定一个整数D是 $a_1 ... a_n$ 的最小公倍数？ P39

（1） $a_i | D$

（2）若 $a_i|D'$ ,则D｜D’

如何构造两个互素的数？

利用基础性质

$(\frac{a}{(a.b)},\frac{b}{a.b})=1$
构造一个ad-bc=1 则(a , b) = 1
通过一个已知的（u，v）= 1构造出（a，b）= 1 P35

$\begin{gathered} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} q & r \\ s & t \end{pmatrix}\begin{pmatrix} u \\ v \end{pmatrix} \end{gathered}$