数论基础

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

整除

整除的性质：

• $a\mid b⟺-a\mid b⟺a\mid -b⟺\left|a\right|\mid |b|$
• $a\mid b\wedge b\mid c⟹a\mid c$
• $a\mid b\wedge a\mid c⟺\mathrm{\forall }x,y\in \mathbf{Z},a\mid (xb+yc)$
• $a\mid b\wedge b\mid a⟹b=\pm a$
• 设 $m\ne 0$，那么 $a\mid b⟺ma\mid mb$．
• 设 $b\ne 0$，那么 $a\mid b⟹\left|a\right|\le |b|$．
• 设 $a\ne 0,b=qa+c$，那么 $a\mid b⟺a\mid c$．

约数

$0$ 是所有非 $0$ 整数的倍数．对于整数 $b\ne 0$，$b$ 的约数只有有限个．

平凡约数（平凡因数）：对于整数 $b\ne 0$，$\pm 1$、$\pm b$ 是 $b$ 的平凡约数．当 $b=\pm 1$ 时，$b$ 只有两个平凡约数．

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

约数的性质：

• 设整数 $b\ne 0$．当 $d$ 遍历 $b$ 的全体约数的时候，${\displaystyle \frac{b}{d}}$ 也遍历 $b$ 的全体约数．
• 设整数 $b>0$，则当 $d$ 遍历 $b$ 的全体正约数的时候，${\displaystyle \frac{b}{d}}$ 也遍历 $b$ 的全体正约数．

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

带余数除法

无论整数 $d$ 取何值，$r$ 统称为余数．$a\mid b$ 等价于 $a\mid r$．

一般情况下，$d$ 取 $0$，此时等式 称为带余数除法（带余除法）．这里的余数 $r$ 称为最小非负余数．

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

• 绝对最小余数：$d$ 取 $a$ 的绝对值的一半的相反数．即 ．
• 最小正余数：$d$ 取 $1$．即 ．

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

余数的性质：

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

最大公约数与最小公倍数

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

最大公约数有如下性质：

• $(a_1,\dots ,a_n)=(|a_1|,\dots ,|a_n|)$；
• $(a,b)=(b,a)$；
• 若 $a\ne 0$，则 $(a,0)=(a,a)=|a|$；
• $(bq+r,b)=(r,b)$；
• $(a_1,\dots ,a_n)=((a_1,a_2),a_3,\dots ,a_n)$．进而 ；
• 对不全为 $0$ 的整数 $a_1,\dots ,a_n$ 和非零整数 $m$，$(m{a}_1,\dots ,m{a}_n)=\left|m\right|(a_1,\dots ,a_n)$；
• 对不全为 $0$ 的整数 $a_1,\dots ,a_n$，若 $(a_1,\dots ,a_n)=d$，则 $(a_1/d,\dots ,a_n/d)=1$；
• $(a^n,b^n)=(a,b{)}^n$．

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

• 若 $b|ac$ 且 $(a,b)=1$，则 $b\mid c$；
• 若 $b|c$、$a|c$ 且 $(a,b)=1$，则 $ab\mid c$；
• 若 $(a,b)=1$，则 $(a,bc)=(a,c)$；
• 若 $(a_i,b_j)=1,\mathrm{\forall }1\le i\le n,1\le j\le m$，则 $(\prod _i{a}_i,\prod _j{b}_j)=1$．特别地，若 $(a,b)=1$，则 $(a^n,b^m)=1$；
• 对整数 $a_1,\dots ,a_n$，若 $\mathrm{\exists }v\in \mathbf{Z},\prod _i{a}_i=v^m$，且 $(a_i,a_j)=1,\mathrm{\forall }i\ne j$，则 $\mathrm{\forall }1\le i\le n,\sqrt[m]{a_i}\in \mathbf{Z}$．

最小公倍数有如下性质：

