跳转至

数论基础

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

整除

整除的定义:设 。如果 ,使得 ,那么就说 可被 整除,记作 不被 整除记作

整除的性质:

  • ,那么
  • ,那么
  • ,那么

约数(因数):若 ,则称 的倍数, 的约数。

是所有非 整数的倍数。对于整数 的约数只有有限个。

平凡约数(平凡因数):对于整数 的平凡约数。当 时, 只有两个平凡约数。

对于整数 的其他约数称为真约数(真因数、非平凡约数、非平凡因数)。

约数的性质:

  • 设整数 。当 遍历 的全体约数的时候, 也遍历 的全体约数。
  • 设整数 ,则当 遍历 的全体正约数的时候, 也遍历 的全体正约数。

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

带余数除法

余数的定义:设 为两个给定的整数,。设 是一个给定的整数。那么,一定存在唯一的一对整数 ,满足

无论整数 取何值, 统称为余数。 等价于

一般情况下,,此时等式 称为带余数除法(带余除法)。这里的余数 称为最小非负余数。

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

绝对最小余数: 的绝对值的一半的相反数。即

最小正余数:。即

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

余数的性质:

  • 任一整数被正整数 除后,余数一定是且仅是 个数中的一个。
  • 相邻的 个整数被正整数 除后,恰好取到上述 个余数。特别地,一定有且仅有一个数被 整除。

最大公约数与最小公倍数

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

互素

两个整数互素(既约)的定义:若 ,则称 互素(既约)。

多个整数互素(既约)的定义:若 ,则称 互素(既约)。

多个整数互素,不一定两两互素。例如 互素,但是任意两个都不互素。

互素的性质与最大公约数理论:裴蜀定理(Bézout's identity)。见 裴蜀定理

辗转相除法

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

素数与合数

关于素数的算法见 素数

设整数 。如果 除了平凡约数外没有其他约数,那么称 为素数(不可约数)。

若整数 不是素数,则称 为合数。

总是同为素数或者同为合数。如果没有特别说明,素数总是指正的素数。

整数的因数是素数,则该素数称为该整数的素因数(素约数)。

素数与合数的简单性质:

  • 大于 的整数 是合数,等价于 可以表示为整数 )的乘积。
  • 如果素数 有大于 的约数 ,那么
  • 大于 的整数 一定可以表示为素数的乘积。
  • 对于合数 ,一定存在素数 使得
  • 素数有无穷多个。
  • 所有大于 的素数都可以表示为 的形式1

算术基本定理

算术基本引理:

是素数,,那么 至少有一个成立。

算术基本引理是素数的本质属性,也是素数的真正定义。

算术基本定理(唯一分解定理):

设正整数 ,那么必有表示:

其中 是素数。并且在不计次序的意义下,该表示唯一。

标准素因数分解式:

将上述表示中,相同的素数合并,可得:

称为正整数 的标准素因数分解式。

算术基本定理和算术基本引理,两个定理是等价的。

同余

同余的定义:设整数 。若 ,称 为模数(模), 同余于 对模 的剩余。记作

否则, 不同余于 不是 对模 的剩余。记作

这样的等式,称为模 的同余式,简称同余式。

根据整除的性质,上述同余式也等价于

如果没有特别说明,模数总是正整数。

式中的 对模 的剩余,这个概念与余数完全一致。通过限定 的范围,相应的有 对模 的最小非负剩余、绝对最小剩余、最小正剩余。

同余的性质:

  • 自反性:
  • 对称性:若 ,则
  • 传递性:若 ,则
  • 线性运算:若 则有:
  • , 则
  • ,则当 成立时,有
  • ,则当 成立时,有
  • ,则当 成立时,有 。若 能整除 中的一个,则 必定能整除 中的另一个。

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

C/C++ 的整数除法和取模运算

在 C/C++ 中,整数除法和取模运算,与数学上习惯的取模和除法不一致。

对于所有标准版本的 C/C++,规定在整数除法中:

  1. 当除数为 0 时,行为未定义;
  2. 否则 (a / b) * b + a % b 的运算结果与 a 相等。

也就是说,取模运算的符号取决于除法如何取整;而除法如何取整,这是实现定义的(由编译器决定)。

从 C992和 C++113标准版本起,规定 商向零取整(舍弃小数部分);取模的符号即与被除数相同。从此以下运算结果保证为真:

1
2
3
4
5 % 3 == 2;
5 % -3 == 2;
-5 % 3 == -2;
-5 % -3 == -2;

数论函数

数论函数指定义域为正整数的函数。数论函数也可以视作一个数列。

积性函数

定义

若函数 满足 都有 ,则 为积性函数。

若函数 满足 都有 ,则 为完全积性函数。

性质

均为积性函数,则以下函数也为积性函数:

为积性函数,则有

为完全积性函数,则有

例子

  • 单位函数:。(完全积性)
  • 恒等函数: 通常简记作 。(完全积性)
  • 常数函数:。(完全积性)
  • 除数函数: 通常简记作 通常简记作
  • 欧拉函数:
  • 莫比乌斯函数:,其中 表示 的本质不同质因子个数,它是一个加性函数。
加性函数

此处加性函数指数论上的加性函数 (Additive function)。对于加性函数 ,当整数 互质时,均有 。 应与代数中的加性函数 (Additive map) 区分。


参考资料与注释