数论基础

【第一讲】

第一讲我们要学习的概念有：

算术基本定理
带余除法、整除
约数、倍数、质数、公约数、公倍数、
gcd、lcm
模运算
同余式

扩展知识：

同余类
完全剩余系
简化剩余系

一、算数基本定理

算术基本定理是数论中的核心定理之一，其内容可表述为：

每个大于1的正整数都可以唯一地表示为有限个质数的乘积，其中唯一性是指在不考虑质数的顺序的情况下。

具体来说，该定理包含两部分核心含义：

存在性：对于任意一个大于1的正整数 $n$ ，总存在至少一组质数 $p_1, p_2, \dots, p_k$ （允许重复），使得
$n = p_1 \times p_2 \times \dots \times p_k$
此外，也可以写成如下形式：
$n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_n}=\prod_{i=1}^{n}p_{i}^{a_{i}}$
唯一性：若 $n$ 有两种不同的质数乘积表示形式 $n = p_1 \times p_2 \times \dots \times p_k = q_1 \times q_2 \times \dots \times q_m$ ，则这两组质数本质上是相同的（仅可能在顺序上不同，且每个质数出现的次数也相同）。

这种唯一的质数乘积形式通常称为该正整数的标准分解式（或 质因数分解式 ），例如 $12 = 2^2 \times 3$ 就是12的标准分解式。

举例：

$600=2^{3}\times 3\times 5^{2}$ 也就是说对 600 进行质因数分解能得到 质因子 $2,3,5$ ，并且这个分解是一定是唯一的，你无法在 600 的因子（约数）中找到其他质数

二、==带余除法与整除==

对于两个整数 $a,b$ ，存在两个唯一的整数 $q,r$ 满足：

b=aq+r

其中

q=\lfloor \frac{b}{a} \rfloor

r=b\%a

我们称 $q$ 是商， $r$ 是余数

当 $r=0$ 时，我们就称作 $a$ 整除 $b$

a|b

注意：

这里需要区分 “除” 与 ”除以”

$b/a$ 表示 $b$ 除以 $a$ ，同时表示 $a$ 除 $b$
$a|b$ 表示 $a$ 整除 $b$ ，同时表示 $b$ 能整除以 $a$ （也就是说 $a$ 是 $b$ 的约数， $b$ 是 $a$ 的倍数）

三、约数、倍数与质数

定义：

对于两个正整数 $a,b$ ，如果有 $a|b$ 那么称 $a$ 是 $b$ 的约数

约数又称因子

引入 带余除法：

对于两个正整数 $a,b$ ，如果满足：

b=aq+r,r=0

也就是说

b=aq,q=\lfloor \frac{b}{a}\rfloor

则称 $a$ 是 $b$ 的约数， $b$ 是 $a$ 的倍数

定义：

当且仅当某一个数的因子只有1和它本身，那么称这个数为质数，质数又称素数

四、公约数与公倍数

定义:

对于两个整数 $a,b$ 如果存在整数 $d$ 满足：

d|a,d|b

则称 $d$ 为 $a,b$ 的 公约数

对于两个整数 $a,b$ 如果存在整数 $d$ 满足：

a|d,b|d

则称 $d$ 为 $a,b$ 的公倍数

五、GCD与LCM

对于两个数 $a,b$ ，在它们的所有公约数 $d_{1},d_{2},...,d_{n}$ 中，最大的一个称为 最大公约数

英文是 Greatest Common Divisor ，简称 GCD

对于两个数 $a,b$ ，在它们的所有公倍数 $d_{1},d_{2},...,d_{n}$ 中，最小的一个称为 最小公倍数

英文是 Least Common Multiple ，简称 LCM

六、模运算

设 $m$ 是一个正整数， $a$ 是任意整数，存在唯一的整数 $q$ （商）和 $r$ （余数），使得：

a=m\cdot q+r

其中 $0\le r < m$ ，此时余数 $r$ 称作 $a$ 模 $m$ 的结果，记为：

r=a\mod m

模运算的基本性质:

（1）模运算对加法、减法、乘法具有 “可分配性” ，即可以先对参与运算的数取模，再进行运算，最后再次对结果取模，结果不变。

设 $a,b$ 为整数， $m$ 为正整数，则：

(a+b)\mod m=[(a\mod m)+(b\mod m)]\mod m

(a-b)\mod m=[(a\mod m)-(b\mod m)]\mod m

(a\times b)\mod m=[(a\mod m)\times (b\mod m)]\mod m

（2）模运算的幂运算性质

幂律：

a^{b}\mod m=[(a\mod m)^{b}]\mod m