• $[a_1,\dots ,a_n]=[|a_1|,\dots ,|a_n|]$；
• $[a,b]=[b,a]$；
• 若 $a\ne 0$，则 $[a,1]=[a,a]=|a|$；
• 若 $a\mid b$，则 $[a,b]=|b|$；
• $[a_1,\dots ,a_n]=[[a_1,a_2],a_3,\dots ,a_n]$．进而 ；
• 若 $a_i\mid m,\mathrm{\forall }1\le i\le n$，则 $[a_1,\dots ,a_n]\mid m$；
• $[m{a}_1,\dots ,m{a}_n]=\left|m\right|[a_1,\dots ,a_n]$；
• $[a,b,c][ab,bc,ca]=[a,b][b,c][c,a]$；
• $[a^n,b^n]=[a,b{]}^n$．

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

• $(a,b)[a,b]=|ab|$；
• $(ab,bc,ca)[a,b,c]=|abc|$；
• ${\displaystyle \frac{(a,b,c{)}^2}{(a,b)(b,c)(a,c)}}={\displaystyle \frac{[a,b,c{]}^2}{[a,b][b,c][a,c]}}$．

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

互素

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

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

辗转相除法

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

素数与合数

关于素数的算法见 素数．

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

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

素数与合数的简单性质：

• 大于 $1$ 的整数 $a$ 是合数，等价于 $a$ 可以表示为整数 $d$ 和 $e$（）的乘积．
• 如果素数 $p$ 有大于 $1$ 的约数 $d$，那么 $d=p$．
• 大于 $1$ 的整数 $a$ 一定可以表示为素数的乘积．
• 对于合数 $a$，一定存在素数 $p\le \sqrt{a}$ 使得 $p\mid a$．
• 素数有无穷多个．
• 所有大于 $3$ 的素数都可以表示为 $6n\pm 1$ 的形式²．

算术基本定理

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

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

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

$$a=p_1{p}_2\cdots p_s$$

其中 $p_j(1\le j\le s)$ 是素数．并且在不计次序的意义下，该表示唯一．

标准素因数分解式

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

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

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

同余

根据整除的性质，上述同余式也等价于 $a\equiv b(\mathrm{mod}(-m))$．

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

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

同余的性质：

• 同余是 等价关系，即同余具有
  • 自反性：$a\equiv a(\mathrm{mod}m)$．
  • 对称性：若 $a\equiv b(\mathrm{mod}m)$，则 $b\equiv a(\mathrm{mod}m)$．
  • 传递性：若 $a\equiv b(\mathrm{mod}m),b\equiv c(\mathrm{mod}m)$，则 $a\equiv c(\mathrm{mod}m)$．
• 线性运算：若 $a,b,c,d\in \mathbf{Z},m\in {\mathbf{N}}^{\ast },a\equiv b(\mathrm{mod}m),c\equiv d(\mathrm{mod}m)$ 则有：
  • $a\pm c\equiv b\pm d(\mathrm{mod}m)$．
  • $a\times c\equiv b\times d(\mathrm{mod}m)$．
• 设 $f(x)=\sum _{i=0}^n{a}_i{x}^i$ 和 $g(x)=\sum _{i=0}^n{b}_i{x}^i$ 是两个整系数多项式，$m\in {\mathbf{N}}^{\ast }$，且 $a_i\equiv b_i(\mathrm{mod}m),0\le i\le n$，则对任意整数 $x$ 均有 $f(x)\equiv g(x)(\mathrm{mod}m)$．进而若 $s\equiv t(\mathrm{mod}m)$，则 $f(s)\equiv g(t)(\mathrm{mod}m)$．
• 若 $a,b\in \mathbf{Z},k,m\in {\mathbf{N}}^{\ast },a\equiv b(\mathrm{mod}m)$, 则 $ak\equiv bk(\mathrm{mod}mk)$．
• 若 $a,b\in \mathbf{Z},d,m\in {\mathbf{N}}^{\ast },d\mid a,d\mid b,d\mid m$，则当 $a\equiv b(\mathrm{mod}m)$ 成立时，有 ．
• 若 $a,b\in \mathbf{Z},d,m\in {\mathbf{N}}^{\ast },d\mid m$，则当 $a\equiv b(\mathrm{mod}m)$ 成立时，有 $a\equiv b(\mathrm{mod}d)$．
• 若 $a,b\in \mathbf{Z},d,m\in {\mathbf{N}}^{\ast }$，则当 $a\equiv b(\mathrm{mod}m)$ 成立时，有 $(a,m)=(b,m)$．若 $d$ 能整除 $m$ 及 $a,b$ 中的一个，则 $d$ 必定能整除 $a,b$ 中的另一个．

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

