数学符号和基础知识

前言

本篇内容不需要单独学习，可以在碰到自己所不熟悉的数学符号时来本页面查阅。

在学习数学的过程中大家会见到许多复杂的公式符号。因此在学习具体内容之前，建议大家首先理解下列常见符号的含义。一些特殊的符号会在对应的章节中讲到，而这里则有一些极为常见的符号需要大家提前掌握。

渐进符号

请参见 复杂度。

整除/同余理论常见符号

1. 整除符号：$x\mid y$，表示 $x$ 整除 $y$，即 $x$ 是 $y$ 的因数。
2. 取模符号：$x\bmod y$，表示 $x$ 除以 $y$ 得到的余数。
3. 互质符号：$x\perp y$，表示 $x$，$y$ 互质。
4. 最大公约数：$\gcd(x,y)$，在无混淆意义的时侯可以写作 $(x,y)$。
5. 最小公倍数：$\operatorname{lcm}(x,y)$，在无混淆意义的时侯可以写作 $[x,y]$。

数论函数常见符号

求和符号：$\sum$ 符号，表示满足特定条件的数的和。举几个例子：

• $\sum_{i=1}^n i$ 表示 $1+2+\dotsb+n$ 的和。其中 $i$ 是一个变量，在求和符号的意义下 $i$ 通常是 正整数或者非负整数（除非特殊说明）。这个式子的含义可以理解为，$i$ 从 $1$ 循环到 $n$，所有 $i$ 的和。这个式子用代码的形式很容易表达。当然，学过简单的组合数学的同学都知道 $\sum_{i=1}^n i=\dfrac{n(n+1)}{2}$。
• $\sum_{S\subseteq T}|S|$ 表示所有被 $T$ 包含的集合的大小的和。
• $\sum_{p\le n,p\perp n}1$ 表示的是 $n$ 以内有多少个与 $n$ 互质的数，即 $\varphi(n)$，$\varphi$ 是欧拉函数。

求积符号：$\prod$ 符号，表示满足特定条件的数的积。举几个例子：

• $\prod_{i=1}^ni$ 表示 $n$ 的阶乘，即 $n!$。在组合数学常见符号中会讲到。
• $\prod_{i=1}^na_i$ 表示 $a_1\times a_2\times a_3\times \dotsb\times a_n$。
• $\prod_{x|d}x$ 表示 $d$ 的所有因数的乘积。

在行间公式中，求和符号与求积符号的上下条件会放到符号的上面和下面，这一点要注意。

其他常见符号

1. 阶乘符号 $!$，$n!$ 表示 $1\times 2\times 3\times \dotsb \times n$。特别地，$0!=1$。
2. 向下取整符号：$\lfloor x\rfloor$，表示小于等于 $x$ 的最大的整数。常用于分数，比如分数的向下取整 $\left\lfloor\dfrac{x}{y}\right\rfloor$。
3. 向上取整符号：$\lceil x\rceil$，与向下取整符号相对，表示大于等于 $x$ 的最小的整数。
4. 组合数：$\binom{x}{y}$
5. 第一类斯特林数：$x\brack y$
6. 第二类斯特林数：$x\brace y$

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

整除

整除的性质：

• $a\mid b\iff-a\mid b\iff a\mid-b\iff|a|\mid|b|$
• $a\mid b\land b\mid c\implies a\mid c$
• $a\mid b\land a\mid c\iff\forall x,y\in\mathbf{Z}, a\mid(xb+yc)$
• $a\mid b\land b\mid a\implies b=\pm a$
• 设 $m\ne0$，那么 $a\mid b\iff ma\mid mb$。
• 设 $b\ne0$，那么 $a\mid b\implies|a|\le|b|$。
• 设 $a\ne0,b=qa+c$，那么 $a\mid b\iff a\mid c$。

约数

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

平凡约数（平凡因数）：对于整数 $b\ne0$，$\pm1$、$\pm b$ 是 $b$ 的平凡约数。当 $b=\pm1$ 时，$b$ 只有两个平凡约数。

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

约数的性质：

• 设整数 $b\ne0$。当 $d$ 遍历 $b$ 的全体约数的时候，$\dfrac{b}{d}$ 也遍历 $b$ 的全体约数。
• 设整数 $b\gt 0$，则当 $d$ 遍历 $b$ 的全体正约数的时候，$\dfrac{b}{d}$ 也遍历 $b$ 的全体正约数。

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

带余数除法

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

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

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

• 绝对最小余数：$d$ 取 $a$ 的绝对值的一半的相反数。即 $b=qa+r,-\dfrac{|a|}{2}\le r<|a|-\dfrac{|a|}{2}$。
• 最小正余数：$d$ 取 $1$。即 $b=qa+r,1\le r<|a|+1$。

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

余数的性质：

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

互素

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

素数与合数