跳转至

数论基础

本文对于数论的开头部分做一个简介。

整除

定义

a,bZa0。如果 qZ,使得 b=aq,那么就说 b 可被 a 整除,记作 abb 不被 a 整除记作 ab

整除的性质:

  • ababab|a||b|
  • abbcac
  • abacx,yZ,a(xb+yc)
  • abbab=±a
  • m0,那么 abmamb
  • b0,那么 ab|a||b|
  • a0,b=qa+c,那么 abac

约数

定义

ab,则称 ba倍数ab约数

0 是所有非 0 整数的倍数。对于整数 b0b 的约数只有有限个。

平凡约数(平凡因数):对于整数 b0±1±bb 的平凡约数。当 b=±1 时,b 只有两个平凡约数。

对于整数 b0b 的其他约数称为真约数(真因数、非平凡约数、非平凡因数)。

约数的性质:

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

在具体问题中,如果没有特别说明,约数总是指正约数。

带余数除法

余数

a,b 为两个给定的整数,a0。设 d 是一个给定的整数。那么,一定存在唯一的一对整数 qr,满足 b=qa+r,dr<|a|+d

无论整数 d 取何值,r 统称为余数。ab 等价于 ar

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

余数往往还有两种常见取法:

  • 绝对最小余数:da 的绝对值的一半的相反数。即 b=qa+r,|a|2r<|a||a|2
  • 最小正余数:d1。即 b=qa+r,1r<|a|+1

带余数除法的余数只有最小非负余数。如果没有特别说明,余数总是指最小非负余数。

余数的性质:

  • 任一整数被正整数 a 除后,余数一定是且仅是 0(a1)a 个数中的一个。
  • 相邻的 a 个整数被正整数 a 除后,恰好取到上述 a 个余数。特别地,一定有且仅有一个数被 a 整除。

最大公约数与最小公倍数

关于公约数、公倍数、最大公约数与最小公倍数,四个名词的定义,见 最大公约数

Warning

一些作者认为 00 的最大公约数无定义,其余作者一般将其视为 0。C++ STL 的实现中采用后者,即认为 00 的最大公约数为 04

最大公约数有如下性质:

  • (a1,,an)=(|a1|,,|an|)
  • (a,b)=(b,a)
  • a0,则 (a,0)=(a,a)=|a|
  • (bq+r,b)=(r,b)
  • (a1,,an)=((a1,a2),a3,,an)。进而 1<k<n1, (a1,,an)=((a1,,ak),(ak+1,,an))
  • 对不全为 0 的整数 a1,,an 和非零整数 m(ma1,,man)=|m|(a1,,an)
  • 对不全为 0 的整数 a1,,an,若 (a1,,an)=d,则 (a1/d,,an/d)=1
  • (an,bn)=(a,b)n

最大公约数还有如下与互素相关的性质:

  • b|ac(a,b)=1,则 bc
  • b|ca|c(a,b)=1,则 abc
  • (a,b)=1,则 (a,bc)=(a,c)
  • (ai,bj)=1, 1in,1jm,则 (iai,jbj)=1。特别地,若 (a,b)=1,则 (an,bm)=1
  • 对整数 a1,,an,若 vZ, iai=vm,且 (ai,aj)=1, ij,则 1in, aimZ

最小公倍数有如下性质:

  • [a1,,an]=[|a1|,,|an|]
  • [a,b]=[b,a]
  • a0,则 [a,1]=[a,a]=|a|
  • ab,则 [a,b]=|b|
  • [a1,,an]=[[a1,a2],a3,,an]。进而 1<k<n1, [a1,,an]=[[a1,,ak],[ak+1,,an]]
  • aim, 1in,则 [a1,,an]m
  • [ma1,,man]=|m|[a1,,an]
  • [a,b,c][ab,bc,ca]=[a,b][b,c][c,a]
  • [an,bn]=[a,b]n

最大公约数和最小公倍数可以组合出很多奇妙的等式,如:

  • (a,b)[a,b]=|ab|
  • (ab,bc,ca)[a,b,c]=|abc|
  • (a,b,c)2(a,b)(b,c)(a,c)=[a,b,c]2[a,b][b,c][a,c]

这些性质均可通过定义或 唯一分解定理 证明,其中使用唯一分解定理的证明更容易理解。

互素

定义

(a1,a2)=1,则称 a1a2 互素既约)。

(a1,,ak)=1,则称 a1,,ak 互素既约)。