同余类与剩余系

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

• $r+A:=\{r+a:a\in A\}$；
• $rA:=\{ra:a\in A\}$；
• $A+B:=\{a+b:a\in A,b\in B\}$；
• $AB:=\{ab:a\in A,b\in B\}$．

由同余类的定义可知：

• ；
• ；
• 对任意 $r,s\in \mathbf{Z}$，要么 ，要么 ；
• 若 $m_1\mid m$，则对任意整数 $r$ 均有 $r+m\mathbf{Z}\subseteq r+m_1\mathbf{Z}$．

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

我们把模 $m$ 的同余类全体构成的集合记为 ${\mathbf{Z}}_m$，即

不难发现：

• 对任意整数 $a$，$a+{\mathbf{Z}}_m={\mathbf{Z}}_m$；
• 对任意与 $m$ 互质的整数 $b$，$b{\mathbf{Z}}_m={\mathbf{Z}}_m$．

由 商群 的定义可知 ${\mathbf{Z}}_m=\mathbf{Z}/m\mathbf{Z}$，所以有时我们也会用 $\mathbf{Z}/m\mathbf{Z}$ 表示 ${\mathbf{Z}}_m$．

由 抽屉原理 可知：

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

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

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

• 最小非负（完全）剩余系：$0,\dots ,m-1$；
• 最小正（完全）剩余系：$1,\dots ,m$；
• 绝对最小（完全）剩余系：$-\lfloor m/2\rfloor ,\dots ,-\lfloor -m/2\rfloor -1$；
• 最大非正（完全）剩余系：$-m+1,\dots ,0$；
• 最大负（完全）剩余系：$-m,\dots ,-1$．

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

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

• 在模 $m$ 的任意一个同余类中，任取两个整数 $a_1,a_2$ 均有 $(a_1,m)=(a_2,m)$．

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

我们把模 $m$ 的既约同余类全体构成的集合记为 ${\mathbf{Z}}_m^{\ast }$，即

由 抽屉原理 可知：

• 任取 $\phi (m)+1$ 个与 $m$ 互质的整数，必有两个整数模 $m$ 同余．
• 存在 $\phi (m)$ 个与 $m$ 互质且两两模 $m$ 不同余的整数．

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

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

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

剩余系的复合

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

• 若 $m=m_1{m}_2,1\le m_1,m_2$，令 $Z_{m_1},Z_{m_2}$ 分别为模 $m_1,m_2$ 的 完全 剩余系，则对任意与 $m_1$ 互质的 $a$ 均有：

  $$Z_m=a{Z}_{m_1}+m_1{Z}_{m_2}.$$

  为模 $m$ 的 完全 剩余系．进而，若 $m=\prod _{i=1}^k{m}_i,1\le m_1,m_2,\dots ,m_k$，令 $Z_{m_1},\dots ,Z_{m_k}$ 分别为模 $m_1,\dots ,m_k$ 的 完全 剩余系，则：

  $$Z_m=\sum _{i=1}^k\left(\prod _{j=1}^{i-1}{m}_j\right)Z_{m_i}.$$

  为模 $m$ 的 完全 剩余系．

证明

只需证明对任意满足 $ax+m_{1}y\equiv a{x}^{\prime }+m_1{y}^{\prime }(\mathrm{mod}{m}_1{m}_2)$ 的 $x,x^{\prime }\in Z_{m_1}$，$y,y^{\prime }\in Z_{m_2}$，都有：

$$ax+m_{1}y=a{x}^{\prime }+m_1{y}^{\prime }.$$

