跳转至

# 数论基础

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

## 整除

定义

设 𝑎,𝑏 ∈𝐙 a,b∈Z，𝑎 ≠0 a≠0．如果 ∃𝑞 ∈𝐙∃q∈Z，使得 𝑏 =𝑎 𝑞 b=a q，那么就说 𝑏 b 可被 𝑎 a 整除，记作 𝑎 ∣𝑏 a∣b；𝑏 b 不被 𝑎 a 整除记作 𝑎 ∤𝑏 a∤b．

整除的性质：

- 𝑎 ∣𝑏 ⟺ −𝑎 ∣𝑏 ⟺ 𝑎 ∣ −𝑏 ⟺ |𝑎| ∣|𝑏|a∣b⟺−a∣b⟺a∣−b⟺|a|∣|b|
- 𝑎 ∣𝑏 ∧𝑏 ∣𝑐 ⟹ 𝑎 ∣𝑐 a∣b∧b∣c⟹a∣c
- 𝑎 ∣𝑏 ∧𝑎 ∣𝑐 ⟺ ∀𝑥,𝑦 ∈𝐙,𝑎 ∣(𝑥 𝑏 +𝑦 𝑐)a∣b∧a∣c⟺∀x,y∈Z,a∣(x b+y c)
- 𝑎 ∣𝑏 ∧𝑏 ∣𝑎 ⟹ 𝑏 = ±𝑎 a∣b∧b∣a⟹b=±a
- 设 𝑚 ≠0 m≠0，那么 𝑎 ∣𝑏 ⟺ 𝑚 𝑎 ∣𝑚 𝑏 a∣b⟺m a∣m b．
- 设 𝑏 ≠0 b≠0，那么 𝑎 ∣𝑏 ⟹ |𝑎| ≤|𝑏|a∣b⟹|a|≤|b|．
- 设 𝑎 ≠0,𝑏 =𝑞 𝑎 +𝑐 a≠0,b=q a+c，那么 𝑎 ∣𝑏 ⟺ 𝑎 ∣𝑐 a∣b⟺a∣c．

### 约数

定义

若 𝑎 ∣𝑏 a∣b，则称 𝑏 b 是 𝑎 a 的 倍数，𝑎 a 是 𝑏 b 的 约数．

0 0 是所有非 0 0 整数的倍数．对于整数 𝑏 ≠0 b≠0，𝑏 b 的约数只有有限个．

平凡约数（平凡因数）：对于整数 𝑏 ≠0 b≠0，±1±1、±𝑏±b 是 𝑏 b 的平凡约数．当 𝑏 = ±1 b=±1 时，𝑏 b 只有两个平凡约数．

对于整数 𝑏 ≠0 b≠0，𝑏 b 的其他约数称为真约数（真因数、非平凡约数、非平凡因数）．

约数的性质：

- 设整数 𝑏 ≠0 b≠0．当 𝑑 d 遍历 𝑏 b 的全体约数的时候，𝑏 𝑑 b d 也遍历 𝑏 b 的全体约数．
- 设整数 𝑏 >0 b>0，则当 𝑑 d 遍历 𝑏 b 的全体正约数的时候，𝑏 𝑑 b d 也遍历 𝑏 b 的全体正约数．

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

## 带余数除法

余数

设 𝑎,𝑏 a,b 为两个给定的整数，𝑎 ≠0 a≠0．设 𝑑 d 是一个给定的整数．那么，一定存在唯一的一对整数 𝑞 q 和 𝑟 r，满足 𝑏 =𝑞 𝑎 +𝑟,𝑑 ≤𝑟 <|𝑎| +𝑑 b=q a+r,d≤r<|a|+d．

无论整数 𝑑 d 取何值，𝑟 r 统称为余数．𝑎 ∣𝑏 a∣b 等价于 𝑎 ∣𝑟 a∣r．

一般情况下，𝑑 d 取 0 0，此时等式 𝑏 =𝑞 𝑎 +𝑟,0 ≤𝑟 <|𝑎|b=q a+r,0≤r<|a| 称为带余数除法（带余除法）．这里的余数 𝑟 r 称为最小非负余数．

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

- 绝对最小余数：𝑑 d 取 𝑎 a 的绝对值的一半的相反数．即 𝑏 =𝑞 𝑎 +𝑟, −|𝑎|2 ≤𝑟 <|𝑎| −|𝑎|2 b=q a+r,−|a|2≤r<|a|−|a|2．
- 最小正余数：𝑑 d 取 1 1．即 𝑏 =𝑞 𝑎 +𝑟,1 ≤𝑟 <|𝑎| +1 b=q a+r,1≤r<|a|+1．

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

余数的性质：

- 任一整数被正整数 𝑎 a 除后，余数一定是且仅是 0 0 到 (𝑎 −1)(a−1) 这 𝑎 a 个数中的一个．
- 相邻的 𝑎 a 个整数被正整数 𝑎 a 除后，恰好取到上述 𝑎 a 个余数．特别地，一定有且仅有一个数被 𝑎 a 整除．

## 最大公约数与最小公倍数

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

Warning

一些作者认为 0 0 和 0 0 的最大公约数无定义，其余作者一般将其视为 0 0．C++ STL 的实现中采用后者，即认为 0 0 和 0 0 的最大公约数为 0 01．

最大公约数有如下性质：

- (𝑎 1,…,𝑎 𝑛) =(|𝑎 1|,…,|𝑎 𝑛|)(a 1,…,a n)=(|a 1|,…,|a n|)；
- (𝑎,𝑏) =(𝑏,𝑎)(a,b)=(b,a)；
- 若 𝑎 ≠0 a≠0，则 (𝑎,0) =(𝑎,𝑎) =|𝑎|(a,0)=(a,a)=|a|；
- (𝑏 𝑞 +𝑟,𝑏) =(𝑟,𝑏)(b q+r,b)=(r,b)；
- (𝑎 1,…,𝑎 𝑛) =((𝑎 1,𝑎 2),𝑎 3,…,𝑎 𝑛)(a 1,…,a n)=((a 1,a 2),a 3,…,a n)．进而 ∀1 <𝑘 <𝑛 −1, (𝑎 1,…,𝑎 𝑛) =((𝑎 1,…,𝑎 𝑘),(𝑎 𝑘+1,…,𝑎 𝑛))∀1<k<n−1, (a 1,…,a n)=((a 1,…,a k),(a k+1,…,a n))；
- 对不全为 0 0 的整数 𝑎 1,…,𝑎 𝑛 a 1,…,a n 和非零整数 𝑚 m，(𝑚 𝑎 1,…,𝑚 𝑎 𝑛) =|𝑚|(𝑎 1,…,𝑎 𝑛)(m a 1,…,m a n)=|m|(a 1,…,a n)；
- 对不全为 0 0 的整数 𝑎 1,…,𝑎 𝑛 a 1,…,a n，若 (𝑎 1,…,𝑎 𝑛) =𝑑(a 1,…,a n)=d，则 (𝑎 1/𝑑,…,𝑎 𝑛/𝑑) =1(a 1/d,…,a n/d)=1；
- (𝑎 𝑛,𝑏 𝑛) =(𝑎,𝑏)𝑛(a n,b n)=(a,b)n．

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