幂的乘法：

a^{b+c}\mod m=[(a^{b}\mod m )\times (a^{c}\mod m)]\mod m

幂的乘方：

(a^{b})^{c}\mod m = a^{bc}\mod m=(a^{c})^{b}\mod m

幂分配律：

(ab)^{c}\mod m=[(a^{c}\mod m)\times (b^{c}\mod m)]\mod m

（3）其他性质

线性组合：

(ka+b)\mod m=[k(a\mod m)+(b\mod m)]\mod m

组合数取模：（Lucas定理）

C_{n}^{k}\mod p=C_{n/p}^{k/p}\times C_{n\mod p}^{k\mod p}\mod p

其中 $p$ 为质数

七、同余式

在式子 $a=m\cdot q+r$ 中，我们称 $r$ 为 $a$ 模 $m$ 的余数，同时

r=m\cdot q'+r

这样我们就得到了两个方程

\begin{cases} r=a-mq \\ r=r-mq' \end{cases}

于是我们定义符号 $\equiv$ 来表示这种关系，称作 “同余” 关系，字面意思为余数相同，写成

a\equiv r\mod m

这个式子就是 同余式

定理：

a\equiv b\pmod{m}\Leftrightarrow m|(a-b)

证明：

首先使用带余除法表示 $a$ 和 $b$
$a=mq_{1}+r,b=mq_{2}+r$
则
$a-b=m(q_{1}-q_{2})$
因为 $(a-b),(q_{1}-q_{2})$ 均为整数，因此
$m|(a-b)$

同余式的基本性质：

（1） 自反性 ：

a\equiv a\mod m

（2） 对称性 ：

若

a\equiv b\mod m

则

b\equiv a\mod m

（3） 传递性 ：

若

a\equiv b\mod m

且

b\equiv c\mod m

则

a\equiv c\mod m

（4）可加性：

若 $a\equiv b\mod m$ ，则对任意整数 $c$ ，有

a+c\equiv b+c\mod m

若 $a\equiv b\mod m$ 且 $c\equiv d\mod m$ ，则

a+c\equiv b+d\mod m

推论：

若 $a+c\equiv b\pmod{m}$ ， $c$ 为整数，则

a\equiv b-c\pmod{m}

（5）可乘性：

若 $a\equiv b\mod m$ ，则对任意整数 $c$ ，有

a\times c\equiv b\times c\mod m

若 $a\equiv b\mod m$ 且 $c\equiv d\mod m$ ，则

a\times c\equiv b\times d\mod m

若 $a\equiv b\pmod{m}$ ， $k$ 为正整数，则

a^{k}\equiv b^{k}\pmod{m}

若 $a\equiv b\pmod{m_{1}},a\equiv b\pmod{m_{2}},\gcd(m_{1},m_{2})=1$ ，则

a\equiv b\pmod{m_{1}m_{2}}

更一般的情况：

若 $a\equiv b\pmod{m_{1}},a\equiv b\pmod{m_{2}}$ ，则

a\equiv b\pmod{lcm(m_{1},m_{2})}

（可扩展到 $m_{1},m_{2},...,m_{n}$ ）

（6）可约性

若 $ac\equiv bc\pmod{m},\gcd(c,m)=1$ ，则

a\equiv b\pmod{m}

更一般的情况

若 $ac\equiv bc\pmod{c\cdot m}$ ，则

a\equiv b\pmod{m}

若 $a\equiv b\pmod{c\cdot m}$ ，则

a\equiv b\pmod{m}

若 $ac\equiv bc\pmod{m},\gcd(c,m)=d$ 则

a\equiv b \pmod{\frac{m}{d}}

扩展：“弃九法”的理论基础

例题：P4942 小凯的数字 - 洛谷

结论： 一个数字各个数位之和除以9的余数等于这个数除以9的余数

证明：

任取一个正整数 $N$ ，假设它是一个 $n$ 位数（ $n\ge1$ ），其各个数位上的数字从高位到低位依次为

N=\overline{a_{n-1}a_{n-2}...a_{1}a_{0}}

那么 $N$ 可表示为

N=a_{n-1}\times10^{n-1}+a_{n-2}\times 10^{n-2}+...+ a_{1}\times10^{1}+a_{0}\times10^{0}

其中 $0\le a_{k}\le9$ （ $k=0,1,2,...,n-1$ ），且 $a_{n-1}\ne0$ （首位数字不为0）

这实质上是对 $N$ 进行了十进制分解

根据 同余的幂运算性质 ：

