数论基础

bbbzzx · 2025-03-03 21:10:55 · 算法·理论

前言

本文对笔者接下来要学习的数论内容做一些铺垫。

本文讨论的所有内容全是在整数集内。

正文

整除

设 n,a \in \Z 且 n \neq 0，若 \exist b \in \Z，使得 n=ab，则 a 整除 n，记为 a \mid n，同时称 a 为 n 的约数（因子、因数），反之则记为 a \nmid n。

性质过于简单，不想写了。

素数、合数与整数唯一分解定理

见这个

gcd和lcm

对于 a,b \in \Z，记两数的最大公约数为 \gcd(a,b)，最小公倍数为 \operatorname{lcm}(a,b)。

• 交换律，\gcd(a,b)=\gcd(b,a)。
• 结合律，\gcd(a_1,a_2,a_3)=\gcd(\gcd(a_1,a_2),a_3)。
• 分配律，\gcd(ma_1,ma_2,ma_3 …)=m\gcd(a_1,a_2,a_3…)。

lcm同理。

以上性质均可用整数唯一分解证明。

互素

对于 a,b \in \Z，若 \gcd(a,b)=1，则称 a，b 互素，记为 a \bot b，根据性质，若 a \bot b，则有 \operatorname{lcm}(a,b)=ab。

剩余

设 a=qm+b，b \in [0,m)，称 b 是 a 对模 m 的剩余，记为 a \bmod m =b，同时称 a，b 对模 m 同余，记为 a \equiv b \pmod m。

• 同余是等价关系。
• 同余有线性运算。若 a \equiv b \pmod m，c\equiv d \pmod m，则 a \pm c \equiv b\pm d \pmod m，ac \equiv bd \pmod m。
• 若 a \equiv b \pmod m，则 \gcd(a,m)=\gcd(b,m)。

剩余类与剩余系

对于模 m，对它的剩余有 0 到 m-1 共 m 种，把所有与一个代表元素 a \in [0,m-1] 同余的整数构成的集合叫做一个剩余类（同余类） [a]，显然模 m 有 m 个同余类。

从 m 的每个剩余类中取一个元素构成一个集合，称为模 m 的一个完全剩余系（完系），从 m 的完系中取所有与 m 互素的数构成的子集称为 m 的简化剩余系（既约剩余系，缩系）。

• 对于模 m 的一个完系 r，\forall a \in \Z,b \in \Z,\gcd(a,m)=1，ar_i+b 也构成一个完系。
• 对于模 m 的一个缩系 r，\forall a \in \Z,\gcd(a,m)=1，ar_i 也构成一个缩系。

剩余系的复合

设模 m=pq，p,q 的完系为 r_p,r_q，\forall x \in r_p,y \in r_q,a \in \Z,\gcd(a,m)=1，ax+py 可以构成 m 的一个完系。

证明：

即证 x_1,x_2 \in r_p，y_1,y_2 \in r_q，若 ax_1+py_1 \equiv ax_2+py_2 \pmod m，一定有 x_1=x_2,y_1=y_2。

因为 m=pq，所以 ax_1+py_1 \equiv ax_2+py_2 \pmod p，于是 ax_1 \equiv ax_2 \pmod p。

因为 \gcd(a,m)=1，所以 x_1 \equiv x_2 \pmod p，于是 x_1=x_2。

再把结论代回，得 py_1 \equiv py_2 \pmod m，根据同余性质有 y_1 \equiv y_2 \pmod q，于是 y_1=y_2，得证。

类似地，设模 m=pq,\gcd(p,q)=1，p,q 的缩系为 r_p,r_q，\forall x \in r_p,y \in r_q，qx+py 可以构成 m 的一个缩系。

数论函数

称定义域 D \subset \N 的函数为数论函数（算术函数）。

积性函数

若函数 f 满足 f(1)=1，\forall x,y \in D,\gcd(x,y)=1，都有f(xy)=f(x)f(y)，称 f 为一个积性函数（乘性函数）。

若函数 f 满足 f(1)=1，\forall x,y \in D，都有f(xy)=f(x)f(y)，称 f 为一个完全积性函数。

若 f,g 为积性函数，则有

为积性函数。

积性函数例子：