- 若 𝑏|𝑎 𝑐 b|a c 且 (𝑎,𝑏) =1(a,b)=1，则 𝑏 ∣𝑐 b∣c；
- 若 𝑏|𝑐 b|c、𝑎|𝑐 a|c 且 (𝑎,𝑏) =1(a,b)=1，则 𝑎 𝑏 ∣𝑐 a b∣c；
- 若 (𝑎,𝑏) =1(a,b)=1，则 (𝑎,𝑏 𝑐) =(𝑎,𝑐)(a,b c)=(a,c)；
- 若 (𝑎 𝑖,𝑏 𝑗) =1, ∀1 ≤𝑖 ≤𝑛,1 ≤𝑗 ≤𝑚(a i,b j)=1, ∀1≤i≤n,1≤j≤m，则 (∏𝑖 𝑎 𝑖,∏𝑗 𝑏 𝑗) =1(∏i a i,∏j b j)=1．特别地，若 (𝑎,𝑏) =1(a,b)=1，则 (𝑎 𝑛,𝑏 𝑚) =1(a n,b m)=1；
- 对整数 𝑎 1,…,𝑎 𝑛 a 1,…,a n，若 ∃𝑣 ∈𝐙, ∏𝑖 𝑎 𝑖 =𝑣 𝑚∃v∈Z, ∏i a i=v m，且 (𝑎 𝑖,𝑎 𝑗) =1, ∀𝑖 ≠𝑗(a i,a j)=1, ∀i≠j，则 ∀1 ≤𝑖 ≤𝑛, 𝑚√𝑎 𝑖 ∈𝐙∀1≤i≤n, a i m∈Z．

最小公倍数有如下性质：

- [𝑎 1,…,𝑎 𝑛] =[|𝑎 1|,…,|𝑎 𝑛|][a 1,…,a n]=[|a 1|,…,|a n|]；
- [𝑎,𝑏] =[𝑏,𝑎][a,b]=[b,a]；
- 若 𝑎 ≠0 a≠0，则 [𝑎,1] =[𝑎,𝑎] =|𝑎|[a,1]=[a,a]=|a|；
- 若 𝑎 ∣𝑏 a∣b，则 [𝑎,𝑏] =|𝑏|[a,b]=|b|；
- [𝑎 1,…,𝑎 𝑛] =[[𝑎 1,𝑎 2],𝑎 3,…,𝑎 𝑛][a 1,…,a n]=[[a 1,a 2],a 3,…,a n]．进而 ∀1 <𝑘 <𝑛 −1, [𝑎 1,…,𝑎 𝑛] =[[𝑎 1,…,𝑎 𝑘],[𝑎 𝑘+1,…,𝑎 𝑛]]∀1<k<n−1, [a 1,…,a n]=[[a 1,…,a k],[a k+1,…,a n]]；
- 若 𝑎 𝑖 ∣𝑚, ∀1 ≤𝑖 ≤𝑛 a i∣m, ∀1≤i≤n，则 [𝑎 1,…,𝑎 𝑛] ∣𝑚[a 1,…,a n]∣m；
- [𝑚 𝑎 1,…,𝑚 𝑎 𝑛] =|𝑚|[𝑎 1,…,𝑎 𝑛][m a 1,…,m a n]=|m|[a 1,…,a n]；
- [𝑎,𝑏,𝑐][𝑎 𝑏,𝑏 𝑐,𝑐 𝑎] =[𝑎,𝑏][𝑏,𝑐][𝑐,𝑎][a,b,c][a b,b c,c a]=[a,b][b,c][c,a]；
- [𝑎 𝑛,𝑏 𝑛] =[𝑎,𝑏]𝑛[a n,b n]=[a,b]n．

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

- (𝑎,𝑏)[𝑎,𝑏] =|𝑎 𝑏|(a,b)[a,b]=|a b|；
- (𝑎 𝑏,𝑏 𝑐,𝑐 𝑎)[𝑎,𝑏,𝑐] =|𝑎 𝑏 𝑐|(a b,b c,c a)[a,b,c]=|a b c|；
- (𝑎,𝑏,𝑐)2(𝑎,𝑏)(𝑏,𝑐)(𝑎,𝑐) =[𝑎,𝑏,𝑐]2[𝑎,𝑏][𝑏,𝑐][𝑎,𝑐](a,b,c)2(a,b)(b,c)(a,c)=[a,b,c]2[a,b][b,c][a,c]．

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

### 互素

定义

若 (𝑎 1,𝑎 2) =1(a 1,a 2)=1，则称 𝑎 1 a 1 和 𝑎 2 a 2 互素（既约）．

若 (𝑎 1,…,𝑎 𝑘) =1(a 1,…,a k)=1，则称 𝑎 1,…,𝑎 𝑘 a 1,…,a k 互素（既约）．

多个整数互素，不一定两两互素．例如 6 6、1 0 10 和 1 5 15 互素，但是任意两个都不互素．

互素的性质与最大公约数理论：裴蜀定理（Bézout's identity）．见 裴蜀定理．

### 辗转相除法

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

## 素数与合数

关于素数的算法见 素数．

定义

设整数 𝑝 ≠0, ±1 p≠0,±1．如果 𝑝 p 除了平凡约数外没有其他约数，那么称 𝑝 p 为 素数（不可约数）．

若整数 𝑎 ≠0, ±1 a≠0,±1 且 𝑎 a 不是素数，则称 𝑎 a 为 合数．

𝑝 p 和 −𝑝−p 总是同为素数或者同为合数．如果没有特别说明，素数总是指正的素数．

整数的因数是素数，则该素数称为该整数的素因数（素约数）．

素数与合数的简单性质：

- 大于 1 1 的整数 𝑎 a 是合数，等价于 𝑎 a 可以表示为整数 𝑑 d 和 𝑒 e（1 <𝑑,𝑒 <𝑎 1<d,e<a）的乘积．
- 如果素数 𝑝 p 有大于 1 1 的约数 𝑑 d，那么 𝑑 =𝑝 d=p．
- 大于 1 1 的整数 𝑎 a 一定可以表示为素数的乘积．
- 对于合数 𝑎 a，一定存在素数 𝑝 ≤√𝑎 p≤a 使得 𝑝 ∣𝑎 p∣a．
- 素数有无穷多个．
- 所有大于 3 3 的素数都可以表示为 6 𝑛 ±1 6 n±1 的形式2．