实际上，由 $m_1\mid m_1{m}_2$，我们有 $ax+m_{1}y\equiv a{x}^{\prime }+m_1{y}^{\prime }(\mathrm{mod}{m}_1)$，进而 $ax\equiv a{x}^{\prime }(\mathrm{mod}{m}_1)$，由 $(a,m_1)=1$ 可知 $x\equiv x^{\prime }(\mathrm{mod}{m}_1)$，进而有 $x=x^{\prime }$．

进一步，$m_{1}y\equiv m_1{y}^{\prime }(\mathrm{mod}{m}_1{m}_2)$，则 $y\equiv y^{\prime }(\mathrm{mod}{m}_2)$，即 $y=y^{\prime }$．

因此，

$$ax+m_{1}y=a{x}^{\prime }+m_1{y}^{\prime }.$$

• 若 $m=m_1{m}_2,1\le m_1,m_2,(m_1,m_2)=1$，令 $Z_{m_1}^{\ast },Z_{m_2}^{\ast }$ 分别为模 $m_1,m_2$ 的 既约 剩余系，则：

  $$Z_m^{\ast }=m_2{Z}_{m_1}^{\ast }+m_1{Z}_{m_2}^{\ast }.$$

  为模 $m$ 的 既约 剩余系．

证明

令 $Z_{m_1},Z_{m_2}$ 分别为模 $m_1,m_2$ 的完全剩余系，我们已经证明了

$$Z_m=m_2{Z}_{m_1}+m_1{Z}_{m_2}$$

为模 $m$ 的完全剩余系．令 $M=\{a\in Z_m:(a,m)=1\}\subseteq Z_m$，显然 $M$ 为模 $m$ 的既约剩余系，所以我们只需证明 $M=Z_m^{\ast }$ 即可．

显然 $Z_m^{\ast }\subseteq Z_m$．

任取 $m_{2}x+m_{1}y\in M$，其中 $x\in Z_{m_1}$ 且 $y\in Z_{m_2}$，有 $(m_{2}x+m_{1}y,m_1{m}_2)=1$，由 $(m_1,m_2)=1$ 可得

$$1=(m_{2}x+m_{1}y,m_1)=(m_{2}x,m_1)=(x,m_1),$$ $$1=(m_{2}x+m_{1}y,m_2)=(m_{1}y,m_2)=(y,m_2).$$

因此可得 $x\in Z_{m_1}^{\ast }$ 且 $y\in Z_{m_2}^{\ast }$，即 $M\subseteq Z_m^{\ast }$．

任取 $m_{2}x+m_{1}y\in Z_m^{\ast }$，其中 $x\in Z_{m_1}^{\ast }$ 且 $y\in Z_{m_2}^{\ast }$，有 $(x,m_1)=1$ 且 $(y,m_2)=1$，由 $(m_1,m_2)=1$ 可得

$$(m_{2}x+m_{1}y,m_1)=(m_{2}x,m_1)=(x,m_1)=1,$$ $$(m_{2}x+m_{1}y,m_2)=(m_{1}y,m_2)=(x,m_2)=1,$$

因此可得 $(m_{2}x+m_{1}y,m_1{m}_2)=1$，即 $Z_m^{\ast }\subseteq M$．

综上所述，

$$Z_m^{\ast }=m_2{Z}_{m_1}^{\ast }+m_1{Z}_{m_2}^{\ast }.$$

为模 $m$ 的 既约 剩余系．

数论函数

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

积性函数

性质

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

对正整数 $x$，设其唯一质因数分解为 $x=\prod p_i^{k_i}$，其中 $p_i$ 为质数．

若 $F(x)$ 为积性函数，则有 $F(x)=\prod F(p_i^{k_i})$．

若 $F(x)$ 为完全积性函数，则有 $F(x)=\prod F(p_i^{k_i})=\prod F(p_i{)}^{k_i}$．

例子

