一、整除的概念，欧几里得除法； 二、整数的表示； 三、最大公因数与广义欧几里得除法； 四、整除的进一步性质及最小公倍数； 五、整数分解； 六、素数的算数基本定理； 七、素数定理。
一、整除的概念，欧几里得除法
设a，b是任意两个整数，其中b ≠ 0.如果存在一个整数q使得等式 a = q · b 成立，就称 b 整除 a 或者 a 被 b 整除，记作 b | a，并把b叫做a的因数，把a叫做b的倍数。人们常把q写成 a / b。否则，就称b不能整除a，或者a不能被b整除。
此外，再不会混淆的情况下，乘法a·b简记为ab。
注：
（1）当b遍历整数a的所有因数时，-b也遍历整数a的所有因数。
（2）当b遍历整数a的所有因数时，a/b也遍历整数a的所有因数。
根据定义有：
0是任何非零整数的倍数。
1是任何整数的倍数。
任何非零整数a是其本身的倍数，也是其自身的因数。
设a，b ≠ 0，c ≠ 0是三个整数。若 b | a，c | b，则c | a。
设a，b，c ≠ 0是三个整数。若c | a，c | b，则c | a ± b。
设a，b，c ≠ 0是三个整数。若c | a，c | b，则对任意整数s，t，有c |（s·a+t·b）。
设整数c ≠ 0。若整数a1，···，an都是整数c的倍数，则对任意n个整数s1，···，sn，整数s1a1 + ··· + snan是c的倍数。
设a，b都是非零整数。若a | b，b | a，则a = ±b。
设整数n ≠ 0，±1.如果除了显然因数±1和±n外，n没有其他因数，那么n就叫做素数（或质数或不可约数），否则，n叫做合数。
设n是一个正合数，p是n的一个大于1的最小正因数，则p一定是素数，且p≤n1/2。
设n是正整数。若果对所有的素数p ≤ n1/2，都有p不被n整除，则n一定是素数。
应用该定理，可得到一个寻找素数的确定性方法，通常叫做平凡除法或厄拉托塞师筛法。
设a，b是两个整数，其中b>0，则存在唯一的整数q，r使得a = q·b + r ，0 ≤ r ≤ b 。
a = q·b + r ，0 ≤ r ≤ b中，q叫做a被b除所得的不完全商，r叫做a被b除所得的余数。
设x是实数，称x的整数部分为小于或等于x的最大整数，记成[x]。
这时，有[x] ≤ x＜ [x]+1。
素数的平凡判别：对于给定正整数N，设不大于N1/2的所有素数为p1，p2,，···，ps。
如果N被所有pi除的余数都不为零，则N是素数。
设a，b是两个整数，其中b＞0.则对任意的整数c，存在唯一的整数q，r使得
a = q·b+r，c ≤ r＜b+c
二、整数的表示
设b是大于1的正整数，则每个正整数n可唯一地表示成
n = ak-1bk-1 + ak-2bk-2 + ··· + a1b + a0，
其中ai是整数，0 ≤ ai ≤ b-1，i = 1，···，k-1，且首项系数ak-1 ≠ 0.
大O符号：
设f(n)和g(n)都是正整数n的正值函数，如果存在一个正常数C，使得对任意的正整数n都有f(n) ≤ Cg(n)，
就称g(n)是f(n)的界，记作f(n) = O(g(n))，简记为f = O(g)。
小o符号：
设f(n)和g(n)都是正整数n的正值函数，如果对任意小的正数€，存在一个正整数N0，使得对任意的正整数n ＞ N0都有f(n) ＜ €g(n)，
就称g(n)是比f(n)高阶的无穷量，记作f(n) = o(g(n))，简记为f = o(g)。
三、最大公因数与广义欧几里得除法
设a1，···，an是n（n≥2）个整数。若整数d是它们中每一个数的因数，则d就叫做a1，···，an的一个公因数。
d是a1，···，an的一个公因数的数学表达式为：d | a1，···，d | an。
如果整数a1，···，an不全为零，那么a1，···，an的所有公因数中最大的一个公因数叫做最大公因数，记作（a1，···，an）。
特别地，当（a1，···，an） = 1 时，称a1，···，an互质或互素。
注①：d ＞ 0是a1，···，an的最大公因数的数学表达式可表述为
d | a1，···，d | an
若 e | a1，···，e | an，则e | d。
注②：a，b的最大公因数 d = （a，b）是集合
{ s · a + t · b | s， t ∈ Z}
注③：a1，···，an的最大公因数 d 是集合
{ s1 · a1 + ··· + sn · an | s1，···，sn ∈ Z}
设a1，···，an是n个不全为零的整数，则
a1，···，an 与 |a1|，···，|an|的公因数相同
（a1，···，an）=（|a1|，···，|an|）。
设b是任一正整数，则（0，b）= b。
设a，b，c是三个不全为零的证书。如果a = q · b + c，其中q是整数，则（a，b）= （b，c）
设a，b是任意两个不全为零的整数，d是正整数，则d是整数a，b的最大公因数的充要条件是：
d | a，b | b；
若 e | a，e | b， 则e | d。
假设1,2成立，那么
说明d是整数a，b的公因数；
说明d是整数a，b的公因数中的最大数，因为e | d 时，有 | e | ≤ d。
因此，d是整数a，b的最大公因数。
四、整除的进一步性质及最小公倍数
设a，b，c是三个整数，且c ≠ 0，如果c | ab，（a，c）= 1，则c | b。
设p是素数。若p | ab，则p | a 或 p | b。
设a1，···，an是n个整数，p是素数。若p | a1，···，an，则p一定整除某一ak，1 ≤ k ≤ n。
五、整数分解
六、素数的算数基本定理
七、素数定理