## 算术基本定理

算术基本引理

设 𝑝 p 是素数，𝑝 ∣𝑎 1 𝑎 2 p∣a 1 a 2，那么 𝑝 ∣𝑎 1 p∣a 1 和 𝑝 ∣𝑎 2 p∣a 2 至少有一个成立．

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

素数的另一种定义

对整数 𝑝 ≠0, ±1 p≠0,±1，若对任意满足 𝑝 ∣𝑎 1 𝑎 2 p∣a 1 a 2 的整数 𝑎 1,𝑎 2 a 1,a 2 均有 𝑝 ∣𝑎 1 p∣a 1 或 𝑝 ∣𝑎 2 p∣a 2 成立，则称 𝑝 p 是素数．

Tip

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

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

设正整数 𝑎 a，那么必有表示：

𝑎=𝑝 1 𝑝 2⋯𝑝 𝑠 a=p 1 p 2⋯p s

其中 𝑝 𝑗(1 ≤𝑗 ≤𝑠)p j(1≤j≤s) 是素数．并且在不计次序的意义下，该表示唯一．

标准素因数分解式

将上述表示中，相同的素数合并，可得：

𝑎=𝑝 1 𝛼 1 𝑝 2 𝛼 2⋯𝑝 𝑠 𝛼 𝑠,𝑝 1<𝑝 2<⋯<𝑝 𝑠 a=p 1 α 1 p 2 α 2⋯p s α s,p 1<p 2<⋯<p s

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

算术基本定理和算术基本引理，两个定理是等价的．

## 同余

定义

设整数 𝑚 ≠0 m≠0．若 𝑚 ∣(𝑎 −𝑏)m∣(a−b)，称 𝑚 m 为 模数（模），𝑎 a 同余于 𝑏 b 模 𝑚 m，𝑏 b 是 𝑎 a 对模 𝑚 m 的 剩余．记作 𝑎 ≡𝑏(m o d 𝑚)a≡b(mod m)．

否则，𝑎 a 不同余于 𝑏 b 模 𝑚 m，𝑏 b 不是 𝑎 a 对模 𝑚 m 的剩余．记作 𝑎 ≢𝑏(m o d 𝑚)a≢b(mod m)．

这样的等式，称为模 𝑚 m 的同余式，简称 同余式．

根据整除的性质，上述同余式也等价于 𝑎 ≡𝑏(m o d( −𝑚))a≡b(mod(−m))．

后文中，如果没有特别说明，模数总是 正整数．

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

同余的性质：

- 同余是 等价关系，即同余具有
  - 自反性：𝑎 ≡𝑎(m o d 𝑚)a≡a(mod m)．
  - 对称性：若 𝑎 ≡𝑏(m o d 𝑚)a≡b(mod m)，则 𝑏 ≡𝑎(m o d 𝑚)b≡a(mod m)．
  - 传递性：若 𝑎 ≡𝑏(m o d 𝑚),𝑏 ≡𝑐(m o d 𝑚)a≡b(mod m),b≡c(mod m)，则 𝑎 ≡𝑐(m o d 𝑚)a≡c(mod m)．
- 线性运算：若 𝑎,𝑏,𝑐,𝑑 ∈𝐙,𝑚 ∈𝐍∗,𝑎 ≡𝑏(m o d 𝑚),𝑐 ≡𝑑(m o d 𝑚)a,b,c,d∈Z,m∈N∗,a≡b(mod m),c≡d(mod m) 则有：
  - 𝑎 ±𝑐 ≡𝑏 ±𝑑(m o d 𝑚)a±c≡b±d(mod m)．
  - 𝑎 ×𝑐 ≡𝑏 ×𝑑(m o d 𝑚)a×c≡b×d(mod m)．
- 设 𝑓(𝑥) =∑𝑛 𝑖=0 𝑎 𝑖 𝑥 𝑖 f(x)=∑i=0 n a i x i 和 𝑔(𝑥) =∑𝑛 𝑖=0 𝑏 𝑖 𝑥 𝑖 g(x)=∑i=0 n b i x i 是两个整系数多项式，𝑚 ∈𝐍∗m∈N∗，且 𝑎 𝑖 ≡𝑏 𝑖(m o d 𝑚), 0 ≤𝑖 ≤𝑛 a i≡b i(mod m), 0≤i≤n，则对任意整数 𝑥 x 均有 𝑓(𝑥) ≡𝑔(𝑥)(m o d 𝑚)f(x)≡g(x)(mod m)．进而若 𝑠 ≡𝑡(m o d 𝑚)s≡t(mod m)，则 𝑓(𝑠) ≡𝑔(𝑡)(m o d 𝑚)f(s)≡g(t)(mod m)．
- 若 𝑎,𝑏 ∈𝐙,𝑘,𝑚 ∈𝐍∗,𝑎 ≡𝑏(m o d 𝑚)a,b∈Z,k,m∈N∗,a≡b(mod m), 则 𝑎 𝑘 ≡𝑏 𝑘(m o d 𝑚 𝑘)a k≡b k(mod m k)．
- 若 𝑎,𝑏 ∈𝐙,𝑑,𝑚 ∈𝐍∗,𝑑 ∣𝑎,𝑑 ∣𝑏,𝑑 ∣𝑚 a,b∈Z,d,m∈N∗,d∣a,d∣b,d∣m，则当 𝑎 ≡𝑏(m o d 𝑚)a≡b(mod m) 成立时，有 𝑎 𝑑 ≡𝑏 𝑑(m o d 𝑚 𝑑)a d≡b d(mod m d)．
- 若 𝑎,𝑏 ∈𝐙,𝑑,𝑚 ∈𝐍∗,𝑑 ∣𝑚 a,b∈Z,d,m∈N∗,d∣m，则当 𝑎 ≡𝑏(m o d 𝑚)a≡b(mod m) 成立时，有 𝑎 ≡𝑏(m o d 𝑑)a≡b(mod d)．
- 若 𝑎,𝑏 ∈𝐙,𝑑,𝑚 ∈𝐍∗a,b∈Z,d,m∈N∗，则当 𝑎 ≡𝑏(m o d 𝑚)a≡b(mod m) 成立时，有 (𝑎,𝑚) =(𝑏,𝑚)(a,m)=(b,m)．若 𝑑 d 能整除 𝑚 m 及 𝑎,𝑏 a,b 中的一个，则 𝑑 d 必定能整除 𝑎,𝑏 a,b 中的另一个．

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