• 单位函数：$\epsilon (n)=[n=1]$．（完全积性）
• 恒等函数：${\mathrm{id}}_k(n)=n^k$，${\mathrm{id}}_1(n)$ 通常简记作 $\mathrm{id}(n)$．（完全积性）
• 常数函数：$1(n)=1$．（完全积性）
• 除数函数：${\sigma }_k(n)=\sum _{d\mid n}{d}^k$．${\sigma }_0(n)$ 通常简记作 $d(n)$ 或 $\tau (n)$，${\sigma }_1(n)$ 通常简记作 $\sigma (n)$．
• 欧拉函数：$\phi (n)=\sum _{i=1}^n[(i,n)=1]$．
• 莫比乌斯函数：，其中 $\omega (n)$ 表示 $n$ 的本质不同质因子个数．

加性函数

性质

对正整数 $x$，设其唯一质因数分解为 $x=\prod p_i^{k_i}$，其中 $p_i$ 为质数．

若 $F(x)$ 为加性函数，则有 $F(x)=\sum F(p_i^{k_i})$．

若 $F(x)$ 为完全加性函数，则有 $F(x)=\sum F(p_i^{k_i})=\sum F(p_i)\cdot k_i$．

例子

为方便叙述，令所有质数组成的集合为 $\mathbf{P}$.

• 素因数分解中 $p$ 的重数：${\nu }_p(n)=max\{k\in \mathbf{N}:p^k\mid n\}$，其中，$p\in \mathbf{P}$．（完全加性）
• 所有质因子数目：$\mathrm{\Omega }(n)=\sum _{p\in \mathbf{P}}{\nu }_p(n)$．（完全加性）
• 相异质因子数目：$\omega (n)=\sum _{p\in \mathbf{P}}[p\mid n]$．
• 所有质因子之和：$a_0(n)=\sum _{p\in \mathbf{P}}{\nu }_p(n)\cdot p$．（完全加性）
• 相异质因子之和：$a_1(n)=\sum _{p\in \mathbf{P}}[p\mid n]\cdot p$．

取整函数

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

$$\lfloor x\rfloor =max\{k\in \mathbf{Z}:k\le x\},\lceil x\rceil =min\{k\in \mathbf{Z}:k\ge x\}.$$

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

取整函数有如下基本性质：（$x\in \mathbf{R},n\in \mathbf{Z}$）

• $x\in \mathbf{Z}⟺x=\lfloor x\rfloor =\lceil x\rceil$．
• $\lceil x\rceil -\lfloor x\rfloor =[x\notin \mathbf{Z}]$．
• ．
• $\lfloor -x\rfloor =-\lceil x\rceil ,\lceil -x\rceil =-\lfloor x\rfloor$．
• $\lfloor x+n\rfloor =\lfloor x\rfloor +n,\lceil x+n\rceil =\lceil x\rceil +n$．
• $\lfloor x\rfloor$ 和 $\lceil x\rceil$ 都是关于 $x$ 的单调弱增函数．

证明关于下（上）取整函数的等式经常用到如下等价形式：（$x\in \mathbf{R},n\in \mathbf{Z}$）

• ．
• ．

证明关于下（上）取整函数的不等式经常用到如下等价形式：（$x\in \mathbf{R},n\in \mathbf{Z}$）

• ．
• ．
• $x\le n⟺\lceil x\rceil \le n$．
• $n\le x⟺n\le \lfloor x\rfloor$．

涉及和、差的性质如下：（$x,y\in \mathbf{R}$）

• $\lfloor x\rfloor +\lfloor y\rfloor \le \lfloor x+y\rfloor \le \lfloor x\rfloor +\lfloor y\rfloor +1$，且恰有一个等号成立．
• $\lceil x\rceil +\lceil y\rceil -1\le \lceil x+y\rceil \le \lceil x\rceil +\lceil y\rceil$，且恰有一个等号成立．
• $\lfloor |x-y|\rfloor \le |\lfloor x\rfloor -\lfloor y\rfloor |\le \lceil |x-y|\rceil$．
• $\lfloor |x-y|\rfloor \le |\lceil x\rceil -\lceil y\rceil |\le \lceil |x-y|\rceil$．

涉及商的性质如下：（$x\in \mathbf{R},n\in \mathbf{Z},m\in {\mathbf{Z}}_{+}$）

