初等数论
threediamond
·
2024-02-03 18:12:39
·
个人记录
定义1：
如果 a 和 b 为整数且 a≠0 ，我们说 a 整除 b 是指存在整数 c 使得 b=ac 。如果 a 整除 b ，我们还称 a 是 b 的一个因子，且称 b 是 a 的倍数。a 整除 b ，则将其记为 a|b ，如果 a 不能整除 b ，则记其为 a ∤b 。
定理1:
如果 a ， b 和 c 是整数，且满足 a|b ， b|c ，则 a|c 。
证明：
因为 a|b ， b|c ，故存在整数 e 和 f ，使得 ae=b ，bf = c 。c = bf = (ae)f = a(ef) ，从而得到 a|c 。
例如：因为 11|66 ，66 | 198 ，故由定理1 可知 11 | 198 。
定理2:
如果 a ，b ，m 和 n 为整数，且 c | a ，c | b ，则 c | (ma+nb) 。
证明：
因为 c | a 且 c | b ，故存在整数 e 和 f ，使得 a = ce ，b = cf 。ma + nb = mce + ncf = c(me + nf) ，从而 c | (ma+nb) 。
例如：由于3 | 21 ，3 | 33 ，故由定理2 可知 3 能够整除 5*21 - 3*33 = 105 - 99 = 6 。
定理3:带余除法
如果 a 和 b 是整数且 b > 0 ，则存在唯一的整数 q 和 r ，使得 a = bq + r , 0 ≤ r < b 。
在带余除法给出的公式中，我们称 q 为商， r 为余数，我们还称 a 为被除数， b 为除数。
例如：如果 a=133 ，b=21 ，则 q=6 ，r=7 ，因为 133-21*6+7 且 0<7<21 。a=-50 ，b=8 ，则 q=-7 ，r=6 ，因为 -50 = 8*(-7)+6 且 0<6<8 。
我们注意到 a 能被 b 整除当且仅当在带余除法中的余数为 0 。
证明:
1.存在性
考虑形如 a-bk 所有整数集合 S ，其中 k 为整数。设 T 是 S 中的所有非负整数构成的集合， T 是非空的，因为当 k 是满足 k <\frac{a}{b} 的整数时，a-bk 是正的。 T 中有最小元 r = a-bq 。( q 和 r 的值如定理中所述。)r 的构造可知 r ≥ 0 ，且容易证明 r < b 。r≥b ，则 r > r-b = a - bq - b = a - b(q+1) ≥ 0 ，这与我们选择 r=a-bq 为形如 a-bk 的整数中的最小元矛盾，因此 0 ≤ r < b 。
2.唯一性
为了证明 q 和 r 的值是唯一的，我们假定有两个方程 a=b*q1+r1 和 a=b*q2+r2 ，满足 0 ≤ r1<b ，0≤r2<b ，把第二个方程从第一个方程中减去，可得 0 = b(q1-q2)+(r1-r2) 。
因此，r2 - r1 = b(q1-q2) ，由此可知 b 整除 r2-r1 。因为 0≤r2<b ，0≤r1<b ，故-b<r2-r1<b ，因此 b 可以整除 r2-r1 只有当 r2 - r1=0 ，或者，换句话说，当 r1 = r2 时，因为 bq1+r1 = bq2+r2 ，且 r1 = r2 ，我们还得到 q1=q2 ，这说明商 q 与余数 r 是唯一的。
定义2:
不全为零的整数 a 和 b 的最大公因子 是指能够同时整除 a 和 b 的最大整数。
$\gcd(0,n) = \gcd(n,0) = n$，虽然所有的正整数都能整除 $0$ ，我们还是定义 $\gcd(0,0) = 0$ (这样可以确保关于最大公因子的相关结论在所有情况下均成立)。
例如： $24$ 和 $84$ 的公因子有 $±1$，$±2$，$±3$，$±4$，$±6$，$±12$，因此 $\gcd(24,84) = 12$ 。类似地，通过查看公因子集合，我们有 $\gcd(0,44)=44$，$\gcd(-6,-15)=3$，$\gcd(-17,289) =17$ 。
# 定义3:
设 $a$ , $b$ 均为非零整数，如果 $a$ 和 $b$ 最大公因子 $\gcd(a,b)=1$，则称 $a$ 与 $b$ 互素。
**注意:** 由于 $-a$ 的因子与 $a$ 的因子相同，故有 $\gcd(a,b)=\gcd(|a|,|b|)$，其中 $|a|$ 表示 $a$ 的绝对值，因此，我们只关注正整数对的最大公因子。
# 定理4:
$a$，$b$ 是整数，且 $\gcd(a,b)=d$，那么 $\gcd(\frac{a}{d},\frac{b}{d})=1$。(换言之，$\frac{a}{d}$ 与 $\frac{b}{d}$ 互素。)
## 证明:
已知 $a$，$b$ 是整数，且 $\gcd(a,b)=d$ 。我们将证明 $\frac{a}{d}$，$\frac{b}{d}$ 除了 $1$ 之外没有其他的公因子。假设还有正整数 $e$ 使得 $e|(\frac{a}{d})$ 且 $e|(\frac{b}{d})$，那么存在整数 $k$ 和 $l$ 使得 $\frac{a}{d}=ke$，$\frac{b}{d}=le$，于是 $a=dek$，$b=del$。因此 $de$ 是 $a$，$b$ 的公因子，又因为 $d$ 是 $a$, $b$ 的最大公因子，故 $de ≤ d$，于是 $e=1$。因此 $\gcd(\frac{a}{d},\frac{b}{d})=1$。
________________
一个分数 $\frac{p}{q}$ 被称为是既约分数，当且仅当 $\gcd(p,q)=1$ 。下面的结论告诉我们每一个分数都与一个既约分数相等.
# 推论1:
如果 $a$，$b$ 为整数，且 $b≠0$，则 $\frac{a}{b}=\frac{p}{q}$，其中 $p$，$q$ 为整数，且 $\gcd(p,q)=1$，$q≠0$ 。
## 证明:
假设 $a$，$b$ 为整数且 $b≠0$，令 $p=\frac{a}{d}$，$q=\frac{b}{d}$，其中 $d=\gcd(a,b)$，则 $\frac{p}{q}=\frac{a}{d} / \frac{b}{d}$ , 由**定理4**可知$\gcd(p,q)=1$，命题得证。
# 定理5:
令 $a$，$b$，$c$ 是整数，那么 $\gcd(a + cb,b) = \gcd(a,b)$ 。
## 证明：
令 $a$，$b$，$c$是整数，证明 $a$，$b$ 的公因子与 $a+cb$，$b$ 的公因子相同，即证明 $\gcd(a+cb,b)=\gcd(a,b)$ 。
令 $e$ 是 $a$，$b$ 的公因子，由**定理2**可知 $e|(a+cb)$，所以 $e$ 是 $a+cb$ 和 $b$ 的公因子。以此类推，如果 $f$ 是 $a+cb$ 和 $b$ 的公因子，由**定理2**可知 $f$ 整除 $(a+cb)-cb= a$，所以 $f$ 是 $a$，$b$ 的公因子，因此$\gcd(a+cb,b)=\gcd(a,b)$。
# 定义4
如果 $a$，$b$ 是整数，那么它们的线性组合具有形式 $ma+nb$，其中 $m$，$n$ 都是整数。
# 定理6
两个不全为零的整数 $a$，$b$ 的最大公因子是 $a$，$b$ 的线性组合中最小的正整数。
## 证明
令 $d$ 是 $a$，$b$ 的线性组合中最小的正整数，$d = ma + nb$ , 其中 $m$，$n$ 是整数，我们先要证明 $d|a$，$d|b$ 。
由带余除法，得到 $a=dq+r$ , $0≤r<d$ 。
由 $a=dq+r$ 和 $d=ma+nb$，得到 $r=a-dq=a-q(ma+nb)=(1-qm)a-qnb$ 。
这就证明了整数 $r$ 是 $a$ , $b$ 的线性组合。因为 $0 ≤ r < d$，而 $d$ 是 $a$ , $b$ 的线性组合中最小的正整数，于是我们得到 $r=0$（如果 $r$ 不是等于 $0$，那意味着 $r$ 才是所有线性组合中最小的正整数，这与 $d$ 是所有线性组合中最小的正整数矛盾），因此 $d|a$，同理可得 $d|b$ 。
我们证明了 $a$ , $b$ 的线性组合中最小的正整数 $d$ 是 $a$ , $b$ 的公因子，剩下要证的是它是 $a$ , $b$ 的最大公因子，即证明 $a$ , $b$ 所有的公因子都能整除 $d$ :
由于 $d = ma + nb$，因此如果 $c | a$ 且 $c | b$，那么由**定理2**有 $c|d$，因此 $d > c$，这就完成了证明。
# 定义5
令 $a1$，$a2$，…，$an$ 是不全为零的整数，这些整数的公因子中最大的整数就是最大公因子。
$a1$，$a2$，…，$an$ 的最大公因子记为 $\gcd(a1,a2,…,an)$ 。(**注意:** $ai$ 在这里面出现的顺序并不影响结果。)
# 引理1
如果 $A1$，$A2$，…，$An$，是不全为零的整数，那么 $\gcd(A1,A2,…,An-1,An) = \gcd(A1,A2,…,An-2,\gcd(An-1,An) )$。
## 证明
$n$ 个整数 $A1$，$A2$ ，…，$An-1$ 和 $An$ 的任意公因子也是 $An-1$ 和 $An$ 的公因子，因此也是 $\gcd(An-1,An)$ 的因子。
同样 $n$ 个整数 $A1$，$A2$，…，$An-2$ 和 $\gcd(An-1,An)$ 的公因子也是 $n$ 个整数 $A1$，$A2$，…，$An-1$，$An$的公因子，因为如果某整数整除 $\gcd(An-1,An)$，那么它一定同时整除 $An-1$ 和 $An$ 。
因此，这 $n$ 个整数的公因子和由前 $n-2$ 个整数与后两个整数的最大公因子组成的集合的公因子完全相同，它们的最大公因子也一定相同。
# 欧几里得算法：
用**辗转相除法**求，即 $\gcd(a,b)=\gcd(b,a\mod b) $ 。
$\gcd$ 函数代码如下：
```cpp
int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}
```
## 证明1
由**定理3**带余除法，存在整数 $q$ , $r$ 使得 $a = bq + r$ , $0 ≤ r <b$ , 得到 $r = a - bq$ 。
由**定理5**得:$\gcd(a,b) = \gcd(a-bq,b) = \gcd(r,b) = \gcd(a\mod b,b) = \gcd(b,a\mod b)$。
## 证明2
令 $d=\gcd(a,b)$，证明 $d | \gcd(b,a\mod b)$，再反证 $\gcd(b,a\mod b) > d$ 是不可能的。
## 时间复杂度的证明
### 设a>b,则分两种情况：
$1$. $b < \frac{a}{2}$，经过一次辗转得到 $\gcd(b,a\mod b)$, $\max(a,b)$ 至少缩小一半。
$2$. $b >=\frac{a}{2}$，经过两次辗转得到彼时的 $\max(a,b)$ 至少缩小一半。
综上所述，最多 $2*\log(n)$ 次辗转算法结束。
更精确的时间复杂度，请参考[拉梅定理](https://en.wikipedia.org/wiki/Gabriel_Lam%C3%A9)等。
# 裴蜀定理：
如果 $a$ 与 $b$ 均为整数，则存在整数 $x$ 和 $y$ 满足 $ax + by = \gcd(a,b)$ 。
由**定理6**容易证明正确性。
下面用扩展欧几里得算法($exgcd$)求出满足 $ax + by = \gcd(a,b)$ 的一个特解。
例如：$a = 99$ , $b = 78$ , 令 $d =\gcd(a,b) = \gcd(99,78) = 3$，求 $99x + 78y = 3$ 的一个特解。那我们就在调用 $exgcd$ 的时候，从后往前依次构造出相应的解。
**那问题来了，如何构造关于 $ax + by = \gcd(a,b)$ 的特解呢，请看下文分解：**
众锁粥汁，在用欧几里得算法求 $\gcd(99,78)$ 的时候，是要先求 $\gcd(78,21)$ 。
假设我们已经求出 $78x + 21y = 3$ 的一个解 $\{x0,y0\} = \{3,-11\}$，即 $78*x0 + 21*y0 = 3$。
那么可以由 $78*x0 + 21*y0 = 3$ ，构造出 $99x + 78y = 3$ 的一个特解。
因 $a=99$ , $b=78$ , $a\mod b=21$ , 因此 $78*x0 + 21*y0 = 3$，可以写成如下式子：
$b*x0 + (a\mod b)*y0 = 3
因为 a\mod b 可以表示为 a-\lfloor \frac{a}{b} \rfloor*b ， 所以以上式子可表示为：
b*x0 + (a-\lfloor \frac{a}{b} \rfloor*b)*y0 = 3
去括号得: b*x0+a*y0-\lfloor \frac{a}{b} \rfloor*b*y0=3
将 b 提取出来得：a*y0+b*(x0-\lfloor \frac{a}{b} \rfloor*y0)=3
通过上面式子的转换，我们发现 x 就相当于上面的 y0 , y 就相当于上面的 x0-\lfloor \frac{a}{b} \rfloor*y0 ，这样就解决问题了。
```cpp
void exgcd(long long a,long long b){//d为gcd(a,b),x和y为ax+by=gcd(a,b)的一个特解。
if(b==0){
d=a,x=1,y=0;
return ;
}
exgcd(b,a%b);
long long t=x;
x=y,y=t-(a/b)*y;
}
```
**注意**:若 $a<0$ 且 $b>=0$ ，那么在求 $ax+by=\gcd(a,b)$ 的时候，可以先求出 $|a|x+by=\gcd(|a|,b)$ 的一组解 $\{x0,y0\}$，然后 $\{-x0,y0\}$ 就是原方程的一个解。$a>=0$ , $b<0$ 和 $a<0$ , $b<0$ 的也同理。
# 定理7:
如果 $a$，$b$ 是正整数，那么所有 $a$，$b$ 的线性组合构成的集合与所有 $\gcd(a,b)$ 的倍数构成的集合相同。
## 证明:
假设 $d = \gcd(a,b)$ 。
($1$) 首先我们证明每个 $a$，$b$ 的线性组合是 $d$ 的倍数。首先注意到由最大公因子的定义，有 $d|a$ 且 $d|b$，每个 $a$ , $b$ 的线性组合具有形式 $ma+nb$，其中 $m$，$n$ 是整数。由**定理$2$**，只要 $m$，$n$ 是整数，$d$ 就整除 $ma+nb$，因此，$ma+nb$ 是 $d$ 的倍数。
($2$) 现在证明每一个 $d$ 的倍数也是 $\gcd(a,b)$ 的线性组合。由**定理$6$**，存在整数 $r$，$s$ 使得 $\gcd(a,b)=ra+sb$ 。而 $d$ 的倍数具有形式 $jd$，其中 $j$ 是整数。在方程 $d = ra + sb$ 的两边同时乘以 $j$，我们得到 $jd = (jr)a + (js)b$ 。
因此，每个 $d$ 的倍数是 $\gcd(a,b)$ 的线性组合。
# 推论2
整数 $a$ 与 $b$ 互素当且仅当存在整数 $m$ 和 $n$ 使得 $ma + nb = 1$ 。
## 证明
如果 $a$，$b$ 互素，那么 $\gcd(a,b)=1$，由**定理$6$** 可知，$1$ 是 $a$ 和 $b$ 的线性组合的最小正整数，于是存在整数 $m$，$n$ 使得 $ma + nb = 1$ 。
反之，如果有整数 $m$ 和 $n$ 使得 $ma + nb = 1$，则由**定理$6$** 可得 $\gcd(a,b)=1$，这是由于 $a$ , $b$ 不同为 $0$ 且 $1$ 显然是 $a$ , $b$ 的线性组合中的最小正整数。