## 同余类与剩余系

为方便讨论，对集合 𝐴,𝐵 A,B 和元素 𝑟 r，我们引入如下记号：

- 𝑟 +𝐴 :={𝑟 +𝑎 :𝑎 ∈𝐴}r+A:={r+a:a∈A}；
- 𝑟 𝐴 :={𝑟 𝑎 :𝑎 ∈𝐴}r A:={r a:a∈A}；
- 𝐴 +𝐵 :={𝑎 +𝑏 :𝑎 ∈𝐴,𝑏 ∈𝐵}A+B:={a+b:a∈A,b∈B}；
- 𝐴 𝐵 :={𝑎 𝑏 :𝑎 ∈𝐴,𝑏 ∈𝐵}A B:={a b:a∈A,b∈B}．

同余类

对非零整数 𝑚 m，把全体整数分成 |𝑚||m| 个两两不交的集合，且同一个集合中的任意两个数模 𝑚 m 均同余，我们把这 |𝑚||m| 个集合均称为模 𝑚 m 的 同余类 或 剩余类．用 𝑟 m o d 𝑚 r mod m 表示含有整数 𝑟 r 的模 𝑚 m 的同余类．

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

由同余类的定义可知：

- 𝑟 m o d 𝑚 ={𝑟 +𝑘 𝑚 :𝑘 ∈𝐙}r mod m={r+k m:k∈Z}；
- 𝑟 m o d 𝑚 =𝑠 m o d 𝑚 ⟺ 𝑟 ≡𝑠(m o d 𝑚)r mod m=s mod m⟺r≡s(mod m)；
- 对任意 𝑟,𝑠 ∈𝐙 r,s∈Z，要么 𝑟 m o d 𝑚 =𝑠 m o d 𝑚 r mod m=s mod m，要么 (𝑟 m o d 𝑚) ∩(𝑠 m o d 𝑚) =∅(r mod m)∩(s mod m)=∅；
- 若 𝑚 1 ∣𝑚 m 1∣m，则对任意整数 𝑟 r 均有 𝑟 +𝑚 𝐙 ⊆𝑟 +𝑚 1 𝐙 r+m Z⊆r+m 1 Z．

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

我们把模 𝑚 m 的同余类全体构成的集合记为 𝐙 𝑚 Z m，即

𝐙 𝑚:={𝑟 m o d 𝑚:0≤𝑟<𝑚}Z m:={r mod m:0≤r<m}

不难发现：

- 对任意整数 𝑎 a，𝑎 +𝐙 𝑚 =𝐙 𝑚 a+Z m=Z m；
- 对任意与 𝑚 m 互质的整数 𝑏 b，𝑏 𝐙 𝑚 =𝐙 𝑚 b Z m=Z m．

由 商群 的定义可知 𝐙 𝑚 =𝐙/𝑚 𝐙 Z m=Z/m Z，所以有时我们也会用 𝐙/𝑚 𝐙 Z/m Z 表示 𝐙 𝑚 Z m．

由 抽屉原理 可知：

- 任取 𝑚 +1 m+1 个整数，必有两个整数模 𝑚 m 同余．
- 存在 𝑚 m 个两两模 𝑚 m 不同余的整数．

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

（完全）剩余系

对 𝑚 m 个整数 𝑎 1,𝑎 2,…,𝑎 𝑚 a 1,a 2,…,a m，若对任意的数 𝑥 x，有且仅有一个数 𝑎 𝑖 a i 使得 𝑥 x 与 𝑎 𝑖 a i 模 𝑚 m 同余，则称这 𝑚 m 个整数 𝑎 1,𝑎 2,…,𝑎 𝑚 a 1,a 2,…,a m 为模 𝑚 m 的 完全剩余系，简称 剩余系．

我们还可以定义模 𝑚 m 的：

- 最小非负（完全）剩余系：0,…,𝑚 −1 0,…,m−1；
- 最小正（完全）剩余系：1,…,𝑚 1,…,m；
- 绝对最小（完全）剩余系：−⌊𝑚/2⌋,…, −⌊ −𝑚/2⌋ −1−⌊m/2⌋,…,−⌊−m/2⌋−1；
- 最大非正（完全）剩余系：−𝑚 +1,…,0−m+1,…,0；
- 最大负（完全）剩余系：−𝑚,…, −1−m,…,−1．

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

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

- 在模 𝑚 m 的任意一个同余类中，任取两个整数 𝑎 1,𝑎 2 a 1,a 2 均有 (𝑎 1,𝑚) =(𝑎 2,𝑚)(a 1,m)=(a 2,m)．

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

既约同余类

对同余类 𝑟 m o d 𝑚 r mod m，若 (𝑟,𝑚) =1(r,m)=1，则称该同余类为 既约同余类 或 既约剩余类．

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

我们把模 𝑚 m 的既约同余类全体构成的集合记为 𝐙∗𝑚 Z m∗，即

𝐙∗𝑚:={𝑟 m o d 𝑚:0≤𝑟<𝑚,(𝑟,𝑚)=1}Z m∗:={r mod m:0≤r<m,(r,m)=1}
Warning

对于任意的整数 𝑎 a 和与 𝑚 m 互质的整数 𝑏 b，𝑏 𝐙∗𝑚 =𝐙∗𝑚 b Z m∗=Z m∗，但是 𝑎 +𝐙∗𝑚 a+Z m∗ 不一定为 𝐙∗𝑚 Z m∗．这一点与 𝐙 𝑚 Z m 不同．

由 抽屉原理 可知：

- 任取 𝜑(𝑚) +1 φ(m)+1 个与 𝑚 m 互质的整数，必有两个整数模 𝑚 m 同余．
- 存在 𝜑(𝑚)φ(m) 个与 𝑚 m 互质且两两模 𝑚 m 不同余的整数．

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

既约剩余系

对 𝑡 =𝜑(𝑚)t=φ(m) 个整数 𝑎 1,𝑎 2,…,𝑎 𝑡 a 1,a 2,…,a t，若 (𝑎 𝑖,𝑚) =1, ∀1 ≤𝑖 ≤𝑡(a i,m)=1, ∀1≤i≤t，且对任意满足 (𝑥,𝑚) =1(x,m)=1 的数 𝑥 x，有且仅有一个数 𝑎 𝑖 a i 使得 𝑥 x 与 𝑎 𝑖 a i 模 𝑚 m 同余，则称这 𝑡 t 个整数 𝑎 1,𝑎 2,…,𝑎 𝑡 a 1,a 2,…,a t 为模 𝑚 m 的 既约剩余系、缩剩余系 或 简化剩余系．

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

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