多个整数互素,不一定两两互素。例如 61015 互素,但是任意两个都不互素。

互素的性质与最大公约数理论:裴蜀定理(Bézout's identity)。见 裴蜀定理

辗转相除法

辗转相除法是一种算法,也称 Euclid 算法。见 最大公约数

素数与合数

关于素数的算法见 素数

定义

设整数 p0,±1。如果 p 除了平凡约数外没有其他约数,那么称 p素数不可约数)。

若整数 a0,±1a 不是素数,则称 a合数

pp 总是同为素数或者同为合数。如果没有特别说明,素数总是指正的素数。

整数的因数是素数,则该素数称为该整数的素因数(素约数)。

素数与合数的简单性质:

  • 大于 1 的整数 a 是合数,等价于 a 可以表示为整数 de1<d,e<a)的乘积。
  • 如果素数 p 有大于 1 的约数 d,那么 d=p
  • 大于 1 的整数 a 一定可以表示为素数的乘积。
  • 对于合数 a,一定存在素数 pa 使得 pa
  • 素数有无穷多个。
  • 所有大于 3 的素数都可以表示为 6n±1 的形式1

算术基本定理

算术基本引理

p 是素数,pa1a2,那么 pa1pa2 至少有一个成立。

算术基本引理的逆命题稍加修改也可以得到素数的另一种定义。

素数的另一种定义

对整数 p0,±1,若对任意满足 pa1a2 的整数 a1,a2 均有 pa1pa2 成立,则称 p 是素数。

Tip

这个定义的动机可以从 素理想 中找到。

算术基本定理(唯一分解定理)

设正整数 a,那么必有表示:

a=p1p2ps

其中 pj(1js) 是素数。并且在不计次序的意义下,该表示唯一。

标准素因数分解式

将上述表示中,相同的素数合并,可得:

a=p1α1p2α2psαs,p1<p2<<ps

称为正整数 a 的标准素因数分解式。

算术基本定理和算术基本引理,两个定理是等价的。

同余

定义

设整数 m0。若 m(ab),称 m模数),a 同余于 bmba 对模 m剩余。记作 ab(modm)

否则,a 不同余于 bmb 不是 a 对模 m 的剩余。记作 ab(modm)

这样的等式,称为模 m 的同余式,简称 同余式

根据整除的性质,上述同余式也等价于 ab(mod(m))

如果没有特别说明,模数总是正整数。

式中的 ba 对模 m 的剩余,这个概念与余数完全一致。通过限定 b 的范围,相应的有 a 对模 m 的最小非负剩余、绝对最小剩余、最小正剩余。

同余的性质:

  • 同余是 等价关系,即同余具有
    • 自反性:aa(modm)
    • 对称性:若 ab(modm),则 ba(modm)
    • 传递性:若 ab(modm),bc(modm),则 ac(modm)
  • 线性运算:若 a,b,c,dZ,mN,ab(modm),cd(modm) 则有:
    • a±cb±d(modm)
    • a×cb×d(modm)
  • f(x)=i=0naixig(x)=i=0nbixi 是两个整系数多项式,mN,且 aibi(modm), 0in,则对任意整数 x 均有 f(x)g(x)(modm)。进而若 st(modm),则 f(s)g(t)(modm)
  • a,bZ,k,mN,ab(modm), 则 akbk(modmk)
  • a,bZ,d,mN,da,db,dm,则当 ab(modm) 成立时,有 adbd(modmd)
  • a,bZ,d,mN,dm,则当 ab(modm) 成立时,有 ab(modd)
  • a,bZ,d,mN,则当 ab(modm) 成立时,有 (a,m)=(b,m)。若 d 能整除 ma,b 中的一个,则 d 必定能整除 a,b 中的另一个。

还有性质是乘法逆元。见 乘法逆元

C/C++ 的整数除法和取模运算

在 C/C++ 中,整数除法和取模运算,与数学上习惯的取模和除法不一致。

对于所有标准版本的 C/C++,规定在整数除法中:

  1. 当除数为 0 时,行为未定义;
  2. 否则 (a / b) * b + a % b 的运算结果与 a 相等。

也就是说,取模运算的符号取决于除法如何取整;而除法如何取整,这是实现定义的(由编译器决定)。

从 C992和 C++113标准版本起,规定 商向零取整(舍弃小数部分);取模的符号即与被除数相同。从此以下运算结果保证为真:

1
2
3
4
5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;

同余类与剩余系