• $\lceil {\displaystyle \frac{n}{m}}\rceil =\lfloor {\displaystyle \frac{n+m-1}{m}}\rfloor ,\lfloor {\displaystyle \frac{n}{m}}\rfloor =\lceil {\displaystyle \frac{n-m+1}{m}}\rceil$．
• $\lfloor {\displaystyle \frac{x+n}{m}}\rfloor =\lfloor {\displaystyle \frac{\lfloor x\rfloor +n}{m}}\rfloor ,\lceil {\displaystyle \frac{x+n}{m}}\rceil =\lceil {\displaystyle \frac{\lceil x\rceil +n}{m}}\rceil$．
• $\lfloor {\displaystyle \frac{\lfloor x/n\rfloor }{m}}\rfloor =\lfloor {\displaystyle \frac{x}{nm}}\rfloor ,\lceil {\displaystyle \frac{\lceil x/n\rceil }{m}}\rceil =\lceil {\displaystyle \frac{x}{nm}}\rceil$．
• 对于 ，有 ${\displaystyle \lfloor \frac{x}{m}\rfloor =\sum _{k=1}^{\lfloor x\rfloor }[m\mid k]}$．

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

• 设 $f$ 为连续单增函数，且只要 $f(x)\in \mathbf{Z}$，就有 $x\in \mathbf{Z}$，那么

  $$\lfloor f(x)\rfloor =\lfloor f(\lfloor x\rfloor )\rfloor ,\lceil f(x)\rceil =\lceil f(\lceil x\rceil )\rceil .$$
  证明

  由对称性，只需要证明第一个等式．如果 $x$ 是整数，那么命题显然．否则，．由 $f$ 和下取整函数的单调性可知，$\lfloor f(x)\rfloor \ge \lfloor f(\lfloor x\rfloor )\rfloor$．如果等号不成立，那么设 $y=\lfloor f(x)\rfloor$，它满足 ，这等价于 ．由 $f$ 的连续性可知，存在 使得 $f(x_0)=y$．因为 $y\in \mathbf{Z}$，所以 $x_0\in \mathbf{Z}$，这与 $\lfloor x\rfloor$ 的定义矛盾．故而，等号成立，即 $\lfloor f(x)\rfloor =\lfloor f(\lfloor x\rfloor )\rfloor$．

最后是一组关于带有取整函数的求和式的结论：（$x\in \mathbf{R},n\in \mathbf{Z},m\in {\mathbf{Z}}_{+}$）

• $n=\lfloor {\displaystyle \frac{n}{2}}\rfloor +\lceil {\displaystyle \frac{n}{2}}\rceil$．
• $n=\lfloor {\displaystyle \frac{n}{m}}\rfloor +\lfloor {\displaystyle \frac{n+1}{m}}\rfloor +\cdots +\lfloor {\displaystyle \frac{n+m-1}{m}}\rfloor$．
• $n=\lceil {\displaystyle \frac{n}{m}}\rceil +\lceil {\displaystyle \frac{n-1}{m}}\rceil +\cdots +\lceil {\displaystyle \frac{n-m+1}{m}}\rceil$．
• $\lfloor mx\rfloor =\lfloor x\rfloor +\lfloor x+{\displaystyle \frac{1}{m}}\rfloor +\cdots +\lfloor x+{\displaystyle \frac{m-1}{m}}\rfloor$．
• $\lceil mx\rceil =\lceil x\rceil +\lceil x-{\displaystyle \frac{1}{m}}\rceil +\cdots +\lceil x-{\displaystyle \frac{m-1}{m}}\rceil$．
• 当 $m⟂n$ 时，${\displaystyle \sum _{k=1}^{m-1}\lfloor \frac{kn}{m}\rfloor =\frac{1}{2}(n-1)(m-1)}$．
• 当 $m⟂n$ 时，${\displaystyle \sum _{k=1}^{m-1}\lceil \frac{kn}{m}\rceil =\frac{1}{2}(n+1)(m-1)}$．

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

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

• 取模运算：．它可以用于 优化整数取模运算．
• 利用 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).

本页面最近更新：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 协议之条款下提供，附加条款亦可能应用