### 剩余系的复合

对正整数 𝑚 m，我们有如下定理：

- 若 𝑚 =𝑚 1 𝑚 2, 1 ≤𝑚 1,𝑚 2 m=m 1 m 2, 1≤m 1,m 2，令 𝑍 𝑚 1,𝑍 𝑚 2 Z m 1,Z m 2 分别为模 𝑚 1,𝑚 2 m 1,m 2 的 完全 剩余系，则对任意与 𝑚 1 m 1 互质的 𝑎 a 均有：

  𝑍 𝑚=𝑎 𝑍 𝑚 1+𝑚 1 𝑍 𝑚 2.Z m=a Z m 1+m 1 Z m 2.

  为模 𝑚 m 的 完全 剩余系．进而，若 𝑚 =∏𝑘 𝑖=1 𝑚 𝑖, 1 ≤𝑚 1,𝑚 2,…,𝑚 𝑘 m=∏i=1 k m i, 1≤m 1,m 2,…,m k，令 𝑍 𝑚 1,…,𝑍 𝑚 𝑘 Z m 1,…,Z m k 分别为模 𝑚 1,…,𝑚 𝑘 m 1,…,m k 的 完全 剩余系，则：

  𝑍 𝑚=𝑘∑𝑖=1(𝑖−1∏𝑗=1 𝑚 𝑗)𝑍 𝑚 𝑖.Z m=∑i=1 k(∏j=1 i−1 m j)Z m i.

  为模 𝑚 m 的 完全 剩余系．

证明

只需证明对任意满足 𝑎 𝑥 +𝑚 1 𝑦 ≡𝑎 𝑥′ +𝑚 1 𝑦′(m o d 𝑚 1 𝑚 2)a x+m 1 y≡a x′+m 1 y′(mod m 1 m 2) 的 𝑥,𝑥′ ∈𝑍 𝑚 1 x,x′∈Z m 1，𝑦,𝑦′ ∈𝑍 𝑚 2 y,y′∈Z m 2，都有：

𝑎 𝑥+𝑚 1 𝑦=𝑎 𝑥′+𝑚 1 𝑦′.a x+m 1 y=a x′+m 1 y′.

实际上，由 𝑚 1 ∣𝑚 1 𝑚 2 m 1∣m 1 m 2，我们有 𝑎 𝑥 +𝑚 1 𝑦 ≡𝑎 𝑥′ +𝑚 1 𝑦′(m o d 𝑚 1)a x+m 1 y≡a x′+m 1 y′(mod m 1)，进而 𝑎 𝑥 ≡𝑎 𝑥′(m o d 𝑚 1)a x≡a x′(mod m 1)，由 (𝑎,𝑚 1) =1(a,m 1)=1 可知 𝑥 ≡𝑥′(m o d 𝑚 1)x≡x′(mod m 1)，进而有 𝑥 =𝑥′x=x′．

进一步，𝑚 1 𝑦 ≡𝑚 1 𝑦′(m o d 𝑚 1 𝑚 2)m 1 y≡m 1 y′(mod m 1 m 2)，则 𝑦 ≡𝑦′(m o d 𝑚 2)y≡y′(mod m 2)，即 𝑦 =𝑦′y=y′．

因此，

𝑎 𝑥+𝑚 1 𝑦=𝑎 𝑥′+𝑚 1 𝑦′.a x+m 1 y=a x′+m 1 y′.

- 若 𝑚 =𝑚 1 𝑚 2, 1 ≤𝑚 1,𝑚 2,(𝑚 1,𝑚 2) =1 m=m 1 m 2, 1≤m 1,m 2,(m 1,m 2)=1，令 𝑍∗𝑚 1,𝑍∗𝑚 2 Z m 1∗,Z m 2∗ 分别为模 𝑚 1,𝑚 2 m 1,m 2 的 既约 剩余系，则：

  𝑍∗𝑚=𝑚 2 𝑍∗𝑚 1+𝑚 1 𝑍∗𝑚 2.Z m∗=m 2 Z m 1∗+m 1 Z m 2∗.

  为模 𝑚 m 的 既约 剩余系．

Tip

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

证明

令 𝑍 𝑚 1,𝑍 𝑚 2 Z m 1,Z m 2 分别为模 𝑚 1,𝑚 2 m 1,m 2 的完全剩余系，我们已经证明了

𝑍 𝑚=𝑚 2 𝑍 𝑚 1+𝑚 1 𝑍 𝑚 2 Z m=m 2 Z m 1+m 1 Z m 2

为模 𝑚 m 的完全剩余系．令 𝑀 ={𝑎 ∈𝑍 𝑚 :(𝑎,𝑚) =1} ⊆𝑍 𝑚 M={a∈Z m:(a,m)=1}⊆Z m，显然 𝑀 M 为模 𝑚 m 的既约剩余系，所以我们只需证明 𝑀 =𝑍∗𝑚 M=Z m∗ 即可．

显然 𝑍∗𝑚 ⊆𝑍 𝑚 Z m∗⊆Z m．

任取 𝑚 2 𝑥 +𝑚 1 𝑦 ∈𝑀 m 2 x+m 1 y∈M，其中 𝑥 ∈𝑍 𝑚 1 x∈Z m 1 且 𝑦 ∈𝑍 𝑚 2 y∈Z m 2，有 (𝑚 2 𝑥 +𝑚 1 𝑦,𝑚 1 𝑚 2) =1(m 2 x+m 1 y,m 1 m 2)=1，由 (𝑚 1,𝑚 2) =1(m 1,m 2)=1 可得

1=(𝑚 2 𝑥+𝑚 1 𝑦,𝑚 1)=(𝑚 2 𝑥,𝑚 1)=(𝑥,𝑚 1),1=(m 2 x+m 1 y,m 1)=(m 2 x,m 1)=(x,m 1), 1=(𝑚 2 𝑥+𝑚 1 𝑦,𝑚 2)=(𝑚 1 𝑦,𝑚 2)=(𝑦,𝑚 2).1=(m 2 x+m 1 y,m 2)=(m 1 y,m 2)=(y,m 2).

因此可得 𝑥 ∈𝑍∗𝑚 1 x∈Z m 1∗ 且 𝑦 ∈𝑍∗𝑚 2 y∈Z m 2∗，即 𝑀 ⊆𝑍∗𝑚 M⊆Z m∗．