为方便讨论,对集合 A,B 和元素 r,我们引入如下记号:

  • r+A:={r+a:aA}
  • rA:={ra:aA}
  • A+B:={a+b:aA,bB}
  • AB:={ab:aA,bB}
同余类

对非零整数 m,把全体整数分成 |m| 个两两不交的集合,且同一个集合中的任意两个数模 m 均同余,我们把这 |m| 个集合均称为模 m同余类剩余类。用 rmodm 表示含有整数 r 的模 m 的同余类。

不难证明对任意非零整数 m,上述划分方案一定存在且唯一。

由同余类的定义可知:

  • rmodm={r+km:kZ}
  • rmodm=smodmrs(modm)
  • 对任意 r,sZ,要么 rmodm=smodm,要么 (rmodm)(smodm)=
  • m1m,则对任意整数 r 均有 r+mZr+m1Z

注意到同余是等价关系,所以同余类即为同余关系的等价类。

我们把模 m 的同余类全体构成的集合记为 Zm,即

Zm:={rmodm:0r<m}

不难发现:

  • 对任意整数 aa+Zm=Zm
  • 对任意与 m 互质的整数 bbZm=Zm

商群 的定义可知 Zm=Z/mZ,所以有时我们也会用 Z/mZ 表示 Zm

抽屉原理 可知:

  • 任取 m+1 个整数,必有两个整数模 m 同余。
  • 存在 m 个两两模 m 不同余的整数。

由此我们给出完全剩余系的定义:

(完全)剩余系

m 个整数 a1,a2,,am,若对任意的数 x,有且仅有一个数 ai 使得 xaim 同余,则称这 m 个整数 a1,a2,,am 为模 m完全剩余系,简称 剩余系

我们还可以定义模 m 的:

  • 最小非负(完全)剩余系:0,,m1
  • 最小正(完全)剩余系:1,,m
  • 绝对最小(完全)剩余系:m/2,,m/21
  • 最大非正(完全)剩余系:m+1,,0
  • 最大负(完全)剩余系:m,,1

若无特殊说明,一般我们只用最小非负剩余系。


我们注意到如下命题成立:

  • 在模 m 的任意一个同余类中,任取两个整数 a1,a2 均有 (a1,m)=(a2,m)

考虑同余类 rmodm,若 (r,m)=1,则该同余类的所有元素均与 m 互质,这说明我们也许可以通过类似方式得知所有与 m 互质的整数构成的集合的结构。

既约同余类

对同余类 rmodm,若 (r,m)=1,则称该同余类为 既约同余类既约剩余类

我们把模 m 既约剩余类的个数记作 φ(m),称其为 Euler 函数

我们把模 m 的既约同余类全体构成的集合记为 Zm,即

Zm:={rmodm:0r<m,(r,m)=1}
Warning

对于任意的整数 a 和与 m 互质的整数 bbZm=Zm,但是 a+Zm 不一定为 Zm。这一点与 Zm 不同。

抽屉原理 可知:

  • 任取 φ(m)+1 个与 m 互质的整数,必有两个整数模 m 同余。
  • 存在 φ(m) 个与 m 互质且两两模 m 不同余的整数。

由此我们给出既约剩余系的定义:

既约剩余系

t=φ(m) 个整数 a1,a2,,at,若 (ai,m)=1, 1it,且对任意满足 (x,m)=1 的数 x,有且仅有一个数 ai 使得 xaim 同余,则称这 t 个整数 a1,a2,,at 为模 m既约剩余系缩剩余系简化剩余系

类似地,我们也可以定义最小非负既约剩余系等概念。

若无特殊说明,一般我们只用最小非负既约剩余系。

剩余系的复合

对正整数 m,我们有如下定理:

  • m=m1m2, 1m1,m2,令 Zm1,Zm2 分别为模 m1,m2完全 剩余系,则对任意与 m1 互质的 a 均有:

    Zm=aZm1+m1Zm2.

    为模 m完全 剩余系。进而,若 m=i=1kmi, 1m1,m2,,mk,令 Zm1,,Zmk 分别为模 m1,,mk完全 剩余系,则:

    Zm=i=1k(j=1i1mj)Zmi.

    为模 m完全 剩余系。

证明

只需证明对任意满足 ax+m1yax+m1y(modm1m2)x,xZm1y,yZm2,都有:

ax+m1y=ax+m1y.

实际上,由 m1m1m2,我们有 ax+m1yax+m1y(modm1),进而 axax(modm1),由 (a,m1)=1 可知 xx(modm1),进而有 x=x

