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

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

整除的性质：

约数（因数）：若 ，则称 是 的倍数， 是 的约数。

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

平凡约数（平凡因数）：对于整数 ，、 是 的平凡约数。当 时， 只有两个平凡约数。

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

约数的性质：

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

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

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

一般情况下， 取 ，此时等式 称为带余数除法（带余除法）。这里的余数 称为最小非负余数。

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

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

最小正余数： 取 。即 。

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

余数的性质：

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

两个整数互素（既约）的定义：若 ，则称 和 互素（既约）。

多个整数互素（既约）的定义：若 ，则称 互素（既约）。

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

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

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

关于素数的算法见 素数。

设整数 。如果 除了平凡约数外没有其他约数，那么称 为素数（不可约数）。

若整数 且 不是素数，则称 为合数。

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

整数的因数是素数，则该素数称为该整数的素因数（素约数）。

素数与合数的简单性质：

算术基本引理：

设 是素数，，那么 和 至少有一个成立。

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

算术基本定理（唯一分解定理）：

设正整数 ，那么必有表示：

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

标准素因数分解式：

将上述表示中，相同的素数合并，可得：

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

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

同余的定义：设整数 。若 ，称 为模数（模）， 同余于 模 ， 是 对模 的剩余。记作 。

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

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

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

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

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

同余的性质：

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

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

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

也就是说，取模运算的符号取决于除法如何取整；而除法如何取整，这是实现定义的（由编译器决定）。

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

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

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

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

若 和 均为积性函数，则以下函数也为积性函数：

设

若 为积性函数，则有 。

若 为完全积性函数，则有 。

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

Are all primes (past 2 and 3) of the forms 6n+1 and 6n-1? ↩

Arithmetic operators (C) - cppreference.com ↩

Arithmetic operators (C++) - cppreference.com ↩