自然数的性质#

1. 后继函数$s(n)$(successor function): $s(0) = 1, s(1) = 2$等等. 加法可以看作后继函数的重复过程, 乘法可以看作是加法的重复过程.
2. 归纳性质(PMI): 对于某关于自然数的谓词$p(n)$, 若$p(0)$为真, 且$p(n) \implies p(n + 1)$为真, 则$\forall n \in N, p(n)$为真.
3. 良序性(WOP): 任何$N$的非空子集必有最小元.
4. 具有整除(divisibility): 若$b = ax(a,b,x \in Z, a\neq 0),$则称a整除b, 或$a|b$.
   • 1. $\forall n\in N, n|0$
   • 2. $a|b, b|c \implies a|c$
   • 3. $a|b, a|c \implies a$

带余除法#

对于$\forall a, b\in Z, a > 0, \exist q, r\in Z$使得$b=aq+r,0\le r < a$ 可记作$r=a\%b$

最大公约数(gcd)#

若$g = \operatorname{gcd}(a, b), \exist v_0, y_0\in Z$使得$g=v_0a+y_0b$.

互质(relatively prime)#

若$\operatorname{gcd}(a,b)=1$则称a,b互质

互质的性质

若$\operatorname{gcd}(a,m)=1, \operatorname{gcd}(b,m)=1,$则$\operatorname{gcd}(ab,m)=1$

若$c|ab,$且$\operatorname{gcd}(c,a)=1,$则$c|b$.

辗转相除法#

求gcd的经典算法.

1. 对a, b做带余除法$b=qa+r$
2. 若$r=0$, 则gcd(a, b) = r.
3. 若$r\neq0$, 则令$b=a, a=r$, 重复第一步
4. 由良序定理这总能得到结果.

算术基本定理#

所有大于0的整数具有唯一质因子分解.

欧几里得定理#

质数有无穷多个.

著名的素数猜想#

1. 哥德巴赫猜想
2. 孪生素数猜想: 有无穷多对差值为2的素数

二项式系数#

$\binom {n}{k}$称为二项式系数.

(杨辉三角)

二项式定理#

勒让德公式#

设某素数$p$在$n!$的分解式中的最高次幂为$E_p(n)$($n!$的质因数分解中含有$p^e$且$E_p(n)$最大)

这其实是个有限和, 因为最后$\frac{n}{p^k}$总会到0.

比如要求$50!$末尾有多少个零, 只需求出其中有多少个2, 多少个5, 取最小值(容易注意到5的数量总是比2小)即可.

在计算机中, 有一个更有用的等价形式(p-adic写法)

将$n$写成$p$进制. $S_p(n)$表示$n$的$p$进制中, 各位数字的和. 则

可以推广出库默尔定理.

库默尔定理#

素数$p$整除$\binom{n}{k}$的次数, 等于在$p$进制下计算$k + (n - k)$的进位次数.

同余#

称模$m$下$a$与$b$同余($m\not = 0$), 当且仅当:

记作

容易证明, 若模$m$下$a$与$b$同余, $c$与$d$同余, 则:

1. $a + c \equiv b + d \space (mod \space m)$
2. $ac \equiv bd \space (mod \space m)$
3. 由性质2可以推导出, $a^k \equiv b^k \space (mod \space m)$
4. 若$x$与$m$互质, $ax \equiv bx \space (mod \space m)$, 则$a \equiv b \space (mod \space m)$

性质1和3说明, 若$a$同余于$b$, $f(x)$是某个多项式, 则$f(a) \equiv f(b) \space (mod \space m)$

剩余类#

所有与整数a模m同余的整数构成的集合叫做模m的一个剩余类. 比如$\set{0, 5, -5, 10, -10}$是模5的一个剩余类.

同理$\set{1, 6, -4, 11, -9}$也是.

完全剩余系#

由m个整数组成的集合$\set{r_1, r_2, ..., r_m}$, 满足:

1. 集合里恰好有m个不重复的数
2. 这m个数来自m个不同的剩余类. 则称该集合为模m的一个完全剩余系(CRS, complete residue system).

例

1. 最小非负剩余系: $\set{0, 1, 2, ..., m - 1}$
2. 最小正剩余系: $\set{1, 2, 3, ..., m}$

在一个CRS上可以定义模加法, 模减法, 模乘法, 对模加法与模乘法形成一个环.

环

某个集合$S$在两个运算(这里以$+$, $\cdot$代替)下构成一个环, 当且仅当:

1. $S$在$+$下构成阿贝尔群(满足交换律的群).
2. $S$在$\cdot$下满足结合律
3. $\cdot$对$+$有左右分配律
4. 满足封闭性

简化剩余系#

某个集合, 满足:

1. 其每个元素各与$m$互质
2. 这些元素恰好构成了所有与$m$互质的同余类的一个完整代表集 则称该集合为模m的一个简化剩余系(RRS).

简化剩余系中的元素个数为欧拉函数$\varphi (m)$, 表示小于m的正整数中与m互质的数的个数.

在简化剩余系中, 可以定义加法, 减法, 乘法, 除法(即模逆元).也就是说其对加法构成一个群, 对乘法构成一个群.

群

称某个集合在某运算’+‘下构成一个群, 当且仅当该运算在该集合中满足:

1. 封闭性
2. 存在单位元
3. 每一个元素均存在逆元
4. 结合律

费马小定理#

若$p$为质数

欧拉定理#

欧拉定理是费马小定理的推广形式.