任取 𝑚 2 𝑥 +𝑚 1 𝑦 ∈𝑍∗𝑚 m 2 x+m 1 y∈Z m∗，其中 𝑥 ∈𝑍∗𝑚 1 x∈Z m 1∗ 且 𝑦 ∈𝑍∗𝑚 2 y∈Z m 2∗，有 (𝑥,𝑚 1) =1(x,m 1)=1 且 (𝑦,𝑚 2) =1(y,m 2)=1，由 (𝑚 1,𝑚 2) =1(m 1,m 2)=1 可得

(𝑚 2 𝑥+𝑚 1 𝑦,𝑚 1)=(𝑚 2 𝑥,𝑚 1)=(𝑥,𝑚 1)=1,(m 2 x+m 1 y,m 1)=(m 2 x,m 1)=(x,m 1)=1, (𝑚 2 𝑥+𝑚 1 𝑦,𝑚 2)=(𝑚 1 𝑦,𝑚 2)=(𝑥,𝑚 2)=1,(m 2 x+m 1 y,m 2)=(m 1 y,m 2)=(x,m 2)=1,

因此可得 (𝑚 2 𝑥 +𝑚 1 𝑦,𝑚 1 𝑚 2) =1(m 2 x+m 1 y,m 1 m 2)=1，即 𝑍∗𝑚 ⊆𝑀 Z m∗⊆M．

综上所述，

𝑍∗𝑚=𝑚 2 𝑍∗𝑚 1+𝑚 1 𝑍∗𝑚 2.Z m∗=m 2 Z m 1∗+m 1 Z m 2∗.

为模 𝑚 m 的 既约 剩余系．

## 数论函数

数论函数（也称算术函数）指定义域为正整数的函数．数论函数也可以视作一个数列．

### 积性函数

定义

在数论中，若函数 𝑓(𝑛)f(n) 满足 𝑓(1) =1 f(1)=1，且 𝑓(𝑥 𝑦) =𝑓(𝑥)𝑓(𝑦)f(x y)=f(x)f(y) 对任意互质的 𝑥,𝑦 ∈𝐍∗x,y∈N∗ 都成立，则 𝑓(𝑛)f(n) 为 积性函数．

在数论中，若函数 𝑓(𝑛)f(n) 满足 𝑓(1) =1 f(1)=1 且 𝑓(𝑥 𝑦) =𝑓(𝑥)𝑓(𝑦)f(x y)=f(x)f(y) 对任意的 𝑥,𝑦 ∈𝐍∗x,y∈N∗ 都成立，则 𝑓(𝑛)f(n) 为 完全积性函数．

#### 性质

若 𝑓(𝑥)f(x) 和 𝑔(𝑥)g(x) 均为积性函数，则以下函数也为积性函数：

ℎ(𝑥)=𝑓(𝑥 𝑝)ℎ(𝑥)=𝑓 𝑝(𝑥)ℎ(𝑥)=𝑓(𝑥)𝑔(𝑥)ℎ(𝑥)=∑𝑑∣𝑥 𝑓(𝑑)𝑔(𝑥 𝑑)h(x)=f(x p)h(x)=f p(x)h(x)=f(x)g(x)h(x)=∑d∣x f(d)g(x d)

对正整数 𝑥 x，设其唯一质因数分解为 𝑥 =∏𝑝 𝑘 𝑖 𝑖 x=∏p i k i，其中 𝑝 𝑖 p i 为质数．

若 𝐹(𝑥)F(x) 为积性函数，则有 𝐹(𝑥) =∏𝐹(𝑝 𝑘 𝑖 𝑖)F(x)=∏F(p i k i)．

若 𝐹(𝑥)F(x) 为完全积性函数，则有 𝐹(𝑥) =∏𝐹(𝑝 𝑘 𝑖 𝑖) =∏𝐹(𝑝 𝑖)𝑘 𝑖 F(x)=∏F(p i k i)=∏F(p i)k i．

#### 例子