进一步,m1ym1y(modm1m2),则 yy(modm2),即 y=y

因此,

ax+m1y=ax+m1y.
  • m=m1m2, 1m1,m2,(m1,m2)=1,令 Zm1,Zm2 分别为模 m1,m2既约 剩余系,则:

    Zm=m2Zm1+m1Zm2.

    为模 m既约 剩余系。

Tip

该定理等价于证明 Euler 函数为 积性函数

证明

Zm1,Zm2 分别为模 m1,m2 的完全剩余系,我们已经证明了

Zm=m2Zm1+m1Zm2

为模 m 的完全剩余系。令 M={aZm:(a,m)=1}Zm,显然 M 为模 m 的既约剩余系,所以我们只需证明 M=Zm 即可。

显然 ZmZm

任取 m2x+m1yM,其中 xZm1yZm2,有 (m2x+m1y,m1m2)=1,由 (m1,m2)=1 可得

1=(m2x+m1y,m1)=(m2x,m1)=(x,m1), 1=(m2x+m1y,m2)=(m1y,m2)=(y,m2).

因此可得 xZm1yZm2,即 MZm

任取 m2x+m1yZm,其中 xZm1yZm2,有 (x,m1)=1(y,m2)=1,由 (m1,m2)=1 可得

(m2x+m1y,m1)=(m2x,m1)=(x,m1)=1, (m2x+m1y,m2)=(m1y,m2)=(x,m2)=1,

因此可得 (m2x+m1y,m1m2)=1,即 ZmM

综上所述,

Zm=m2Zm1+m1Zm2.

为模 m既约 剩余系。

数论函数

数论函数(也称算数函数)指定义域为正整数的函数。数论函数也可以视作一个数列。

积性函数

定义

在数论中,若函数 f(n) 满足 f(1)=1,且 f(xy)=f(x)f(y) 对任意互质的 x,yN 都成立,则 f(n)积性函数

在数论中,若函数 f(n) 满足 f(1)=1f(xy)=f(x)f(y) 对任意的 x,yN 都成立,则 f(n)完全积性函数

性质

f(x)g(x) 均为积性函数,则以下函数也为积性函数:

h(x)=f(xp)h(x)=fp(x)h(x)=f(x)g(x)h(x)=dxf(d)g(xd)

对正整数 x,设其唯一质因数分解为 x=piki,其中 pi 为质数。

F(x) 为积性函数,则有 F(x)=F(piki)

F(x) 为完全积性函数,则有 F(x)=F(piki)=F(pi)ki

例子

  • 单位函数:ε(n)=[n=1]。(完全积性)
  • 恒等函数:idk(n)=nkid1(n) 通常简记作 id(n)。(完全积性)
  • 常数函数:1(n)=1。(完全积性)
  • 除数函数:σk(n)=dndkσ0(n) 通常简记作 d(n)τ(n)σ1(n) 通常简记作 σ(n)
  • 欧拉函数:φ(n)=i=1n[(i,n)=1]
  • 莫比乌斯函数:μ(n)={1n=10d>1,d2n(1)ω(n)otherwise,其中 ω(n) 表示 n 的本质不同质因子个数。

加性函数

定义

在数论中,若函数 f(n) 满足 f(1)=0f(xy)=f(x)+f(y) 对任意互质的 x,yN 都成立,则 f(n)加性函数

在数论中,若函数 f(n) 满足 f(1)=0f(xy)=f(x)+f(y) 对任意的 x,yN 都成立,则 f(n)完全加性函数

加性函数

本节中的加性函数指数论上的加性函数 (Additive function),应与代数中的 Additive map 做区分。

性质

对正整数 x,设其唯一质因数分解为 x=piki,其中 pi 为质数。

F(x) 为加性函数,则有 F(x)=F(piki)

F(x) 为完全加性函数,则有 F(x)=F(piki)=F(pi)ki

例子

为方便叙述,令所有质数组成的集合为 P.

  • 所有质因子数目:Ω(n)=pn[pP]k=1logpn[pknpk+1n]k。(完全加性)
  • 相异质因子数目:ω(n)=pn[pP]
  • 所有质因子之和:a0(n)=pn[pP]k=1logpn[pknpk+1n]kp。(完全加性)
  • 相异质因子之和:a1(n)=pn[pP]p

参考资料与注释

  1. 潘承洞,潘承彪。初等数论。北京大学出版社。