若 $x\equiv y\pmod{m}$ ，则对任意非负整数 $k$ ，有

x^{k}\equiv y^{k}\pmod{m}

我们知道 $10\equiv 1\pmod{9}$

因此，对 $10$ 的任意非负整数次幂 $10^{k}$ （ $k>0$ ），有

10^{k}\equiv 1^{k}\equiv 1\pmod{9}

设 $S$ 为 $N$ 的各个数位之和，即

S=a_{n-1}+a_{n-2}+...+a_{1}+a_{0}

根据 同余的加法与乘法性质

若 $x\equiv y\pmod{m}$ ，则 $c\times x\equiv c\times y\pmod{m}$ （ $c$ 为整数）
若 $x\equiv y\pmod{m}$ 且 $u\equiv v\pmod{m}$ ，则 $x+u\equiv y+v\pmod{m}$

对 $N$ 的每一项 $a_{k}\times10^{k}$ 应用同余性质

因为 $10^{k}\equiv1\pmod{9}$ ，所有

a_{k}\times 10^{k}\equiv a_{k}\times 1\equiv a_{k}\pmod{9}

将所有项相加，依据同余的加法性质

N=a_{n-1}\times10^{n-1}+a_{n-2}\times 10^{n-2}+...+ a_{1}\times10^{1}+a_{0}\times10^{0}

\equiv a_{n-1}+a_{n-2}+...+a_{1}+a_{0}\pmod{9}\equiv S\pmod{9}

八、剩余类和剩余系

1 同余类

一个整数除以 $m$ 所得的最小非负余数是 $0,1,2,...,m-1$ 这 $m$ 个数之一，所以，以 $m$ 为模可将整数分为 $m$ 类：

km,km+1,km+2,...,km+(m-1)

在这 $m$ 类中，每一类的所有数对 $m$ 同余，而任意两个不同类中的数对 $m$ 不同余，这样我们就可以定义同余类或者叫做 剩余类

定义：

对模 $m$ 同余的数的集合，叫做模 $m$ 的一个 同余类 或者 剩余类，用 $[r]_{m}$ 表示对模 $m$ 同余 $r$ 的剩余类

例如：

5k，5k+1,5k+2,5k+3,5k+4

是模五的五个不同的剩余类，依次记作

[0]_{5},[1]_{5},[2]_{5},[3]_{5},[4]_{5}

定理：

（1）对模 $m$ 有且仅有 $m$ 个互不相同的剩余类

（2）模 $m$ 的一个剩余类中的一切数，与模 $m$ 的最大公约数都相等

说明：例如 $\gcd(6k+2,6)=\gcd(6q+2,6)$

2 完全剩余系

从模 $m$ 的每个剩余类中各取一个数，这 $m$ 个数所组成的集合叫做模 $m$ 的一个 完全剩余系

下面是几个常用的 完全剩余系 ：

（1）把 $\{0,1,2,...,m-1\}$ 叫做模 $m$ 的 最小非负完全剩余系

（2）把 $\{1,2,...,m-1,m\}$ 叫做模 $m$ 的 最小正完全剩余系

（3）把 $\{-(m-1),-(m-2),...,-1,0\}$ 叫做模 $m$ 的 最大非正完全剩余系

（4）把 $\{-m,-(m-1),-(m-2),...,-1\}$ 叫做模 $m$ 的 最大负完全剩余系

（5）当 $m$ 为奇数时，把 $\{-\frac{m-1}{2},...,-1,0,1,...,\frac{m-1}{2}\}$ 叫做模 $m$ 的 绝对最小完全剩余系

（6）当 $m$ 为偶数时，把 $\{-\frac{m}{2}+1,...,-1,0,1,...,\frac{m}{2}\}$ 叫做模 $m$ 的 绝对最小完全剩余系

定理：

（1） $m$ 个数 $a_{1},a_{2},...,a_{m}$ 构成模 $m$ 的 完全剩余系 ，则这 $m$ 个数一定是模 $m$ 的不同剩余类中的代表，因此这 $m$ 个数中的任意两个对模 $m$ 两两不同余

（2）设 $a_{1},a_{2},...,a_{m}$ 是模 $m$ 的一个完全剩余系， $b$ 是任意一个整数，则 $a_{1}+b,a_{2}+b,...,a_{m}+b$ 也是模 $m$ 的一个完全剩余系

（3）设 $a_{1},a_{2},...,a_{m}$ 是模 $m$ 的一个完全剩余系， $\gcd(b,m)=1$ ，则 $a_{1}b,a_{2}b,...,a_{m}b$ 也是模 $m$ 的一个完全剩余系