数论

前言

本蒟蒻在写初赛题后听讲评时，听得一脸懵，发现对数论无所了解，于是疯狂地补，此博客在有生之年不会完结（吧），希望 hzxhzx 不会又说我。

符号

整除符号：x∣yx∣y

取模符号：xmodyxmody

互质符号：x⊥yx⊥y

最大公约数：gcd(x,y)gcd(x,y)

最小公倍数：lcm(x,y)lcm(x,y)

求和符号：∑∑

求积符号：∏∏

阶乘：n!n!（即 ∏ni=1i∏ni=1i）

注：0!=10!=1

向下取整：⌊x⌋⌊x⌋

向上取整：⌈x⌉⌈x⌉

数论基础概念

整除

整除的定义

设 a,b∈Z,a≠0a,b∈Z,a≠0。如果 ∃q∈Z∃q∈Z，使得 b=aqb=aq，那么就说 bb 可被 aa 整除，记作 a∣ba∣b，且称 bb 是 aa 的倍数，aa 是 bb 的约数（因数）。

注：bb 不被 aa 整除记作 a∤b。

整除的性质

• a∣b⟺−a∣b⟺−b∣a⟺|a|∣|b|

• a∣b∧b∣c⟹a∣c

• a∣b∧a∣c⟺∀x,y∈Z,a∣(xb+yc)

  证明：设 b=an,c=am，那么 xb+yc=xan+yam=a(xn+ym)。

• a∣b∧b∣a⟹b=±a

• 设 m≠0，那么 a∣b⟺ma∣mb

• 设 b≠0，那么 a∣b⟹|a|≤|b|

• 设 a≠0,b=qa+c，那么 a∣b⟺a∣c

约数和倍数

通过对倍数的定义，可得 0 是所有非 0 整数的倍数。（0 不可以做被除数）

对于任何整数 b≠0，对于 b 的约数只有有限个。

显然约数（显然因数）：对于整数 b≠0，±1、±b 是 b 的显然约数。当 b=±1 时，b 只有两个显然约数。

对于整数 b≠0，b 的其他约数为真约数（真因数、非显然约数、非显然因数）。

约数的性质

• 设整数 b≠0，当 d 遍历 b 的全体约数时，bd 也遍历 b 的全体约数。

• 设整数 b>0，则当 d 遍历 b 的全体正约数时，bd 也遍历 b 的全体正约数。

带余数除法

余数的定义

设 a,b 为两个给定的正整数，a≠0。设 d 是一个给定的整数。那么，一定存在唯一的一对整数 q,r，满足 b=qa+r(d≤r<|a|+d)。

无论整数 d 取何值，r 统称为余数。均有 a∣b 等价于 a∣r。

一般情况下，d 取 0，此时等式 b=qa+r(0≤r<|a|) 称为带余数除法（带余除法）。这里的余数 r 称为最小非负余数。

余数的另外两种常见取法

绝对最小余数：d 取 |a| 的一半的相反数。即 b=qa+r(−|a|2≤r<|a|−|a|2)。

最小正余数：d 取 1。即 b=qa+r(1≤r<|a|+1)。

带余数除法的余数只有非负最小余数。如果没有特殊证明，余数总是指最小非负余数。

余数的性质

• 任一整数被正整数 a 除后，余数一定是且仅是 0 到 (a−1) 这 a 个数中的一个。

• 相邻的 a 个整数被正整数 a 除后，恰好取到上述 a 个余数。特别的，一定有且仅有一个数被 a 整除。

最大公约数与最小公倍数

最大公约数（gcd）定义

一组整数的公约数，是指同时是这组数中每一个数的约数。±1 是任意一组整数的公约数。

那么最大公约数，顾名思义，就是这组数的公约数中最大的一个。

求最大公约数（欧几里得算法，也称辗转相除法）

设 ∀a,b∈Z(a>b)。

可以整除的情况：如果 b 是 a 的约数，那么 b 就是二者的最大公约数。

不可以整除的情况：a=bq+r（带余除法）,通过证明可得，gcd(a,b)=gcd(b,amodb)。

证明如下：

设 a=bq+r(r=amodb)，设 d∣a,d∣b（即 d 为 a b 的公约数）,则 r=a−bq,rd=ad−bdq。

由上面的式子可知 rd 为整数，那么可得 d∣r，所以 d 也会是 amodb 的公约数。

可得 a,b 与 a,amodb 的公约数相同，那么二者的最大公约数也相同。

即 gcd(a,b)=gcd(a,amodb)。

递归代码易得：

int gcd(int a,int b) {
	if(b==0) return a;
	return gcd(b,a%b);
}

最小公倍数（lcm）定义

一组整数的公倍数，是指同时是这组数中的每一个数的公倍数。0 是任意一组整数的公倍数。

顾名思义，一组整数的最小公倍数，是指所有正公倍数中最小的一个。

求最小公倍数

设 a=pka11pka22…pkann,b=pkb11pkb22…pkann。

对于 a 和 b，二者的最大公约数是 pmax(ka1,kb1)1pmax(ka2,kb2)2…pmax(kan,kbn)n

最小公倍数是 pmin(ka1,kb1)1pmin(ka2,kb2)2…pmin(kan,kbn)n

由于 ka+kb=max(ka,kb)+min(ka,kb)

所以 gcd(a,b)×lcm(a,b)=a×b，即 lcm(a,b)=a×b÷gcd(a,b)。

int gcd(int a,int b) {
	if(b==0) return a;
	return gcd(b,a%b);
}

int lcm(int a,int b) {
	return a*b*1.0/gcd(a,b);
}

互素

两个整数互素，即 gcd(a,b)=1。

多个整数互素，即 gcd(a1,…,an)。

多个整数互素，不一定任意两两互素。

素数和合数

素数与合数的定义

设 p≠0,±1。如果除了 p 的显然约数外 p 没有其他约数，那么称 p 为素数（不可约数）。

反之，若 p≠0,±1 且 p 不是素数，那么称 p 为合数。

若整数的因数是素数，则该素数成为该整数的素因数（素约数）。

素数与合数的性质

• 大于 1 的整数 a 是合数，等价于 a 可以表示为整数 d 和 e (1<d,e<a) 的乘积。

• 如果素数 p 有大于 1 的约数 d，那么 d=p。

• 大于 1 的整数 a 一定可以表示为素数的乘积。

• 对于合数 a，一定存在素数 p≤√a 使得 p∣a。

• 素数有无穷多个。

• 所有大于 3 的素数都可以表示为 6n+1 的形式。

算术基本定理（唯一分解定理）

算术基本引理

设 p 是素数，p∣a1a2，那么 p∣a1 和 p∣a2 至少有一个成立。

算法基本定理

设正整数 a，那么必有表示（素数与合数的性质）：

a=p1p2p3…pn

其中 pj(1≤j≤n) 是素数。

将上述表示中相同的素数合并可得标准素因数分解式：

a=pk11pk22pk33…pknn

算术基本定理与算法基本引理是等价的。