- 单位函数：𝜀(𝑛) =[𝑛 =1]ε(n)=[n=1]．（完全积性）
- 恒等函数：i d 𝑘⁡(𝑛) =𝑛 𝑘 id k⁡(n)=n k，i d 1⁡(𝑛)id 1⁡(n) 通常简记作 i d⁡(𝑛)id⁡(n)．（完全积性）
- 常数函数：1(𝑛) =1 1(n)=1．（完全积性）
- 除数函数：𝜎 𝑘(𝑛) =∑𝑑∣𝑛 𝑑 𝑘 σ k(n)=∑d∣n d k．𝜎 0(𝑛)σ 0(n) 通常简记作 𝑑(𝑛)d(n) 或 𝜏(𝑛)τ(n)，𝜎 1(𝑛)σ 1(n) 通常简记作 𝜎(𝑛)σ(n)．
- 欧拉函数：𝜑(𝑛) =∑𝑛 𝑖=1[(𝑖,𝑛) =1]φ(n)=∑i=1 n[(i,n)=1]．
- 莫比乌斯函数：𝜇(𝑛) =⎧{ {⎨{ {⎩1 𝑛=1 0∃𝑑>1,𝑑 2∣𝑛(−1)𝜔(𝑛)o t h e r w i s e μ(n)={1 n=1 0∃d>1,d 2∣n(−1)ω(n)otherwise，其中 𝜔(𝑛)ω(n) 表示 𝑛 n 的本质不同质因子个数．

### 加性函数

定义

在数论中，若函数 𝑓(𝑛)f(n) 满足 𝑓(1) =0 f(1)=0 且 𝑓(𝑥 𝑦) =𝑓(𝑥) +𝑓(𝑦)f(x y)=f(x)+f(y) 对任意互质的 𝑥,𝑦 ∈𝐍∗x,y∈N∗ 都成立，则 𝑓(𝑛)f(n) 为 加性函数．

在数论中，若函数 𝑓(𝑛)f(n) 满足 𝑓(1) =0 f(1)=0 且 𝑓(𝑥 𝑦) =𝑓(𝑥) +𝑓(𝑦)f(x y)=f(x)+f(y) 对任意的 𝑥,𝑦 ∈𝐍∗x,y∈N∗ 都成立，则 𝑓(𝑛)f(n) 为 完全加性函数．

加性函数

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

#### 性质

对正整数 𝑥 x，设其唯一质因数分解为 𝑥 =∏𝑝 𝑘 𝑖 𝑖 x=∏p i k i，其中 𝑝 𝑖 p i 为质数．

若 𝐹(𝑥)F(x) 为加性函数，则有 𝐹(𝑥) =∑𝐹(𝑝 𝑘 𝑖 𝑖)F(x)=∑F(p i k i)．

若 𝐹(𝑥)F(x) 为完全加性函数，则有 𝐹(𝑥) =∑𝐹(𝑝 𝑘 𝑖 𝑖) =∑𝐹(𝑝 𝑖) ⋅𝑘 𝑖 F(x)=∑F(p i k i)=∑F(p i)⋅k i．

#### 例子

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

- 素因数分解中 𝑝 p 的重数：𝜈 𝑝(𝑛) =m a x{𝑘 ∈𝐍 :𝑝 𝑘 ∣𝑛}ν p(n)=max{k∈N:p k∣n}，其中，𝑝 ∈𝐏 p∈P．（完全加性）
- 所有质因子数目：Ω(𝑛) =∑𝑝∈𝐏 𝜈 𝑝(𝑛)Ω(n)=∑p∈P ν p(n)．（完全加性）
- 相异质因子数目：𝜔(𝑛) =∑𝑝∈𝐏[𝑝 ∣𝑛]ω(n)=∑p∈P[p∣n]．
- 所有质因子之和：𝑎 0(𝑛) =∑𝑝∈𝐏 𝜈 𝑝(𝑛) ⋅𝑝 a 0(n)=∑p∈P ν p(n)⋅p．（完全加性）
- 相异质因子之和：𝑎 1(𝑛) =∑𝑝∈𝐏[𝑝 ∣𝑛] ⋅𝑝 a 1(n)=∑p∈P[p∣n]⋅p．

## 取整函数

对于实数 𝑥 x，定义 下取整函数（floor function）和 上取整函数（ceiling function）分别为

⌊𝑥⌋=m a x{𝑘∈𝐙:𝑘≤𝑥}, ⌈𝑥⌉=m i n{𝑘∈𝐙:𝑘≥𝑥}.⌊x⌋=max{k∈Z:k≤x}, ⌈x⌉=min{k∈Z:k≥x}.

利用下取整函数，一个实数可以分解为整数部分和小数部分：𝑥 =⌊𝑥⌋ +{𝑥}x=⌊x⌋+{x}．其中，{𝑥}{x} 表示 𝑥 x 的小数部分．

取整函数有如下基本性质：（𝑥 ∈𝐑, 𝑛 ∈𝐙 x∈R, n∈Z）

- 𝑥 ∈𝐙 ⟺ 𝑥 =⌊𝑥⌋ =⌈𝑥⌉x∈Z⟺x=⌊x⌋=⌈x⌉．
- ⌈𝑥⌉ −⌊𝑥⌋ =[𝑥 ∉𝐙]⌈x⌉−⌊x⌋=[x∉Z]．
- 𝑥 −1 <⌊𝑥⌋ ≤𝑥 ≤⌈𝑥⌉ <𝑥 +1 x−1<⌊x⌋≤x≤⌈x⌉<x+1．
- ⌊ −𝑥⌋ = −⌈𝑥⌉, ⌈ −𝑥⌉ = −⌊𝑥⌋⌊−x⌋=−⌈x⌉, ⌈−x⌉=−⌊x⌋．
- ⌊𝑥 +𝑛⌋ =⌊𝑥⌋ +𝑛, ⌈𝑥 +𝑛⌉ =⌈𝑥⌉ +𝑛⌊x+n⌋=⌊x⌋+n, ⌈x+n⌉=⌈x⌉+n．
- ⌊𝑥⌋⌊x⌋ 和 ⌈𝑥⌉⌈x⌉ 都是关于 𝑥 x 的单调弱增函数．

证明关于下（上）取整函数的等式经常用到如下等价形式：（𝑥 ∈𝐑, 𝑛 ∈𝐙 x∈R, n∈Z）

- ⌊𝑥⌋ =𝑛 ⟺ 𝑛 ≤𝑥 <𝑛 +1 ⟺ 𝑥 −1 <𝑛 ≤𝑥⌊x⌋=n⟺n≤x<n+1⟺x−1<n≤x．
- ⌈𝑥⌉ =𝑛 ⟺ 𝑛 −1 <𝑥 ≤𝑛 ⟺ 𝑥 ≤𝑛 <𝑥 +1⌈x⌉=n⟺n−1<x≤n⟺x≤n<x+1．

证明关于下（上）取整函数的不等式经常用到如下等价形式：（𝑥 ∈𝐑, 𝑛 ∈𝐙 x∈R, n∈Z）

- 𝑥 <𝑛 ⟺ ⌊𝑥⌋ <𝑛 x<n⟺⌊x⌋<n．
- 𝑛 <𝑥 ⟺ 𝑛 <⌈𝑥⌉n<x⟺n<⌈x⌉．
- 𝑥 ≤𝑛 ⟺ ⌈𝑥⌉ ≤𝑛 x≤n⟺⌈x⌉≤n．
- 𝑛 ≤𝑥 ⟺ 𝑛 ≤⌊𝑥⌋n≤x⟺n≤⌊x⌋．

涉及和、差的性质如下：（𝑥,𝑦 ∈𝐑 x,y∈R）

- ⌊𝑥⌋ +⌊𝑦⌋ ≤⌊𝑥 +𝑦⌋ ≤⌊𝑥⌋ +⌊𝑦⌋ +1⌊x⌋+⌊y⌋≤⌊x+y⌋≤⌊x⌋+⌊y⌋+1，且恰有一个等号成立．
- ⌈𝑥⌉ +⌈𝑦⌉ −1 ≤⌈𝑥 +𝑦⌉ ≤⌈𝑥⌉ +⌈𝑦⌉⌈x⌉+⌈y⌉−1≤⌈x+y⌉≤⌈x⌉+⌈y⌉，且恰有一个等号成立．
- ⌊|𝑥 −𝑦|⌋ ≤|⌊𝑥⌋ −⌊𝑦⌋| ≤⌈|𝑥 −𝑦|⌉⌊|x−y|⌋≤|⌊x⌋−⌊y⌋|≤⌈|x−y|⌉．
- ⌊|𝑥 −𝑦|⌋ ≤|⌈𝑥⌉ −⌈𝑦⌉| ≤⌈|𝑥 −𝑦|⌉⌊|x−y|⌋≤|⌈x⌉−⌈y⌉|≤⌈|x−y|⌉．

涉及商的性质如下：（𝑥 ∈𝐑, 𝑛 ∈𝐙, 𝑚 ∈𝐙+x∈R, n∈Z, m∈Z+）

- ⌈𝑛 𝑚⌉ =⌊𝑛+𝑚−1 𝑚⌋, ⌊𝑛 𝑚⌋ =⌈𝑛−𝑚+1 𝑚⌉⌈n m⌉=⌊n+m−1 m⌋, ⌊n m⌋=⌈n−m+1 m⌉．
- ⌊𝑥+𝑛 𝑚⌋ =⌊⌊𝑥⌋+𝑛 𝑚⌋, ⌈𝑥+𝑛 𝑚⌉ =⌈⌈𝑥⌉+𝑛 𝑚⌉⌊x+n m⌋=⌊⌊x⌋+n m⌋, ⌈x+n m⌉=⌈⌈x⌉+n m⌉．
- ⌊⌊𝑥/𝑛⌋𝑚⌋ =⌊𝑥 𝑛 𝑚⌋, ⌈⌈𝑥/𝑛⌉𝑚⌉ =⌈𝑥 𝑛 𝑚⌉⌊⌊x/n⌋m⌋=⌊x n m⌋, ⌈⌈x/n⌉m⌉=⌈x n m⌉．
- 对于 𝑥 >0 x>0，有 ⌊𝑥 𝑚⌋ =⌊𝑥⌋∑𝑘=1[𝑚 ∣𝑘]⌊x m⌋=∑k=1⌊x⌋[m∣k]．

其中，第二条和第三条性质都可以看作是如下结论的直接推论：

- 设 𝑓 f 为连续单增函数，且只要 𝑓(𝑥) ∈𝐙 f(x)∈Z，就有 𝑥 ∈𝐙 x∈Z，那么

  ⌊𝑓(𝑥)⌋=⌊𝑓(⌊𝑥⌋)⌋, ⌈𝑓(𝑥)⌉=⌈𝑓(⌈𝑥⌉)⌉.⌊f(x)⌋=⌊f(⌊x⌋)⌋, ⌈f(x)⌉=⌈f(⌈x⌉)⌉.
  证明

  由对称性，只需要证明第一个等式．如果 𝑥 x 是整数，那么命题显然．否则，⌊𝑥⌋ <𝑥⌊x⌋<x．由 𝑓 f 和下取整函数的单调性可知，⌊𝑓(𝑥)⌋ ≥⌊𝑓(⌊𝑥⌋)⌋⌊f(x)⌋≥⌊f(⌊x⌋)⌋．如果等号不成立，那么设 𝑦 =⌊𝑓(𝑥)⌋y=⌊f(x)⌋，它满足 ⌊𝑓(⌊𝑥⌋)⌋ <𝑦 ≤⌊𝑓(𝑥)⌋⌊f(⌊x⌋)⌋<y≤⌊f(x)⌋，这等价于 𝑓(⌊𝑥⌋) <𝑦 ≤𝑓(𝑥)f(⌊x⌋)<y≤f(x)．由 𝑓 f 的连续性可知，存在 ⌊𝑥⌋ <𝑥 0 ≤𝑥⌊x⌋<x 0≤x 使得 𝑓(𝑥 0) =𝑦 f(x 0)=y．因为 𝑦 ∈𝐙 y∈Z，所以 𝑥 0 ∈𝐙 x 0∈Z，这与 ⌊𝑥⌋⌊x⌋ 的定义矛盾．故而，等号成立，即 ⌊𝑓(𝑥)⌋ =⌊𝑓(⌊𝑥⌋)⌋⌊f(x)⌋=⌊f(⌊x⌋)⌋．

最后是一组关于带有取整函数的求和式的结论：（𝑥 ∈𝐑, 𝑛 ∈𝐙, 𝑚 ∈𝐙+x∈R, n∈Z, m∈Z+）

- 𝑛 =⌊𝑛 2⌋ +⌈𝑛 2⌉n=⌊n 2⌋+⌈n 2⌉．
- 𝑛 =⌊𝑛 𝑚⌋ +⌊𝑛+1 𝑚⌋ +⋯ +⌊𝑛+𝑚−1 𝑚⌋n=⌊n m⌋+⌊n+1 m⌋+⋯+⌊n+m−1 m⌋．
- 𝑛 =⌈𝑛 𝑚⌉ +⌈𝑛−1 𝑚⌉ +⋯ +⌈𝑛−𝑚+1 𝑚⌉n=⌈n m⌉+⌈n−1 m⌉+⋯+⌈n−m+1 m⌉．
- ⌊𝑚 𝑥⌋ =⌊𝑥⌋ +⌊𝑥+1 𝑚⌋ +⋯ +⌊𝑥+𝑚−1 𝑚⌋⌊m x⌋=⌊x⌋+⌊x+1 m⌋+⋯+⌊x+m−1 m⌋．
- ⌈𝑚 𝑥⌉ =⌈𝑥⌉ +⌈𝑥−1 𝑚⌉ +⋯ +⌈𝑥−𝑚−1 𝑚⌉⌈m x⌉=⌈x⌉+⌈x−1 m⌉+⋯+⌈x−m−1 m⌉．
- 当 𝑚 ⟂𝑛 m⟂n 时，𝑚−1∑𝑘=1⌊𝑘 𝑛 𝑚⌋ =1 2(𝑛 −1)(𝑚 −1)∑k=1 m−1⌊k n m⌋=1 2(n−1)(m−1)．
- 当 𝑚 ⟂𝑛 m⟂n 时，𝑚−1∑𝑘=1⌈𝑘 𝑛 𝑚⌉ =1 2(𝑛 +1)(𝑚 −1)∑k=1 m−1⌈k n m⌉=1 2(n+1)(m−1)．

这些乃至更一般的类似形式求和式的推导可以参考 类欧几里得算法 页面．

取整函数的更多性质以及应用可以参考如下页面：

- 取模运算：𝑛 m o d 𝑚 =𝑛 −⌊𝑛 𝑚⌋𝑚 n mod m=n−⌊n m⌋m．它可以用于 优化整数取模运算．
- 利用 Gauss 引理证明 二次互反律．
- 数论分块，尤其是它的性质证明部分．
- 计算阶乘中素数因子幂次的 Legendre 公式．
- Beatty 数列、Rayleigh 定理以及 Wythoff 博弈．

## 参考资料与注释

- 潘承洞，潘承彪．初等数论．北京大学出版社．
- Floor and ceiling functions - Wikipedia
- Graham, Ronald L., Donald E. Knuth, and Oren Patashnik. "Concrete mathematics: a foundation for computer science." (1989).

1. std::gcd - cppreference.com ↩

2. Are all primes (past 2 and 3) of the forms 6n+1 and 6n-1? ↩

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：c-forrest, Tiphereth-A, Enter-tainer, Great-designer, HeRaNO, ksyx, 383494, buuzzing, cr4c1an, Emp7iness, jifbt, Kaiser-Yang, Koishilll, Marcythm, Qiu-Quanzhi, SaisycJiang, sshwy, StarryReverie, StudyingFather, Xeonacid, xyf007
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用